2018年11月12日 星期一

Q441:Lotto

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=382


這題是利用回朔言算法來枚舉,排列出所有的可能組合,題目要求輸入一串數列,第一個數字(k)代表接下來後面會有幾個數字,最後就會從S1~Sk中取六個出來的所有組合。

在解這提前可以思考如何利用回朔法來將1 2 3 4 5這五個數字取三個出來的組合,答案如下,總共十個:
注意 1 2 3 和 1 3 2 是一樣的所以每個答案是要從小到大排列,請參考Main.java

1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5 


若沒有大小順序限制則要建立一個check[]陣列來檢查目前此數是否在答案中且不重複(程式碼請參考Main2.java)


題目要求由小至大所以我們拿第一個程式下去修改實做(參Q441:Lotto.java)