小明看完电影《第39级台阶》，离开电影院的时候，他数了数视觉的台阶数，恰好是39级。
站在台阶前，他突然又想起一个问题：如果我每一步只能迈上1个或2个台阶，先迈左脚，然后左右交替，最后一步迈右脚，也就是说一共要迈偶数步。那么，上完39级台阶，有多少种不同的上法呢？ 请利用计算机的优势，帮助小明寻找答案。
分析：
采用了两种方法：第一种traceback(t)中参数t 代表步数；第二种traceback(t)中t代表台阶数
/*
t代表台阶
*/
#include<stdio.h>
#define n 39
int step=0; //步数
int count=0; //方案数
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代表的是台阶数
printf("%d",count);
return 0;
}
/*
t代表步数
*/
#include<stdio.h>
#define n 39
int step=0; //步数
int taijie=0; //台阶数
int count=0; //方案数
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代表步数
printf("%d",count);
return 0;
}
运行截图
