整數的分劃問題

整數的分劃問題。

如，對於正整數n=6，可以分劃為：

6

5+1

4+2,   4+1+1

3+3,   3+2+1,  3+1+1+1

2+2+2, 2+2+1+1, 2+1+1+1+1

1+1+1+1+1+1+1

現在的問題是，對於給定的正整數n,編寫算法打印所有劃分。

用戶從鍵盤輸入 n （範圍1~10）

程序輸出該整數的所有劃分。

今天花了差不多一天的時間用java把這個整數劃分問題解决了，思路很清晰，邏輯卻有點複雜哦

基本思路是：使用棧結構，從後邊向前邊推，把每一次分解出的數放到一個動態數組ArrayList中，然後根據動態數組中的數產生一個輸出字符串，並放到棧裏面，當然，逗號，換行也在適當時候放到棧裏，然後就是輸出了，說也沒怎麼說清楚，就看代碼吧，看了可能會更糊塗，不過花點時間還是可以理解的

package com.challenge; import java.util.ArrayList; import java.util.Scanner; import java.util.Stack; public class Design2 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String str="請輸入你要劃分的整數："; while(true){ try{ System.out.print("/n"+str); int n=sc.nextInt(); if(n<=0||n>50){ str="請輸入【1,50】之間的整數："; continue; } print(n); str="請輸入你要劃分的整數："; }catch(Exception e){ str="輸入格式錯誤，請重新輸入:"; sc.next(); } } } public static void print(int n) { String str = "1"; // n個一相加 for (int j = 1; j < n; j++) { str = str + "+" + 1; } // System.out.println(str); Stack<String> stack = new Stack<String>(); stack.push(str); int temp = 0; ArrayList<String> strs = new ArrayList<String>(); String[] nums = depart(str); for (int i = 0; i < nums.length; i++) { strs.add(nums[i]); } while (!strs.get(0).equals(n + "")) { int index = strs.indexOf("1");// 第一個出現的比特置 int size = strs.size();// 字符串的長度 if (index > 0) {// 第一個操作數不是1 if (index != size - 1) {// 第一個1出現比特置的後面還有1 // // temp = Integer.parseInt(strs.get(index))+ // Integer.parseInt(strs.get(index-1)); // 操作數减少 strs.add(index, "2"); strs.remove(strs.size() - 1); strs.remove(strs.size() - 1); // 產生要輸出字符串 str = combo(strs); // System.out.println(str); stack.push(","); stack.push(str); } else { // 當前數和他前面的數相加 temp = Integer.parseInt(strs.get(index)) + Integer.parseInt(strs.get(index - 1)); // 如果當前數1和前一個數相加的和大於第一個數，換行 if (temp > Integer.parseInt(strs.get(0))) { temp = Integer.parseInt(strs.get(0)) + 1; strs.clear(); str = temp + ""; strs.add(temp + ""); for (int i = 1; i <= n - temp; i++) { str = str + "+" + 1; strs.add(1 + ""); } stack.push("/n"); stack.push(str); } else if (temp > Integer.parseInt(strs.get(index - 2))) { // 如果當前操作數和前面的操作數的和大於他前面的操作數，temp放第二比特 strs.add(1, temp + ""); // strs.remove(strs.size() - 1); strs.remove(strs.size() - 1); // 重構要輸出的字符串 str = combo(strs); stack.push(","); stack.push(str); } else { // temp小於等於他前面的操作數 strs.add(index - 1, temp + ""); strs.remove(strs.size() - 1); strs.remove(strs.size() - 1); str = combo(strs); stack.push(","); stack.push(str); } } } else if (index == 0) { if (strs.size() > 2) {// 開始時，操作數都為1 strs.add(0, "2"); strs.remove(strs.size() - 1); strs.remove(strs.size() - 1); str = combo(strs); stack.push("/n"); stack.push(str); } else {// 為2，只可分解為1+1 str = 2 + ""; strs.add(0, "2"); stack.push("/n"); stack.push(str); } } else {// index<0,沒有1 if (strs.size() == 2) { temp = Integer.parseInt(strs.get(0)) + 1; str = temp + ""; strs.clear(); strs.add(temp + ""); for (int i = 1; i <= n - temp; i++) { str = str + "+" + 1; strs.add(1 + ""); } stack.push("/n"); stack.push(str); } else{// if (strs.size() >= 3) temp = Integer.parseInt(strs.get(1)) + 1; if (temp <= Integer.parseInt(strs.get(0))) { // strs.remove(1); strs.add(1, temp + ""); // ; temp = Integer.parseInt(strs.get(strs.size() - 1)) - 1; if (temp > 0) { strs.add(strs.size() - 1, temp + ""); } strs.remove(strs.size() - 1); str = combo(strs); stack.push(","); stack.push(str); } else { temp = Integer.parseInt(strs.get(0)) + 1; str = temp + ""; strs.clear(); strs.add(temp + ""); for (int i = 1; i <= n - temp; i++) { str = str + "+" + 1; strs.add(1 + ""); } stack.push("/n"); stack.push(str); } // } // if(strs.size()) } } } while (!stack.empty()) { System.out.print(stack.pop()); } } public static String[] depart(String str) { return str.split("[+]"); } public static String combo(ArrayList<String> ars) { if (ars.size() <= 0) return null; String str = ars.get(0); for (int i = 1; i < ars.size(); i++) { str = str + "+" + ars.get(i); } return str; } }
程序運行效果如下：
請輸入你要劃分的整數：60

請輸入【1,50】之間的整數：50
請輸入你要劃分的整數：10
10
9+1
8+2,8+1+1
7+3,7+2+1,7+1+1+1
6+4,6+3+1,6+2+2,6+2+1+1,6+1+1+1+1
5+5,5+4+1,5+3+2,5+2+2+1,5+2+1+1+1,5+1+1+1+1+1
4+4+2,4+3+3,4+3+2+1,4+2+2+2,4+2+2+1+1,4+2+1+1+1+1,4+1+1+1+1+1+1
3+3+2+2,3+2+2+2+1,3+2+2+1+1+1,3+2+1+1+1+1+1,3+1+1+1+1+1+1+1
2+2+2+2+2,2+2+2+2+1+1,2+2+2+1+1+1+1,2+2+1+1+1+1+1+1,2+1+1+1+1+1+1+1+1
1+1+1+1+1+1+1+1+1+1
請輸入你要劃分的整數：