今天在群里师兄发了一道公务员试题：4个球放入8个编号不同的盒子，每个盒子可放0－4个，则有几种放法？

我们可以进行推广，就是m个球放入n个编号不同的盒子，每个盒子可放0－m个，则有几种放法？

解题思路1：

用递归：

1个盒子,m个球:1种方法
2个盒子,m个球:分别有(0,m)   (1,m-1)   (2,m-2)...(4,0)   共m+1种方法

设n个盒子,m个球有f(n,m)种放置方法，现取第1个盒子的球数分别为0,1,2,.,i,..m   ,对于这m+1种情况中的第i种情况，有f(n-1,m-i)个含n-1个元素的字符串数组
全部拼起来即可

 

解题思路2：

/*这其实是一个n进制数的问题
假定存在一个m位的n进制数，他的k位上的数字表示第k个球所在盒子的编号，可以证明这个m位的n进制数和盒子的排列是一一对应的 我们知道，对于这种题目，可能的组合数为n^m，那么你只要把0- >n^m-1的数转换成n进制数，再检查对应的每位数既可知道每个球所在的盒子 所以唯一的难点就是整数转换成n进制数的问题，这个好像不是难题哦，学过计组的都应该知道除余法 也就是对于整数x,   x%n表示n进制数个位上的数字，要求更高位的数字，要用x=   x/n迭代*/

递归的程序实现：

#include <cstdlib>
#include <iostream>
using namespace std;
int   *a;
int   n;
int cnt =0;
void  f( int len, int sum ){
      int  i;
      if( sum==0 ){
          for( i=0; i<len; ++i )
               cout<<a[i]<<" ";
          for( ; i<n; ++i )
               cout<<0<<" ";
          cout<<endl;
    cnt++;
          return;
      }
      if( len==n-1 )
   {
          a[len]=sum;
          for( i=0; i<=len; ++i )
               cout<<a[i]<<" ";
          cout<<endl;
     cnt++;
          return;
      }
      for( i=0; i<=sum; ++i ){
           a[len]=i;
           f( len+1, sum-i );
      }
}

int main( )
{
    int  m;
   while(cin>>m>>n)
   {
 cnt = 0;
    a=new int[n];
    f( 0, m );
 cout<<cnt<<endl;
    delete a;
   }

    return 0;
}