你的位置:首页 > 软件开发 > Java > 【每天一题ACM】可重复组合数的实现,求解素数解组合Prime Solutions

【每天一题ACM】可重复组合数的实现,求解素数解组合Prime Solutions

发布时间:2016-04-10 23:00:12
先看题目:Prime Solutions 以下是一段中學時代的慘痛回憶…每當學到排列組合的單元時,最痛苦的不是分析題目,也不是帶錯公式或計算錯誤,而是所謂的「苦工題」,以下這題是個例子:給定正整數N與S,求出方程式(1)的 ...

【每天一题ACM】可重复组合数的实现,求解素数解组合Prime Solutions

先看题目:

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。

本题主要考验的是质数的求解(简单)以及可重复排列数的实现(时间复杂度较大)

根据题目需要,可以大概得到这样一个流程:

【每天一题ACM】可重复组合数的实现,求解素数解组合Prime Solutions

关键的难点在于可重复排列数,其思路是设定一个标签来标记当前的位置,循环+递归。同时附加从大到小或者从小到大排列能够节省大量的运算时间。

下面来看代码:

 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 (#换成@)。

可能感兴趣文章

我的浏览记录