你的位置:首页 > Java教程

[Java教程]【每天一题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所有数的和是否等于sum107   */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: isPrimeNumber130    * @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: sort144    * @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: 按照格式输出rs160   */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 }

 

 

欢迎指正!