طراحی وب سایت

چنان که در ویکی پدیا آمده، فیبوناچی نام ریاضیدان ایتالیایی است که در مسابقات سال 1225 برای حل مساله مطرح شده راه حلی ارائه داد که جواب آن سری فیبوناچی شد و به احترام او این سری اعداد را سری فیبوناچی نامگذاری کردند. این سری به دنباله ای از اعداد گفته می شود که به ازای هر x عضو اعداد صحیح مثبت بزرگ تر از ? داشته باشیم:
f(x)=f(x-1)+f(x-2)
و به ازای x=0,1 داریم: f(x)=x.
جمله عمومی سری فیبوناچی به صورت زیر است:
حال ما قصد داریم همین اعداد را با برنامه نویسی محاسبه کنیم. اولین سوال ما به دست آوردن یک عنصر مشخص از اعداد فیبوناچی است، مثلا عنصر xام از این سری از اعداد را به دست بیاورید.
برای این کار باید در یک حلقه اعداد را با دو عدد قبلی جمع کنیم، مثلا اگر عنصر 10 ام سری فیبوناچی را از ما خواستند در یک حلقه از 1 تا 10 اعداد را با دو عدد پیشین جمع می کنیم.
فقط دقت داشته باشید که دو عدد اول 0 و 1 هستند. فرض می کنیم عدد اول a و عدد دوم b باشد و fib عدد مورد نظر ما باشد. در هر بار اجرا شدن حلقه فوق داریم:
fib = a + b;
a = b;
b = fib;
این طوری می دانیم که در هر مرحله عدد فیبوناچی مورد نظر ما چیست. پس کد را به صورت زیر می نویسیم:
long fibonacci(int no) {
long a = 0, b = 1;
long fib = 0;
if (no « 2) {
return no;
}
for (int i = 1; i « no; i++) {
fib = a + b;
a = b;
b = fib;
}
return fib;
}
بسیار خب این روش ترتیبی برای به دست آوردن اعداد فیبوناچی است، می توانیم به صورت بازگشتی نیز اعداد فیبوناچی را محاسبه کنیم.
در روش بازگشتی در هر مرحله تابع به دو بخش تقسیم می شود و برای هر دو بخش دوباره تابع فراخوانی می شود. در مرحله اول تابع به ازای (fibonacci (no–1 و (fibonacci (no–2 دوبار اجرا می شود و همین طور در مرحله بعدی این دو تابع از حل 4 تابع دیگر به دست می آید و همین طور اگر حساب کنیم می بینیم که در محاسبه عدد nام سری فیبوناچی باید 2 به توان n + 1 بار تابع اجرا شود. از آنجا که در توابع بازگشتی از stack پشته استفاده می شود و فضای پشته محدود است با زیاد شدن no دچار خطایstack overflow خواهیم شد!
پس در محاسبه اعداد بزرگ بهتر است از روش بازگشتی استفاده نکنیم.
کد روش بازگشتی به صورت زیر است:
long fibonaccirecursive(int no) {
if ((no == 1) || (no == 2))
return 1;
else if (no == 0)
return 0;
else
return fibonaccirecursive(no - 1) + fibonaccirecursive(no - 2);
}
در هر دو روش ممکن است عدد فیبوناچی حاصل بقدری بزرگ باشد که در متغیر های معمول زبان های برنامه نویسی جای نگیرد، آن وقت تکلیف چیست؟
برای حل این مشکل باید عدد حاصل را یک آرایه تعریف کرده و فرض کنید هر رقم از آرایه یک رقم از عدد است. برای اطلاعات بیشتر در مورد پیاده سازی جمع برای اعداد بزرگ به مقاله های قبلی که پیرامون این موضوع هستند مراجعه کنید.
آیا راه حل دیگری برای به دست آوردن عدد فیبوناچی وجود دارد؟ بله! با استفاده از عدد طلایی phi.
برای محاسبه عدد فیبوناچی با استفاده از عدد طلایی کافیست جای n در فرمول زیر شماره عدد فیبوناچی مورد نظر را قرار دهید.
fn = math.pow(phi, n) / math.sqrt( 5)
عدد فی برابر است با: (25/1+ 1) / 2 = 1.6180339
double phi = (math.sqrt(5) + 1) / 2;
double fibonachi = math.pow(phi, 40) / math.sqrt(5);
بسیار خب ما توانستیم برای محاسبه عدد فیبوناچی از سه روش استفاده کنیم، هر کدام از روش های ذکر شده ویژ گی های خود را دارند.
مزیت روش آخر نسبت به روش های دیگر این است که دیگر حلقه ای اجرا نمی شود و بیشتر از توابع کتابخانه ای هر زبان استفاده شده است (توابع math.pow تابع توان و math.sqrt تابع جذر).
یکی دیگر از مسائلی که در مورد اعداد فیبوناچی مطرح می شود این است که عکس مراحل بالا را انجام دهیم، یعنی یک عدد به ما بدهند و تشخیص بدهیم که آیا این عدد جزئی از سری فیبوناچی است یا نه؟ یا به اصطلاح این عدد فیبوناچی است یا خیر؟ حل این مساله بر عهده خواننده گذاشته شده است.
امیربهاالدین سبط الشیخ

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