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

系统管理员 2022-06-12 11:56 229阅读 0赞

# **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;
        }
    
    }

**测试结果**

![这里写图片描述][SouthEast]

[SouthEast]: /images/20220612/7d2b7be8a90449e7b6fe4ca337810827.png