了解网站开发 后台流程,源码网站大淘客cms,WordPress邮件回复stmp,48互联网站建设菲波那契数列定义为#xff1a;f(1) 1; f(2) 1; 当n2时#xff0c;f(n) f(n-1) f(n-2)#xff0c;输入n#xff0c;求菲波那契数列的第n项。要求#xff1a;用递归函数求菲波那契数列的第n项。
1.递归 代码如下#xff08;未优化#xff09;#xff1a;
//We…菲波那契数列定义为f(1) 1; f(2) 1; 当n2时f(n) f(n-1) f(n-2)输入n求菲波那契数列的第n项。要求用递归函数求菲波那契数列的第n项。
1.递归 代码如下未优化
//Wecccccccc
//2021.1.6
#include iostream
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, c;cin n;c fib(n);cout c endl;return 0;
}
优化代码如下
//Wecccccccc
//2021.1.6
#include iostream
using namespace std;
int fibs[1000];int fib(int n) {if (n 1 || n 2) {return 1;}if (fibs[n] ! 0) {return fibs[n];}return fibs[n] fib(n - 1) fib(n - 2);
}int main() {int n, c 0;cin n;c fib(n);cout c endl;return 0;
}2.递推 代码如下
//author:Wecccccccc
//time:2021.1.29
#include iostream
using namespace std;
int f[50];int main() {int n;cin n;f[1] 1, f[2] 1;for (int i 3; i n; i) {f[i] f[i - 1] f[i - 2];}cout f[n] endl;return 0;
}
