Fibonacci基础讲解
数列递推公式:f(n) = f(n - 1) + f(n - 2);
这里我只讲斐波那契的基础写法,不讲优化,所以平时写时间复杂度不要求的话直接写递归就行,
递归好写,但是要求时间复杂度的话,递归可以用Dp(动态规划)来优化or记忆化搜索等等,
这里不是算法分析或算法竞赛不展开细讲,只按基础写法来说递推效率比递归效率高
原因很简单,每一次递归都会有重复的递归分支影响整体时间效率
这里我说一下,也可以用数组来写,注意下标为0的赋值0,然后递推公式就可以
类型1:返回Fibonacci数列的第n项数
递归写法:
递归他的前一项和前前一项返回并累加即可!
//递归基本上都是在函数中调用,所以我只写递归函数就行
int fibo(int n)
{
if(n == 1 || n == 2) return 1;
return fibo(n - 1) + fibo(n - 2);
}
递推写法:
按公式写就行,特判前两项,循环的时候注意更新交换的次序
#include <iostream>
#include <stdio.h>
using namespace std;
int main()
{
//输入一个n,返回斐波那契数列第n项的元素
int n;
scanf("%d", &n);
if(n <= 2)
{
printf("1");
return 0; //如果是前两项直接返回1,结束程序
}
//F(n) = F(n-1) + F(n-2)
int f1 = 1, f2 = 1, f3;
for(int i = 3;i <= n;i ++)
{
f3 = f1 + f2;
//注意:先移f1,再移f2,防止冲突
f1 = f2;
f2 = f3;
}
printf("%d",f3);
return 0;
}
类型2:输出Fibonacci数列的前n项
上面看懂了,直接自己改写就行,很简单
递归写法:
#include <iostream>
#include <stdio.h>
using namespace std;
int fibo(int n)
{
if(n == 1 || n == 2) return 1;
return fibo(n - 1) + fibo(n - 2);
}
int main()
{
//输入一个n,返回斐波那契数列第n项的元素
int n;
scanf("%d", &n);
for(int i = 1;i <= n;i ++)
printf("%d ",fibo(i));
return 0;
}
递推写法:
特判前两项,递推前n项
#include <iostream>
#include <stdio.h>
using namespace std;
int main()
{
//输入一个n,返回斐波那契数列第n项的元素
int n;
scanf("%d", &n);
//把前两项特判输出
if(n > 1) printf("1 ");
if(n > 2) printf("1 ");
//F(n) = F(n-1) + F(n-2)
int f1 = 1, f2 = 1, f3;
for(int i = 3;i <= n;i ++)
{
f3 = f1 + f2;
//注意:先移f1,再移f2,防止逻辑冲突
f1 = f2;
f2 = f3;
printf("%d ",f3);
}
return 0;
}
类型3:判断n是否为斐波那契数列的一项元素
这里面需要知道一点:
数列的第n项元素fibo(n),
在n=5的时候,n=fibo(5),
在n<5的时候,n>fibo(n),
在n>5以后,n<fibo(n);
根据上面规律已经得出…
递归写法
理解上面的写法以后,这种写法很容易改写
#include <iostream>
#include <stdio.h>
using namespace std;
int fibo(int n)
{
if(n == 1 || n == 2) return 1;
return fibo(n - 1) + fibo(n - 2);
}
int main()
{
//输入一个n,返回斐波那契数列第n项的元素
int n;
scanf("%d", &n);
for(int i = 1;i <= n;i ++)
{
int t = fibo(i);
if(t == n)
{
printf("Yes");
break;
}
if(t > n)
{
printf("No");
break;
}
}
return 0;
}
递推写法:
推荐用递推
#include <iostream>
#include <stdio.h>
using namespace std;
int main()
{
int n;
scanf("%d", &n);
//先判断前5项
if(n <= 5)
{
if(n == 1 || n == 2 || n == 3 || n == 5)
printf("Yes");
if(n == 4)
printf("No");
return 0;
}
//再遍历第5项以后
int f1 = 3, f2 = 5, f3;
for(int i = 6;i <= n;i ++)
{
f3 = f1 + f2;
f1 = f2;
f2 = f3;
if(f3 == n)
{
printf("Yes");
break;
}
if(f3 > n)
{
printf("No");
break;
}
}
return 0;
}