描述
小樂樂上課需要走n階臺階,因為他腿比較長,所以每次可以選擇走一階或者走兩階,那么他一共有多少種走法?
輸入描述
輸入包含一個整數n (1 ≤ n ≤ 30)
輸出描述
輸出一個整數,即小樂樂可以走的方法數。
思路:(采用遞歸的思想)
1.如果只有1級臺階,那么就只有1種跳法。
2.如果有2級臺階,那么就有兩種跳法,一次跳一級或者一次跳兩級。
3.如果臺階級數大于2,設為n的話,這時我們把n級臺階的跳法看成n的函數,記為f(n),第一次跳的時候有兩種選擇:一是第一次跳一級,此時跳法的數目等于后面剩下n-1級臺階的跳法數目,即f(n-1),二是第一次跳兩級,此時跳法的數目等于后面剩下n-2級臺階的跳法數目,即f(n-2),因此n級臺階的不同跳法數目的總數為f(n)=f(n-1)+f(n-2),不難看出就是斐波那契數列。
?
?
#include <stdio.h>
int fib(int n)
{if(n==1)return 1;if(n==2)return 2;return fib(n-1)+fib(n-2);}
int main()
{int n=0;scanf("%d",&n);int ret = fib(n);printf("%d",ret);return 0;
}