984
2013藍橋杯【初賽試題】第39階台階
第39階台階
小明剛剛看完電影《第39級台階》，離開電影院的時候，他數了數禮堂前的台階數，恰好是39級!
站在台階前，他突然又想著一個問題：
如果我每一步隻能邁上1個或2個台階。先邁左腳，然後左右交替，最後一步是邁右腳，也就是說一共要走偶數步。那麼，上完39級台階，有多
少種不同的上法呢？
請你利用計算機的優勢，幫助小明尋找答案。
要求提交的是一個整數。
注意：不要提交解答過程，或其它的輔助說明文字。
思路：(原先用斐波那契額真是大錯特錯.....)這一題的重點是偶數步（先邁左右腳是幹擾），因為隻有39個台階，
數據量不大，我們可以選擇遞歸，每次加1步或2步，每次判斷台階總數是否滿39，滿了的話判斷
AC代碼：
#include<stdio.h>
int Sum=0;
//sidestep是剩餘的台階數
//step是走上麵這些台階用了多少步
void Total(int sidestep,int step)
{
if(sidestep<0) return; //台階走完函數結束
if(sidestep==0) //台階全部走完
{
if(step%2 == 0) Sum++; //如果總步數是偶數，方法數加1
return;
}
//分別是走一步和走兩步的方法向下遞歸
Total(sidestep-1,step+1);
Total(sidestep-2,step+1);
}
int main()
{
Total(39,0);
printf("%d\n",Sum);
return 0;
}
結果為：51167078步
最後更新：2017-04-03 12:55:21