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