主题：[转帖]全国15亿人口中选1000个代表有多少种选法？
seawaycao
[专家分：3910] 发布于 2006-02-09 15:42:00
‘快速组合数C（N，K）=N*（N-1）*（N-2）*...*(N-K+1)/1*2*3*...*K 的求法：
Function ZDGYS(ByVal x As Long, ByVal y As Long) As Long 'GET Greatest Common Divisor最大公约数
Dim TEMP As Long
If x > y Then TEMP = x: x = y: y = TEMP 'LET X < Y
Do
TEMP = y Mod x
If TEMP = 0 Then ZDGYS = x: Exit Function
y = x
x = TEMP
Loop
End Function
Sub CALC(ByVal N As Long, ByVal K As Long, Optional ByRef CNK As String) '计算C（N，K），赋值给CNK
Dim XYS() As Integer, x() As Integer, y() As Integer, result() As String, i As Long, j As Long, T As Long, TEMP As Long, stimer As Double
If N < 0 Or N < K Then Exit Sub
stimer = Timer
If K = N Or K = 1 Then CNK = N: GoTo R '特殊情况
If N > 0 And K = 0 Then CNK = 1: GoTo R '特殊情况
If K > N - K Then K = N - K '减少计算量
Dim NN() As Long, NK() As Long
ReDim NN(1 To K)
ReDim NK(1 To K)
For i = 1 To K
NN(i) = N + 1 - i ' N*(N-1)*(N-2)*....*(N+1-K)
NK(i) = i ' 1*2*3*...*K
Next
For i = K To 1 Step -1
For j = 1 To K
TEMP = ZDGYS(NK(j), NN(i)) '最大公约数
If TEMP > 1 Then '消除分子分母
NN(i) = NN(i) / TEMP
NK(j) = NK(j) / TEMP
End If
Next
Next
ReDim x(1)
ReDim XYS(1)
x(1) = 1 '初始化数组
XYS(1) = 1
T = 1
Do While Not T > K
TEMP = Len(CStr(NN(T)))
ReDim y(1 To TEMP)
For i = 1 To TEMP
y(i) = Val(Mid(NN(T), TEMP + 1 - i, 1))
Next
ReDim XYS(1 To UBound(x) + UBound(y))
For i = 1 To UBound(x)
For j = 1 To UBound(y)
XYS(i + j - 1) = XYS(i + j - 1) + x(i) * y(j) '模拟乘法运算
Next
Next
For i = 1 To UBound(x) + UBound(y) - 1 '进位
TEMP = XYS(i) \ 10
XYS(i) = XYS(i) Mod 10
XYS(i + 1) = XYS(i + 1) + TEMP
Next
T = T + 1
x = XYS
If x(UBound(x)) = 0 Then ReDim Preserve x(1 To UBound(x) - 1) '第一位为零则去掉之
Loop
ReDim result(1 To UBound(x)) '逐位赋值
For i = 1 To UBound(x)
result(i) = x(UBound(x) + 1 - i)
Next
CNK = Join(result, "") '最后结果
R:
Debug.Print "C(" & N & "," & K & ")=" & CNK & vbCrLf & "用时 "; Timer - stimer & " 秒, 结果大约为 " & Val(Left(CNK, 3)) / 100 & "* 10^" & Len(CNK) - 1
Erase x() '释放
Erase y()
Erase XYS()
Erase result()
Erase NN()
Erase NK()
End Sub
Private Sub Command1_Click()
CALC 1500000000, 1000
End Sub
回复列表 （共16个回复）
沙发
seawaycao [专家分：3910] 发布于 2006-02-09 15:45:00
C(1500000000,1000)=30652804367164696580061245618584644612627630767867968160482287207505578854118075767413733341865113545827821943234215925381601476838491502713562101051308121811886256344264074095500443454498544782873527381232953591608839778443126863125303594776637408010065945137971003022970106087272779912095118673993148835415545404803408210359936057541641298321398866367630909780954427950260602677841356572015384593028076391922880188863454695625613158555189739103273043693186054292522757402389201949262458783982625369769215639665513120651343627077305247225448215405511745177315577297307995592278944000912129608635572003811892730638646576505559665098287067901804492021447447275828527448463319437263974332506979369648426322521012083011115417734792185803613847776098673007574058102010392545564626748974852860654213922561671313738154819315936146389699558632939168101222776477404052002491162770708016843923192174292119830692530203631071406591557820008413480936874626325481432195805380233658534174129959183937867662826991079111
338507834850334729288527369247878587832565479208744508778338876845312482987364108498465104568456246126301664867675212989415452257963231582428804132453530623562038287815118381775031194128075371634249125005163175363459748867914155909874673736671257895290315504998299550045865237426434834900678181142251825976824066859247763393966728415101293183767884565520685140354199404573267540148178613083039288640368764932196092260612808432688740318168177149884264936965681432808552602506769960231167314402042115391322928445848804527619718942273029739119754679079466440615744683934345683854846607341007539932315717364854225714347670890166770915776776243078592968724832489687527728645194872553456998869305207865806227228240462763947538604009461323117527793289745018918680050158833377256878342226038335968075073066708948751926064101932688708070972742976746669773522500626362218897275189840528789502160913361730351366579932326949751303046239529917281431024867799141200833929055039117446235095261319287039924501955885408786864766666179804050
926238297570352362160646695473979572080274723182393467252406938755835973585538888233140836639673055810280530161047565105056191259402557546062663149807820850721607832667883835853491798687285433469973723070029887151224892374554667132810263246741920398381560995586116435336668086735996210380651185950181222288773122498950468782425732304340361291059389453644565588619918495101003681448457650276701709851748681473864319718504684039251604015610508150552147153808743465905683130916303237016638713958685021075266783472002051065502419194601235929294444041936017137491251351327293306795207718070253412158539452418227263212189992863000083749471357436062471359873115691304279442807157134670115889000449540459077189604149293330863116234937585596100863199359470190862668063710752295922314349843213145637598520454977206161737311181275038945492592107963547180908095567677268276647414212537107884627846628529110671588643375513826567593228681751623648914212833098504187516701899089836341651632877201830938439864542029138356501030414803306920
447442494403172023855874827652475829549179429277923966103280437285008533655739559815237810160800404271399529345607321632407618302218506087747281711816275952385300123419119651812539626008479518803800204241415723861161475364403266589079446760547415461785658842813934872809441606838372946069290650323137211372623387643292062185604875098174848114827946543780012495836176514887528611865682171001390146194237358933818961231577169742945244631925175731309409301203657814823561195573417039611685481744639624779650478031797010310193910143720654230005835120916672556896141697397124339430683527827346088199310425977296050580090894283395562704660146243992392610035169484756111583491872862842868457498966835895427651725999857936637086391945848855014479550565464117387609584985877716361649333274656753939030226599302839809864418684901638821616862306126650440096166767836408098656108833121089444398772930568736130647757518593668394884786266077836647532339577756373420434996413495897686581823977660804033665502785475102224252209292029993611
973111630567923202130236172993790468519068097560331447667156754481552389915055679452243901867070960504820067533077519253044934814738418475323276577651573117613929110679583241598821342133286854135114641836617103340959538580141766352964056130377868411677064134191963547647821092141752214130376514371154199597115096013123251962105435209793277590292746117930770158363984816437578188877646885535829840139260790187239964576753133879602246222195440414904360290591431920697858688941168252075913192849124095823735035610688810536296984397392576312316030466020230922735495213642465325908670489533147544350504927145825552336844598901731352703951202001682805822762181488084037210852553303240934860684452020661409138404483324127416350569013971093174139044447543969011785964836991820774313345242843531533310366839217358944686766837116322982077976549965011772397935089695854830829802125669887971805854020389536518536720768528446163580336019777554816562078402481584088674520715956235635211663382724625917579085260675573363716833815966503860
993811980475311411632351682411636284449523363102094638794683659899605243052500175768769099173718367066781811361348638425178173533659503191787287397210467403797148018620943140078863571236739256270024107992839957976629695925235827394515603914164183723922107475389399917198511707432424313798630024979383132858351486262556758911527206975222453347937597508581111638702889231077175618142416071510061074549357572130933606480227128227922241716100276558744960483990492564330618193933962874467321168691702843418522393313197859657767931876154079079628597519811667958999436727218235364130406291499386395626751121774249109113139023137242731007972509781943833703136500894934240004229538784683585221465034084172567082331416819337218490736760012020257897928012089371742387533535843560376935269710997788468956524236901127076130233737094320642223543634031712270479693894837408024549625851428164388516669349329127033123394379811722300561676344810618825484416094886382203022666376818249128029887498208543129659288646346274769309292407404574993
6608908558954975144280515042437103513526943923346637991231240111666845924976878803784724718010351062368178879274540425781148703984672314559414795767769357321073222899722903734370283198049596503724417629404981774693732136715506926958567040649893166041510601704826598030208663351081485700207580107291827140144496139095464493330834978911758605670606624144954404663833872654567200762263525195723339349006395584852284826376552648716276636192737185771244752744819887086709751962025613217186000000
用时 9.03125 秒, 结果大约为 3.06* 10^6608
3 楼
zaqwedc [专家分：280] 发布于 2006-02-10 11:09:00
能不能说一下你的设计思路？
4 楼
seawaycao [专家分：3910] 发布于 2006-02-10 11:22:00
我是转的别人的帖子哦……大家可以一起研究一下！！
5 楼
凡尘 [专家分：9680] 发布于 2006-02-10 15:09:00
C(1500000000,1000)用时 7.35962499999732 秒, 结果大约为 3.06* 10^6608
6 楼
seawaycao [专家分：3910] 发布于 2006-02-10 18:59:00
结果的运行时间和机器的配置及系统的环境有关系哦……
7 楼
boxertony [专家分：23030] 发布于 2006-02-10 19:41:00
楼主所贴程序的大致思路如下：
1。分别把1,2,...,k和N,N-1,...,N-k+1赋给两个数组
2。用一个二重循环对两个数组的所有元素相互之间求最大公约数并抵消掉，那么最终的结果是把数组1（1，2，...,k）消除（因为结果必然是整数，肯定可以抵消掉）
3。对剩下的第二个数组的k个整数求积
这样做的好处是可以抵消掉一个数组，然后就可以免除做大数的除法运算。
8 楼
zaqwedc [专家分：280] 发布于 2006-02-10 21:01:00
本贴中大数乘法运算大概解释：
1.
For i = 1 To TEMP
y(i) = Val(Mid(NN(T), TEMP + 1 - i, 1))
Next
将NN()数组中的一个值赋予到y()数组中，具体过程是：将数值中的每一个数拆分成单独的字符串，并反向（算法要求如此）将其赋予到y()数组中。
2.
For i = 1 To UBound(x)
For j = 1 To UBound(y)
XYS(i + j - 1) = XYS(i + j - 1) + x(i) * y(j) '模拟乘法运算
Next
Next
用数组模拟计算两个数相乘（x()*y()），在第一次循环中x()模拟的值是1，在以后的循环中x()的作用是保存乘积结果并将结果作为乘数乘以y()。x()乘y()的结果为XYS()，但不是最终结果，因为还没有作进位和反向处理。
举个例子：x()中的数为9、9、9 y()中的数也为9、9、9，则XYS()中的数据为81、162、243、162、81
3.
For i = 1 To UBound(x) + UBound(y) - 1 '进位
TEMP = XYS(i) \ 10
XYS(i) = XYS(i) Mod 10
XYS(i + 1) = XYS(i + 1) + TEMP
Next
作了进位处理后，结果大体上是出来了，但因为y()的值是反向录入，所以XYS()的值也是反向的。
比如XYS()的值是81、162、243、162、81，则进位处理后为XYS(1)＝1，XYS(2)＝0，XYS(3)＝0，XYS(4)＝8，XYS(5)＝9，XYS(6)＝9，实际值：998001
4.
For i = 1 To UBound(x)
result(i) = x(UBound(x) + 1 - i)
Next
作了反向处理后result()就是结果
这个用数组模拟计算两个数相乘的算法还真是妙，以前也想作一个的，但没成功。
9 楼
boxertony [专家分：23030] 发布于 2006-02-11 20:12:00
其实消除k!可以不用二重循环，一重循环即可解决。如下：
For i = K To 2 Step -1
NN（(N MOD I)+1) = NN（(N MOD I)+1) / I
Next
也就是说树祖NK可以不要。
注：本人不会BASIC,所以程序如果语法不对请自己纠正
N MOD I表示 求N除以I的余数
10 楼
mxalbert1996 [专家分：780] 发布于 2006-02-11 20:36:00
C(1500000000,1000)=30652804367164696580061245618584644612627630767867968160482287207505578854118075767413733341865113545827821943234215925381601476838491502713562101051308121811886256344264074095500443454498544782873527381232953591608839778443126863125303594776637408010065945137971003022970106087272779912095118673993148835415545404803408210359936057541641298321398866367630909780954427950260602677841356572015384593028076391922880188863454695625613158555189739103273043693186054292522757402389201949262458783982625369769215639665513120651343627077305247225448215405511745177315577297307995592278944000912129608635572003811892730638646576505559665098287067901804492021447447275828527448463319437263974332506979369648426322521012083011115417734792185803613847776098673007574058102010392545564626748974852860654213922561671313738154819315936146389699558632939168101222776477404052002491162770708016843923192174292119830692530203631071406591557820008413480936874626325481432195805380233658534174129959183937867662826991079111
338507834850334729288527369247878587832565479208744508778338876845312482987364108498465104568456246126301664867675212989415452257963231582428804132453530623562038287815118381775031194128075371634249125005163175363459748867914155909874673736671257895290315504998299550045865237426434834900678181142251825976824066859247763393966728415101293183767884565520685140354199404573267540148178613083039288640368764932196092260612808432688740318168177149884264936965681432808552602506769960231167314402042115391322928445848804527619718942273029739119754679079466440615744683934345683854846607341007539932315717364854225714347670890166770915776776243078592968724832489687527728645194872553456998869305207865806227228240462763947538604009461323117527793289745018918680050158833377256878342226038335968075073066708948751926064101932688708070972742976746669773522500626362218897275189840528789502160913361730351366579932326949751303046239529917281431024867799141200833929055039117446235095261319287039924501955885408786864766666179804050
926238297570352362160646695473979572080274723182393467252406938755835973585538888233140836639673055810280530161047565105056191259402557546062663149807820850721607832667883835853491798687285433469973723070029887151224892374554667132810263246741920398381560995586116435336668086735996210380651185950181222288773122498950468782425732304340361291059389453644565588619918495101003681448457650276701709851748681473864319718504684039251604015610508150552147153808743465905683130916303237016638713958685021075266783472002051065502419194601235929294444041936017137491251351327293306795207718070253412158539452418227263212189992863000083749471357436062471359873115691304279442807157134670115889000449540459077189604149293330863116234937585596100863199359470190862668063710752295922314349843213145637598520454977206161737311181275038945492592107963547180908095567677268276647414212537107884627846628529110671588643375513826567593228681751623648914212833098504187516701899089836341651632877201830938439864542029138356501030414803306920
447442494403172023855874827652475829549179429277923966103280437285008533655739559815237810160800404271399529345607321632407618302218506087747281711816275952385300123419119651812539626008479518803800204241415723861161475364403266589079446760547415461785658842813934872809441606838372946069290650323137211372623387643292062185604875098174848114827946543780012495836176514887528611865682171001390146194237358933818961231577169742945244631925175731309409301203657814823561195573417039611685481744639624779650478031797010310193910143720654230005835120916672556896141697397124339430683527827346088199310425977296050580090894283395562704660146243992392610035169484756111583491872862842868457498966835895427651725999857936637086391945848855014479550565464117387609584985877716361649333274656753939030226599302839809864418684901638821616862306126650440096166767836408098656108833121089444398772930568736130647757518593668394884786266077836647532339577756373420434996413495897686581823977660804033665502785475102224252209292029993611
973111630567923202130236172993790468519068097560331447667156754481552389915055679452243901867070960504820067533077519253044934814738418475323276577651573117613929110679583241598821342133286854135114641836617103340959538580141766352964056130377868411677064134191963547647821092141752214130376514371154199597115096013123251962105435209793277590292746117930770158363984816437578188877646885535829840139260790187239964576753133879602246222195440414904360290591431920697858688941168252075913192849124095823735035610688810536296984397392576312316030466020230922735495213642465325908670489533147544350504927145825552336844598901731352703951202001682805822762181488084037210852553303240934860684452020661409138404483324127416350569013971093174139044447543969011785964836991820774313345242843531533310366839217358944686766837116322982077976549965011772397935089695854830829802125669887971805854020389536518536720768528446163580336019777554816562078402481584088674520715956235635211663382724625917579085260675573363716833815966503860
993811980475311411632351682411636284449523363102094638794683659899605243052500175768769099173718367066781811361348638425178173533659503191787287397210467403797148018620943140078863571236739256270024107992839957976629695925235827394515603914164183723922107475389399917198511707432424313798630024979383132858351486262556758911527206975222453347937597508581111638702889231077175618142416071510061074549357572130933606480227128227922241716100276558744960483990492564330618193933962874467321168691702843418522393313197859657767931876154079079628597519811667958999436727218235364130406291499386395626751121774249109113139023137242731007972509781943833703136500894934240004229538784683585221465034084172567082331416819337218490736760012020257897928012089371742387533535843560376935269710997788468956524236901127076130233737094320642223543634031712270479693894837408024549625851428164388516669349329127033123394379811722300561676344810618825484416094886382203022666376818249128029887498208543129659288646346274769309292407404574993
6608908558954975144280515042437103513526943923346637991231240111666845924976878803784724718010351062368178879274540425781148703984672314559414795767769357321073222899722903734370283198049596503724417629404981774693732136715506926958567040649893166041510601704826598030208663351081485700207580107291827140144496139095464493330834978911758605670606624144954404663833872654567200762263525195723339349006395584852284826376552648716276636192737185771244752744819887086709751962025613217186000000
用时 12.8904374999984 秒, 结果大约为 3.06* 10^6608
我的机子运行速度好像有点慢~~
我来回复
您所在位置：