求和替n的连续正整数序列

求和为n的连续正整数序列

题目：输入一个正数n，输出所有和为n连续正整数序列。

 

例如输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以输出3个连续序列1-5、4-6和7-8。

 

 

解法1

 

因为整数序列是有序的，可以设立两个游标begin和end，通过判区间[begin,end]的和是否为N来得到这个序列。如果区间和大于n，begin往前移动，如果小于n，end往前移动，等于就输出这个区间。时间复杂度是0(n)。

 

public void find(int n) {
    if (n > 0 && ((n & n-1) == 0)) {
        System.out.println("no way");
	return;
    }
		
    int begin = 1; 
    int end = 2;
    int sum = begin + end;
		
    while (begin < end && begin < (n+1)/2) {
        if (sum < n) {
	    end++;
	    sum += end;
	} else if (sum > n) {
	    sum -= begin;
	    begin++;
	} else {
	    System.out.println(n + " can be divided from " + begin + " to " + end);
	    sum -= begin;
	    begin++;
	}
    }
}

 

 

解法2

 

假设自然数n可以拆分成：m, m+1, …, m+k-1 (m >= 1, k >= 2)，则 n = (m + m+k-1)*k/2 即 2*n = (2*m+k-1)*k。

由于(2*m+k-1)与k的奇偶性是相反的，因此，可以先将n的所有质因子2提取出来，得到：2 * n = 2^t * a * b，由于(2*m+k-1)与k的奇偶性相反，且(2*m+k-1) > k，当确定了a，b时，可得到2*n的两组拆分(2^t * a, b) 和 (a, 2^t * b)（当a等于b时，这两组拆分是一样的），对每组拆分，k是较小的数。

 

public void find2(int n) {
    if (n <= 0)
        return;
		
    int count = 1;
    int i;
    int j;
    while(n % 2 == 0) {
        n /= 2;
	count++;
    }
		
    for (i = 1; ; i += 2) {
        if (n % i != 0)
            continue;
        j = n / i;
        if (i > j)
            break;
			
        if ((i << count) < j)
            print(j, i << count);
        else 
            print(i << count, j);
			
        if (i == j) break;
        if (i == 1) continue;
			
        if ((j << count) < i)
            print(i, j << count);
        else
            print(j << count, i);
    }
}
	
private void print(int i, int j) {
    int k = j;
    int m = (i-j+1) / 2;
    System.out.println("from " + m + " to " + (m+k-1));
}