上阶梯★★★

上阶梯，你可以一个一个阶梯上，也可以两个两个地来，也可以一个和二个间隔着上，甚至可以一次k个

阶梯
问题是，上一个阶梯数为n，每步能上1至k个阶的话，你有多少种方法走完它？

如 n = 5 , k = 2，可以
1,1,1,1,1
2,1,1,1
1,2,1,1
1,1,2,1
1,1,1,2
2,2,1
2,1,2
1,2,2
共8种

输入阶梯数n(1 <= n <= 30)和每步最大阶数k(1<=k<=n)：
5 2
5 3

输出：
8
13

解题报告：不记得什么时候写的程序了，当时写了个简单思路“斐波那弃序列变种” ，现在自己看了十几分钟才弄明白。因此写个详细的报告，以备不时之需：我们先看下 k=2 的情况，设 f(n) 表示走完台阶数为 n 的方法如果n = 1， 显然 f(1) = 1如果n = 2，台阶: 1 1 我们的走法是 f(1) 1, 2, 即若最后一步走一步则走法是 f(1) , 还有两个台阶   一步走完又是一种方法，所以 f(2) = f(1)+1 = 2;如果n = 3，同 2 我们有 f(3)=f(2)+f(1),即最后一步走一个台阶就是 f(2), 另外最后一步走两个台阶  则为 f(1), 因为k=2,最后一步不能超过 2，因此 3 2 的走法就是 f(3) = f(2)+f(1)。一般的 n = m 我们有 f(m) = f(m-1)+f(m-2) (m>=3) 即 k=2 时为正中的斐波那弃序列。

通常的 n k ,我们防上面的方法: 有 f(m) = f(m-1)+f(m-2)+ ... + f(m-k)
证明：显然 f(1) = 1 如果 k>=2 则 f(2) = 2, 如果 k>=3 , 则 f(3) = f(2)+f(1)+1 表示最后一步分别走 1，2，3个台阶。 我们按最后一步的走法即可得上面的公式：
 f(m) = f(m-1)+f(m-2)+ ... + f(m-k) (m>k)

// 下面是实现代码 f(n) 的值记录在 数组 a 中了

#include <stdio.h>
#define MAX 30
int main(){
        int  n,k,i,j,t,m,a[MAX];
        while(scanf("%d %d",&n,&k)!=EOF){
                for(a[1]=i=1; i <= k; i++){ // 求 k 个台阶的 f() 值
                        for(j=i-1,t=0; j>=0; j--)
                                t += a[j]; // 公式 f(m)=f(m-1)+f(m-2)+...+f(1) 
                   a[i] = t+1; // 因为m <= k 所以我们可以一步走完所有台阶，因此加1
                }
                for(i=k+1; i <= n; i++){ 
                      for(m=t=1,j=i-1; m <= k; m++,j--)
                             t += a[j]; // 用公式：f(m) = f(m-1)+f(m-2)+ ... + f(m-k)
                   a[i] = t; // 这里不加 1，因为 i > k 因此一步不能走完i个台阶
                }
                printf("%d\n",a[i]);
        }
        return 0;
}

/// 提交代码：（用 0 表示了一个台阶）

#include <stdio.h>
#define MAX 30
int main(){
        int  n,k,i,j,t,m,a[MAX];
        while(scanf("%d %d",&n,&k)!=EOF){
                for(a[1]=i=1; i <= k; i++){
                        for(j=i-1,t=0; j>=0; j--)
                                t += a[j];
                        a[i] = t+1;
                }
                for(i=k+1; i <= n; i++){
                        for(m=t=1,j=i-1; m <= k; m++,j--)
                                t += a[j];
                        a[i] = t;
                }
                printf("%d\n",a[i]);
        }
        return 0;
}

评论