一、斐波那契数列的定义
二、Fibonacci算法设计
2.1、递归算法
int Fibonacci(int n)
{
if (n <= 0)
return 0;
if (n == 1 || n == 2)
return 1;
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
#include <stdio.h>
#include <stdlib.h>
int Fibonacci(int n)
{
if (n <= 0)
return 0;
if (n == 1 || n == 2)
return 1;
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
int main(int argc,char **argv)
{
int n = 6;
if (argc > 1)
n = atoi(argv[1]);
printf("n= %d, Fibonacci: %d\n", n, Fibonacci(n));
return 0;
}
$ ./Fibonacci
n= 6, Fibonacci: 8
$ ./Fibonacci 10
n= 10, Fibonacci: 55
2.2、算法时间复杂度
2.3、算法改进1
int Fibonacci_1(int n) {
int *F = new int[n + 1];//定义一个长度为n+1的数组，空间尚未使用
F[1] = 1;
F[2] = 1;
for (int i = 3; i <= n; i++)
F[i] = F[i - 1] + F[i - 2];
return F[n];
}
2.4、算法优化2
int Fibonacci_2(int n){
if(n==1||n==2)
return 1;
int f1=1;
int fs2=1;
for(int i=3;i<=n;i++){
int tmp=f1+f2;
f1=f2;
f2=tmp;
}
return f2;
}
三、斐波那契数列与黄金分割数
总结
欢迎关注我的公众号
每日推送文章
