Java青蛙跳臺階問題的解決思路與代碼

問題描述

一隻青蛙一次可以跳上1級臺階,也可以一次跳上2級臺階,請問跳上n級臺階,該請娃一共有多少種跳法?

解決思路

①如果隻有1級臺階,那顯然隻有一種跳法。

②如果有2級臺階,那麼就有2種跳法,一種是分2次跳。每次跳1級,另一種就是一次跳2級。

③如果臺階級數大於2,設為n的話,這時我們把n級臺階時的跳法看成n的函數,記為,第一次跳的時候有2種不同的選擇:一是第一次跳一級,此時跳法的數目等於後面剩下的n-1級臺階的跳法數目,即為,二是第一次跳二級,此時跳法的數目等於後面剩下的n-2級臺階的跳法數目,即為,因此n級臺階的不同跳法的總數為,不難看出就是斐波那契數列。

實現代碼

1.青蛙跳臺階遞歸方法
 public static int f1(int n){
 if(n==1||n==2){
 return n;
 }
 else{
 return f1(n-1)+f1(n-2);
 }
 }

2.青蛙跳臺階非遞歸方法
 public static int f2(int m){
 if(m==1||m==2){
 return m;
 }
 int a1 = 1;
 int a2 = 2;
 int result = 0;

 for (int i = 3; i <= m; i++) {
 result = a1 + a2;
 a1 = a2;
 a2 = result;
 }
 return result;
 }

 public static void main(String[] args) {
 Scanner sc = new Scanner(System.in);
 int num = sc.nextInt();
 System.out.println("遞歸青蛙跳"+num+"級臺階共有"+f1(num)+"種方法!");
 System.out.println("非遞歸青蛙跳"+num+"級臺階共有"+f2(num)+"種方法!");
 }

運行結果:

總結

到此這篇關於Java青蛙跳臺階問題的解決思路與代碼的文章就介紹到這瞭,更多相關Java青蛙跳臺階內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!

推薦閱讀: