《編程之美》讀書筆記25： 2.21只考加法的面試題
我們知道:
1+2 = 3；
4+5 = 9；
2+3+4 = 9。
等式的左邊都是兩個或兩個以上連續的自然數相加，是不是所有的整數都可以寫成這樣的形式呢？
問題1： 對于一個64位正整數，輸出它所有可能的連續自然數（兩個以上）之和的算式。
問題2： 大家在測試上面程序的過程中，肯定會注意到有一些數字不能表達為一系列連續的自然數
之和，例如32好像就找不到。那么，這樣的數字有什么規律呢？能否證明你的結論？
問題3： 在64位正整數范圍內，子序列數目最多的數是哪一個？
假設自然數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是較小的數。
對問題一：
最高效的解決方法是：找出2*n的所有質因子，然后再組合這些質因子。
可以用一個隊列保存前m個因子的組合結果。（該隊列所用的內存并不大。）
另見： 輸出和為n的所有的連續自然數序列 輸出自然數n的所有因子
對問題二：
要使n不能拆分，則說明兩組拆分 (2^t * a, b) 和 (a, 2^t * b)都不能存在。
因而 min(2^t * a, b) < 2， min(2^t * b, a) < 2 （即都不滿足k值>=2）
因而 b < 2 且 a < 2 即 a = b = 1， n = 2^(t-1)
因而： 當n等于2的t次冪時，n不能被拆分。
對問題三：
顯然，拆分個數，只與奇質因子的數目有關。
2 ^ 64 = 1.8e19
3 * 5 *7 *11 *13 *17 * 19 *23 *29 *31 * 37 *41 * 43 *47 *53 = 1.6e19
假設N是有最多因子個數的最小64位奇數，設 N = 3^a3 * 5^a5 * 7^a7 …
則一定有 a3 >= a5 >= a7 … 否則只要交換不滿足條件的那兩個數，得到相同因子個數但比N更小的數，這與假設矛盾。
S = 2 ^ 64 = 1.8e19
M=3*5*7*11*13*17*19*23*29*31*37*41*43*47*53=1.6e19（因子個數2^15）
因而，N的最大質因子一定小等于53
由S / (M / 53) = 60 可將60拆分成3^3（因子數5*2^13） 3^2 * 5（因子數3*2^14）
可得局部最優解：R1 = 3^3 *5^2 *7*11*13*17*19*23*29*31*37*41*43*47
如果N不等于R1，則a47 = 0（要將S / (M / 53/47)) = 2820 拿出來拆分）
若N包含k個質因子a， t為滿足a^t > 47（顯然t >= 2）的最小整數，則 k < 2*t-1
（否則若將t個a拆分成47，由 (k+1)*1 – (k-t+1) * 2 = 2*t-k-1 <=0，
可知拆分后得到的數更優，與N最優矛盾）。
因此a3 <=2*4-2=6，
a5 <= 2*3 – 2 = 4,
a7 <= 2*2-2 = 2
a11 <= 2*2-2 = 2
若a7 <=1， 則a3<=4，否則可以將2個3拆成1個7，得到更優解。由
S/(3^4*5^4)/ (7*11*13*17*19*23*29*31*37*41) = 35
（能得到的最多因子個數為25*2^10 < 3*2^14不是最優解）
因而 a7 = 2
（ 若az = 2, ax = a, ay =b 且 z > x * y，若不能將 z拆分成 x * y，則有
(a+1)*(b+1)*3 > (a+2)*(b+2)*2，即 (a-1)*(b-1) >= 7 ）
若a23=2則可將1個23拆成3和7，由 (1+a3)*3*3 – (1+a3+1)*4*2 = a3-7<0
可知得到的數更優，與假設矛盾，因而 a23<=1，
由于 S/(3^6*5^4)/(7*11*13*17*19)^2 = 387 > 23因而 一定含有因子23，a23 = 1
若a31=0，則 a5 = 2（否則，5*7合并成31，得到更優解）
由 2^64 / (3^6*(5*7*11*13*17*19)^2 * 23 * 29) = 14
可知，該情況下得到的最大數不是最優， 因而 a31 = 1
（若a17 =2則 a3>=5, a5=3 或 a3>=4 a5=4，否則可以將17拆分成3*5）
利用前面的結論，
a3 >= a5 >= a7 …
a3 <= 6 a5 <= 4 a7 = 2 a23 = 1 a31 = 1 a47 = 0
可在較短時間內搜索出滿足上述條件的因子個數最多的奇數，再與局部最優解R1進行比較，就可以確定最優解。
作者： flyinghearts
出處： http://www.cnblogs.com/flyinghearts/
本文采用知識共享署名-非商業性使用-相同方式共享 2.5 中國大陸許可協議進行許可，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接，否則保留追究法律責任的權利。