سری اعداد فیبوناچی

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 تابع جذر).

یکی دیگر از مسائلی که در مورد اعداد فیبوناچی مطرح می‌شود این است که عکس مراحل بالا را انجام دهیم، یعنی یک عدد به ما بدهند و تشخیص بدهیم که آیا این عدد جزئی از سری فیبوناچی است یا نه؟ یا به اصطلاح این عدد فیبوناچی است یا خیر؟

حل این مساله بر عهده خواننده گذاشته شده است.

امیربهاالدین سبط‌الشیخ