
انجام عملیات ریاضی با اعداد بزرگ و طولانی: جمع ، ضرب ، توان
خیلی از وقت ها وقتی می خواهیم برنامه ای بنویسیم احتیاج داریم با اعداد خیلی بزرگ و سنگین کار کنیم که از محدوده ی نوع های زبان برنامه نویسیمون خارج است حتی در محدوده double هم قرار نمی گیره .اون موقع است که برناممون دچار مشکل می شه و متغییر هامون سرریز می کنند . در این مطلب می خواهیم با کدنویسی راه حلی برای این مسئله ایجاد کنیم.
فهرست مطالب
مسئله محاسبات با اعداد بسیار بزرگ
برای حل این مشکل معمولا برنامه نویسان کلاس ها و تابع هایی را می نویسند البته بعضی زبان های برنامه نویسی امکانات خوبی در اختیار می گذارند مانند پایتون که می شه باه راحتی با اعداد خیلی بزرگ کار کرد من قبلا در پستی هایی جداگانه “پروژه ماشین حساب با عملیات روی اعداد ۱۰۰۰ رقمی با c” و “الگوریتم تقسیم اعداد بزرگ (fifty digit division)” به این مشکل ها پرداخته بودم ولی اون برنامه ها زیاد سریع نبودن و برای اعداد ۱۰۰۰ رقمی بودن و محدودیت اعداد داشتند.
پیاده سازی برنامه محاسبات اعداد بزرگ
امروز در حال نوشتن برنامه ای بودم که احتیاج پیدا کردم که بتوانم اعداد صحیح بزرگ تر مساوی صفر را با هم جمع ، ضرب کنم و به توان هم برسانم به همین دلیل تابع هایی نوشتم که بتوان این کار را کنم و مثل قبل محدودیت کمتری داشته باشم .البته به مرور زمان هر چه در پروژه خیام و حکیم فردوسی جلو برویم این برنامه ها رو گسترش می دهیم و تقسیم و تفریق آنها را اضافه می کنیم و قابلیت اعداد منفی و اعشاری هم به آن ها می دهیم چون کار زمان بری است پله پله این کار را می کنیم.
ورودی و خروجی این توابع رشته است زیرا کار با آن ها خیلی راحت است و می توان رشته ای خیلی طولانی داشت ولی خود رشته ها هم محدودیت طول دارند دقیق یادم نیست ولی فکر کنم طولشون از ۲ میلیون هم بیشتر بشه ولی برای این مشکل می تونید از روش هایی دیگه استفاده کنید.
تابع tipper
من تابعی به اسم Tipper نوشتم که که عدد را برعکس می کنه ولی عملیات های ریاضی به همون شکل عادی صورت می گیرد برای این این کار را کردم که کار با اعداد راحت تر شود و اگر خواستم رقمی به یک رشته اضافه کنم به تونم به راحتی از تابع push_back استفاده کنم مخصوصا وقتی که هنگام ضرب باید صفر هایی جلوی اعدا د گذاشت.
1 2 3 4 5 6 7 8 9 10 11 12 13 | // void Tipper(string& Num) { int i; char ch; for (i = 0; i < (int(Num.size() / 2)); i++) { ch = Num.at(i); Num.at(i) = Num.at((Num.size() - 1) - i); Num.at((Num.size() - 1) - i) = ch; } } // |
تابع sum
تابع بعدی تابع جمع sum است که برای اعداد صحیح بزرگ تر مساوی صفر است
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | // Sum for heavy number string sum(string Num1, string Num2) { int i; int MaxLen; int sum = 0; int r = 0; char ch; string Num3; Tipper(Num1); Tipper(Num2); if (Num1.size() < Num2.size()) { MaxLen = Num2.size(); } else { MaxLen = Num1.size(); } for (i = 0; i < MaxLen; i++) { sum = 0; if (i < int(Num1.size())) { sum += Num1.at(i) - 48; } if (i < int(Num2.size())) { sum += Num2.at(i) - 48; } ch = ((sum + r) % 10) + 48; Num3.push_back(ch); r = (sum + r) / 10; } if (r != 0) { ch = r + 48; Num3.push_back(ch); } Tipper(Num3); return Num3; } // End of Sum for heavy number |
تابع ضرب یا multiplication
تابع بعدی تابع ضرب multiplication است این تابع دقیقا مثل ضرب کردن اعداد توسط خودمون عمل می کند و در آن از تابع جمع sum استفاده شده است ، ورودی این تابع اعداد دو رشته است و خروجی اش هم به صورت رشته است:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | //Multiplication for heavy number string multiplication(string Num1, string Num2) { int i; int j; int t; int r = 0; int mult = 0; char ch; string Num3; string Sum = "0"; Tipper(Num1); Tipper(Num2); if (Num1.size() > Num1.size()) { Num1.swap(Num2); } for (i = 0; i < int(Num1.size()); i++) { r = 0; for (t = 0; t < i; t++) { Num3.push_back('0'); } for (j = 0; j < int(Num2.size()); j++) { mult = (Num1.at(i) - 48) * (Num2.at(j) - 48); ch = ((mult + r) % 10) + 48; Num3.push_back(ch); r = (mult + r) / 10; } if (r != 0) { ch = r + 48; Num3.push_back(ch); } Tipper(Num3); Sum = sum(Sum, Num3); Num3.clear(); } return Sum; } //end Multiplication for heavy number |
تابع توان یا power
این تابع هم تابع توان power است که در آن از تابع ضرب استفاده شده است ورودی اول که رشته است پایه توان است و عدد بعدی که از نوع int است عددی است که پایه باید به توان آن برسد:
1 2 3 4 5 6 7 8 9 10 11 12 13 | //Power for heavy number string power(string Num1, int Num2) { int i; string result = "1"; for (i = 0; i < Num2; i++) { result = multiplication(result, Num1); } return result; } //end Power for heavy number |
کد نهایی و کامل
اینم کد کلی برنامه که برای مثال در آن ۲ به توان ۱۰۰۰ را حساب می کند :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 | // Heavy Number.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include <iostream> #include <string> using namespace std; // void Tipper(string& Num) { int i; char ch; for (i = 0; i < (int(Num.size() / 2)); i++) { ch = Num.at(i); Num.at(i) = Num.at((Num.size() - 1) - i); Num.at((Num.size() - 1) - i) = ch; } } // // Sum for heavy number string sum(string Num1, string Num2) { int i; int MaxLen; int sum = 0; int r = 0; char ch; string Num3; Tipper(Num1); Tipper(Num2); if (Num1.size() < Num2.size()) { MaxLen = Num2.size(); } else { MaxLen = Num1.size(); } for (i = 0; i < MaxLen; i++) { sum = 0; if (i < int(Num1.size())) { sum += Num1.at(i) - 48; } if (i < int(Num2.size())) { sum += Num2.at(i) - 48; } ch = ((sum + r) % 10) + 48; Num3.push_back(ch); r = (sum + r) / 10; } if (r != 0) { ch = r + 48; Num3.push_back(ch); } Tipper(Num3); return Num3; } // End of Sum for heavy number //Multiplication for heavy number string multiplication(string Num1, string Num2) { int i; int j; int t; int r = 0; int mult = 0; char ch; string Num3; string Sum = "0"; Tipper(Num1); Tipper(Num2); if (Num1.size() > Num1.size()) { Num1.swap(Num2); } for (i = 0; i < int(Num1.size()); i++) { r = 0; for (t = 0; t < i; t++) { Num3.push_back('0'); } for (j = 0; j < int(Num2.size()); j++) { mult = (Num1.at(i) - 48) * (Num2.at(j) - 48); ch = ((mult + r) % 10) + 48; Num3.push_back(ch); r = (mult + r) / 10; } if (r != 0) { ch = r + 48; Num3.push_back(ch); } Tipper(Num3); Sum = sum(Sum, Num3); Num3.clear(); } return Sum; } //end Multiplication for heavy number //Power for heavy number string power(string Num1, int Num2) { int i; string result = "1"; for (i = 0; i < Num2; i++) { result = multiplication(result, Num1); } return result; } //end Power for heavy number int main() { cout << "5 ^ 1000 = " << endl << power("2", 1000) << endl; return 0; } |
اینم حاصل ۲ به توان ۱۰۰۰ :
امیدوارم از حل این سوال لذت برده باشید اگر راهی داشتید یا برنامه ای برای این سوال نوشته اید حتما آن را برای ما ایمیل کنید یا در نظرات بنویسید ، کد شما در همین صفحه قرار خواهد گرفت با تشکر فراوان از این که ما را دنبال می کنید.
با عرض سلام و خسته نباشیدو تشکر بابت سایت عالیتون.
سلام و خسته نباشید. این برنامه با کلاس پیاده سازی شده؟
سلام
خیر. اما خودتون می تونید با کمی تغییر و استفاده از توابع تعریف شده، کلاس مورد نظرتون رو بسازید
سلام وقتتون بخیر اقای دلیرانی میخواستم راجب برج هانوی توضیح بدین و بگین چطور برنامه بنویسم براش بصورت گرافیکی نمایش بدیم بی زحمت در ضمن سایت بسیار خوب و مفیدی دارید ممنونم ازتون
الان خیلی درگیر هستم. متاسفانه وقت نمی کنم. ولی یک پست در بلاگ هست در این مورد:
https://open-mind.ir/1393/%d8%a8%d8%b1%d8%ac-%d9%87%d8%a7%d9%86%d9%88%db%8c/
همین طور توی گیت هاب هم به آدرس زیر:
https://github.com/search?utf8=%E2%9C%93&q=Tower+of+Hanoi&type=
صدها پیاده سازی برج هانوی هست با زبان های مختلف برنامه نویسی و روش های مختلف.
که می تونی یکیشون رو که مد نظرت هست رو بخونی و یاد بگیری و پیاده سازی کنی.
همین طور یادداشت کردم که برج هانوی رو گرافیکی بعد در سایت هر وقت تونستم بنویسم.
با تشکر
سلام ما استادمون یه پروژه داره که باید ساختار داده که اعداد صحیح بزرگ را نایش بده و جمع و تفریق و تقسیم و ضرب روشون انجام بدیم و در نهایت چاپشون کنیم طوری که تو برنامه از تابع درونی استفاده نکنیم و نوع داده هامونم از نوع intباشند فقط چطور این برنامه رو بنویسم میشع راهنمایی کنید .تشکر*
سلام.
با توجه به جزییات پروژه استادتون، باید با استفاده آرایه ای از int ها رقم های اعداد بزرگ رو نگه داری کنید (هر رقم در یک خانه از آرایه قرار می گیرد). در کد ارائه شده در این مطلب، از آرایه کاراکترها (رشته) برای نگه داری هر رقم استفاده شده است (هر رقم به عنوان یک کاراکتر در آرایه ذخیره شده).
موفق باشید
واقعا عالی بود
سایتتون فوق العاده ست. ممنون بابت زحماتتون
با سلام
آیا نمی شود در برنامه از رشته ها استفاده نکرد ؟
یعنی به جای Num1.size از کاربر طول عدد را بپرسیم ؟
یا اگر کاربر به جای رشته ها از آرایه ها استفاده کنیم هزینه برنامه کاهش می یابد یا افزایش ؟؟
هر کاراکتر یک بایت است در نتیجه یک آرایه ی ۵ تایی از کاراکتر ها ۵ بایت می شود
در حالی که int در حالت عادی ۴ بایت است در نتیجه یک آرایه ۵ تا از آن ها می شود ۲۰ بایت
سلام
میتونید یه برنامه برای ضرب دو عدد ۵۰ رقمی بنویسید.
اگر تونستید بنویسید بهم میل بزنید
ممنون
سلام
الگوریتم تقسیم اعداد بزرگ ۵۰ رقمی (fifty digit division)
پروژه ماشین حساب با عملیات روی اعداد ۱۰۰۰ رقمی با زبان c
سایتت خیلی عالیه .مرسی…
فقط یه سوال.
میشه راهنماییم کنی جمع وتفریق ۲ عدد بزرگ که ممکنه منفی باشن چطوریه؟(برنامه نویسی c)
این یک برنامه ساده و کوچک است تا کلیت کار را نشان بدهد ، ولی اگر می خواهید پیشترفته ترش کنید بهتر است ساختمان داده ای جدید در نظر بگیرید و یک خانه با توجه به منفی بودن و یا مثبت بودن در نظر بگیرید و با توجه به علامت ها عملیات مورد نظر خود را پیاده سازی کنید . کلا چهار حالت داریم : هر دو مثبت باشند که در این صورت همان جمع می شود.هر دو منفی باشند که باز مثل حالت قبل هر دو را جمع می کنید بعد علامت را منفی می کنیم یکی مثبت باشد و دیگری منفی که همان منها می شود
سلام.با تشکر از این پست مفیدتون.می خواستم خواهش کنم اگر امکان داره تابع های تقسیم و تفریق وجمع وضرب رو با تحلیل کامل که بتونم با نرم افزار توربو سی اجرا کنم قرار بدید.
ممنون
سلام
من دانشجوی کامپیوتر هستم، استاد درس ساختمان داده همین رو به عنوان پروژه به ما گفته، ضرب دو عدد ۲۰ رقمی با استفاده از لیست های پیوندی. اگه امکانش باشه من رو راهنمایی کنید. استاد گفته اول اعداد رو شش رقم شش رقم بشکنیم و داخل لیست پیوندی قرار بدیم، بعد ضرب کنیم، اگه راهنماییم کنید ممنون میشم.
به پست link list در همین بلاگ بروید و بجای آرایه لینک لیست بفرستید تو تابع
دستت درد نکنه، یه دو هفته رو این سوال کار کردم، بعدش بی خیال شدم، تا این که این پست رو خوندم. ممنون
خوشحال شدیم تونستیم کمک کنیم.
عدد ها باید به صورت رشته ای وارد بشن ؟ واسه جمع و تفریق میگم .
#include “stdafx.h” واسه چیه ؟
مهرنوش @ include “stdafx.h #” یک کتاب خانه است است که کامپایلر ویژوال استدیو به آن نیاز دارد . ولی کامپایلر هایی مثل مثل کد بلاک به آن نیاز ندارند.
بله باید به صورت رشته وارد شوند البته این برنامه فقط جمع دارد برای منها می توانید به این پست مراجعه کنید
http://open-mind.ir/?p=87
misheh begin t , r , ch , mult vaseh chiyan ? r hamoun carry ye ? ch ham yeh temp vaseh negahdashtan meghdare zarb gaei k anjam misheh ? mult ham k akherin meghdare zarb ro negah midareh , dorosteh ? t vaseh chiyeh ?
اگه تفریق و تقسیمش هم بذاری و تبدیل به کلاسش کنی خوب می شود
mohammad @ بله قصد همین کار را داریم ولی به مرور زمان .
سلام.با تشکر از این پست مفیدتون.می خواستم خواهش کنم اگه امکان داره تابع های تقسیم و تفریق رو هم قرار بدید.
ممنون
در این پست ها می توانید منها و جمع و تقسیم را پیدا کنید:
http://open-mind.ir/?p=87
http://open-mind.ir/?p=135
سلام اقای دلیرانی ممنون بابت برنامه ها.میخواستم ببینم شما کلاس تدریس برنامه نویسی هم دارید؟
تشکر ، خیر کلاس برای آموزش برنامه نویسی ندارم ولی در آینده حتما ویدیو های آموزشی درست می کنیم و به صورت رایگان در اختیار خوانندگان می گذاریم.