先看题目:Prime Solutions 以下是一段中學時代的慘痛回憶…每當學到排列組合的單元時,最痛苦的不是分析題目,也不是帶錯公式或計算錯誤,而是所謂的「苦工題」,以下這題是個例子:給定正整數N與S,求出方程式(1)的 ...
先看题目:
Prime Solutions
以下是一段中學時代的慘痛回憶…每當學到排列組合的單元時,最痛苦的不是分析題目,也不是帶錯公式或計算錯誤,而是所謂的「苦工題」,以下這題是個例子:
給定正整數N與S,求出方程式(1)的所有質數解(全為質數)。
遇到這題,通常只能硬著頭皮將每一組以「土法煉鋼」的方式一一列出,然而到了大學修過程式設計與演算法課,俾使我們能在電腦上撰寫程式輕鬆解決此問題。
INPUT
第一行一樣為測資個數
每一行輸入正整數與正整數,N與S之間相隔一個空白鍵。
(提示: 計算之前先考慮方程式有沒有解可以加速程式執行。)
OUTPUT
N個質數相加剛好等於S有哪些可能的組合,質數可以重複,但請由小到大排列,若無解(例如100個質數相加等於23無解)則輸出0,解可能不只一組,若有多組解時,靠左邊的數字較小的那組解則優先輸出,請參照SAMPLE OUTPUT。每一筆測資的輸出之間也換一行。
SAMPLE INPUT
4
2 5
100 23
3 8
4 25
SAMPLE OUTPUT
2 3
0
2 3 3
2 2 2 19
2 3 3 17
2 3 7 13
2 5 5 13
2 5 7 11
---------------分割线---------------
首先先来解释一下题目,首先input第一行的4是资料的笔数,之后的2 5代表 5以内的质数取2个相加等于5,5以内的质数有 2、3,2+3=5所以输出2 3。
本题主要考验的是质数的求解(简单)以及可重复排列数的实现(时间复杂度较大)
根据题目需要,可以大概得到这样一个流程:
关键的难点在于可重复排列数,其思路是设定一个标签来标记当前的位置,循环+递归。同时附加从大到小或者从小到大排列能够节省大量的运算时间。
下面来看代码:
1 /** 2 * @Title: getCombination 3 * @Description: 递归取得可重复排列数 4 * @throws 5 */ 6 private void getCombination(ArrayList<Integer> arr, int n, int begin, ArrayList<Integer> rs, int index) { 7 if (n == 0) { 8 rsList.add(rs); 9 return;10 }11 for (int i = 0; i < arr.size(); i++) {12 13 if (index == 0 || arr.get(i) >= rs.get(index - 1)) {14 rs.set(index, arr.get(i));15 getCombination(arr, n - 1, i + 1, clone(rs), index + 1);16 }17 }18 }
原标题:【每天一题ACM】可重复组合数的实现,求解素数解组合Prime Solutions
关键词:
*特别声明:以上内容来自于网络收集,著作权属原作者所有,如有侵权,请联系我们:
admin#shaoqun.com
(#换成@)。