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