本文共 1885 字，大约阅读时间需要 6 分钟。

整数拆分：即把一个给定的正整数拆分为若干个连续正整数之和

例如: 将输入一个整数15，可以拆分为:

15 = 1+2+3+4+5

15 = 4+5+6

15=7+8

分析:

由题可知，拆分的起始项i不会超过该数n的一半减一(1~(n-1)/2)，累加项不会超过该数的一半加一(i~(n+1)/2)

这里可以作为循环的条件，在j循环中若s(总和) >= n(原整数),则退出，否则继续求和。

代码实现:

/** * 拆分连续正整数之和 * @author evan_qb * */public class Demo2 {	public static void main(String[] args) {		Scanner input = new Scanner(System.in);		System.out.println("请输入拆分数n:");		int n = input.nextInt();		//统计个数		int count = 0;		//起始项范围:1 ~ (n-1)/2		for (int i = 1; i <= (n-1)/2; i++) {			//定义求和的结果			int sum = 0;			//累加项范围:i ~ (n+1)/2 			for (int j = i; j <= (n+1)/2; j++) {				sum += j;				if (sum >= n) {					if (sum == n) {						//个数加一						count++;						if (j - i == 1) {							System.out.println(count + ":" + i + "+" + j);						}else{							System.out.println(count + ":" + i + "+ ... +" + j);						}						break;					}				}			}		}		System.out.println("共有" + count + "个解!!!");		input.close();	}}

算法优化:

优化要点:

累加项个数优化:

设正整数的个数为k,k的最大值为t

1+2+...+ t = t*(t+1)/2 = n,即t < sqrt(2t)

设起始值m的连续k项(2<= k < t)之和为n

m + (m+1) + ... + (m+k-1) = k*(2*m + k -1)/2 = n

推出:

m = (2*n/k-k+1)/2

在循环中:

正整数的个数k的范围为:  2 ~ t，如果2*n不能被k整除，或(2*n/k-k+1)不能被2整除，说明此时m不是整数,则返回。

否则为正整数 m = (2*n/k-k+1)/2,即为解

代码实现:

/** * 拆分数优化版 */public void test1(){	Scanner input = new Scanner(System.in);	System.out.println("请输入拆分数n:");	long n = input.nextLong();	//统计个数	int count = 0;	//t为拆分项的最大个数	long t = (long) Math.sqrt(2*n);	//k为拆分项的个数	for (long k = 2; k <= t; k++) {		//判断是否存在这个整数使得m + (m+1) + ... + (m+k-1) = k*(2*m + k -1)/2(各个项之和) = n(拆分数)		if ((2*n) % k != 0 || (2*n/k - k + 1) % 2 > 0) {			continue;		}		//设置起始项为start		long start = (2*n/k - k + 1)/2;		//满足的条件的个数		count++;		//打印出来		if (k == 2) {			System.out.println(count + ":" + start + "+" + (start + k -1));		}else{			System.out.println(count + ":" + start + "+ ... +" + (start + k -1));		}			}	System.out.println("一共有" + count + "个解");	input.close();}