小明看完電影《第39級臺階》护赊，離開電影院的時候，他數(shù)了數(shù)視覺的臺階數(shù)舀武，恰好是39級拄养。
站在臺階前，他突然又想起一個問題：如果我每一步只能邁上1個或2個臺階银舱，先邁左腳瘪匿，然后左右交替跛梗，最后一步邁右腳，也就是說一共要邁偶數(shù)步棋弥。那么核偿，上完39級臺階，有多少種不同的上法呢顽染？ 請利用計算機的優(yōu)勢宪祥，幫助小明尋找答案。
分析：
采用了兩種方法：第一種traceback(t)中參數(shù)t 代表步數(shù)家乘；第二種traceback(t)中t代表臺階數(shù)
/*
t代表臺階
*/
#include<stdio.h>
#define n 39
int step=0; //步數(shù)
int count=0; //方案數(shù)
void traceback(int t){
if(t==n&&step%2==0){
count++;
return;
}
step++;
t++;
if(t<=n)
traceback(t);
t--;
step--;
step++;
t+=2;
if(t<=n)
traceback(t);
t-=2;
step--;
}
int main(){
traceback(0); //t代表的是臺階數(shù)
printf("%d",count);
return 0;
}
/*
t代表步數(shù)
*/
#include<stdio.h>
#define n 39
int step=0; //步數(shù)
int taijie=0; //臺階數(shù)
int count=0; //方案數(shù)
void traceback(int t){
if(taijie==n&&t%2==0){
count++;
return;
}
taijie++;
t++;
if(taijie<=n)
traceback(t);
t--;
taijie--;
taijie+=2;
t++;
if(taijie<=n)
traceback(t);
t--;
taijie-=2;
}
int main(){
traceback(0); //t代表步數(shù)
printf("%d",count);
return 0;
}
運行截圖
