拆解数字

是的。

/**
* 递归，将上一个数字拆解的情况做一个二维数字
比喻3=2+1=2+1+1 可以存储为int[][] arr
arr[0]={3]
arr[1]={2，1}
arr[2]={1，1，1}

* @author peter.e.king
*
*/
public class SplitNumber {
public static void splitNumber(int x){
if(x<1){
System.out.println("请输入自然数！");
} else if (x==1){
System.out.println("数字『1』可以分解成的组合数为："+1);
System.out.println("数字『1』可以分解成的表达式为：1");
}else {
StringBuffer  showStr = new StringBuffer("1");
for(int i=2;i<=x;i++){
getByPreArr(showStr);
}
System.out.println("数字『"+x+"』可以分解成的组合数为："+showStr.toString().split("=").length);
System.out.println("数字『"+x+"』可以分解成的表达式为："+showStr.toString());
}
}

/**
* 根据上一级的表达式得到当前表单式
* @param preString 上一级表达式
*/
public static void getByPreArr(StringBuffer preString){
String [] pre1Arr =preString.toString().split("=");
preString.delete(0, preString.length());
for(int i=0,len=pre1Arr.length;i<len;i++) {
String[] pre2Arr = pre1Arr[i].split("[+]");
int point=0;//出现的位置
for(int j=0,len2=pre2Arr.length;j<len2;j++) {
int temp = Integer.parseInt(pre2Arr[j]);
String pString = pre1Arr[i].substring(0,point);
String nString = pre1Arr[i].substring(point+pre2Arr[j].length());
point+=pre2Arr[j].length()+1;//多一个加号的位置
if(j>0&&temp==Integer.parseInt(pre2Arr[j-1])) continue;
/**
* 我写的算法不够完美，没有过滤掉结果完全相同的表达式。所以这里需要检查一下
*/
if(preString.toString().indexOf("="+pString+(temp+1)+nString+"=")==-1){
preString.append(pString+(temp+1)+nString+"=");
}
}
}
preString.append(pre1Arr[pre1Arr.length-1]+"+1");
}

public static void main(String[] a){
splitNumber(6);
}
}

假设拆解10，那么我们有一下几种分法
   10 =9 + 1
=8 + 2 =8 + 1 + 1
=7 + 3 =7 + 2 + 1 =7 + 1 + 1 + 1
=6 + 4 =...（到这里的时候，我们看一下前面的3行，第1行是9+1，第2行是8+（2的两种拆分），第3行是7+（3的3种拆分拆分），到本行就是6+（4的各种拆分））
=5 + 5的各种拆分
=4 + ...(到这里我们不能用6的各种拆分，因为这样会与前面的数据有所重合，要保证这里每行的数据与其他行的数据不重合，我采用的方法是第一行每种拆分的最大值都是9，第二行的拆分的最大值都是8，到本行拆分的最大值应该是。所以，应该是4+小于等于4的书对6的拆分)
=3 + 小于等于3的数对7的各种拆分
=2 + 小于等于2的数对8的各种拆分
=1 + 小于等于1的数对9的各种拆分

如果，我们把小于等于x的数对于y的拆分表示成f(x,y),则上面的式子可以表示为：
  10 =9 + f(1,1)
=8 + f(2,2)
=7 + f(3,3)
=6 + f(4,4)
=5 + f(5,5)
=4 + f(4,6)
=3 + f(3,7)
=2 + f(2,8)
=1 + f(1,9)
看上面的式子能得出一个规律，1-5行实际上是1的拆分、2的拆分、3的拆分、4的拆分、5的拆分；
4-9行是f(n,10-n), n<5

这就需要研究f(x,y)的递归规律，
举例： f(3,5) = 3 + f(3, 2)
= 2 + f(2, 3)
= 1 + f(1, 4)

不难得出其中的循环规律。代码为：

import java.util.ArrayList;
import java.util.List;

public class TestHello {

    public static void main(String[] args) {
        final int NUM = 10;
        List<String> list = f(NUM, NUM);
        int total = list.size();
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
        System.out.println("数字"+NUM+"共有" + total + "种拆法");

    }

