算法-名企面试(360)

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

Answer解法
方式一：采用逆向思维
非常明显这是一道简单动态规划的题目，

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

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

方式二：采用正向思维
从a0和a1，逐个往后计算，知道找到自己需要的值。

代码如下：
public static void main(String args[ ]){
int a0=0;
int a1=1;

        System.out.println("方法一测试结果："+getNum(a0, a1, 30));
        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;
    }

测试结果：

1555581542(1).jpg