دنباله فیبوناچی یا سری فیبوناچی چیه؟

اگر بخواهیم این دنباله را به زبان ریاضی نمایش دهیم از رابطه‌های زیر کمک خواهیم گرفت:

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++‎برنامه نویسی سی پلاس پلاس چیست؟ مزایای برنامه نویسی C++‎؟برنامه نویسی سی پلاس پلاس چیست و چه کاربردی دارد؟ این صفحه عالی به بررسی مزایای برنامه نویسی C++ پرداخته و نمونه هایی از کدهای زبان برنامه نویسی ++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;  
}

#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;  
 }

#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امین عدد فیبوناچی در پایتونزبان برنامه نویسی پایتون چیست؟ – نحوه شروع و دلایل محبوبیتزبان برنامه نویسی پایتون (Python) چیست؟ این مقاله عالی به بررسی دلایل محبوبیت پایتون، موارد استفاده از پایتون و نحوه شروع به برنامه نویسی پایتون پرداخته:

# 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))

# 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امین عدد فیبوناچی در جاواجاوا چیست؟ تعریف، معنی و ویژگی های جاوا (java) از 0تا100جاوا یک زبان برنامه نویسی همه منظوره، مبتنی بر کلاس و شی گرا است که برای داشتن وابستگی های پیاده سازی کمتر طراحی شده است، زبان برنامه نویسی جاوا شبیه ++C است:

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;
    }
  }
}

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));
    }
}

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;
}

#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;
}

جمع‌بندی

روش‌های مختلفی برای پیاده سازی دنباله فیبوناچی وجود دارد. اما همانطور که می‌دانید در پیاده سازی یک الگوریتم همواره بهتر است از روش بهینه آن استفاده شود. استفاده از روش بازگشت و فرمول ریاضی فیبوناچی بالاترین پیچیدگی زمانی را دارد پس برای بهینه کردن این پیچیدگی از دو روش پویا و توان ماتریس می‌توان استفاده کرد.

چگونه روش پویا باعث بهینه‌تر شدن الگوریتم فیبوناچی می‌شود؟

اگر شما طبق فرمول فیبوناچی درخت متناسب آن را ترسیم کنید. متوجه خواهید شد برخی از توابع تکرار می‌شوند در روش پویا این توابع پس از یکبار محاسبه ذخیره می‌شوند تا از تکرار آن جلوگیری شود.