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 تابع جذر).
يکي ديگر از مسائلي که در مورد اعداد فيبوناچي مطرح مي‌شود اين است که عکس مراحل بالا را انجام دهيم، يعني يک عدد به ما بدهند و تشخيص بدهيم که آيا اين عدد جزئي از سري فيبوناچي است يا نه؟ يا به اصطلاح اين عدد فيبوناچي است يا خير؟
حل اين مساله بر عهده خواننده گذاشته شده است.
اميربهاالدين سبط‌الشيخ
