整数的拆分
一、概念
所谓整数的拆分，是指把一个正整数拆分成若干正整数的和。
拆分数即对应不同的拆分法的个数。
如：正整数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
大小: 16.7 KB
分享到：
2012-10-19 13:49
浏览 7940
评论