求助：一个取球问题的算法，请各位高手指点一下。
我编写了一个程序，速度太慢，如果是40个球，有两个篮子都要计算好几个小时，希望各位有C/C++程序的能贴一个上来，多谢了。题目如下：
假如有N个球，要放入a个不同的篮子中，球必须全部放完，请问怎么求有几种放的方式（球不记先后顺序）。
即当有4个球，要放入3个篮子时，结果为
序号 第一个球所在的篮子号 第二个球所在的篮子号 第三个球... 第四个球...
0 1111 //四个球都在1号篮子里
1 2111 //2,3,4号球在1号篮子里，1号球在2号篮子里
2 1211 //1,3,4号球在1号篮子里，2号球在2号篮子里
3 1121
4 1112
5 2211
6 2121
7 2112
8 1221
9 1212
10 1122
11 2221
12 2212
13 2122
14 1222
15 2222
16 3111
17 3211
18 3121
19 3112
20 3221
21 3212
22 3122
23 3222
24 1311
25 2311
26 1321
27 1312
28 2321
29 2312
30 1322
31 2322
32 1131
33 2131
34 1231
35 1132
36 2231
37 2132
38 1232
39 2232
40 1113
41 2113
42 1213
43 1123
44 2213
45 2123
46 1223
47 2223
48 3311
49 3321
50 3312
51 3322
52 3131
53 3231
54 3132
55 3232
56 3113
57 3213
58 3123
59 3223
60 1331
61 2331
62 1332
63 2332
64 1313
65 2313
66 1323
67 2323
68 1133
69 2133
70 1233
71 2233
72 3331
73 3332
74 3313
75 3323
76 3133
77 3233
78 1333
79 2333
80 3333
问题点数：50、回复次数：21Top
1 楼spirit_sheng（老盛）回复于 2006-12-08 19:33:13 得分 0
首先, 你这做法就有问题, 既然球不分先后顺序, 那就不能象你这么做
你这种做法是球分先后顺序的, 如果还应分先后顺序, 则结果为 a^N
就向你上面这种做法, 3^4=81
Top
2 楼spirit_sheng（老盛）回复于 2006-12-08 19:40:46 得分 10
如果球不分先后顺序, 则结果为 C(a+N-1, a-1)
可以如下考虑, 将篮子和球沿一条直线排开, 每个篮子后面跟着放入其中的球, 篮子依序摆放
则每一种摆放方式与结果中的一种放入方式一一对应
由于第一个位置必须是第一个篮子, 所以种数为在剩下 a+N-1 个位置中, 挑a-1个位置放篮子, 其种数为 C(a+N-1, a-1)
Top
3 楼spirit_sheng（老盛）回复于 2006-12-08 19:42:43 得分 0
如果按你的理解, 则40个球, 两个篮子, 则结果一共有 2^40种, 当然要计算很长时间了
但如果是第二种, 则C(41,1)=41种Top
4 楼litaoye（）回复于 2006-12-08 23:35:36 得分 5
问题一：球是否有编号？如果没有编号，只是每个篮子里面球个数的问题，计算量要小很多。
问题二：篮子是否有编号，如果没有编号，计算量又会小很多。Top
5 楼spirit_sheng（老盛）回复于 2006-12-09 09:47:06 得分 0
其实题目说得已经很清楚了
一: "（球不记先后顺序）"
二: "放入a个不同的篮子中"Top
6 楼MagicPeng（彭彭）回复于 2006-12-09 12:22:55 得分 0
恩 排列 组合Top
7 楼lsh1000（）回复于 2006-12-09 12:34:22 得分 0
呵呵，多谢各位了。可能是我描述有问题，说的不是很清楚。
我这里做的是有编号的，即球是从1号-N号 ，篮子也是从1号-A号,遍历所有可能的结果。但是球必须要全部放完，即某一个球一定在某一个篮子里。
因为可能计算的数目比较大，我原来写的程序效率不是很高，想看看各位有没有好的方法能更快一些。
Top
8 楼lsh1000（）回复于 2006-12-09 12:52:44 得分 0
呵呵，多谢各位了。可能是我描述有问题，说的不是很清楚。
我这里做的是有编号的，即球是从1号-N号 ，篮子也是从1号-A号,遍历所有可能的结果。但是球必须要全部放完，即某一个球一定在某一个篮子里。
因为可能计算的数目比较大，我原来写的程序效率不是很高，想看看各位有没有好的方法能更快一些。
(还要考虑的：设立一个数组，记录每一个篮子的装球范围，也就是每一个篮子必须装I-J个球，即1号篮子必须装2-4个球，2号篮子必须装1-3个球，3号篮子必须装0-2个球......，对这种情况如何实现。)
有源代码的最好能贴一个上来。多谢了。
我原来想的是 对所有的球用递归的方法来进行深度优先遍历，每一个球必在1-A个篮子中，即对任一个球遍历1-A次。
（下面这个是没有设立装球范围数组的，如果要考虑每个篮子装球范围的需要怎么做）
即当有4个球，要放入3个篮子时，结果为
序号 第一个球所在的篮子号 第二个球所在的篮子号 第三个球... 第四个球...
0 1111 //四个球都在1号篮子里
1 2111 //2,3,4号球在1号篮子里，1号球在2号篮子里
2 1211 //1,3,4号球在1号篮子里，2号球在2号篮子里
3 1121
4 1112
5 2211
6 2121
7 2112
8 1221
9 1212
10 1122
11 2221
12 2212
13 2122
14 1222
15 2222
16 3111
17 3211
18 3121
19 3112
20 3221
21 3212
22 3122
23 3222
24 1311
25 2311
26 1321
27 1312
28 2321
29 2312
30 1322
31 2322
32 1131
33 2131
34 1231
35 1132
36 2231
37 2132
38 1232
39 2232
40 1113
41 2113
42 1213
43 1123
44 2213
45 2123
46 1223
47 2223
48 3311
49 3321
50 3312
51 3322
52 3131
53 3231
54 3132
55 3232
56 3113
57 3213
58 3123
59 3223
60 1331
61 2331
62 1332
63 2332
64 1313
65 2313
66 1323
67 2323
68 1133
69 2133
70 1233
71 2233
72 3331
73 3332
74 3313
75 3323
76 3133
77 3233
78 1333
79 2333
80 3333Top
9 楼spirit_sheng（老盛）回复于 2006-12-09 13:33:52 得分 0
首先楼主搞清楚, 是只要求出有多少种, 而是要列出每一种的情况
如果要列出每一种的情况, 而且球有分别, 例如, 对于40个球, 如果每个筐放20个球, 也有
C(40, 20)=137,846,528,820 如果要输出每种情况, 这么大的数量, 打印显然没意义, 如果是保存, 假设你最优的保存方式, 每个球用1个bit表示, 那每种结果需要40bit, 即5字节, 那你所有这些结果需要 137,846,528,820 * 5 Bytes 那需要 642 GBytes 的磁盘空间才能保存, 你认为这样的输出有意义吗?
如果只需要计算次数, 那就简单多了, 根据数学公式计算即可, 不需要象你这样遍历来解决问题Top
10 楼lsh1000（）回复于 2006-12-09 13:47:21 得分 0
呵呵，多谢各位的帮助。其实并不需要这么多的球，只需要计算10-15个球，篮子数目2-4个，但是必须要全部遍历所有的结果并且保存。
也不需要用bit来保存，使用一个INT型数组来存放一个遍历结果就可以了。
计算次数是可以根据数学公式，但是我需要列出所有的情况。
当然球数目和篮子数目是自己确定的，不需要设这么大的球数，但是我是想找一种方法来尽量提高效率，使计算尽可能快一些就行。
我需要简洁一些的代码，并且效率要高一些。
Top
11 楼nako_ruru（娜可露露）回复于 2006-12-09 22:37:44 得分 0
spirit_sheng(老盛) ，你並沒有考慮完善樓主的想法。
樓主的結果裡面是沒有空籃子的。在這種情況下該方法數應該為C(N - 1, a - 1)
Top
12 楼ctu_85（青灯照壁人初睡，冷雨敲窗被未温）回复于 2006-12-11 11:02:38 得分 0
其实答案很简单
结果是:
a exp (N)
对于本题来说就是3的4次方啊
不存在C(N - 1, a - 1)的结果Top
13 楼ctu_85（青灯照壁人初睡，冷雨敲窗被未温）回复于 2006-12-11 11:11:00 得分 5
这个题目的解答方法是:
设4个非负树x1,x2,x3,x4
求解sum=x1+x2+x3+x4的结果在4-16范围内所有可能的取值
答案是无意义的,因为本题不存在任何解答技巧问题
如果限制了蓝筐的容量为h,那么本题的结果可以归纳为对拥有h+1高度的N叉树(N为篮子数目)的形态结构问题
相信这个解答用Recrusive解决会很简单的Top
14 楼mathe（）回复于 2006-12-11 11:28:44 得分 30
其实就是将所有N位a进制数输出就可以了。
有很多种方法，其实本质上效率都差不多。
void output(int index, int x[]){
int i;
printf("%d\t",index);
for(i=0;i<N;i++)printf("%d",x[i]+1);
printf("\n");
}
int buf[N];
int index=0;
for(i=0;i<N;i++)buf[i]=0;
for(;;index++){
output(index,buf);
for(i=N-1;i>=0&&buf[i]==a-1;i--)buf[i]=0;
if(i<0)break;
buf[i]++;
}Top
15 楼zssxfc（）回复于 2006-12-11 13:28:02 得分 0
zzzzTop
16 楼vividw（vividw）回复于 2006-12-11 16:27:42 得分 0
同意 mathe() 直接生成结果 解空间映射Top
17 楼lsh1000（）回复于 2006-12-11 16:52:00 得分 0
这是我原来写的，使用了递归，效率不是太好。球越多，递归就越深。使用time函数检测了一次两个程序的时间开销,
debug: 我的是1485，mathe的是489
release:我的是318，mathe的是234
/////////////////////////////////////////////////////
struct MyData
{
INT nNumOfBall;
INT* pValue;
INT nNumOfBox;
};
INT DealData(MyData* pData)
{
static INT njishu = 0;
printf("%d\t",njishu++);
for (INT i=1; i<=pData->nNumOfBall;i++)
{
printf("%d",pData->pValue[i]);
}
printf("\n");
}
INT TraverseBox(MyData* pData, INT nCurBall)
{
for (INT i=1; i<=pData->nNumOfBox; i++)
{
pData->pValue[nCurBall] = i;
TraverseBall(pData,nCurBall+1);
}
return TRUE;
}
INT TraverseBall(MyData* pData, INT nCurBall)
{
if (nCurBall > pData->nNumOfBall)
{
DealData(pData);
return TRUE;
}
TraverseBox(pData,nCurBall);
return TRUE;
}
int main()
{
MyData data;
data.nNumOfBall = 10;
data.nNumOfBox = 3;
data.pValue = (INT*)malloc((data.nNumOfBall+1)*sizeof(INT));
if (NULL == data.pValue)
{
return 0;
}
memset(data.pValue,0,(data.nNumOfBall+1)*sizeof(INT));
TraverseBox(&data,1);
free(data.pValue);
return 0;
}Top
18 楼lsh1000（）回复于 2006-12-11 17:05:05 得分 0
多谢mathe了，你的方法很不错，代码也很简洁，而且还没有递归调用。呵呵，多谢了。Top
19 楼lsh1000（）回复于 2006-12-11 17:30:11 得分 0
多谢各位，结贴。呵呵，多谢了。Top
20 楼tdktdktdk（）回复于 2006-12-12 08:49:02 得分 0
用排列组合：Power(a,N-1)/N!Top
21 楼daidodo（火箭发射机）回复于 2006-12-12 09:57:15 得分 0
C(N + 1,a)Top
