当前位置:C++技术网 > 资讯 > 走台阶问题--递归问题

走台阶问题--递归问题

更新时间:2015-10-20 17:15:57浏览次数:1+次

题目是这样的:

一个楼梯有50个台阶,每一步可以走一个台阶,也可以走两个台阶,请问走完这个楼梯共有多少种方法?

举个例子,假设有3个台阶,则有三种走法:分别是,1-1-1, 1-2, 2-1。


很简单的一道题,学过组合数学的人很快就能想到,这是一个递推关系。假设走完k个台阶有f(k)种走法。

  • k = 1时,f(k) = 1
  • k = 2时,f(k) = 2
  • k = n时,第一步走一个台阶,剩n-1个台阶,有f(n - 1)种走法。第一步走两个台阶,剩n-2个台阶,有f(n - 2)种走法。所以共有f(n - 1) + f(n - 2)种走法。

于是有如下公式



int count(unsigned int n)
{
    if(n == 1)
        return 1 ;
    if(n == 2)
        return 2 ;
    else 
        return count(n - 1) + count(n - 2) ;
}

上面只给出了有多少种走法,那么具体每一种走法是怎么走的呢?比如n=4时,五种走法分别如下:

1,1,1,1

1,1,2

1,2,1

2,1,1

2,2

我们用一个整型数组来存放每一步的内容,1表示这步走了一个台阶,2表示这步走了两个台阶。回溯法搞定。代码如下。

void count(int n, int t)
{
    if(n < 0)
        return ;
    if (n == 0)
        Output(step, t) ;
    else
    {
        for (int i = 1; i <= 2; ++i)
        {
            step[t] = i ;
            count(n - i, t + 1) ;
        }
    }
}


后来发现其实很多类似的问题,比如铺地砖问题,自然数拆分等。希望我写的这些给大家一些帮助。