在此之前你需要具备一下知识:1. 一门编程语言基础,最好是C或者C++,其他语言如果你能看懂也可以看
如果你不具备以上知识,请你先补补课再来看
递归是啥我也不具体多说了,直接上代码。
初始的斐波那契代码:
#include <bits/stdc++.h>
using namespace std;
int fib(int n){
if(n == 1||n==2) return 1;
return fib(n-1)+fib(n-2);
}
int main(){
int n;
cin>>n;
int sum=fib(n);
cout<<sum;
return 0;
}
优化后的斐波那契代码
#include <bits/stdc++.h>
using namespace std;
int fib(int n,int arr[]){
if(n == 1||n==2) return 1;
if(arr[n]==true) return arr[n];
arr[n]=fib(n-1,arr)+fib(n-2,arr);
return arr[n];
}
int main(){
int n;
cin>>n;
int arr[n];
memset(arr,0,sizeof(arr));
int sum=fib(n,arr);
cout<<sum;
return 0;
}
递归式都是F(n-1)+F(n-2),这里会调用两次递归,而两次递归中又有一些递归调用会有重复,所以,我们不妨把每次递归调用后的结果存在一个数组里,在下一次调用的时候直接判断其对应的数组是否有值,有的话直接输出,这样可以节省不必要的运算,从而降低算法的时间复杂度,但空间复杂度会有一定的增加。
优化前
优化后
正文完