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

測試結果

總結

以上是生活随笔為你收集整理的算法--360面试：使用递归实现：a0=1，a1=1;a2=a0+a1;a3=a1+a2...以此类推，求a30的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。