整数的拆分
一、概念
所谓整数的拆分,是指把一个正整数拆分成若干正整数的和。
拆分数即对应不同的拆分法的个数。
如:正整数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
分享到:
相关推荐
整数拆分整数拆分整数拆分整数拆分整数拆分整数拆分整数拆分整数拆分
正整数拆分的一个简单的例子,C++实现,结果输出拆分的方案数
能够给出任意正整数的所有拆分情况和种数,注释详细,只用了一个嵌套函数。
Java实现正整数分解质因数的例子。如果数学好,相信这个代码不会难。在本例子中,输入90,打印出90=2*3*3*5。解题思路和方法:对n分解质因数,需要先找到一个最小的质数k,然后按下述步骤完成: (1)如果这个质数恰...
// 给定一个正整数N, 其中 // N = A1 + A2 + ... + An 其中A1, A2, ..., An为斐波那契数列不重复的正整数 (不会有 2个1 这种结果) // 请实现下面的function (function格式请勿修改) // 其中输入参数为N, 返回值为A1,...
补充2019-07-18的源码《将一个正整数拆分成若干个正整数的和》
java任意正整数取出每位数,就一句话,需要的就来看看吧。
正整数无序分拆算法设计及论证,如果错误请指正。
正整数x 的约数是能整除x 的正整数。正整数x 的约数个数记为div(x)。例如,1,2,5,10 都是正整数10 的约数,且div(10)=4。设a 和b 是2 个正整数,a≤b,找出a 和b之间约数个数最多的数x。 编程任务:对于给定的2 ...
大整数算法和二分搜索算法大整数算法和二分搜索算法大整数算法和二分搜索算法大整数算法和二分搜索算法大整数算法和二分搜索算法大整数算法和二分搜索算法大整数算法和二分搜索算法
将正整数n表示成一系列正整数之和:n=n1+n2+…+nk,其中n1≥n2≥…≥nk≥1,k≥1。 正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数。 例如正整数6有如下11种不同的划分: 6; 5+1; 4+2,4+1+1...
对于给定的n位正整数a 和正整数k,设计一个算法找出剩下数字组成的新数 最小的删数方案。 «编程任务: 对于给定的正整数a,编程计算删去k个数字后得到的最小数。 Input 由文件input.txt提供输入数据。文件的第1...
给定n位正整数a,去掉其中任意k个数字后,剩下的数字按原次序排列成一个新的正整数。 算法设计: 给定n (1)位的正整数a和k,此时,k小于n。 试着设计一个算法,找出删去k个数,剩下数字组成的新数最小的删数方案...
java代码-使用java输入参数是一个正整数,输出该整数所对应的二进制数对应的字符串的源代码 ——学习参考资料:仅用于个人学习使用!
java小程序。猜数字游戏:随机产生一个100以内的正整数,用户通过键盘输入所猜的数字,并给与相应的提示(有代码详细解释)
给定一个正整数a,以及另外的5个正整数,问题是:这5个整数中,小于a的整数的和是多少? 输入要求 输入一行,只包括6个小于100的正整数,其中第一个正整数就是a。 输出要求 输出一行,给出一个正整数,是5个数中...
运用C#窗体空间,加上素数的算法,实现了一个可以直接输入正整数后直接判断出该正整数有几个素数。
大于1 的正整数n可以分解为:n=X1*X2*…*Xm。 例如,当n=12 时,共有8 种不同的分解式: 12=12; 12=6*2; 12=4*3; 12=3*4; 12=3*2*2; 12=2*6; 12=2*3*2; 12=2*2*3。 编程任务: 对于给定的正整数n...
对算法分析与设计课程中大整数乘法的实现,并实现不同位数的大整数相乘