Re: [問題] 關於C語言for寫法

看板C_and_CPP (C/C++)作者yauhh (喲)時間15年前 (2010/10/02 23:43)推噓14(14推 0噓 18→)

留言32則, 6人參與討論串1/1

※ 引述《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, , 1^F

10/02 23:53, 1^F

→

yauhh

10/02 23:59, , 2^F

10/02 23:59, 2^F

推

purpose

10/03 00:02, , 3^F

10/03 00:02, 3^F

推