    /**
     * 小于等于x的数对y的拆分
     *
     * @return List的每一个元素为一种拆分情况
     */
    static List<String> f(int x, int y) {
        if (x < 1 || y < 1)
            return null;
        if (x > y) {
            return f(y, y); // 小于等于3的数对2的拆分，跟小于等于2的数对2的拆分实际上是一样的
        }
        List<String> result = new ArrayList<String>();
        if (x == 1) {
            StringBuilder sb = new StringBuilder("1");
            for (int i = 1; i < y; i++) {
                sb.append("+1");
            }
            result.add(sb.toString());
            return result;
        }else if (x == 2 && y == 2) {
            result.add("1+1");
            result.add("2");
            return result;
        }else{
            if (x == y) {
                result.add("" + x);
            }
            for (int i = x; i > 0; i--) {
                List<String> l = f(i, y - i);
                if(l==null){
                    continue;
                }
                for (int j = 0; j < l.size(); j++) {
                    String s = i + "+" + l.get(j);
                    result.add(s);
                }
            }
        }
        return result;
    }
}

那这个是不是会产生重复？

晕，还用set那么麻烦

import java.util.LinkedList;

/**
 * 将任一个数字进行拆解，例如：
 * 
 * 3 = 2+1 = 1+1+1 所以3有三種拆法 
 * 4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1 共五種 
 * 5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 +1 +1 +1　共七种
 * 
 * 随便给一个数字，对其进行拆解，并打印可拆解情况和拆解结果数。
 */
public class Uncoil {
	public static void main(String[] args) {
		LinkedList<LinkedList<LinkedList<Integer>>> results = new LinkedList<LinkedList<LinkedList<Integer>>>();
		
		
		LinkedList<LinkedList<Integer>> result = new LinkedList<LinkedList<Integer>>();
		LinkedList<Integer> oneResult;
		
		int input = 20;

		for (int i = 1; i <= input; i++) {
			result = new LinkedList<LinkedList<Integer>>();
			oneResult = new LinkedList<Integer>();
			oneResult.add(i);
			result.add(oneResult);
			for (int j = 1; j <= i / 2; j++) {
				LinkedList<LinkedList<Integer>> lefts = results.get(i - j - 1);
				for (LinkedList<Integer> left : lefts) {
					if (left.getLast() < j) {
						break;
					}
					oneResult = new LinkedList<Integer>();
					oneResult.addAll(left);
					oneResult.add(j);
					result.add(oneResult);
				}
			}
			results.add(result);
		}
		
		for (LinkedList<LinkedList<Integer>> os : results) {
			System.out.println("====================" + os.size());
			for (LinkedList<Integer> o : os) {
				System.out.println(o);
			}
		}
	}
}

实验了一下，对6的拆分中少了2+2+2这种情况

import java.util.Scanner;

/**
* @author tianchi.gzt
*
* 求数字n的拆分的方法的总数（不考虑顺序）
*/
public class test {
int[][] dp;
int n;
public test(){
}
public void setN(int n){
this.n = n;
dp = new int[n+1][n+1];
dp[1][1] = dp[0][0] =1;

for(int i = 2; i <= n; i++){
for(int j = 1; j <= i; j++){
for(int k = 0; k <= j; k++){
dp[i][j] += dp[i-j][k];
}
}
}
}
public int solve(){
int result = 0;
for(int i = 1; i <= n; i++){
result += dp[n][i];
}
return result;
}
public void show(){
for(int i = n; i >= 0; --i){
for(int j = 0; j <=n; j++){
System.out.print(dp[i][j] + " ");
}
System.out.println();
}
}
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
test a = new test();
while(true){
a.setN(scanner.nextInt());
a.show();
System.out.println(a.solve());
}
}
}

现在补充代码，测试过了，可以算出来，可以看出具体的分法的大概。:) 休息吧。。。

不太会用这个

1:1
2:2
3:3
4:5
5:7
6:11
7:15
8:22
9:30
10:42
11:56
12:77
13:101
14:135
15:176
16:231
17:297
18:385
19:490
20:627
21:792
22:1002
23:1255
24:1575
25:1958
26:2436
27:3010
28:3718
29:4565
30:5604
31:6842
32:8349
33:10143
34:12310
35:14883
36:17977
37:21637
38:26015
39:31185
40:37338
这个是1到40的分法的值，大家可以测试一下代码。