ACM组合数学题解题思路总结

ACM组合数学题解题思路总结

这是一个渐进式的总结,随着我的理解的深入,会不断完善的。

1,找递推方程;

2,套组合数学成型的公式;

3,生成函数;

题目:m个相同的苹果放到n个相同的盘子里,允许有空盘子出现,问有多少种放法?

思路1 分析出这种递归结构:f(m, n) = f(m-n, n) + f(m, n-1),f(m, n)的意思是把m个苹果放到n个盘子里,允许有空盘子的放法数。

代码如下

思路2 套公式p(k, n)表示n个相同的物体的k拆分的方法数,要求每个拆分不能为空。

p(k, n) = p(r, n-k);

p(2, n) = [n/2];

p(1, n) = 1;

#include

int f(int m,int n)

{

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

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

if(m

else return f(m-n,n)+f(m,n-1);

}

int main()

{

int t=0;

int m,n;

scanf("%d", &t);

while(t--)

{

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

printf("%d\n", f(m, n));

}

return 0; }

相关推荐
相关主题
热门推荐