首页 > 代码库 > 数论 UVA 10943

数论 UVA 10943

这是一道关于组合数和隔板法的数论题目。题目说的是选出k个不同且不大于N的数字进行相加,要求这些数字之和等于N,结果要求输出这样的数有多少组。这里可以将问题利用隔板法来转换,那么题目的叙述可以转换成:这里有N个相同的小球,要求放到k个相同的盒子中,盒子可以为空,但一定要把所有球都放进盒子中,问共有多少种放法。经过题目描述的转换,这道题目就可以运用隔板法的公式:所有符合条件的情况的种数为c[N+k-1][k-1]。

由组合数的公式可得c[m][n]=c[m-1][n-1]+c[m-1][n]。由于这道题目的N、k的范围都在100以内,所以可以先打表再对应查找。

#include<stdio.h>
#include<string.h>
int c[200][200];
int main()
{
int i,j;
memset(c,0,sizeof(c));
for(i=0;i<200;i++)
c[i][0]=1;
for(i=1;i<200;i++)
for(j=1;j<=i;j++)
{
c[i][j]=(c[i-1][j]+c[i-1][j-1])%1000000;
}
int n,k;
while(scanf("%d%d",&n,&k)!=EOF)
{
if(n==0&&k==0)
break;
printf("%d\n",c[n+k-1][k-1]);
}
return 0;
}

数论 UVA 10943