放苹果:放苹果实例解答

问题描述:
把M个同样苹果放在N个同样盘子里允许有盘子空着不放问共有多少种区别分法？(用K表示)511和151 是同种分法

Input

第行是测试数据数目t(0 <= t <= 20)以下每行均包含 2个整数M和N以空格分开1<=MN<=10

Output

对输入每组数据M和N用行输出相应K

Sample Input

17 3Sample Output

8f(m,n)=f(m-n,n)+f(m,n-1)f(m,n)表示将m个苹果放到n个盘中思路方法数f(m-n,n)表示先拿n个苹果每个盘中放个,保证每个盘中都有苹果f(m,n-1)表示至少有个盘中没有苹果显然f(m,n)=f(n-m,n)+f(m,n-1);特殊情况考虑:若n>mf(m,n)=f(m,m);f(m,0)=0;f(m,1)=1;f(1,m)=1;

考虑不允许为空情况:

M个苹果放入N个盘中若M <N,0种MN1种情况M>N时我们这样考虑先将N个苹果放入N个盘中每个盘放个然后考虑将剩下M-N个苹果放入M-N个盘中允许为空即可

延伸阅读