首页 > 代码库 > 数论 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。