為什麼這篇巴斯卡三角形演算法鄉民發文收入到精華區：因為在巴斯卡三角形演算法這個討論話題中，有許多相關的文章在討論，這篇最有參考價值！作者skywillnosky (Alfred)看板C_and_CPP標題[問題] 關於組合的演算法....
如題
我想做出一個組合C(m,n)->(m取n m>n>0)的程式
由於要考慮溢位問題
所以一般用兩個正數變數做運算是不可行的
以下是我的想法
請各位看看可不可行
1.假設是C(100,40)
判定n 跟m-n 的大小
若是(m-n)<n 則m-n 取代n
反之n不變
2.依照組合公式
將分母與分子的乘數分別放入等長的陣列內
如:分母[0] = 100 分子[0] = 40
分母[1] = 99 分子[1] = 39
...
分母[39] = 61 分子[39] = 1
3.用分子逐一尋找可整除之分母數 達到消去的效果
如:分母[58] % 分子[0] = 0 // 80 % 40 = 0
分母[58] = 商
分子[0] = 1
當所有的分子都消一輪後
剩餘不等於1的分子
用最大公因數(遞迴的函數 在此省略)消掉
4.將沒被消掉的分母乘起來
乘的方式為:
1)創一個長度為100的整數陣列 ans[100]
2)將分母陣列一個個值依序乘並放入ans陣列
3)每當ans[n]裡的值>10就要將多的數字進位到ans[n+1]裡
目前遇到的問題:
步驟3(分子尋找合適的分母) 和 4
都還是會造成高時間複雜度
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 125.230.116.178
→ firejox:好三角形不用嗎？ 04/21 23:16
推 stupid0319:有看沒有懂,感覺原PO把他複雜化了 04/22 00:12
推 stupid0319:不考慮處理速度的話,直接大數乘除就好了 04/22 00:17
推 dio833:m如果不限制大小，不溢位很難，一個巨大的質數塞進去就爆了 04/22 00:19
→ dio833:原po的考量是否指的是盡量不溢位? 04/22 00:20
→ dio833:如不溢位是必要條件，可能如同s大說的，用大數運算比較妥 04/22 00:21
推 stupid0319:第3點還滿蝦的,因為一定可以找到分子*2的分母 04/22 00:30
→ stupid0319:跟本不用什麼最大公因數吧??完全看不懂= =" 04/22 00:31
→ stupid0319:是分子*N的分母,其實沒那麼高時間複雜度 04/22 00:34
推 dio833:分子*2的分母，不一定找得到喔!例如C10取3 04/22 00:36
→ blackwindy:你先訂出m跟n的值域再來討論吧... 04/22 00:37
→ blackwindy:印象中ACM寫過類似題 04/22 00:37
→ blackwindy:大多數的情況int64都可以直接搞定 04/22 00:38
推 EdisonX:你可以先對分子/分母進行質因式分解，如果先建立質數表, 04/22 00:59
→ EdisonX:效能會再往上拉一些。 04/22 00:59
→ loveme00835:之前有用double硬幹過, 分子分母一一配對結果先做出來 04/22 01:02
→ loveme00835:然後再逐個乘上去最後round成整數 04/22 01:03
推 bob123:原po問題應該是在於結果不溢位,但計算過程會溢位吧 04/22 03:48
→ bob123:其實1樓f大已經說了.. 用巴斯卡三角形來解 04/22 03:50
→ bob123:好用特性 C(m,n) = ΣC(k,n-1) , k=(n-1)...(m-1) 04/22 03:52
→ bob123:要加速的話就把某一層的結果都先算出來放在程式裡 04/22 03:54
→ skywillnosky:感謝解答=.= 原來帕斯卡就可以了... 04/27 20:51