圣诞礼物

圣诞礼物

时间限制:1000MS 内存限制:65535K 提交次数:0 通过次数:0
语言: not limited
描述
圣诞节到了，圣诞老人给 N 个小朋友准备了 M 个同样的礼物。每个小朋友有一个袜子（袜子不编号，无区别，认为袜子都相同），圣诞老人将 M 个礼物装到 N 个袜子中的放法有多少种？
注意：
1）若M=7 N=3，那么5,1,1的放法和1,5,1的放法算是同一种装法。
2）允许袜子为空。
3）M和N无大小关系，M可以比N大，M也可以比N小。
输入格式
输入数据包含两个整数 M,N。1<=M,N<=50。
M在前，N在后，中间空格。
输出格式
输出共有几种不同的放法。
输入样例
7 3
输出样例

8

--------------------------------------------

9714  圣诞礼物                                     （递归、分治）

#include<stdio.h>

#include<malloc.h>

int q(int n,int m)

{

if((m<1)||(n<1)) return 0;

if((n==1)||(m==1)) return 1;

if(n<m) return q(n,n);

if(n==m) return q(n,m-1)+1;

return q(n,m-1)+q(n-m,m);

}

int main()

{

int n,m,sum=0,i;

scanf("%d %d",&n,&m);

for(i=1;i<=m;i++)

{

sum=+q(n,i);

}

printf("%d",sum);

}