() lis temp -1 代码 需要 cci key
今天研究了下 Fibonacci 算法,实现了递归和非递归两种方式得到指定第 n 个的值。
代码如下:
- 递归方式:public static int getFib(int a) {
- if (a == 1 || a == 2) {
- return 1;
- }
- return getFib(a - 2) + getFib(a - 1);
- }
- 非递归方式:
- public static intgetFib2(int a){
- intx=1;
- inty=1;
- if(a==1||a==2){
- return1;
- }
- for(inti=3;i<=a;i++){
- inttemp=y;
- y=x+y;
- x=temp;
- }
- return y;
- }
- 打印出前n项,每行5个
- public static voidlistFib(int a){
- StringBuilder sb =new StringBuilder();
- for(inti=1;i<=a;i++){
- sb.append(getFib2(i)+" ");
- if(i%5 == 0)
- sb.append("\n");
- }
- System.out.println(sb);
- }
- 测试:
- public static void main(String[] args){
- listFib(40);
- }
- 测试结果:
- 1 1 2 3 5
- 8 13 21 34 55
- 89 144 233 377 610
- 987 1597 2584 4181 6765
- 10946 17711 28657 46368 75025
- 121393 196418 317811 514229 832040
- 1346269 2178309 3524578 5702887 9227465
- 14930352 24157817 39088169 63245986 102334155
比较递归和非递归两种算法,发现递归算法效率较低,主要原因是递归会涉及到重复计算,可以通过缓存方式缓解,具体就是将计算的每项记录到一个 map 里,需要时直接 get 而不必重新计算,优化后代码如下:
- 加入缓存优化后的递归算法:public static int getFib(int a) {
- Map map = new HashMap();
- if (a == 1 || a == 2) {
- return 1;
- }
- if (map.containsKey(a)) {
- return map.get(a);
- }
- Integer b = getFib(a - 2) + getFib(a - 1);
- map.put(a, b);
- return b;
- }
斐波那契数列算法
来源: http://www.bubuko.com/infodetail-2086777.html