طراحی وب سایت

قصد داریم چند مساله را که بیشتر جنبه ریاضی دارند، حل کرده و برنامه آنها را بنویسیم. بی شک یکی از تاثیرگذار ترین رشته ها در علوم کامپیوتر، ریاضی است. پس بد نیست کمی دید ریاضی خود را گسترش دهیم تا بتوانیم برنامه هایی بنویسیم که مسائل ریاضی را بسادگی و در کمترین زمان ممکن حل کنند.
مساله اول: برنامه ای بنویسید که 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
امیربهاءالدین سبط الشیخ

منبع : جام جم آنلاین  تاریخ : 23   آبان   1389  شاخه : برنامه نویسی