全部博文(164)
分类: C/C++
2012-04-20 15:23:07
题目:输入一个正数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,因为序列中至少要有两个数字。
思路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为整数。
扩展题目1:某些数n并不能表示为一系列连续的自然数之和,例如4、8、32就不行,那么这样的数有什么规律呢?能否证明你的结论?
思路:2的整数次幂不能表示为一系列连续的自然数之和,如上思路2所示,若要2n/i为整数,则i必为偶数,而当i为偶数时,2n/i-i为偶数,2n/i-i+1为奇数,此时(2n/i-i+1)/2就不可能为整数了,即不存在连续自然数之和了,故命题得证。
扩展题目2:在64位正整数范围内,子序列数目最多的是哪一个?能否用数学知识推导出来?求思路
(转载)