题目:输入一个正数n,输出所有和为n的连续正数序列,例如输入15,由于1+2+3+4+5=4+5+6=7+8=15,所以输出3个连续序列1-5、4-6、7-8。
思路1:我们用两个数small和big分别表示序列的最小值和最大值。首先把small初始化为1,big初始化为2,如果从small到big的序列的和大于n的话,我们向右移动small,相当于从序列中去掉较小的数字。如果从small到big的序列的和小于n的话,我们向右移动big,相当于向序列中添加big的下一个数字,一直到small等于(1+n)/2,因为序列中至少要有两个数字。
void FindContinuousSequence(int n) { assert(n >= 3); int small = 1; int big = 2; int mid = (1+n)/2; int sum = small+big; while(small < mid) { if(sum == n) { cout << small << "-" << big << endl; sum -= small; small++; } else if(sum > n) { sum -= small; small++; } else { big++; sum += big; } } }
思路2:按照等差数列计算,连续数列有i个数,首数为x,和为n=(2x+i-1)*i/2,解得x=(2n/i-i+1)/2,注意x>0且i为整数,可得i的取值范围为[2, sqrt(2*n)],又x为整数,故2n/i为整数,且(2n/i-i+1)/2为整数。
void FindContinuousSequence(int n) { assert(n >= 3); for(int i=2; i<=sqrt(2*n); i++) { if((2*n)%i == 0) { int temp = 2*n/i-i+1; if(temp%2 == 0) { cout << temp/2 << "-" << temp/2+i-1 << endl; } } } }
扩展题目1:某些数n并不能表示为一系列连续的自然数之和,例如4、8、32就不行,那么这样的数有什么规律呢?能否证明你的结论?
思路:2的整数次幂不能表示为一系列连续的自然数之和,如上思路2所示,若要2n/i为整数,则i必为偶数,而当i为偶数时,2n/i-i为偶数,2n/i-i+1为奇数,此时(2n/i-i+1)/2就不可能为整数了,即不存在连续自然数之和了,故命题得证。