題目鏈接:
http://acm.hdu.edu.cn/showproblem.php?pid=2041

題目要求:

有一樓梯共M級(jí)，剛開始時(shí)你在第一級(jí)，若每次只能跨上一級(jí)或二級(jí)，要走上第M級(jí)，共有多少種走法？

image.png

做題思路:

剛開始沒有做草稿，坐在那看著電腦空想，怎么也想不到思路，后來(lái)動(dòng)手列了幾個(gè)情況才找到規(guī)律。
按照樓梯一級(jí)一級(jí)找規(guī)律，
f(1) = 0
f(2) = 1
f(3) = 2
f(4) = 3
f(5) = 5
很快可以看到規(guī)律，就是從第三階樓梯之后，
都有f(n) = f(n-1)+f(n-2),斐波那契數(shù)列；
通過遞推法就可以求到后面的數(shù)了

代碼:

#include "stdio.h"

int a(int m) {
    if(m == 2 || m == 3)
        return m-1;
    else
        return a(m-1)+a(m-2);
}

int main() {
    int n,m,count=0;
    scanf("%d",&n);
    while (n-- > 0) {
        scanf("%d",&m);
        printf("%d\n",a(m));
    }
}