问:
大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。
n<=39
斐波那契数列简单介绍
image我的解法:
public static int Fibonacci(int n) {
if(n <= 1){
return n;
}
return Fibonacci(n-1)+Fibonacci(n-2);
}
my.png
注:从Fibonacci(n-1)+Fibonacci(n-2)明显看出使用的是递归,此题用递归两三行代码即可搞定。但是,若出题者准备着一个超大的n,那么很有可能会 Stack Overflow(递归的本质就是栈),为什么会栈溢出?因为重复计算,举个栗子:
当n=4时,
Fibonacci(4) = Fibonacci(3) + Fibonacci(2)
= Fibonacci(2) + Fibonacci(1) + Fibonacci(1) + Fibonacci(0)
= Fibonacci(1) + Fibonacci(0) + Fibonacci(1) + Fibonacci(1) + Fibonacci(0);
由于我们的代码并没有记录Fibonacci(1)和Fibonacci(0)的结果,对于程序来说它每次递归都是未知的,因此光是n=4时Fibonacci(1)就重复计算了3次之多。
其他解法:
public int Fibonacci(int n) {
int preNum=1;
int prePreNum=0;
int result=0;
if(n<=1)
return n;
for(int i=2;i<=n;i++){
result=preNum+prePreNum;
prePreNum=preNum;
preNum=result;
}
return result;
}
Snipaste_2019-02-09_20-54-33.png
注:<font color="blue">动态规划</font>(Dynamic Programming)。
动态规划简单介绍:https://blog.csdn.net/u013309870/article/details/75193592
动态规划算法也可以说是 '记住求过的解来节省时间';
动态规划算法的核心就是记住已经解决过的子问题的解。
上述代码需要用到三个数进行操作(preNum、prePreNum、result),实际上可以简化为两个数,从而节省空间,代码如下:
public static int Fibonacci(int n) {
int pre = 0, next = 1;
while(n-->0) {
next += pre;
pre = next - pre;
}
return pre;
}
网友评论