剑指offer例题——裴波那契数列

编程题:大家都知道裴波那契数列,现在要求输入一个整数n,请你输出裴波那契数列的第n项(从0开始,第0项为0)。n<=39

 public class Solution {
public int Fibonacci(int n) {
Double a = 1/Math.sqrt(5)*(Math.pow(((1+Math.sqrt(5))/2),n)-Math.pow(((1-Math.sqrt(5))/2),n));
int b = a.intValue();
return b;
}
}

第一遍程序,结果运行时间和占用内存都不理想。

裴波那契数列,嗯。。。我不属于“大家都知道”系列,先百度该数列,想起来了,这是高中数学接触的生兔子问题,即1、1、2、3、5、8、13、21、34、……其遵循F(1)=1,F(2)=1, F(n)=F(n-1)+F(n-2)(n>=3,n∈N*)

由于查到其有一个通项公式:剑指offer例题——裴波那契数列

而且,n=0,1,2也都遵循该通式,故我的编程即从其入手。

在上述运算过程中遇到的第一个问题,即sqrt与pow函数的使用,然后是Double到int的强制类型转换,我发现double无法强制转换为int,百度后,发现需要改为Double。

double和Double的关系就像int和Integer的关系一样。一个是基本类型,一个是封装类类型。而基本类型是无法调用方法的,故需要用Double。

之后查看大神的讨论,采用了迭代的方法求得了新程序。

 public class Solution {
public int Fibonacci(int n) {
int a = 1;
int b = 0;
int c = 0;
if (n==0|n==1)
return n;
else
for(int i = 2;i<=n;i++){
c = a+b;
b = a;
a = c;
}
return c;
}
}

第二次编程,迭代部分已经编写出来了,但是运行始终出错,后来发现有三处错误:

1)for的使用中,三部分之间用;符号隔离;

2)对for循环中的i进行初始化时,忽略了类型int;

3)对实例变量进行声明的时候,将其放在了else后面,结果一直提示错误。

技巧:

1)利用通式计算既耗时,又耗内存,而利用迭代,则时间和资源耗费都减少了。

该次实战的经验:

1)函数调用要符合规范;

2)自己对于错误提示还不太会看,否则改起来应该会更快一点。

上一篇:【BZOJ5304】[HAOI2018]字串覆盖(后缀数组,主席树,倍增)


下一篇:详解 Python 的二元算术运算,为什么说减法只是语法糖?