编程之美 2.21
我们知道：1+2=3;
4+5=9;
2+3+4=9;
[question]
等式左边都是两个以上连续的自然数相加，那么是不是所有的整数都可以写成这种形式呢？
写一个程序，对于一个32位正整数，输出它所有的连续自然数之和的算式。
1.思路：
两数之和 K+K+1=2K+1
三数之和 K+K+1+K+2 = 3K+1+2
四数之和 4K+1+2+3
N数之和 N*K+1+2+3+...+(N-1)
输入的为input = N*K + 1+(N-1)*N/2
K为整数，K>=1 && k<=N的平方根
解答1：
程序就不写了，基本思路就是对于给定的数N，遍历2~N的数，满足条件就输出。这样的话复杂度是O(N)。
做一些优化，发现 i = 2~N 增长到一定程度后，会出现其边缘序列已经超出整数范围，故后面的值不用再遍历，可直接退出循环。
这样优化后，测试发现N=10^7时需循环4470次，比O(N)好了许多。
进一步进行理论分析如下：
设N = k*m ，k表示k个数之和，m表示序列的中点数(若k为偶数则m的小数部分必须为0.5才有解)
由于序列起点至少为1，所以有
m - (k + 1)/2 >= 0 (*)
将 m = N/k 代入上式，整理得 k^2 + k - 2*N <=0，解得 0 < k <= ( sqrt(1 + 8 * N) - 1) / 2
不等式右侧就是k取值的上界，由此可将算法改进，时间复杂度降为O(sqrt(N))
2. 不是所有的数都能被这么表示的
2的N次幂就不能够被这么表示，为什么？证明，不会.....(数学学得有点失败)
连续自然数之和(从m到n)可以表示为(m+n)*(n-m+1)/2。
如果m+n为偶数，则n-m+1为奇数，反之亦然。即(m+n)和(n-m+1)，必有一个是奇数。
2的N次幂的值不可能有奇数因子，所以...
3. 见other的blog,未懂
http://hi.baidu.com/shiqicai/blog/item/abaa0916b566f756f2de3231.html
http://hi.baidu.com/yjsagacity/blog/item/85b9428b506efb1bc9fc7a4b.html
解答3：
由解答1可知，k的上界与N有关，N越大则k的取值范围越大，可能的序列数目就越多。
因此，由贪心策略得，最大值MAX应具有如下形式
MAX = 3^n 这个不懂？？
由于是64位整数，有
3^n < 2^64
解得
n < (ln2/ln3)*64 ，n是整数，n最大值是40
所以有MAX = 3^40
再由解答1得，序列数最多为20*2 = 40个
《编程之美》的官方blog
http://www.cnblogs.com/bvbook/archive/2008/11/18/1335742.html