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

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经典算法

    以上四个算法涵盖了从基础的斐波那契数列到较为复杂的正整数分解质因数等内容,对于Java初学者来说是非常好的实践练习。这些示例不仅帮助理解基本的编程逻辑和算法思想,还能提高解决问题的能力。

    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经典算法40题

    将一个正整数分解成若干个质因数的乘积形式。 #### 解决方案: 题目提供了一个解决方案,主要包括以下步骤: - 从最小的质数2开始尝试分解。 - 如果当前数可以被某个质数整除,则打印该质数,并继续分解剩余部分。 ...

    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