توی این مطلب می خوام یکم راجع به بیگ نام بگم!
خب، حالا شروع می کنم، اول برای نشون دادن کاربرد این مبحث، می خوام از سایت ProjectEuler چند تا سوال بگم که خیلی هم ساده هستن:
سوال 16:
2[SUP]15[/SUP] = 32768 و مجموع ارقامش میشه 3 + 2 + 7 + 6 + 8 = 26. حالا شما بگید مجموع ارقام 2[SUP]1000[/SUP] چنده؟
سوال 20:
n! = n * ... * 3 * 2 * 1 مثلا !10 = 10 * 9 * ... * 1 = 3628800 که مجموع ارقامش میشه 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27، حالا شما بگید مجموع ارقام !100 چنده؟
خب این دو سوال تقریبا شبیه به همند، اول نحوه کار تقریبی با bignum رو یاد می گیریم و بعد چیزایی رو که بلدیم، پیاده سازی می کنیم.
برای نگهداری اعداد کافیه فرض کنیم اعداد همون رشته ها هستند، فقط باید تمام اعمال + و * و ! و ^ (توان رساندن) و شبیه به این ها رو برای این رشته ها تعریف کنیم، اینطوری دیگه برای نگهداری اعداد محدودیتی نداریم، چون اعداد مثل متن نگه داری میشن! اول باید ببینیم SUM چجوری تعریف میشه؟ ( + بین دو رشته )
مثلا جمع دو تا رشته مثل 2198683 و 193247 چجوریه؟ کافیه زیر هم بنویسیمشون: (و در واقع به جای هر جای خالی یه 0 می گذاریم)
0110110
2198683
0193247
_______+
2391930
اون 0 و 1 هایی که اون بالاست نشان دهنده ی همون ده بر یک ها هستند، مثلا 9 + 9 میشه 18، 8 میمونه، یه 10 بر یک میره عدد بعد و همراه با اونا جمع میشه، پس ما الگوریتم کلی جمع دو تا رشته رو فهمیدیم.
حالا کدش به ++C، اما قبل از اون برای راحتی کار چند تا define# انجام میدیم.
[TABLE="class: pastetable cke_show_border"]
[TR]
[TD="class: linenos"][/TD]
[TD="class: code"]
#define LEN(x) x.length() #define FOR(i, a, b) for(long long i = a; i < b; i++) #define ROF(i, a, b) for(long long i = a; i >= b; i--) #define INT(x) ((x) - '0')[/TD]
[/TR]
[/TABLE]
خب حالا جمع رو تعریف می کنیم:
[TABLE="class: pastetable cke_show_border"]
[TR]
[TD="class: linenos"][/TD]
[TD="class: code"]
string sum(string a, string b) //Sum 2 strings! { string ans; char ch; if(LEN(a) < LEN(b)) swap(a, b); ROF(i, LEN(a) - LEN(b), 1) { b = '0' + b; } FOR(i, 0, LEN(a)) { ans = ans + '0'; } ROF(i, LEN(a) - 1, 0) { ans += INT(a) + INT(b); if(i) { ans[i - 1] += INT(ans) / 10; ans = INT(ans) % 10 + '0'; } } if(INT(ans[0]) > 9) { ch = INT(ans[0]) / 10 + '0'; ans[0] = INT(ans[0]) % 10 + '0'; ans = ch + ans; return ans; } else { return ans; } }[/TD]
[/TR]
[/TABLE]
تابعی که تعریف کردیم، تقریبا گویای مطالب هست! حالا ضرب رو باز 2 جور می تونیم تعریف کنیم یکی اینکه A * B = A + A + A + ... + A ( تعداد A ها B تاست)
خب اینکارو انجام میدیم!
[TABLE="class: pastetable cke_show_border"]
[TR]
[TD="class: linenos"][/TD]
[TD="class: code"]
string muls(string a, string b) //Basic mult function! based on sum. { if(a == "0" || b == "0") return "0"; string temp = b; string i = "1"; while(i != a) { b = sum(b, temp); i = sum(i, "1"); } return b; } string epow(string a, long long b) { FOR(i, 0, b) { a += '0'; } return a; }[/TD]
[/TR]
[/TABLE]
البته ما یه تابع دیگه هم تعریف کردیم به نام epow که b تا صفر جلوی a می گذاره، یعنی a رو به a * 10**b تبدیل میکنه ( ** عمل توانه )
این تابع به درده چی می خوره؟ به درد راه دیگری برای ضرب که همون الگوریتم ضرب دو عدده که زیر هم می نویسیم، دیگه توضیح بیشتری نمیدم!
[TABLE="class: pastetable cke_show_border"]
[TR]
[TD="class: linenos"][/TD]
[TD="class: code"]
string mul(string a, string b) //This mul function is so faster than muls! { if(a == "0" || b == "0") return "0"; if(LEN(a) < LEN(b)) swap(a, b); string ans = "0", temp, t; ROF(i, LEN(b) - 1, 0) { temp += b; temp = muls(temp, a); temp = epow(temp, LEN(b) - 1 - i); ans = sum(ans, temp); temp = ""; t = ""; } return ans; }[/TD]
[/TR]
[/TABLE]
نمی خواهیم وارد بخث Order شویم ولی بصورت واضح قبول داشته باشید (!) که mul از تابع قبلی یعنی muls سریع تر است.
حالا پیشنیاز های ما فراهمه، میتونیم توابع توان و فاکتوریل رو بنویسیم. حالا برای توان باز دو راه داریم، یکی اینکه A^B = A**B = A A A A ... A (^ و ** نماد های توان هستند)
یک دفعه میریم سراغه توان سریع تر، با اینکه نمیخواستم وارد مرتبه بشم، ولی چون تقریبا خیلی راحت و قابل فهمه بگم که روش اول به توان رسوندن B تا عمل انجام میده، حالا روش دوم چیه؟ مثلا A**16 = (((A**2)**2)**2)**2، این چند تا عمل انجام داده؟ اول A = A * A بعد A = A * A بعد A = A * A و باز هم A = A * A پس در واقع مثل این میمونه که A به توان 16 رسیده باشه! ولی 4 تا عمل انجام شده، یعنی برای A**B، لگاریتم بر مبنای 2ـی B یا lg B عمل انجام میشه، اما ما این الگوریتم رو (همیشه) بکار نمیبریم! اگه گفتید چرا؟ چون ما نمیتونیم A / 2 رو پیدا کنیم! در واقع برای اینکه بخوایم A / 2 رو حساب کنیم، باید یه تابع برای تقسیم هم بنویسیم! که حسش نیست! پس به جای اینکه توان رو هم string بگیریم، از int یا long long استفاده می کنیم، و قطعا توان از 64**2 کمتره! و اگه بیشتر باشه، یه توماری عدد میشه ( اگه پایه از 1 بیشتر باشه!) پس تابع pow رو به شکل زیر می نویسیم:
[TABLE="class: pastetable cke_show_border"]
[TR]
[TD="class: linenos"][/TD]
[TD="class: code"]
string pow(string a, long long b) { if(!b) return "1"; if(b == 1) return a; return mul(pow(a, b / 2), pow(a, (b + 1) / 2)); }[/TD]
[/TR]
[/TABLE]
در واقع b + 1 تقسیم بر 2 همون سقفه b / 2 ـه! حالا با function هایی که داریم بریم سراغ حل سوال 16 !
[TABLE="class: pastetable cke_show_border"]
[TR]
[TD="class: linenos"][/TD]
[TD="class: code"]
int main(){ int ans = 0; string a = pow("2", 1000); for(int i = 0; i < a.length(); i++) ans += INT(a); cout << ans; return 0;}[/TD]
[/TR]
[/TABLE]
خب اینم از mainـمون! بریم ببینیم کل برنامه چی شد! برنامه رو از اینجا ببینید که چی شد: Ubuntu Pastebin
سوال 20 رو هم که دیگه راحت شد! کافیه یه تابع فاکتوریل تعریف کنید و همین کارایی که توی سوال 16 کردیم! امیدوارم مفید بوده باشه، نظر یا سوالی داشتید بیان کنید!
چون کد ها رو من درست نوشتم! ولی اینجا داغووون نشون میده! پس خودتون برید همون آخر ببینید که چی شد!
خب، حالا شروع می کنم، اول برای نشون دادن کاربرد این مبحث، می خوام از سایت ProjectEuler چند تا سوال بگم که خیلی هم ساده هستن:
سوال 16:
2[SUP]15[/SUP] = 32768 و مجموع ارقامش میشه 3 + 2 + 7 + 6 + 8 = 26. حالا شما بگید مجموع ارقام 2[SUP]1000[/SUP] چنده؟
سوال 20:
n! = n * ... * 3 * 2 * 1 مثلا !10 = 10 * 9 * ... * 1 = 3628800 که مجموع ارقامش میشه 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27، حالا شما بگید مجموع ارقام !100 چنده؟
خب این دو سوال تقریبا شبیه به همند، اول نحوه کار تقریبی با bignum رو یاد می گیریم و بعد چیزایی رو که بلدیم، پیاده سازی می کنیم.
برای نگهداری اعداد کافیه فرض کنیم اعداد همون رشته ها هستند، فقط باید تمام اعمال + و * و ! و ^ (توان رساندن) و شبیه به این ها رو برای این رشته ها تعریف کنیم، اینطوری دیگه برای نگهداری اعداد محدودیتی نداریم، چون اعداد مثل متن نگه داری میشن! اول باید ببینیم SUM چجوری تعریف میشه؟ ( + بین دو رشته )
مثلا جمع دو تا رشته مثل 2198683 و 193247 چجوریه؟ کافیه زیر هم بنویسیمشون: (و در واقع به جای هر جای خالی یه 0 می گذاریم)
0110110
2198683
0193247
_______+
2391930
اون 0 و 1 هایی که اون بالاست نشان دهنده ی همون ده بر یک ها هستند، مثلا 9 + 9 میشه 18، 8 میمونه، یه 10 بر یک میره عدد بعد و همراه با اونا جمع میشه، پس ما الگوریتم کلی جمع دو تا رشته رو فهمیدیم.
حالا کدش به ++C، اما قبل از اون برای راحتی کار چند تا define# انجام میدیم.
[TABLE="class: pastetable cke_show_border"]
[TR]
[TD="class: linenos"][/TD]
[TD="class: code"]
#define LEN(x) x.length() #define FOR(i, a, b) for(long long i = a; i < b; i++) #define ROF(i, a, b) for(long long i = a; i >= b; i--) #define INT(x) ((x) - '0')[/TD]
[/TR]
[/TABLE]
خب حالا جمع رو تعریف می کنیم:
[TABLE="class: pastetable cke_show_border"]
[TR]
[TD="class: linenos"][/TD]
[TD="class: code"]
string sum(string a, string b) //Sum 2 strings! { string ans; char ch; if(LEN(a) < LEN(b)) swap(a, b); ROF(i, LEN(a) - LEN(b), 1) { b = '0' + b; } FOR(i, 0, LEN(a)) { ans = ans + '0'; } ROF(i, LEN(a) - 1, 0) { ans += INT(a) + INT(b); if(i) { ans[i - 1] += INT(ans) / 10; ans = INT(ans) % 10 + '0'; } } if(INT(ans[0]) > 9) { ch = INT(ans[0]) / 10 + '0'; ans[0] = INT(ans[0]) % 10 + '0'; ans = ch + ans; return ans; } else { return ans; } }[/TD]
[/TR]
[/TABLE]
تابعی که تعریف کردیم، تقریبا گویای مطالب هست! حالا ضرب رو باز 2 جور می تونیم تعریف کنیم یکی اینکه A * B = A + A + A + ... + A ( تعداد A ها B تاست)
خب اینکارو انجام میدیم!
[TABLE="class: pastetable cke_show_border"]
[TR]
[TD="class: linenos"][/TD]
[TD="class: code"]
string muls(string a, string b) //Basic mult function! based on sum. { if(a == "0" || b == "0") return "0"; string temp = b; string i = "1"; while(i != a) { b = sum(b, temp); i = sum(i, "1"); } return b; } string epow(string a, long long b) { FOR(i, 0, b) { a += '0'; } return a; }[/TD]
[/TR]
[/TABLE]
البته ما یه تابع دیگه هم تعریف کردیم به نام epow که b تا صفر جلوی a می گذاره، یعنی a رو به a * 10**b تبدیل میکنه ( ** عمل توانه )
این تابع به درده چی می خوره؟ به درد راه دیگری برای ضرب که همون الگوریتم ضرب دو عدده که زیر هم می نویسیم، دیگه توضیح بیشتری نمیدم!
[TABLE="class: pastetable cke_show_border"]
[TR]
[TD="class: linenos"][/TD]
[TD="class: code"]
string mul(string a, string b) //This mul function is so faster than muls! { if(a == "0" || b == "0") return "0"; if(LEN(a) < LEN(b)) swap(a, b); string ans = "0", temp, t; ROF(i, LEN(b) - 1, 0) { temp += b; temp = muls(temp, a); temp = epow(temp, LEN(b) - 1 - i); ans = sum(ans, temp); temp = ""; t = ""; } return ans; }[/TD]
[/TR]
[/TABLE]
نمی خواهیم وارد بخث Order شویم ولی بصورت واضح قبول داشته باشید (!) که mul از تابع قبلی یعنی muls سریع تر است.
حالا پیشنیاز های ما فراهمه، میتونیم توابع توان و فاکتوریل رو بنویسیم. حالا برای توان باز دو راه داریم، یکی اینکه A^B = A**B = A A A A ... A (^ و ** نماد های توان هستند)
یک دفعه میریم سراغه توان سریع تر، با اینکه نمیخواستم وارد مرتبه بشم، ولی چون تقریبا خیلی راحت و قابل فهمه بگم که روش اول به توان رسوندن B تا عمل انجام میده، حالا روش دوم چیه؟ مثلا A**16 = (((A**2)**2)**2)**2، این چند تا عمل انجام داده؟ اول A = A * A بعد A = A * A بعد A = A * A و باز هم A = A * A پس در واقع مثل این میمونه که A به توان 16 رسیده باشه! ولی 4 تا عمل انجام شده، یعنی برای A**B، لگاریتم بر مبنای 2ـی B یا lg B عمل انجام میشه، اما ما این الگوریتم رو (همیشه) بکار نمیبریم! اگه گفتید چرا؟ چون ما نمیتونیم A / 2 رو پیدا کنیم! در واقع برای اینکه بخوایم A / 2 رو حساب کنیم، باید یه تابع برای تقسیم هم بنویسیم! که حسش نیست! پس به جای اینکه توان رو هم string بگیریم، از int یا long long استفاده می کنیم، و قطعا توان از 64**2 کمتره! و اگه بیشتر باشه، یه توماری عدد میشه ( اگه پایه از 1 بیشتر باشه!) پس تابع pow رو به شکل زیر می نویسیم:
[TABLE="class: pastetable cke_show_border"]
[TR]
[TD="class: linenos"][/TD]
[TD="class: code"]
string pow(string a, long long b) { if(!b) return "1"; if(b == 1) return a; return mul(pow(a, b / 2), pow(a, (b + 1) / 2)); }[/TD]
[/TR]
[/TABLE]
در واقع b + 1 تقسیم بر 2 همون سقفه b / 2 ـه! حالا با function هایی که داریم بریم سراغ حل سوال 16 !
[TABLE="class: pastetable cke_show_border"]
[TR]
[TD="class: linenos"][/TD]
[TD="class: code"]
int main(){ int ans = 0; string a = pow("2", 1000); for(int i = 0; i < a.length(); i++) ans += INT(a); cout << ans; return 0;}[/TD]
[/TR]
[/TABLE]
خب اینم از mainـمون! بریم ببینیم کل برنامه چی شد! برنامه رو از اینجا ببینید که چی شد: Ubuntu Pastebin
سوال 20 رو هم که دیگه راحت شد! کافیه یه تابع فاکتوریل تعریف کنید و همین کارایی که توی سوال 16 کردیم! امیدوارم مفید بوده باشه، نظر یا سوالی داشتید بیان کنید!
چون کد ها رو من درست نوشتم! ولی اینجا داغووون نشون میده! پس خودتون برید همون آخر ببینید که چی شد!
PHP
//Includes { #include <iostream> #include <cstring> #include <string>//}using namespace std;//Defines { #define LEN(x) x.length() #define FOR(i, a, b) for(long long i = a; i < b; i++) #define ROF(i, a, b) for(long long i = a; i >= b; i--) #define INT(x) ((x) - '0')//}//Functions { string sum(string a, string b) //Sum 2 strings! { string ans; char ch; if(LEN(a) < LEN(b)) swap(a, b); ROF(i, LEN(a) - LEN(b), 1) { b = '0' + b; } FOR(i, 0, LEN(a)) { ans = ans + '0'; } ROF(i, LEN(a) - 1, 0) { ans[i] += INT(a[i]) + INT(b[i]); if(i) { ans[i - 1] += INT(ans[i]) / 10; ans[i] = INT(ans[i]) % 10 + '0'; } } if(INT(ans[0]) > 9) { ch = INT(ans[0]) / 10 + '0'; ans[0] = INT(ans[0]) % 10 + '0'; ans = ch + ans; return ans; } else { return ans; } } string muls(string a, string b) //Basic mult function! based on sum. { if(a == "0" || b == "0") return "0"; string temp = b; string i = "1"; while(i != a) { b = sum(b, temp); i = sum(i, "1"); } return b; } string epow(string a, long long b) { FOR(i, 0, b) { a += '0'; } return a; } string mul(string a, string b) //This mul function is so faster than muls! { if(a == "0" || b == "0") return "0"; if(LEN(a) < LEN(b)) swap(a, b); string ans = "0", temp, t; ROF(i, LEN(b) - 1, 0) { temp += b[i]; temp = muls(temp, a); temp = epow(temp, LEN(b) - 1 - i); ans = sum(ans, temp); temp = ""; t = ""; } return ans; } string pow(string a, long long b) { if(!b) return "1"; if(b == 1) return a; return mul(pow(a, b / 2), pow(a, (b + 1) / 2)); }//}int main(){ int ans = 0; string a = pow("2", 1000); for(int i = 0; i < a.length(); i++) { ans += INT(a[i]); } cout << ans; return 0; }
آخرین ویرایش توسط مدیر
