编程题 :
有12组球,每组有编号为ABCD四个球. 任意球可记为 nX (1<=n<=12 ,X ={A B C D}).随机抽取7个球.问抽到结果中,存在7个不同组的球的可能性.6个呢? 进而(5,4,3,2个的可能性)?
解题思路:
应用 编程题 -- 分组问题,输出公式(一) 中的结果,计算 grouping 7 7 4 ;grouping 7 6 4 ....
得到:
7:
7*1
6:
5*1 + 1*2 ( 解释下这个结果,后面的就自然明了. 从5个组中各抽一个球且从另一个组中抽3个球 )
5:
4*1 + 1*3
3*1 + 2*2
4:
3*1 + 1*4
2*1 + 1*2 + 1*3
1*1 + 3*2
3:
2*2 + 1*3
1*1 + 2*3
1*1 + 1*2 + 1*4
2:
1*3 + 1*4
下示C(n,m)表示从n个数的集合中抽取m个数的子集的组合数计算. pow(x,y)表示x的y次方
从48个球中抽取7个的组合数为: total = C(48,7)
抽出来7个不同组的组合数为: c7=C(12,7)*pow(C(4,1),7)
抽出来6个不同组的组合数为: c6=C(12,1)*C(4,2)*C(11,5)*pow(C(4,1),5)
抽出来5个不同组的组合数为: c5=C(12,1)*C(4,3)*C(11,4)*pow(C(4,1),4) + C(12,3)*pow(C(4,1),3)*C(9,2)*pow(C(4,2),2)
抽出来4个不同组的组合数为: c4=C(12,1)*C(4,4)*C(11,3)*pow(C(4,1),3) + C(12,1)*C(4,2)*C(11,1)*C(4,3)*C(10,2)*pow(C(4,1),2) + C(12,1)*C(4,1)*C(11,3)*pow(C(4,2),3)
抽出来3个不同组的组合数为: c3=C(12,1)*C(4,3)*C(11,2)*pow(C(4,2),2) + C(12,1)*C(4,1)*C(11,2)*pow(C(4,3),2) + C(12,1)*C(4,1)*C(11,1)*C(4,2)*C(10,1)*C(4,4)
抽出来2个不同组的组合数为: c2=C(12,1)*C(4,3)*C(11,1)*C(4,4)
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #include "combination.h" typedef long (*Com)(long,long); Com C=combination; // 这个函数请自行网上找组合计算的实现. 这里不罗唆. int main(int argc,char** argv) { //long base=strtol(argv[1],NULL,10); //long select=strtol(argv[2],NULL,10); //printf("%ld %ld: %ld ",base,select,combination(base,select)); long total=combination(48,7); long c7=C(12,7)*pow(4,7); long c6=C(12,1)*C(4,2)*C(11,5)*pow(C(4,1),5); long c5=C(12,1)*C(4,3)*C(11,4)*pow(C(4,1),4) + C(12,3)*pow(C(4,1),3)*C(9,2)*pow(C(4,2),2); long c4=C(12,1)*C(4,4)*C(11,3)*pow(C(4,1),3) + C(12,1)*C(4,2)*C(11,1)*C(4,3)*C(10,2)*pow(C(4,1),2) + C(12,1)*C(4,1)*C(11,3)*pow(C(4,2),3); long c3=C(12,1)*C(4,3)*C(11,2)*pow(C(4,2),2) + C(12,1)*C(4,1)*C(11,2)*pow(C(4,3),2) + C(12,1)*C(4,1)*C(11,1)*C(4,2)*C(10,1)*C(4,4); long c2=C(12,1)*C(4,3)*C(11,1)*C(4,4); #define PRT(X) printf("%s : %ld : %.7lf%% ",#X,(X),((double)(X))/total*100); PRT(total); PRT(c7); PRT(c6); PRT(c5); PRT(c4); PRT(c3); PRT(c2); printf("add up : %ld ,total: %ld " ,c2+c3+c4+c5+c6+c7,total); return 1; }
输出结果:
total : 73629072 : 100.0000000%
c7 : 12976128 : 17.6236474%
c6 : 34062336 : 46.2620743%
c5 : 22302720 : 30.2906439%
c4 : 4118400 : 5.5934428%
c3 : 168960 : 0.2294746%
c2 : 528 : 0.0007171%
add up : 73629072 ,total: 73629072