Fibonacci数列
一、斐波那契数列
斐波纳契数是以下整数序列中的数字。
0,1,1,2,3,5,8,13,21,34,55,89,144 ......
在数学术语中,斐波那契数的序列Fn由递归关系定义
二、斐波那契数列的实现
方法1(使用递归)
一种简单的方法,它是上面给出的直接递归实现数学递归关系。
如给定数n=8,打印第n个Fibonacci数。
C:
//Fibonacci Series using Recursion
#include<stdio.h>
int fib(int n)
{
if (n <= 1)
return n;
return fib(n-1) + fib(n-2);
}
int main ()
{
int n = 8;
printf("%d", fib(n));
getchar();
return 0;
}
Java:
//Fibonacci Series using Recursion
class fibonacci
{
static int fib(int n)
{
if (n <= 1)
return n;
return fib(n-1) + fib(n-2);
}
public static void main (String args[])
{
int n = 8;
System.out.println(fib(n));
}
}
/* This code is contributed by Rajat Mishra */
Python:
# Function for nth Fibonacci number
def Fibonacci(n):
if n<0:
print("Incorrect input")
# First Fibonacci number is 0
elif n==1:
return 0
# Second Fibonacci number is 1
elif n==2:
return 1
else:
return Fibonacci(n-1)+Fibonacci(n-2)
# Driver Program
print(Fibonacci(8))
#This code is contributed by Saket Modi
C#:
// C# program for Fibonacci Series
// using Recursion
using System;
public class GFG
{
public static int Fib(int n)
{
if (n <= 1)
{
return n;
}
else
{
return Fib(n - 1) + Fib(n - 2);
}
}
// driver code
public static void Main(string[] args)
{
int n = 8;
Console.Write(Fib(n));
}
}
// This code is contributed by Sam007
PHP:
<?php
// Fibonacci Series
// using Recursion
// function returns
// the Fibonacci number
function fib($n)
{
if ($n <= 1)
return $n;
return fib($n - 1) +
fib($n - 2);
}
// Driver Code
$n = 8;
echo fib($n);
// This code is contributed by aj_36
?>
时间复杂度: T(n)= T(n-1)+ T(n-2)是指数的。
我们可以观察到这个实现做了很多重复的工作(参见下面的递归树)。所以这对于第n个Fibonacci数是一个糟糕的实现。
fib(5)
/
fib(4)fib(3)
/ /
fib(3)fib(2)fib(2)fib(1)
/ / /
fib(2)fib(1)fib(1)fib(0) fib(1)fib(0)
/
fib(1)fib(0)
空间:如果我们考虑函数调用堆栈大小,则为O(n),否则为O(1)。
方法2(使用动态编程)
C:
//Fibonacci Series using Dynamic Programming
#include<stdio.h>
int fib(int n)
{
/* Declare an array to store Fibonacci numbers. */
int f[n+2]; // 1 extra to handle case, n = 0
int i;
/* 0th and 1st number of the series are 0 and 1*/
f[0] = 0;
f[1] = 1;
for (i = 2; i <= n; i++)
{
/* Add the previous 2 numbers in the series
and store it */
f[i] = f[i-1] + f[i-2];
}
return f[n];
}
int main ()
{
int n = 9;
printf("%d", fib(n));
getchar();
return 0;
}
Java:
// Fibonacci Series using Dynamic Programming
class fibonacci
{
static int fib(int n)
{
/* Declare an array to store Fibonacci numbers. */
int f[] = new int[n+2]; // 1 extra to handle case, n = 0
int i;
/* 0th and 1st number of the series are 0 and 1*/
f[0] = 0;
f[1] = 1;
for (i = 2; i <= n; i++)
{
/* Add the previous 2 numbers in the series
and store it */
f[i] = f[i-1] + f[i-2];
}
return f[n];
}
public static void main (String args[])
{
int n = 9;
System.out.println(fib(n));
}
}
/* This code is contributed by Rajat Mishra */
Pyhon:
# Fibonacci Series using Dynamic Programming
def fibonacci(n):
# Taking 1st two fibonacci nubers as 0 and 1
FibArray = [0, 1]
while len(FibArray) < n + 1:
FibArray.append(0)
if n <= 1:
return n
else:
if FibArray[n - 1] == 0:
FibArray[n - 1] = fibonacci(n - 1)
if FibArray[n - 2] == 0:
FibArray[n - 2] = fibonacci(n - 2)
FibArray[n] = FibArray[n - 2] + FibArray[n - 1]
return FibArray[n]
print(fibonacci(9))
时间复杂度: O(n)
空间: O(n)
方法3(空间优化方法2)
我们可以通过存储前两个数字来优化方法2中使用的空间,因为这是我们获得下一个Fibonacci数串行所需的全部内容。
C:
// Fibonacci Series using Space Optimized Method
#include<stdio.h>
int fib(int n)
{
int a = 0, b = 1, c, i;
if( n == 0)
return a;
for (i = 2; i <= n; i++)
{
c = a + b;
a = b;
b = c;
}
return b;
}
int main ()
{
int n = 9;
printf("%d", fib(n));
getchar();
return 0;
}
Java:
// Java program for Fibonacci Series using Space
// Optimized Method
class fibonacci
{
static int fib(int n)
{
int a = 0, b = 1, c;
if (n == 0)
return a;
for (int i = 2; i <= n; i++)
{
c = a + b;
a = b;
b = c;
}
return b;
}
public static void main (String args[])
{
int n = 9;
System.out.println(fib(n));
}
}
// This code is contributed by Mihir Joshi
Python:
# Function for nth fibonacci number - Space Optimisataion
# Taking 1st two fibonacci numbers as 0 and 1
def fibonacci(n):
a = 0
b = 1
if n < 0:
print("Incorrect input")
elif n == 0:
return a
elif n == 1:
return b
else:
for i in range(2,n+1):
c = a + b
a = b
b = c
return b
# Driver Program
print(fibonacci(9))
#This code is contributed by Saket Modi
时间复杂度: O(n)
额外空间: O(1)
方法4(使用矩阵的幂{{1,1},{1,0}})
这另一个O(n)依赖于如果我们乘以矩阵M = {{1,1}的事实, {1,0}}自身(换句话说,计算功率(M,n)),然后我们得到第(n + 1)个斐波纳契数作为结果矩阵中行和列(0,0)的元素。
矩阵表示为Fibonacci数提供以下闭合表达式:
C:
#include <stdio.h>
/* Helper function that multiplies 2 matrices F and M of size 2*2, and
puts the multiplication result back to F[][] */
void multiply(int F[2][2], int M[2][2]);
/* Helper function that calculates F[][] raise to the power n and puts the
result in F[][]
Note that this function is designed only for fib() and won't work as general
power function */
void power(int F[2][2], int n);
int fib(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 M[2][2])
{
int x = F[0][0]*M[0][0] + F[0][1]*M[1][0];
int y = F[0][0]*M[0][1] + F[0][1]*M[1][1];
int z = F[1][0]*M[0][0] + F[1][1]*M[1][0];
int w = F[1][0]*M[0][1] + F[1][1]*M[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 M[2][2] = {{1,1},{1,0}};
// n - 1 times multiply the matrix to {{1,0},{0,1}}
for (i = 2; i <= n; i++)
multiply(F, M);
}
/* Driver program to test above function */
int main()
{
int n = 9;
printf("%d", fib(n));
getchar();
return 0;
}
Java:
class fibonacci
{
static int fib(int n)
{
int F[][] = new int[][]{{1,1},{1,0}};
if (n == 0)
return 0;
power(F, n-1);
return F[0][0];
}
/* Helper function that multiplies 2 matrices F and M of size 2*2, and
puts the multiplication result back to F[][] */
static void multiply(int F[][], int M[][])
{
int x = F[0][0]*M[0][0] + F[0][1]*M[1][0];
int y = F[0][0]*M[0][1] + F[0][1]*M[1][1];
int z = F[1][0]*M[0][0] + F[1][1]*M[1][0];
int w = F[1][0]*M[0][1] + F[1][1]*M[1][1];
F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}
/* Helper function that calculates F[][] raise to the power n and puts the
result in F[][]
Note that this function is designed only for fib() and won't work as general
power function */
static void power(int F[][], int n)
{
int i;
int M[][] = new int[][]{{1,1},{1,0}};
// n - 1 times multiply the matrix to {{1,0},{0,1}}
for (i = 2; i <= n; i++)
multiply(F, M);
}
/* Driver program to test above function */
public static void main (String args[])
{
int n = 8;
System.out.println(fib(n));
}
}
/* This code is contributed by Rajat Mishra */
Python:
# Helper function that multiplies
# 2 matrices F and M of size 2*2,
# and puts the multiplication
# result back to F[][]
# Helper function that calculates
# F[][] raise to the power n and
# puts the result in F[][]
# Note that this function is
# designed only for fib() and
# won’t work as general
# power function
def fib(n):
F = [[1, 1],
[1, 0]]
if (n == 0):
return 0
power(F, n – 1)
return F[0][0]
def multiply(F, M):
x = (F[0][0] * M[0][0] +
F[0][1] * M[1][0])
y = (F[0][0] * M[0][1] +
F[0][1] * M[1][1])
z = (F[1][0] * M[0][0] +
F[1][1] * M[1][0])
w = (F[1][0] * M[0][1] +
F[1][1] * M[1][1])
F[0][0] = x
F[0][1] = y
F[1][0] = z
F[1][1] = w
def power(F, n):
M = [[1, 1],
[1, 0]]
# n – 1 times multiply the
# matrix to {{1,0},{0,1}}
for i in range(2, n + 1):
multiply(F, M)
# Driver Code
if __name__ == “__main__”:
n = 8
print(fib(n))
# This code is contributed
# by ChitraNayal
时间复杂度: O(n)
额外空间: O(1)