回溯39级台阶

---

---

小明看完电影《第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;
} 

运行截图