Java正整数拆分算法

整数的拆分

一、概念
所谓整数的拆分，是指把一个正整数拆分成若干正整数的和。
拆分数即对应不同的拆分法的个数。
如：正整数4的拆分数
4=4
4=3+1
4=2+2
4=2+1+1
4=1+1+1+1

二、模型
正整数n的拆分，相当于把n个相同的球放进n个相同的盒子里，盒子中可以有一个以上的球，也可以空着。还以正整数4为例，球的放法如下：


三、算法：
定义一个方法Q(sum, max)，表示整数sum所有加数都不超过max的拆分数
sum的拆分数就表示为Q(sum, sum)
递归关系如下：
1、Q(sum, sum) = 1 + Q(sum, sum)
2、Q(sum, max) = Q(sum-max, max) + Q(sum, max-1)
3、Q(sum, 1) = 1或者Q(1,max) = 1， 停止。

四、java代码实现

package temporary;

public class SplitInteger {
	/**
	 * 正整数加法不同的分解法
	 * @param sum：和
	 * @param max：最大值
	 * @param data：记录不同的加法形式
	 * @param index：加法分解数的最大个数
	 * @return 分解个数
	 */
	public static int  splitInteger(int sum, int max, int[] data, int index) {
		if (max > sum) max = sum;
		if (sum < 1 || max < 1) return 0;
		if (sum == 1 || max == 1) {
			if (sum == 1) {
				data[index] = sum;
				print(data, index+1);
			} else {
				for (int i = 0; i < sum; i++) {
					data[index++] = max;
				}
				print(data, index);
			}
			return 1;
		}
		if (sum == max) {
			data[index] = max;
			print(data, index+1);
			return 1 + splitInteger(sum, max-1, data, index);
		} else if (sum > max) {
			data[index] = max;
			//一定注意这里的先后顺序
			return splitInteger(sum-max, max, data, index+1) + splitInteger(sum, max-1, data, index);			
		} else { 
			//sum < max
			return splitInteger(sum, sum, data, index);
		}
	}
	
	//打印数组
	public static void print(int[] data, int index) {
		for (int i = 0; i < index -1; i++) {
			System.out.print(data[i] + "+");
		}
		System.out.println(data[index-1]);
	}
	/**
	 * 正整数加法不同分解的个数:最大值为max，和为sum的加法个数
	 * 递归形式： f(sum, max) = f(sum-max, max) + f(sum, max-1); 
	 * @param sum
	 * @param max
	 * @return
	 */
	public static int count(int sum, int max) {
		if (sum < 1 || max < 1) return 0;
		else if (sum == 1 || max == 1){ 
			return 1;
		} else if (sum < max) {
			return count(sum,sum);
		} else if (sum == max) {
			return 1+count(sum, sum-1);
		} else {
			return count(sum, max-1)+count(sum-max,max);
		}
	}
	
	public static void main(String[] args) {
		int n = 4;
		int[] data = new int[n];
		System.out.println("正整数\'" + n + "\'可以分解为如下不同的加法形式：");
		System.out.println("正整数\'" + n + " \'加法分解个数为：\t" + splitInteger(n,n,data,0));	
		
		n = 100;
		System.out.println("正整数\'" + n + "\'加法分解个数为(包含本身)：\t" + count(n,n));
		System.out.println("正整数\'" + n + "\'加法分解个数为(不包含本身)：\t" + count(n,n-1));
	}

}

//output~
正整数'4'可以分解为如下不同的加法形式：
4
3+1
2+2
2+1+1
1+1+1+1
正整数'4 '加法分解个数为： 5
正整数'100'加法分解个数为(包含本身)： 190569292
正整数'100'加法分解个数为(不包含本身)： 190569291