`
cooliufang
  • 浏览: 129691 次
社区版块
存档分类
最新评论

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
  • 大小: 16.7 KB
分享到:
评论

相关推荐

    将一个正整数拆分成若干个正整数的和.zip

    `Demo02.java`可能是一个演示或示例代码,用于展示如何解决这个正整数拆分的问题。而`Composition.java`很可能包含了核心的算法实现,"Composition"这个词可能是指组合的意思,与题目中的“拆分”相对应,暗示了代码...

    JAVA经典算法案例

    质因数分解是将一个正整数表示为其所有质因数的乘积。程序通过不断尝试将输入的数除以最小的质数,直到无法再除尽,打印出所有已找到的质因数。此过程采用递归,每次尝试将当前数除以找到的质因数,然后继续对商...

    java经典算法最常用算法42例

    **标题描述**:将输入的一个正整数分解为其质因数的乘积形式。 **代码实现**: ```java package cn.com.flywater.FiftyAlgorthm; import java.util.Scanner; public class FourthPrimeFactor { static int n, k ...

    整数划分问题java源码

    整数划分问题的定义是:给定一个非负整数n,寻找所有可能的方式将其拆分为若干个正整数的和,这些正整数称为划分的“部分”。例如,当n=4时,有效的划分有{4}、{3,1}、{2,2}、{2,1,1}和{1,1,1,1}。 在Java中解决这...

    JAVA经典算法40题.doc

    质因数分解是将一个正整数拆分成质数的乘积。在`exp2`类中,`fengjie`方法使用一个循环来寻找并打印出给定数的质因数。它从2开始尝试除以当前数,如果可以整除,就打印出质因数并继续用商作为新的数重复过程,直到...

    Java经典问题算法大全1

    - **题目**:给定一个正整数,将其分解成质因数的形式,如90=2*3*3*5。 - **程序分析**:从最小的质数2开始,不断除以当前数,直到无法再除以任何质数为止。 - **代码实现**:用一个循环从2开始,每次尝试将输入...

    java se经典算法案例

    将一个正整数分解为其所有质因数的乘积形式。 **技术要点:** 1. **质因数分解:**通过寻找最小的质数因子并不断除以该因子,直到结果为1。 ```java public void fengjie(int n) { for (int i = 2; i ; i++) { ...

    密码学RSA算法实现代码

    - **计算φ(n)**:欧拉函数φ(n) = (p-1)*(q-1),表示小于n且与n互质的正整数个数。 - **选择e**:选取一个与φ(n)互质的整数e,通常取e为65537,因为它是2^16+1,且与φ(n)互质。 - **计算d**:寻找d,使得(e * ...

    JAVA经典算法40例

    给定一个正整数n,需要将其分解成质因数的乘积。代码中定义了一个名为`fengjie`的方法,使用一个循环从2开始,依次检查每个数是否是n的因数。如果找到了一个因数,就将其打印出来,并将n除以这个因数,继续寻找下一...

    2016JAVA算法面试编程题全集(50题及答案)

    - **质因数分解**:对于任意正整数n,其质因数分解就是将n表示为多个质数的乘积形式。 - **实现逻辑**: - 从最小的质数2开始,检查当前的数n是否可以被2整除。 - 如果可以,则记录2作为一个质因数,并用n除以2...

    JAVA经典算法,有可能在面试中出现的题目哟

    此题要求将一个正整数n分解为质因数的乘积。算法思路是从最小的质数2开始,检查n是否能被i整除,如果能,则打印i并更新n为n/i,继续循环。如果不能整除,则i加1,重复此过程。质因数是只有1和它自身两个正因数的...

    Java经典问题算法大全[归纳].pdf

    - 该程序的目标是将一个正整数分解为它的质因数乘积。 - 算法采用了一种迭代的方法,从最小的质数2开始尝试,依次检查能否整除输入的数,如果是,则将质数和商继续分解,直到商为1为止。 - 代码使用了一个while...

    JAVA经典算法42例.doc

    基本思路是:对于任何大于1的整数n,如果它能被小于或等于它的平方根的任何正整数整除,那么n就不是素数。因此,只需要检查从2到√n的每个数是否能整除n,如果能则返回false,否则返回true。 【程序3】涉及到的是...

    经典基础算法编程(JAVA)

    - `FourthPrimeFactor`类的目标是将一个正整数分解成它的质因数。质因数是能够整除给定数的最小正质数。 - 分解质因数通常采用试除法,从最小的质数2开始,逐个检查能否整除输入的数,如果可以,将其因子输出并用...

    40例java经典算法研究.pdf

    质因数是指能整除给定正整数的质数。对于输入的90,我们需要输出它的质因数分解,即90=2*3*3*5。实现方法是通过不断找到能整除当前数的最小质数,并更新这个数直到1。这里同样使用了`math`类,包含一个`shushili ...

    java方法练习题及答案.doc.pdf

    分解质因数是将一个正整数拆分为质数乘积的过程。对于给定的数n,我们可以从最小的质数2开始,不断除以n并更新n,直到n变为1,表示分解完成。这个过程体现了因数分解和循环结构的使用。 条件运算符在Java中用于根据...

    Java基础编程实例

    阶乘是一个正整数n的所有小于等于n的正整数的乘积,可以表示为n!。在Java中,递归函数可以这样定义: ```java public int factorial(int n) { if (n == 1 || n == 0) { return 1; } else { return n * ...

Global site tag (gtag.js) - Google Analytics