算法--360面试：使用递归实现：a0=1，a1=1;a2=a0+a1;a3=a1+a2...以此类推，求a30

Q题目

编程求解

使用递归实现：a0=1，a1=1;a2=a0+a1;a3=a1+a2;a4=a2+a3...以此类推，求a30

Answer解法

方式一：采用逆向思维

非常明显这是一道简单动态规划的题目，

从后往前逆向推理，递推公式如下：

An=A(n−1)+A(n−2)

终止条件：当n=2时，A(n-1 )和 A(n-2)分别为 A0 和 A1

方式二：采用正向思维

从a0和a1，逐个往后计算，知道找到自己需要的值。

代码如下：

public class Test {
    public static void main(String args[ ]){
        int a0=1;
        int a1=1;
        System.out.println("方法一测试结果："+getNum(a0, a1, 29));
        System.out.println();
        System.out.println("方法二测试结果："+getNum(30));
    }
    /**正向思维：优点，起始值可以人为控制；不局限于本题的a0=a1=1； 缺点：计算过程复杂一些
     * 使用递归实现：a0=1，a1=1;a2=a0+a1;a3=a1+a2;a4=a2+a3...以此类推，求an
     * @param a  起始数1：a0
     * @param b  起始数2：a1
     * @param times 递归次数：an，则times=n-1
     * @return
     */
    public static int getNum(int a,int b,int times){
        int temp=a+b;
        times--;
        if(times==0){
            return temp;
        }
        return getNum(b, temp,times);
    }
    /**逆向思维：优点，清晰明了
     * 使用递归实现：a0=1，a1=1;a2=a0+a1;a3=a1+a2;a4=a2+a3...以此类推，求an
     * @param num 是an的下标，即num=n
     * @return
     */
    public static int getNum(int num){
        if (num==0||num==1) {
            num=1;
        }else {
            num=getNum(num-1)+getNum(num-2);
        }
        return num;
    }
}