اگر بخواهیم این دنباله را به زبان ریاضی نمایش دهیم از رابطه‌های زیر کمک خواهیم گرفت:
F0 = 0
F1 = 1
Fi = Fi-1 + Fi-2
به این ترتیب اگر مقدار i را از صفر آغاز کنیم دنباله یا سری فیبوناچی تولید خواهد شد.
اعداد فیبوناچی اعدادی هستند که در توالی اعداد صحیح زیر قرار داشته باشند:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …
برنامه بازگشتی محاسبه nامین عدد فیبوناچی در ++C
اولین و ساده‌ترین راه برای محاسبه دنباله فیبوناچی استفاده از فرمول ریاضی‌ای است که بالاتر به آن اشاره کردیم. اکنون کد پیاده سازی الگوریتم فیبوناچی را در زبان های برنامه نویسی مختلف برای شما به اشتراک می‌گذاریم:
سورس کد برنامه بازگشتی محاسبه nامین عدد فیبوناچی در زبان C++:
#include <iostream>
using namespace std;
void printFibonacci(int n){
static int n1=0, n2=1, n3;
if(n>0){
n3 = n1 + n2;
n1 = n2;
n2 = n3;
coutn3" ";
printFibonacci(n-1);
}
}
int main(){
int n;
cout>n;
cout"Fibonacci Series: ";
cout"0 ""1 ";
printFibonacci(n-2); //n-2 because 2 numbers are already printed
return 0;
}
در کد فوق عدد ورودی را از کاربر می‌گیریم سپس این عدد را به تابع فیبوناچی (fibo) برمی‌گردانیم و طبق فرمول ریاضی فیبوناچی به صورت بازگشتی نتیجه را محاسبه می‌کنیم.
برنامه بازگشتی محاسبه nامین عدد فیبوناچی در C
#include<stdio.h>
void printFibonacci(int n){
static int n1=0,n2=1,n3;
if(n>0){
n3 = n1 + n2;
n1 = n2;
n2 = n3;
printf("%d ",n3);
printFibonacci(n-1);
}
}
int main(){
int n;
printf("Enter the number of elements: ");
scanf("%d",&n);
printf("Fibonacci Series: ");
printf("%d %d ",0,1);
printFibonacci(n-2);//n-2 because 2 numbers are already printed
return 0;
}
در کد برنامه نویسی الگوریتم فیبوناچی فوق عدد ورودی را برابر 28 در نظرگرفته‌ایم تا نتیجه را باهم بررسی کنیم.
خروجی الگوریتم فوق به صورت بازگشتی به شکل زیر است:
Enter the number of elements: 28 Fibonacci Series: 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418
برنامه بازگشتی محاسبه nامین عدد فیبوناچی در پایتون
سورس کد برنامه بازگشتی محاسبه nامین عدد فیبوناچی در پایتون:
# Function for nth Fibonacci number
def Fibonacci(n):
# Check if input is 0 then it will
# print incorrect input
if n < 0:
print("Incorrect input")
# Check if n is 0
# then it will return 0
elif n == 0:
return 0
# Check if n is 1,2
# it will return 1
elif n == 1 or n == 2:
return 1
else:
return Fibonacci(n-1) + Fibonacci(n-2)
# Driver Program
print(Fibonacci(28))
برنامه بازگشتی محاسبه nامین عدد فیبوناچی در java
سورس کد برنامه بازگشتی محاسبه nامین عدد فیبوناچی در جاوا:
class Main {
public static void main(String[] args) {
int n = 10, firstTerm = 0, secondTerm = 1;
System.out.println("Fibonacci Series till " + n + " terms:");
for (int i = 1; i = n; ++i) {
System.out.print(firstTerm + ", ");
// compute the next term
int nextTerm = firstTerm + secondTerm;
firstTerm = secondTerm;
secondTerm = nextTerm;
}
}
}
بررسی پیچیدگی زمانی فیبوناچی در روش بازگشتی:
طبق فرمول ریاضی پیچیدگی به صورت بازگشتی به شکل زیر است:
T(n-2)+ T(n-1)=T(n)
که اگر از کران یابی استفاده کنیم پیچیدگی زمانی فیبوناچی برابر O(2^n) و به صورت نمایی است. پس پیاده سازی فیبوناچی به صورت بازگشتی نامناسب است.
الگوریتم فیبوناچی به روش پویا
در روش بالا اگر از درخت استفاده کنیم متوجه می‌شویم که خیلی از اعداد تکرار می‌شوند. در روش بازگشتی همراه با برنامه نویسی پویا از ذخیره اعداد استفاده می‌کنیم. به این صورت که اعداد فیبوناچی که تا الان محاسبه شده‌اند را ذخیره می‌کنیم تا از محاسبه تکراری آنها جلوگیری شود.
برنامه محاسبه nامین عدد فیبوناچی در #C
using System;
class fibonacci {
static int fib(int n)
{
int []f = new int[n + 2];
int i;
f[0] = 0;
f[1] = 1;
for (i = 2; i = n; i++)
{
f[i] = f[i - 1] + f[i - 2];
}
return f[n];
}
public static void Main ()
{
int n = 28;
Console.WriteLine(fib(n));
}
}
پیچیدگی زمانی الگوریتم فیبوناچی به روش پویا برابر O(n) می‌شود که بسیار بهینه‌تر از روش بازگشتی است.
الگوریتم فیبوناچی به روش توان ماتریس
در این روش، از به توان رساندن ماتریس { ,{1,1}{1,0} } برای محاسبه nامین عدد فیبوناچی استفاده شده است. در این روش، ماتریس فوق n بار در خودش ضرب می‌شود و n+1 امین عدد فیبوناچی به عنوان عنصری در سطر و ستون (0,0) در ماتریس نتیجه بدست می‌آید.
استفاده از روش ماتریس در الگوریتم فیبوناچی، عبارت زیر را به ما می‌دهد:
[Fn+1 Fn Fn Fn-1]^n = [1 1 1 0]
برنامه محاسبه nامین عدد فیبوناچی در c به روش توان ماتریس
#include <stdio.h>
void multiply(int F[2][2], int p[2][2]);
void power(int F[2][2], int n);
int fibo(int n)
{
int F[2][2] = {{1,1},{1,0}};
if (n == 0)
return 0;
power(F, n-1);
return F[0][0];
}
void multiply(int F[2][2], int p[2][2])
{
int x = F[0][0]*p[0][0] + F[0][1]*p[1][0];
int y = F[0][0]*p[0][1] + F[0][1]*p[1][1];
int z = F[1][0]*p[0][0] + F[1][1]*p[1][0];
int w = F[1][0]*p[0][1] + F[1][1]*p[1][1];
F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}
void power(int F[2][2], int n)
{
int i;
int p[2][2] = {{1,1},{1,0}};
for (i = 2; i <= n; i++)
multiply(F, p);
}
int main()
{
int n = 28;
printf("%d", fibo(n));
getchar();
return 0;
}
جمع‌بندی
روش‌های مختلفی برای پیاده سازی دنباله فیبوناچی وجود دارد. اما همانطور که می‌دانید در پیاده سازی یک الگوریتم همواره بهتر است از روش بهینه آن استفاده شود. استفاده از روش بازگشت و فرمول ریاضی فیبوناچی بالاترین پیچیدگی زمانی را دارد پس برای بهینه کردن این پیچیدگی از دو روش پویا و توان ماتریس می‌توان استفاده کرد.
چگونه روش پویا باعث بهینه‌تر شدن الگوریتم فیبوناچی می‌شود؟
اگر شما طبق فرمول فیبوناچی درخت متناسب آن را ترسیم کنید. متوجه خواهید شد برخی از توابع تکرار می‌شوند در روش پویا این توابع پس از یکبار محاسبه ذخیره می‌شوند تا از تکرار آن جلوگیری شود.
آیا روش بهینه‌تری نیز وجود دارد؟
بله،این روش در واقع بهینه شده روش توان ماتریس است.به این صورت که می‌توان از ضرب POWER (M,N) بازگشتی برای محاسبه استفاده کرد.
آیا فرمول بهینه‌تری برای دنباله فیبوناچی وجود دارد؟
بله
برای n های زوج: f(k)* ( f(k)+2*f(k-1) )=f(n)
برای n های فرد: f(k-1) * f(k-1)+ f(k)* f(k)=f(n)
