盒子放球排列组合问题请教~
n个盒子,m个球,把m个球放到n个盒子中,盒子可以为空,列出所有可能排列组合~
如2个球放到3个盒子中
2 0 0
1 1 0
1 0 1
0 1 1
0 2 0
0 0 2
数学没学好，请教各位老大~谢谢的说,解决马上给分~
[解决办法]
问题可以转化成：求方程 x1+x2+x3+...+xn=m 的非负整数解的个数。
可以采用“挡板法”来解决。
记C(m,n)为n个中选m个的组合数。
求非负整数解，相当于在m个1中间插入n-1个0，这n-1个0将m个1分成了n部分，第i部分中的1的个数，就是xi对应的值。换个角度，上述一共有 m+n-1个元素（0或1），只要确定m个1的位置或者n-1个0的位置，就得到方程组的一个解。
于是解的个数为：C(m,m+n-1)。
[解决办法]
这其实是一个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>int *list;int n;void f( int len, int sum ){ int i; if( sum==0 ){ for( i=0; i<len; ++i ) std::cout<<list[i]<<" "; for( ; i<n; ++i ) std::cout<<0<<" "; std::cout<<std::endl; return; } if( len==n-1 ){ list[len]=sum; for( i=0; i<=len; ++i ) std::cout<<list[i]<<" "; std::cout<<std::endl; return; } for( i=0; i<=sum; ++i ){ list[len]=i; f( len+1, sum-i ); }};int main( ){ int m; std::cin>>m>>n; list=new int[n]; f( 0, m ); delete list; system("PAUSE"); return EXIT_SUCCESS;}