数据结构与算法斐波那契数列

斐波那契数列通过添加两个先前的数字来生成后续的数字。斐波那契数列从两个数字开始 - F ₀和 F ₁。_{F 0}和F ₁的初始值可以分别取0、1或1、1。

斐波那契数列满足以下条件 -

F_n = F_n-1 + F_n-2

因此，斐波那契数列可以如下所示 -

F ₈ = 0 1 1 2 3 5 8 13

或者，这个 -

F ₈ = 1 1 2 3 5 8 13 21

出于说明目的，F ₈的斐波那契显示为 -

斐波那契迭代算法

首先，我们尝试起草斐波那契数列的迭代算法。

Procedure Fibonacci(n)
   declare f₀, f₁, fib, loop 
   
   set f₀ to 0
   set f₁ to 1
   
   <b>display f₀, f₁</b>
   
   for loop ← 1 to n
   
      fib ← f₀ + f₁   
      f₀ ← f₁
      f₁ ← fib

      <b>display fib</b>
   end for
	
end procedure

斐波那契递归算法

让我们学习如何创建斐波那契数列的递归算法。递归的基本标准。

START
Procedure Fibonacci(n)
   declare f₀, f₁, fib, loop 
   
   set f₀ to 0
   set f₁ to 1
   
   display f₀, f₁
   
   for loop ← 1 to n
   
      fib ← f₀ + f₁   
      f₀ ← f₁
      f₁ ← fib

      display fib
   end for

END

例子

C C++ Java Python

#include <stdio.h>
int factorial(int n) {
   //base case
   if(n == 0) {
      return 1;
   } else {
      return n * factorial(n-1);
   }
}
int fibbonacci(int n) {
   if(n == 0){
      return 0;
   } else if(n == 1) {
      return 1;
   } else {
      return (fibbonacci(n-1) + fibbonacci(n-2));
   }
}
int main() {
   int n = 5;
   int i;
	
   printf("Factorial of %d: %d\n" , n , factorial(n));
   printf("Fibbonacci of %d: " , n);
   for(i = 0;i<n;i++) {
      printf("%d ",fibbonacci(i));            
   }
}

输出

Factorial of 5: 120
Fibbonacci of 5: 0 1 1 2 3

// C++ Code for Fibonacci series
#include <iostream>
int factorial(int n) {
   //base case
   if(n == 0) {
      return 1;
   } else {
      return n * factorial(n-1);
   }
}
int fibbonacci(int n) {
   if(n == 0){
      return 0;
   } else if(n == 1) {
      return 1;
   } else {
      return (fibbonacci(n-1) + fibbonacci(n-2));
   }
}
int main() {
   int n = 5;
   int i;
   std::cout << "Factorial of " << n << ": " << factorial(n) << std::endl;
   std::cout << "Fibbonacci of " << n << ": ";
   for(i = 0;i<n;i++) {
      std::cout << fibbonacci(i) << " ";            
   }
}

输出

Factorial of 5: 120
Fibbonacci of 5: 0 1 1 2 3

// Java Code for Fibonacci series
public class Fibonacci {
    public static int factorial(int n) {
        // base case
        if (n == 0) {
            return 1;
        } else {
            return n * factorial(n - 1);
        }
    }
    public static int fibonacci(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        } else {
            return fibonacci(n - 1) + fibonacci(n - 2);
        }
    }
    public static void main(String[] args) {
        int n = 5;
        int i;
        System.out.println("Factorial of " + n + ": " + factorial(n));
        System.out.print("Fibonacci of " + n + ": ");

        for (i = 0; i < n; i++) {
            System.out.print(fibonacci(i) + " ");
        }
    }

输出

Factorial of 5: 120
Fibonacci of 5: 0 1 1 2 3

#Python code for fibonacci Series
def factorial(n):
   # base case
   if n == 0:
      return 1
   else:
      return n * factorial(n-1)

def fibonacci(n):
   if n == 0:
      return 0
   elif n == 1:
      return 1
   else:
      return fibonacci(n-1) + fibonacci(n-2)

if __name__ == "__main__":
   n = 5
   print("Factorial of", n, ":", factorial(n))
   print("Fibonacci of", n, ": ")
   for i in range(n):
      print(fibonacci(i))

输出

Factorial of 5 : 120
Fibonacci of 5 : 
0
1
1
2
3