[問題] 關於組合的演算法...(考慮溢位)
看板C_and_CPP (C/C++)作者skywillnosky (Alfred)時間14年前 (2012/04/21 22:27)推噓7(7推 0噓 15→)留言22則, 8人參與討論串1/2 (看更多)
如題
我想做出一個組合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
→
04/21 23:16, , 1F
04/21 23:16, 1F
推
04/22 00:12, , 2F
04/22 00:12, 2F
推
04/22 00:17, , 3F
04/22 00:17, 3F
推
04/22 00:19, , 4F
04/22 00:19, 4F
→
04/22 00:20, , 5F
04/22 00:20, 5F
→
04/22 00:21, , 6F
04/22 00:21, 6F
推
04/22 00:30, , 7F
04/22 00:30, 7F
→
04/22 00:31, , 8F
04/22 00:31, 8F
→
04/22 00:34, , 9F
04/22 00:34, 9F
推
04/22 00:36, , 10F
04/22 00:36, 10F
→
04/22 00:37, , 11F
04/22 00:37, 11F
→
04/22 00:37, , 12F
04/22 00:37, 12F
→
04/22 00:38, , 13F
04/22 00:38, 13F
推
04/22 00:59, , 14F
04/22 00:59, 14F
→
04/22 00:59, , 15F
04/22 00:59, 15F
→
04/22 01:02, , 16F
04/22 01:02, 16F
→
04/22 01:03, , 17F
04/22 01:03, 17F
推
04/22 03:48, , 18F
04/22 03:48, 18F
→
04/22 03:50, , 19F
04/22 03:50, 19F
→
04/22 03:52, , 20F
04/22 03:52, 20F
→
04/22 03:54, , 21F
04/22 03:54, 21F
→
04/27 20:51, , 22F
04/27 20:51, 22F
討論串 (同標題文章)
完整討論串 (本文為第 1 之 2 篇)：
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
