[問題] 數學 組合的問題

看板C_and_CPP作者 (一生一世我愛你)時間14年前 (2010/01/20 13:24), 編輯推噓11(11推 0噓 17→)
留言28則, 10人參與, 最新討論串1/7 (看更多)
遇到的問題： (題意請描述清楚) 不知道該怎麼去寫這個程式 我想配的是，例如說我給五組字串 apple banana grape peach orange 然後我要組成 I love apple, banana, grape, peach, orange 這個是C5取5的情況 假設是C5取1就是 I love apple I love banana I love grape I love peach I love orange 變成五行 C5取2 = 10 I love apple, banana I love apple, grape I love apple, peach I love apple, orange I lvoe banana, grape I love banana, peach I love banana, orange I love grape, peach I love grape, orange I love peach, orange 有沒有什麼好的演算法可以去運算這個呢 印象中老師有教過dynamic programming可以處理這種問題 不過我一直都沒學會 囧 太混 希望得到的正確結果： 都在上面了，省略 程式跑出來的錯誤結果： 無 開發平台： (例: VC++ or gcc/g++ or Dev-C++, Windows or Linux) XP codeblock 有問題的code： (請善用置底文標色功能) QQ 我還不知道該怎麼寫 補充說明： 這不是作業，只是自己會用到的一個小程式XD -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.227.181.216
推
01/20 13:29, , 1F
看起來像是要不定數量的for?
01/20 13:29, 1F
→
01/20 13:46, , 2F
是的 很類似
01/20 13:46, 2F
推
01/20 13:48, , 3F
不重複的字典排序
01/20 13:48, 3F
QQ?
推
01/20 13:49, , 4F
不考慮順序的話, 當成一個5 bits的數從0跑到最大值, 第
01/20 13:49, 4F
→
01/20 13:49, , 5F
幾bit是1就印第幾個字串就好....XD
01/20 13:49, 5F
對不起小妹資質駑鈍 還望V大稍為解釋一下，感謝 ※ 編輯: l314520 來自: 61.227.181.216 (01/20 13:57)
推
01/20 13:58, , 6F
我順便解釋他的好了 首先先確定你的問題是否有排序問題
01/20 13:58, 6F
→
01/20 13:59, , 7F
ABCDE 五個英文字 前面的I LOVE基本上是墜字 不用管他
01/20 13:59, 7F
→
01/20 14:00, , 8F
如果不考慮排序 那就是5個BIT 0 0 0 0 0 ABCDE都不選
01/20 14:00, 8F
→
01/20 14:01, , 9F
一直+1 到11111 全選 如果取2 就是 選幾個
01/20 14:01, 9F
→
01/20 14:02, , 10F
假設 取二 會有 00011 00101 00110 01001 01010......
01/20 14:02, 10F
→
01/20 14:02, , 11F
不過這是沒有依照你上面給的OUTPUT輸出的順序
01/20 14:02, 11F
→
01/20 14:03, , 12F
如果要順序 我看到的直覺就是用字典排序解決
01/20 14:03, 12F
→
01/20 14:03, , 13F
關於字典排序你可以搜尋一下 不知道有沒有其他大大有更好
01/20 14:03, 13F
→
01/20 14:03, , 14F
的方法 小弟能力事實上有限XD
01/20 14:03, 14F
感謝您 我不需要排序@@ 不過如果能連排序的方法一起學是最好啦XD 多學一個總是好的:P ※ 編輯: l314520 來自: 61.227.181.216 (01/20 14:04) 現在在想要怎樣去implement這個bit的演算法 五個取兩個 如何去知道01001跟01010有沒有被選過呢? 會不會在印出結果上 出現重複印出資料的結果? 我最後的測資 如果印出重複的結果是沒什麼關係 不過還是希望可以越精簡越好 感謝 ※ 編輯: l314520 來自: 61.227.181.216 (01/20 14:08)
推
01/20 14:09, , 15F
不會印出重複的呀 00000 一直+1 到11111 如何會重複?
01/20 14:09, 15F
→
01/20 14:10, , 16F
如何拆解 就是 從0 ~2^5迴圈 並且驗證BIT
01/20 14:10, 16F
→
01/20 14:10, , 17F
驗證BIT的方法 可以用SHIFT 或者 %=2 /=2的方式
01/20 14:10, 17F
QQ 思考一下 有點轉不太過來 ※ 編輯: l314520 來自: 61.227.181.216 (01/20 14:12) 所以就是不斷的+1 +1 那麼只要bit 1的個數不是我麼要的(如C5取2 不是2bit) 就不取了嗎? 感覺如果測資夠大(例如C100取50)就會爆炸的感覺XD 是說我也不會用到這麼大的測資啦@@ 感謝您~~ ※ 編輯: l314520 來自: 61.227.181.216 (01/20 14:14)
推
01/20 14:23, , 18F
BIT的話會掛沒錯 2^100次 應該可以跑到世界末日
01/20 14:23, 18F
推
01/20 15:11, , 19F
http://0rz.tw/7KHeH 如果不是要自己實作的話 我會用這個
01/20 15:11, 19F
→
01/20 15:37, , 20F
小妹威能阿 好踴躍回覆阿
01/20 15:37, 20F
推
01/20 15:54, , 21F
DFS
01/20 15:54, 21F
推
01/20 16:29, , 22F
小弟我每次遇到排列組合就想到遞迴, 然後就不會寫XD
01/20 16:29, 22F
→
01/20 16:30, , 23F
遞迴只會解河內塔而已....Orz
01/20 16:30, 23F
推
01/20 17:59, , 24F
取組合的演算法在非遞迴方面,通常是以像算盤操作那樣思考...
01/20 17:59, 24F
→
01/20 18:00, , 25F
推得出來也不容易把方法記住
01/20 18:00, 25F
→
01/20 20:05, , 26F
next_permutation
01/20 20:05, 26F
推
01/21 09:20, , 27F
除了遞迴一途，也可以試試 iterative 的思路，
01/21 09:20, 27F
→
01/21 09:20, , 28F
這樣得到的結果就是 STL 的 next_permutation。
01/21 09:20, 28F
‣ 更多 l314520 的文章
文章代碼(AID): #1BLfEAe8 (C_and_CPP)
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 1 之 7 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共7篇)
‣ 更多 l314520 的文章
文章代碼(AID): #1BLfEAe8 (C_and_CPP)