题目是这样的:
一个楼梯有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) ;
}
}
}
后来发现其实很多类似的问题,比如铺地砖问题,自然数拆分等。希望我写的这些给大家一些帮助。