【算法讨论】关于一个爬台阶的问题，求思路或代码

问题描述：

   有n阶台阶，每次可以爬一个或两个台阶，请统计共有多少种走台阶的方法，并且把所有可能的组合输出到屏幕

请算法君指点一下，说说这道题目用C来解决的思路和方法，感激不尽

9 个解决方案

#1

F(n)=F(n-1)+F(n-2); 

#2

要打印所有可能的组合，不知道N的范围是多大呢...可以这样考虑：
假设第K次迈出脚步之前还有N个阶梯等着上，则
（1）如果N >= 2，本次可以选择上2级阶梯也可以选择上1级阶梯，如果上2级阶梯，则问题变为第K+1次迈出脚步之前还有N-2级阶梯等着上；如果上1级阶梯则问题变为第K+1次迈出脚步之前还有N-1级阶梯等着上
（2）如果N == 1，只能上1级阶梯，当然这也是最后一级阶梯
（3）如果N == 0，则阶梯已经上完，打印第1步到最后一步的选择
按这样的思路写出递归程序即可打印所有走台阶的方法，我试了下，N <= 20的情况都可以秒出结果的，由于可能的组合是指数增加的，N = 21时就不能秒出了

#3

引用 2 楼 uuuououlcz 的回复:

要打印所有可能的组合，不知道N的范围是多大呢...可以这样考虑：
假设第K次迈出脚步之前还有N个阶梯等着上，则
（1）如果N >= 2，本次可以选择上2级阶梯也可以选择上1级阶梯，如果上2级阶梯，则问题变为第K+1次迈出脚步之前还有N-2级阶梯等着上；如果上1级阶梯则问题变为第K+1次迈出脚步之前还有N-1级阶梯等着上
（2）如果N == 1，只能上1级阶梯，当然这也是最后一级阶梯
（3）如果N == 0，则阶梯已经上完，打印第1步到最后一步的选择
按这样的思路写出递归程序即可打印所有走台阶的方法，我试了下，N <= 20的情况都可以秒出结果的，由于可能的组合是指数增加的，N = 21时就不能秒出了

请大哥贴出来代码给俺看看。。。。。

#4

引用 1 楼 derekrose 的回复:

F(n)=F(n-1)+F(n-2); 

我之前看过这个公式，但还是不太懂该怎么写算法

#5

以前剽窃的，仅供参考

//每一步只能迈上1个或2个台阶。先迈左脚，然后左右交替，最后一步是迈右脚，也就是说一共要走偶数步。那么，上完39级台阶，有多少种不同的上法呢？
//-------------------------------------------------------
//状态c[i][0]表示走到第i个楼梯时最后一步是左脚的方法数，c[i][1]是右脚的方法数。。
//那么，由于每一步能上一到两级，c[i][0] = c[i-1][1]+c[i-2][1](因为最后一步为左脚，
//倒数第二步肯定为右脚。。)。。然后一直递推。。最后c[39][1]即上到第39级而且是右脚的方法数即为答案。
#include <stdio.h>
int c[40][2];//0为左脚，1为右脚。。
int main(){
    int i;
    c[0][0] = c[1][1] = 0;
    c[0][1] = c[1][0] = 1;
    for(i = 2; i <= 39; ++i){
        c[i][0] = c[i - 1][1] + c[i - 2][1];
        c[i][1] = c[i - 1][0] + c[i - 2][0];
    }
    printf("%d\n", c[39][1]);
    return 0;
}
//-------------------------------------------------------
//走到第n级台阶的时候，他的上一步不是在n-1级就是在n-2级上，
// f(n) = f(n - 1) + f(n - 2) 很简单的递归思想
int num=0;
void fun(int n,int step)
{
  if(n<0)
    return;
  if(n==0)
  {
    if(step%2==0) num++;
    return;
   }
   fun(n-1,step+1);
   fun(n-2,step+1);
}
void main()
{
  fun(39,0);
  printf("%d",num);
}
//-------------------------------------------------------
int aux(int steps, int cnt)
{
    if (steps <= 0)
    {
        if (0 == steps && (cnt && !(cnt % 2)))
            return 1;
        return 0;
    }
    return aux(steps - 1, cnt + 1) + aux(steps - 2, cnt + 1);
}<br>
inline int func(steps)
{
    return aux(steps, 0);
}
//-------------------------------------------------------
#include <stdio.h>
static int trace[40];
static int count=0;
void go(int, int, int);
int main()
{
        go(39, 0, 1);
        go(39, 0, 2);
        printf("count=%d\n",count);
}
//
// left: left steps
// mt:   mount_times
// step: steps of current movement
//
void go(int left, int mt, int step)
{
    int i;
    if(left < 0)return;
    if(left == 0){
        if(!(mt%2)&&(step==1)){
            /* 用来记录小明的脚步，当然题目里并不要求我们记下来。
            for(i=0;i<mt;i++){
                    printf("%3d",trace[i]);
            }
            printf("\n");
            for(i=mt;i<sizeof(trace);i++){
                    trace[i]=0;
            }
            */
            count++;
        }
        return;
    }
    trace[mt] = step;
    left -= step;
    mt++;
    go(left, mt, 1);
    go(left, mt, 2);
}

#6

long Fib(long n)
{
  if(n <= 1)
    return n;
  else
    return Fib(n-1) + Fib(n-2)
}

其他输出自己加

#7

引用 3 楼 zbl100911063 的回复:

Quote: 引用 2 楼 uuuououlcz 的回复:

要打印所有可能的组合，不知道N的范围是多大呢...可以这样考虑：
假设第K次迈出脚步之前还有N个阶梯等着上，则
（1）如果N >= 2，本次可以选择上2级阶梯也可以选择上1级阶梯，如果上2级阶梯，则问题变为第K+1次迈出脚步之前还有N-2级阶梯等着上；如果上1级阶梯则问题变为第K+1次迈出脚步之前还有N-1级阶梯等着上
（2）如果N == 1，只能上1级阶梯，当然这也是最后一级阶梯
（3）如果N == 0，则阶梯已经上完，打印第1步到最后一步的选择
按这样的思路写出递归程序即可打印所有走台阶的方法，我试了下，N <= 20的情况都可以秒出结果的，由于可能的组合是指数增加的，N = 21时就不能秒出了

请大哥贴出来代码给俺看看。。。。。

#include <stdio.h>
#define MAX 20

void getUpStairs(char step[], int next, int remain)
{
    if(remain == 0){
        step[next-1] = '\0';
        puts(step);
        return;
    }
    //choose to get up 2 stairs this time
    if(remain >= 2){
        step[next] = '2';
        step[next+1] = ' ';
        getUpStairs(step, next+2, remain-2);
    }
    //choose to get up 1 stair this time
    step[next] = '1';
    step[next+1] = ' ';
    getUpStairs(step, next+2, remain-1);
}

int main()
{
    int N;
    char step[MAX*2];
    
    while(scanf("%d", &N) == 1){
        if(N > 0) getUpStairs(step, 0, N);
    }
    
    return 0;
}

#8

可以用递归来做

#9

递归时候注意效率f[n] = f[n-1]+f[n-2]
int f[N];
int dfs(int n)
{
if(f[n]) return f[n];
if(n == 1) return f[n] = 1;
if(n == 2) return f[n] = 2;
return f[n] = dfs(n - 1) + dfs(n - 2);
}