有一家便當店生意很好,他們的特色是每一個便當內的配菜組合都不會跟當
天的另一個便當完全相同。這家店的秘訣是依靠一個能夠產生所有從{1, 2,
3, …, n}中取k 組合的程式。當設定好n 與k 值後,這個程式就會輸出C(n, k)
列,每一列都是以k 個數的遞增數列來表示一種k 組合,而這些k 組合又是依照
字典遞增順序(increasing lexicographic order)來產生,也就是說,在k
組合均以k 個數的遞增數列來表示的前提下,第1 個數越小的k 組合會越先產
生,若第1 個數一樣,則第2 個數越小的k 組合會越先產生,依此類推。假設便
當店當天的配菜共有n 種,每一種份量都很充足,且製作每一個便當均需放入k
種配菜,那麼便當店只要設定好程式的n 與k 值後,當天編號1 的便當就依程式
輸出第1列的k組合來配菜,編號2的便當就依程式輸出第2列的k組合來配菜,
依此規則,配菜組合自然就不會重複了。舉例來說,當n 為5,k 為3 時,便當
編號與配菜組合的對應如下:
便當編號 配菜組合
1 1 2 3
2 1 2 4
3 1 2 5
4 1 3 4
5 1 3 5
6 1 4 5
7 2 3 4
8 2 3 5
9 2 4 5
10 3 4 5
現在要請你寫一個目的有點不同的程式,當輸入便當店所有配菜種類數n、
每一便當所需配菜種類數k、與某一個{1, 2, 3, …, n}中取k 的配菜組合後,
你的程式要在第1 列輸出這個配菜組合對應的便當編號,並在第2 列輸出下一編
號(上面的編號加1)便當的配菜組合。萬一輸入的配菜組合已經是最後一種組
合,第1 列還是要先輸出對應的便當編號,而因為沒有下一編號的便當,第2
列只要輸出『no next combination』即可。
輸入範例1: 5 3 1 4 5 輸入範例2: 5 3 3 4 5
輸出範例1: 6 2 3 4 輸出範例2: 10 no next combination
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」
|