› 看板 C_and_CPP 關於我們 聯絡資訊
作者yauhh (喲)
看板C_and_CPP
標題Re: [問題] 關於C語言for寫法
時間Sat Oct 2 23:43:18 2010
※ 引述《lomokissyou ()》之銘言： : 輸出: : 012 013 023 123 : 上述程式的目標是列出所有{0,1,2,3}的3-subset : 問題是當我輸入turn =2時，如何寫才能動態決定for迴圈的數量 : 也這是說不管我的turn輸入為何 程式都能正確。 : 上述的程式碼在turn=2時就是錯的!應該只需要兩個for迴圈 : 我知道有一種解法是遞迴，不過礙於速度暫不考慮。 : 希望高手可以提示一下方向。感謝!! 你要的 n-subsets 也就是 n-combinations 的非遞迴方法,有很不錯的一種演算法. 我忘了什麼名字,暫且叫它為算珠取法. 例如,對以下二十個數字,用下面類似算盤算珠方式標記它的取出狀態: 12345678901234567890 ++++++-------------- 一開始取了最前面六個. 之後,第一步是先找到最右邊的一項,該項的右邊包含 其他未選擇項目. 以上例來看,是 6 號這一項. 我們把這一項 + 號一次一次向右移. ( 再說一次這個規則: 找到最右邊的一項,它的右邊包含未選擇項目,或者 包含其他已選擇但不符合本規則的其他項. 此原則的模式很明確,只是 在口語上比較不容易二,三句話講清楚. ) 12345678901234567890 +++++-+------------- 12345678901234567890 +++++--+------------ ... 幾次之後 ... 12345678901234567890 +++++--------------+ 這樣, "12345" 開頭的情況全都找到了. 接著下一步,回憶一下那個取下一選項的 規則: 找到最右的一項,其符合的原則是在右邊存在至少一個空位. 所以下一個找到 的是 5. 12345678901234567890 +++++--------------+ ^ 這個找法是用一個 while 迴圈,從右端向左找. 篩選條件想一下就明白了. 不過,現在要補充說明,在將選到的 + 號往右移動,每移一步都要做一個後續動作是: 把右邊的完全靠右的 + 號全部拉回來,靠到本項右邊. 回顧一下,當時挑選到 "6",由於它右邊沒有 + 號,所以什麼也沒做. 接下來,選到 "5" 的時候,下一步是二個動作: (1) "5" 的 + 號右移一次, (2) 移動後的 + 號右邊的 + 號全部拉回來. 所以下一步結果: 12345678901234567890 ++++-++------------- 所以,總而言之,珠子的右移規則是: 1. 選擇最右邊沒有完全靠右的珠子. 2. 將選到的珠子右移一格. 3. 將右移過的珠子右邊的珠子全都拉回,緊靠著本珠子. 下一步,用同樣的規則挑選,會挑到 "7". 所以下一個結果是這樣: 12345678901234567890 ++++-+-+------------ 算珠取法,好好享受吧! -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.231.69.221 ※ 編輯: yauhh 來自: 61.231.69.221 (10/02 23:47)
推 purpose:感覺不錯，好奇出處在哪 10/02 23:53
→ yauhh:某本離散數學課本,連書名我都忘了. 10/02 23:59
推 purpose:謝謝 10/03 00:02
推 lomokissyou:謝謝你喔!我研究一下。 10/03 00:05
推 loveme00835:這個比較好玩, 迴圈版寫不出來...( ￣ c￣)y▂ξ 10/03 00:20
推 lomokissyou:演算法懂了!感謝你的熱心~~不過我想不到怎麼把它變成 10/03 00:25
→ lomokissyou:function，也就是說FunctionName(input array,turn) 10/03 00:26
→ lomokissyou:turn 就是欲取出的長度組合，謝謝你。 10/03 00:27
推 purpose:先自己用文字整理一遍給你假想的好朋友威爾森看... 10/03 00:29
→ purpose:起碼想個半天再尋求幫助 10/03 00:29
推 lomokissyou:恩恩~好的!!我只是想說給原PO回應一下 感謝他的熱心 10/03 00:32
→ lomokissyou:話說威爾森是啥咪...聽不太懂!! 10/03 00:33
推 loveme00835:浩劫重生 10/03 00:33
→ lomokissyou:謝謝各位的幫忙~我剛剛寫了遞迴。最後還是用遞迴囉~ 10/03 01:50
→ lomokissyou:其實這個演算法就是我for迴圈的寫法.... 10/03 02:34
推 loveme00835:仔細一看好像真的是耶! @_@ 樓上好用心! 10/03 02:38
→ lomokissyou:http://codepad.org/1rUXd6Zv 不過還是謝謝原PO的幫忙 10/03 02:39
→ yauhh:假想的朋友命名為Watson比較酷 10/03 14:20
→ yauhh:我找出資料來源了,是Richard Johnsonbaugh的Discrete Mathe- 10/03 14:29
→ yauhh:matics, 5/e. 談到combination演算法的那一頁. 10/03 14:30
推 purpose:瞭解，有機會看看； 這演算法是有比較快，但還是遞迴寫起 10/04 00:46
→ purpose:來比較爽快 http://codepad.org/Xzb0kZch 10/04 00:46
推 purpose:剛剛才發現原PO問到自D了，呵呵，這社會真是垃圾 10/04 01:13
→ lomokissyou:自D有怎麼樣嗎?我最後選擇遞迴~問題解決了。把問題刪 10/04 09:02
→ lomokissyou:了，對大家比較好吧。 10/04 09:03
推 lomokissyou:不過你比較強，真的寫出來了。還是感謝你~雖然我用遞 10/04 09:40
→ lomokissyou:迴了。 10/04 09:40
推 lomokissyou:剛剛研究了P大的程式!!謝謝P大的教學~~我非遞迴部分寫 10/04 11:05
→ lomokissyou:很久都寫不出來。感謝你... 10/04 11:06
推 nowar100:本版不歡迎問到自D 謝謝 10/04 11:16
→ x000032001:問完就刪掉 簡直是浪費回答你的人的時間 10/04 21:24
→ lomokissyou:樓上說的很有道理!!各位抱歉囉~~下次不會了!!感謝~~ 10/04 22:41