2014NOIP普及组初赛 二、问题求解 1、把M个同样的球……
2015-10-20 15:11阅读：
2014NOIP普及组初赛 二、问题求解
1、把M个同样的球放到N个同样的袋子里，允许有的袋子空着不放，问共有多少种不同的放置方法？（用k表示）
例如：M=7，N=3时，K=8；在这里认为（5，1，1）和（1，5，1）是同一种放置方法。
问：M=8，N=5时，K= ？
刚看到这题时，就想到是组合数学问题，由于是填空题，就先采取笨办法，手工排同时去重。
囗 囗 囗
囗
囗
0 0 0
0 8
0 0 0
1 7
0 0 1
1 6
0 1 1
1 5
1 1 1
1 4
0 0 0
2 6
………………………
………………………
就这样细
心一点也能排出来，当然这个真是个很笨的办法。
如果要用程序来处理，该如何写呢？通过查询网络，发现这题就是跟放苹果的题目一样。
我用c++这样写，也可以的，代码如下：
#include< iostream>
#include< cstdio>
using namespace std;
int putBall(int,int );
int main()
{
int m,n,k;
cin>>m>>n;
k=putBall(m,n);
cout<<k;
return(0);
}
int putBall(int m,int n)
{
if(m<=1||n<=1) return 1;//如果球或袋子数小于等于1,只有一种摆放方式
//也是递归退出条件
if(m < n) return
putBall(m,n-1);//如果球比袋子少，慢慢拿掉袋子，直到退出
return putBall(m-n,n)+putBall(m,n-1);
//两种情况，先取出n个球一个袋子放一个球，再将剩下的m-n球放到n个袋子中。
// 还有一种情况就是至少一个袋子不放球，这样想当于f(m,n-1)
}
----------------------------------------------------------------------------------------------------------------
参考解释：
http://www.cnblogs.com/dongsheng/archive/2012/08/15/2640468.html
C语言:
01
21 #include
22
23 int
fun(int
m,int
n)
//m个苹果放在n个盘子中共有几种方法
24 {
25
if(m==0||n==1)
//因为我们总是让m>=n来求解的，所以m-n>=0,所以让m=0时候结束，如果改为m=1，
26
return 1;
//则可能出现m-n=0的情况从而不能得到正确解
27
if(n>m)
28
return
fun(m,m);
29 else
30
return
fun(m,n-1)+fun(m-n,n);
31 }
32
33 int
main()
34 {
35 int
T,m,n;
36
scanf('%d',&T);
37
while(T--)
38 {
39
scanf('%d%d',&m,&n);
40
printf('%d',fun(m,n));
41 }
42 }
