整数的拆分
一、概念
所谓整数的拆分,是指把一个正整数拆分成若干正整数的和。
拆分数即对应不同的拆分法的个数。
如:正整数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
分享到:
相关推荐
`Demo02.java`可能是一个演示或示例代码,用于展示如何解决这个正整数拆分的问题。而`Composition.java`很可能包含了核心的算法实现,"Composition"这个词可能是指组合的意思,与题目中的“拆分”相对应,暗示了代码...
质因数分解是将一个正整数表示为其所有质因数的乘积。程序通过不断尝试将输入的数除以最小的质数,直到无法再除尽,打印出所有已找到的质因数。此过程采用递归,每次尝试将当前数除以找到的质因数,然后继续对商...
**标题描述**:将输入的一个正整数分解为其质因数的乘积形式。 **代码实现**: ```java package cn.com.flywater.FiftyAlgorthm; import java.util.Scanner; public class FourthPrimeFactor { static int n, k ...
整数划分问题的定义是:给定一个非负整数n,寻找所有可能的方式将其拆分为若干个正整数的和,这些正整数称为划分的“部分”。例如,当n=4时,有效的划分有{4}、{3,1}、{2,2}、{2,1,1}和{1,1,1,1}。 在Java中解决这...
质因数分解是将一个正整数拆分成质数的乘积。在`exp2`类中,`fengjie`方法使用一个循环来寻找并打印出给定数的质因数。它从2开始尝试除以当前数,如果可以整除,就打印出质因数并继续用商作为新的数重复过程,直到...
- **题目**:给定一个正整数,将其分解成质因数的形式,如90=2*3*3*5。 - **程序分析**:从最小的质数2开始,不断除以当前数,直到无法再除以任何质数为止。 - **代码实现**:用一个循环从2开始,每次尝试将输入...
将一个正整数分解为其所有质因数的乘积形式。 **技术要点:** 1. **质因数分解:**通过寻找最小的质数因子并不断除以该因子,直到结果为1。 ```java public void fengjie(int n) { for (int i = 2; i ; i++) { ...
- **计算φ(n)**:欧拉函数φ(n) = (p-1)*(q-1),表示小于n且与n互质的正整数个数。 - **选择e**:选取一个与φ(n)互质的整数e,通常取e为65537,因为它是2^16+1,且与φ(n)互质。 - **计算d**:寻找d,使得(e * ...
给定一个正整数n,需要将其分解成质因数的乘积。代码中定义了一个名为`fengjie`的方法,使用一个循环从2开始,依次检查每个数是否是n的因数。如果找到了一个因数,就将其打印出来,并将n除以这个因数,继续寻找下一...
- **质因数分解**:对于任意正整数n,其质因数分解就是将n表示为多个质数的乘积形式。 - **实现逻辑**: - 从最小的质数2开始,检查当前的数n是否可以被2整除。 - 如果可以,则记录2作为一个质因数,并用n除以2...
此题要求将一个正整数n分解为质因数的乘积。算法思路是从最小的质数2开始,检查n是否能被i整除,如果能,则打印i并更新n为n/i,继续循环。如果不能整除,则i加1,重复此过程。质因数是只有1和它自身两个正因数的...
- 该程序的目标是将一个正整数分解为它的质因数乘积。 - 算法采用了一种迭代的方法,从最小的质数2开始尝试,依次检查能否整除输入的数,如果是,则将质数和商继续分解,直到商为1为止。 - 代码使用了一个while...
基本思路是:对于任何大于1的整数n,如果它能被小于或等于它的平方根的任何正整数整除,那么n就不是素数。因此,只需要检查从2到√n的每个数是否能整除n,如果能则返回false,否则返回true。 【程序3】涉及到的是...
- `FourthPrimeFactor`类的目标是将一个正整数分解成它的质因数。质因数是能够整除给定数的最小正质数。 - 分解质因数通常采用试除法,从最小的质数2开始,逐个检查能否整除输入的数,如果可以,将其因子输出并用...
质因数是指能整除给定正整数的质数。对于输入的90,我们需要输出它的质因数分解,即90=2*3*3*5。实现方法是通过不断找到能整除当前数的最小质数,并更新这个数直到1。这里同样使用了`math`类,包含一个`shushili ...
分解质因数是将一个正整数拆分为质数乘积的过程。对于给定的数n,我们可以从最小的质数2开始,不断除以n并更新n,直到n变为1,表示分解完成。这个过程体现了因数分解和循环结构的使用。 条件运算符在Java中用于根据...
阶乘是一个正整数n的所有小于等于n的正整数的乘积,可以表示为n!。在Java中,递归函数可以这样定义: ```java public int factorial(int n) { if (n == 1 || n == 0) { return 1; } else { return n * ...