حل مسائل ریاضی با برنامهنویسی
ریاضیات بیتی
قصد داریم چند مساله را که بیشتر جنبه ریاضی دارند، حل کرده و برنامه آنها را بنویسیم. بیشک یکی از تاثیرگذارترین رشتهها در علوم کامپیوتر، ریاضی است. پس بد نیست کمی دید ریاضی خود را گسترش دهیم تا بتوانیم برنامههایی بنویسیم که مسائل ریاضی را بسادگی و در کمترین زمان ممکن حل کنند.
مساله اول: برنامهای بنویسید که 2 عدد را گرفته و بزرگترین مقسومعلیه مشترک آنها را چاپ کند.
چند روش برای محاسبه بزرگترین مقسومعلیه مشترک یا همان ب.م.م وجود دارد. یکی از روشها این است که بیاییم تمام مقسومعلیههای 2 عدد را محاسبه کنیم و سپس اعداد مشترک را حساب کرده و در یک مجموعه ذخیره کنیم و بزرگترین عضو آن را به عنوان ب.م.م در نظر بگیریم. حال نکته این است که آیا این روش، روشی بهینه است؟ یعنی میتوان راهی راحتتر و بهتر از این ارائه داد؟
پاسخ «آری» است. یکی دیگر از روشهای محاسبه ب.م.م روش نردبانی یا همان روش تقسیمات متوالی است. در روش تقسیمات متوالی عدد بزرگتر را بر عدد کوچکتر تقسیم میکنیم، اگر خارج قسمت برابر صفر شد، عدد کوچکتر ب.م.م است و اگر صفر نشد، مقسوم علیه را به عنوان عدد بزرگتر در نظر میگیریم و باقیمانده را بهعنوان عدد کوچکتر و سپس عدد بزرگتر را بر عدد کوچکتر تقسیم میکنیم، آنقدر این کار را تکرار میکنیم که باقیمانده برابر صفر شود. وقتی باقیمانده برابر صفر شد، عدد بزرگتر که مقسوم علیه مرحله پیشین است را به عنوان ب.م.م در نظر میگیریم.
int num1 = 48, num2 = 16, max , min, temp = 1;
max = num1 » num2 ? num1 : num2;
min = num1 « num2?num1:num2;
while (temp != 0) {
temp = max % min;
max = min;
min = temp;
}
cout «« max;
مساله دوم:
مقدار تابع نمایی یک عدد را محاسبه کنید.منظور از تابع نمایی، تابع e بهتوان x است. برای محاسبه این تابع میتوان از بسط تیلور این تابع که بهصورت زیر است، استفاده کرد:
خب، حال اگر بخواهیم سری را حساب کنیم، نیاز به یک حلقه داریم تا تکتک جملات سری را حساب کرده و با جملات قبلی جمع کنیم. در مواقعی که نیاز به محاسبه یکسری است باید به این نکته توجه داشت که سری همگراست یا واگرا. اگر واگرا بود جوابی برای مساله وجود نخواهد داشت چون هیچ وقت حلقه ما به پایان نمیرسد، ولی اگر همگرا بود، میتوان با گذاشتن یک شرط تمام شدن آن را نشان داد. مثلا تفاضل جمله nام با جمله n-1ام از یک عدد بسیار کوچکی کمتر باشد یا شرایطی از این دست.
بسیار خب، برگردیم به مساله خودمان. میدانیم که این سری همگراست چون درجه رشد !X از x به توان n بیشتر است، پس همیشه به ازای مقادیر بزرگ، حاصلی کوچکتر از یک تولید میشود. مقدار همگرایی سری برابر جواب مساله یعنی همان مقدار تابع e به توان x است. خب حال مساله این است که چگونه سری را حساب کنیم؟
میدانیم که رشد عدد !x بسیار زیاد است مثلا !1000 یک عدد 154 رقمی میشود و میدانیم که متغیری به این اندازه در زبانهای برنامهنویسی وجود ندارد و اگر هم وجود داشته باشد، میزان حافظه اشغالی زیادی نیاز دارد.
راهحل این مساله، استفاده از آرایه است که در شمارههای قبلی در مورد آن توضیح داده شد.
یعنی !1000 را با یک آرایه پیادهسازی کنیم و همینطور !1001 و اعداد دیگر و اعمال ریاضی را روی این اعداد انجام دهیم. این راهحل منطقی نیست و زمانبر است، اما آیا این تنها راهحل است؟ پاسخ «نه» است.
در این مقاله قصد داریم راهحل دیگری ارائه دهیم که هم سرعت بیشتری دارد و هم حافظه مصرفی کمتری. در این راهحل برای محاسبه جمله کنونی از جمله پیشین استفاده میکنیم. این روش چند مزیت دارد چون از جمله قبلی استفاده میشود، به این صورت که اگر در مرحله Nام باشیم و حاصل عبارت X باشد برای محاسبه جمله n+1 نیازی نداریم که X به توان N+1 تقسیم بر !(N+1) را حساب کنیم. کافی است جمله nام را در X/N+1 ضرب کنیم. با این روش دیگر نیازی به محاسبه اعداد بزرگ نیست و جواب را با کمترین میزان حافظه مصرفی و سرعت بیشتری پیدا میکنیم. مانند کد زیر:
const double epmax = 0.00000000000000005;
double number = 2, n = 0, newer = 0, older = 1, sum = 1;
while (older » epmax) {
n++;
newer = older * (number / n);
sum = sum + newer;
older = newer;
}
کد واضح است، میدانیم جملات سری در حال کوچکتر شدن هستند و در هر مرحله بررسی میکنیم که آیا مقدار older که آخرین جمله است از یک عدد بسیار کوچک بزرگتر باشد. اگر کوچکتر باشد از حلقه خارج میشود و مقدار sum همان همگرایی سری و مقدار تابع e به توان x است که همان جواب مساله ماست.
منابع: www.ehow.com و en.wikipedia.org
امیربهاءالدین سبطالشیخ
گفت و گو
