求递归算法

Question

一列数的规则如下: 1、1、2、3、5、8、13、21、34......  求第30位数是多少，用递归算法实现

Answer 1

public int a(int n) {
return (n > 2) ? a(n-1) + a(n-2) : 1;
}

Answer 2

package com.test;public class Test2{
public static void main(String[] args){
System.out.println(method(30));//测试
}
public static int method(int n){//递归算法
if(n <= 0){
return 0;
}else{
if(n == 1 || n == 2){
return 1;
}else{
return method(n-1) + method(n-2);
}
}

}
}

Answer 3

       wonderful      

Answer 4

public class Main {
    static int[] ia = new int[30];
    /** Creates a new instance of Main */
    public Main() {
    }
    
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) throws Exception {
        ia[0]=1;
        ia[1]=1;
        aa(ia[0],ia[1],2);
        System.out.println(ia[29]);
    }
    
    static void aa(int i,int j,int end){
        ia[end]=i+j;
        if(end==29){
            return ;
        }
        aa(ia[end-1],ia[end],end+1);
    }
}

Answer 5

用递归也太慢了
public class Test {
public static void main(String[] args) {
long star = System.currentTimeMillis();
//getNum01(100);
System.out.println(getNum01(30) + " : " + (System.currentTimeMillis() - star));
System.out.println("~~~~~~~~~~~~~~~~~~~~~~~~~");
star = System.currentTimeMillis();
System.out.println(getNum02(30) + " : " + (System.currentTimeMillis() - star));
}
static long getNum01(int i){
long[] values = new long[i];
values[0] = 1;
values[1] = 1;
for(int m = 2; m < i; m++){
values[m] = values[m-1] + values[m-2];
}
return values[i-1];
}
static long getNum02(int i){
return i > 2 ? getNum02(i -1) + getNum02(i - 2) : 1 ;
}
}
测试结果：
832040 : 0
~~~~~~~~~~~~~~~~~~~~~~~~~
832040 : 16
这还好是求 30 位的 ，如果求 50位的话，你就会以为自己那死机了呢。

Answer 6

掉入陷井!!!!
private int[] _a(int n) {
if (n < 0) return new int[]{ 0, 0 };
if (n < 3) return new int[]{ 1, n-1 };
int[] ary = _a(n - 1);
int i = ary[0];
ary[0] = i + ary[1];
ary[1] = i;
return ary;
}
public int a(int n) {
return _a(n)[0];
}

Answer 7

递归的话，1楼那个就是最简洁的了。
14楼的代码，没看出优化在哪。我感觉一点都没优化。
我也写一个，非递归：
public static long[] a(int n) {
long[] arr = new long[n];
arr[0] = 1;
arr[1] = 1;
for (int i = 2; i < n; i++) {
arr[i] = arr[i - 1] + arr[i - 2];
} return arr;
}

Answer 8

不是说要递归吗？楼上几位赖皮啊。哈哈。
这样的话，俺就只能上公式了。
public class Fibonacci {    static double sqrt5 = Math.sqrt(5);    /**
     * @param args
     */
    public static void main(String[] args) {        for (int i = 0; i < 20; i++) {
            System.out.println("F" + i + ":" + getFibonacci(i));
        }    }    public static int getFibonacci(int n) {        return (int) ((Math.pow(((1.0 + sqrt5) / 2.0), n) - Math.pow(((1.0 - sqrt5) / 2.0), n)) / sqrt5);
    }}
输出：
F0:0
F1:1
F2:1
F3:2
F4:3
F5:5
F6:8
F7:13
F8:21
F9:34
F10:55
F11:89
F12:144
F13:233
F14:377
F15:610
F16:987
F17:1597
F18:2584
F19:4181

Answer 9

package Practice01;
import java.util.*;
public class Test15 {
/***
 *15，求斐波那契数列前n项的和值,斐波那契数列如下：
       1，1，2，3，5，8，13，21……
     前两位数是1，从第三位开始每位数都是前两位数之和 
 * 
 */
public static void main(String[] args) {
System.out.println("请问您要前几项的和？(整数)");
Scanner input =new Scanner(System.in);
int length=input.nextInt();
int []a =new int [length];
new Test15().output(a, a.length);

}

void output(int[]a,int n)
{

  int sum=0;
  for(int i=0;i<n;i++)//给数组赋值
  {
  if (i==0||i==1) 
  {
a[i]=1;
  }
  else 
  {
a[i]=a[i-1]+a[i-2];
  }
  }
  for(int i=0;i<n;i++)//求和
  {
  sum+=a[i];
  }
  System.out.println("斐波那契数列前"+n+"项的和是"+sum);
}
}