【每天一题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。

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

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

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

下面来看代码：

 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     }
 1     /**
 2      * @Description: 得到质数表
 3      */
 4     private ArrayList<Integer> getAllPrimeNum(int num) {
 5         ArrayList<Integer> primeNums = new ArrayList<>();
 6         for (int i = 2; i <= num; i++) {
 7             if (isPrimeNumber(i))
 8                 primeNums.add(i);
 9         }
10         return primeNums;
11     }
 1     /**
 2      * @Title: isPrimeNumber
 3      * @Description: 判断是否是质数
 4      */
 5     public boolean isPrimeNumber(int number) {
 6         if (number <= 1)
 7             return false;
 8         for (int i = 2; i <= Math.sqrt(number); i++) {
 9             if (number % i == 0)
10                 return false;
11         }
12         return true;
13     }
 1     /** 
 2     * @Title: isEquals 
 3     * @Description: 判断arr所有数的和是否等于sum
 4     */
 5     public boolean isEquals(ArrayList<Integer> arr, int sum) {
 6         int temp = 0;
 7         for (int num : arr) {
 8             temp += num;
 9         }
10         return sum == temp;
11     }
 1 /**
 2      * @Title: sort
 3      * @Description: 无聊的排序而已，按照hashCode排序
 4      */
 5     public void sort(ArrayList<ArrayList<Integer>> rs) {
 6         for (int i = 0; i < rs.size(); i++) {
 7             for (int j = i + 1; j < rs.size(); j++) {
 8                 if (rs.get(i).hashCode() > rs.get(j).hashCode()) {
 9                     ArrayList<Integer> temp = rs.get(i);
10                     rs.set(i, rs.get(j));
11                     rs.set(j, temp);
12                 }
13             }
14         }
15     }
 1 /** 
 2     * @Title: primeSolution 
 3     * @Description: 程序主逻辑
 4     */
 5     public ArrayList<ArrayList<Integer>> primeSolution(int n, int num) {
 6         ArrayList<Integer> arr = getAllPrimeNum(num);
 7         ArrayList<Integer> temp = getAllPrimeNum(n);
 8         ArrayList<ArrayList<Integer>> okList = new ArrayList<>();
 9 
10         while (temp.size() < n) {
11             temp.add(0);
12         }
13         if ((!isHasResult(arr, num, n)) && n > arr.size())
14             return null;
15 
16         getCombination(arr, n, 0, temp, 0);
17         for (ArrayList<Integer> rs : rsList) {
18             if (isEquals(rs, num) && rs.size() == n) {
19                 okList.add(rs);
20             }
21         }
22         return okList;
23     }

