《編程之美》讀書筆記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 中國大陸許可協議進行許可，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接，否則保留追究法律責任的權利。