学步园

 取数

从键盘上输入两个自然数n和k（n<=100,k<=10），从1，2，。。。，n中任取k个数，要求所取的k个数中，任意两个数不能相差1。编程求有多少种取法。

如：n=6 ，k=3,，从1，2，3，4，5，6中取3个数，任意两个数不能相差1，取法如下：

（1 3 5） （1 3   6） （1 4 6） （2 4 6）

共有4种取法。

提示：（1 3 5）和（3 1 5）属于一种取法。

要求：

输入：一行，n和k，中间用空格隔开。

输出：一行，取法的种数。

样例：

输入：6 3

输出：4

 

分析：用 F(I,j)表示从1到I中任取j个数，任意两个数不能相邻：

如果取I，则不能取I-1，必须从1到I-2中取j-1个数，即f(I-2,j-1).

如果不取I，则只能从1到I-1中取j个数，即f(I-1,j).

故F(I,j)= f(I-2,j-1)+ f(I-1,j)

f[I,1]=I

f[1,I]=0

这个递推式的结果是:矩形的上三角全0(a[1][1]元素除外),第一列为[1~n],其它元素为a[i-2][j-1]+a[i-1][j],最终所要的结果在a[n][k].(为什么是这样,自己多推几步就知道了)

 

直接使用递归肯定要超时,这道题是典型的以空间换时间算法.

 

#include<stdio.h>
int main()
{
    int n,k,i,j,a[100][100];
    while(scanf("%d %d",&n,&k)!=EOF)
    {
        for(i=1;i<=n;i++)
            a[i][1]=i;
        for(i=2;i<=k;i++)
            a[1][i]=0;
        for(i=2;i<=n;i++)
        {
            for(j=2;j<=k;j++)
            {
                if(i<=j)
                    a[i][j]=0;
                else
                    a[i][j]=a[i-2][j-1]+a[i-1][j];
            }
        }
        printf("%d",a[n][k]);
    }
    return 0;
}