完整代码如下：

  1 import java.util.ArrayList;
  2 import java.util.Scanner;
  3 
  4 /**
  5  * @author lcc 957109587@qq.com
  6  * @version 2016年3月9日 下午9:00:43
  7  * @Description
  8  */
  9 public class PrimeSolutions {
 10     static ArrayList<ArrayList<Integer>> rsList = new ArrayList<>();
 11 
 12     public static void main(String[] args) {
 13         @SuppressWarnings("resource")
 14         Scanner scan = new Scanner(System.in);
 15         ArrayList<ArrayList> okList = new ArrayList<>();
 16         PrimeSolutions primeSolutions = new PrimeSolutions();
 17         int runtimes = scan.nextInt();
 18         for (int i = 0; i < runtimes; i++) {
 19             int n = scan.nextInt();
 20             int num = scan.nextInt();
 21             okList.add(primeSolutions.primeSolution(n, num));
 22         }
 23         for (int j = 0; j < okList.size(); j++) {
 24             if (okList.get(j) == null) {
 25                 System.out.println(0);
 26             } else {
 27                 primeSolutions.outPut(okList.get(j));
 28             }
 29             if (j < okList.size() - 1) {
 30                 System.out.println();
 31             }
 32         }
 33     }
 34 
 35     /** 
 36     * @Title: primeSolution 
 37     * @Description: 程序主逻辑
 38     */
 39     public ArrayList<ArrayList<Integer>> primeSolution(int n, int num) {
 40         ArrayList<Integer> arr = getAllPrimeNum(num);
 41         ArrayList<Integer> temp = getAllPrimeNum(n);
 42         ArrayList<ArrayList<Integer>> okList = new ArrayList<>();
 43 
 44         while (temp.size() < n) {
 45             temp.add(0);
 46         }
 47         if ((!isHasResult(arr, num, n)) && n > arr.size())
 48             return null;
 49 
 50         getCombination(arr, n, 0, temp, 0);
 51         for (ArrayList<Integer> rs : rsList) {
 52             if (isEquals(rs, num) && rs.size() == n) {
 53                 okList.add(rs);
 54             }
 55         }
 56         return okList;
 57     }
 58 
 59     /** 
 60     * @Title: getCombination 
 61     * @Description: 递归取得可重复排列数
 62     * @throws 
 63     */
 64     private void getCombination(ArrayList<Integer> arr, int n, int begin, ArrayList<Integer> rs, int index) {
 65         if (n == 0) {
 66             rsList.add(rs);
 67             return;
 68         }
 69         for (int i = 0; i < arr.size(); i++) {
 70 
 71             if (index == 0 || arr.get(i) >= rs.get(index - 1)) {
 72                 rs.set(index, arr.get(i));
 73                 getCombination(arr, n - 1, i + 1, clone(rs), index + 1);
 74             }
 75         }
 76     }
 77 
 78     /** 
 79     * @Title: clone 
 80     * @Description: 深拷贝List
 81     */
 82     private ArrayList<Integer> clone(ArrayList<Integer> rs) {
 83         ArrayList<Integer> tocopy = new ArrayList<>();
 84         for (int num : rs) {
 85             int temp = num;
 86             tocopy.add(temp);
 87         }
 88         return tocopy;
 89     }
 90 
 91     /** 
 92     * @Title: isHasResult 
 93     * @Description: 判断是否有结果条件之一
 94     */
 95     public boolean isHasResult(ArrayList<Integer> arr, int num, int n) {
 96         for (int temp : arr) {
 97             if (temp * n == num) {
 98                 return true;
 99             }
100         }
101         return false;
102     }
103 
104     /** 
105     * @Title: isEquals 
106     * @Description: 判断arr所有数的和是否等于sum
107     */
108     public boolean isEquals(ArrayList<Integer> arr, int sum) {
109         int temp = 0;
110         for (int num : arr) {
111             temp += num;
112         }
113         return sum == temp;
114     }
115 
116     /**
117      * @Description: 得到质数表
118      */
119     private ArrayList<Integer> getAllPrimeNum(int num) {
120         ArrayList<Integer> primeNums = new ArrayList<>();
121         for (int i = 2; i <= num; i++) {
122             if (isPrimeNumber(i))
123                 primeNums.add(i);
124         }
125         return primeNums;
126     }
127 
128     /**
129      * @Title: isPrimeNumber
130      * @Description: 判断是否是质数
131      */
132     public boolean isPrimeNumber(int number) {
133         if (number <= 1)
134             return false;
135         for (int i = 2; i <= Math.sqrt(number); i++) {
136             if (number % i == 0)
137                 return false;
138         }
139         return true;
140     }
141 
142     /**
143      * @Title: sort
144      * @Description: 无聊的排序而已，按照hashCode排序
145      */
146     public void sort(ArrayList<ArrayList<Integer>> rs) {
147         for (int i = 0; i < rs.size(); i++) {
148             for (int j = i + 1; j < rs.size(); j++) {
149                 if (rs.get(i).hashCode() > rs.get(j).hashCode()) {
150                     ArrayList<Integer> temp = rs.get(i);
151                     rs.set(i, rs.get(j));
152                     rs.set(j, temp);
153                 }
154             }
155         }
156     }
157 
158     /**
159      * @Description: 按照格式输出rs
160      */
161     public void outPut(ArrayList<ArrayList<Integer>> rs) {
162         sort(rs);
163         for (int i = 0; i < rs.size(); i++) {
164             for (int temp : rs.get(i))
165                 System.out.print(temp + " ");
166             System.out.println();
167         }
168     }
169 }

欢迎指正！

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Linccy/p/5376331.html