mysileng

  程序員編程藝術第十一章：最長公共子序列(LCS)問題

0、前言

    程序員編程藝術系列重新開始創作了（前十章，請參考程序員編程藝術第一~十章集錦與總結）。回顧之前的前十章，有些代碼是值得商榷的，因當時的代碼只顧闡述算法的原理或思想，所以，很多的與代碼規范相關的問題都未能做到完美。日后，會著力修繕之。

    搜遍網上，講解這個LCS問題的文章不計其數，但大多給讀者一種并不友好的感覺，稍感晦澀，且代碼也不夠清晰。本文力圖避免此些情況。力保通俗，闡述詳盡。同時，經典算法研究系列的第三章（三、dynamic programming）也論述了此LCS問題。有任何問題，歡迎不吝賜教。

第一節、問題描述

    什么是最長公共子序列呢?好比一個數列 S，如果分別是兩個或多個已知數列的子序列，且是所有符合此條件序列中最長的，則S 稱為已知序列的最長公共子序列。

    舉個例子，如：有兩條隨機序列，如 1 3 4 5 5 ，and 2 4 5 5 7 6，則它們的最長公共子序列便是：4 5 5。

    注意最長公共子串（Longest CommonSubstring）和最長公共子序列（LongestCommon Subsequence, LCS）的區別：子串（Substring）是串的一個連續的部分，子序列（Subsequence）則是從不改變序列的順序，而從序列中去掉任意的元素而獲得的新序列；更簡略地說，前者（子串）的字符的位置必須連續，后者（子序列LCS）則不必。比如字符串acdfg同akdfc的最長公共子串為df，而他們的最長公共子序列是adf。LCS可以使用動態規劃法解決。下文具體描述。

第二節、LCS問題的解決思路

• 窮舉法   

    解最長公共子序列問題時最容易想到的算法是窮舉搜索法，即對X的每一個子序列，檢查它是否也是Y的子序列，從而確定它是否為X和Y的公共子序列，并且在檢查過程中選出最長的公共子序列。X和Y的所有子序列都檢查過后即可求出X和Y的最長公共子序列。X的一個子序列相應于下標序列{1, 2, …, m}的一個子序列，因此，X共有2^m個不同子序列（Y亦如此，如為2^n），從而窮舉搜索法需要指數時間（2^m * 2^n）。

• 動態規劃算法

    事實上，最長公共子序列問題也有最優子結構性質。

記:

Xi=﹤x1，⋯，xi﹥即X序列的前i個字符 (1≤i≤m)（前綴）

Yj=﹤y1，⋯，yj﹥即Y序列的前j個字符 (1≤j≤n)（前綴）

假定Z=﹤z1，⋯，zk﹥∈LCS(X , Y)。

• 若xm=yn（最后一個字符相同），則不難用反證法證明：該字符必是X與Y的任一最長公共子序列Z（設長度為k）的最后一個字符，即有zk = xm = yn 且顯然有Zk-1∈LCS(Xm-1 , Yn-1)即Z的前綴Zk-1是Xm-1與Yn-1的最長公共子序列。此時，問題化歸成求Xm-1與Yn-1的LCS（LCS(X , Y)的長度等于LCS(Xm-1 , Yn-1)的長度加1）。

• 若xm≠yn，則亦不難用反證法證明：要么Z∈LCS(Xm-1, Y)，要么Z∈LCS(X , Yn-1)。由于zk≠xm與zk≠yn其中至少有一個必成立，若zk≠xm則有Z∈LCS(Xm-1 , Y)，類似的，若zk≠yn 則有Z∈LCS(X , Yn-1)。此時，問題化歸成求Xm-1與Y的LCS及X與Yn-1的LCS。LCS(X , Y)的長度為：max{LCS(Xm-1 , Y)的長度, LCS(X , Yn-1)的長度}。

    由于上述當xm≠yn的情況中，求LCS(Xm-1 , Y)的長度與LCS(X , Yn-1)的長度，這兩個問題不是相互獨立的：兩者都需要求LCS(Xm-1，Yn-1)的長度。另外兩個序列的LCS中包含了兩個序列的前綴的LCS，故問題具有最優子結構性質考慮用動態規劃法。

    也就是說，解決這個LCS問題，你要求三個方面的東西：1、LCS（Xm-1，Yn-1）+1；2、LCS（Xm-1，Y），LCS（X，Yn-1）；3、max{LCS（Xm-1，Y），LCS（X，Yn-1）}。

    行文至此，其實對這個LCS的動態規劃解法已敘述殆盡，不過，為了成書的某種必要性，下面，我試著再多加詳細闡述這個問題。

第三節、動態規劃算法解LCS問題

3.1、最長公共子序列的結構

    最長公共子序列的結構有如下表示：

    設序列X=<x₁, x₂, …, x_m>和Y=<y₁, y₂, …, y_n>的一個最長公共子序列Z=<z₁, z₂, …, z_k>，則：

1. 若x_m=y_n，則z_k=x_m=y_n且Z_k-1是X_m-1和Y_n-1的最長公共子序列；
2. 若x_m≠y_n且z_k≠x_{m ，}則Z是X_m-1和Y的最長公共子序列；
3. 若x_m≠y_n且z_k≠y_n ，則Z是X和Y_n-1的最長公共子序列。

    其中X_m-1=<x₁, x₂, …, x_m-1>，Y_n-1=<y₁, y₂, …, y_n-1>，Z_k-1=<z₁, z₂, …, z_k-1>。

3、2.子問題的遞歸結構

    由最長公共子序列問題的最優子結構性質可知，要找出X=<x₁, x₂, …, x_m>和Y=<y₁, y₂, …, y_n>的最長公共子序列，可按以下方式遞歸地進行：當x_m=y_n時，找出X_m-1和Y_n-1的最長公共子序列，然后在其尾部加上x_m(=y_n)即可得X和Y的一個最長公共子序列。當x_m≠y_n時，必須解兩個子問題，即找出X_m-1和Y的一個最長公共子序列及X和Y_n-1的一個最長公共子序列。這兩個公共子序列中較長者即為X和Y的一個最長公共子序列。

    由此遞歸結構容易看到最長公共子序列問題具有子問題重疊性質。例如，在計算X和Y的最長公共子序列時，可能要計算出X和Y_n-1及X_m-1和Y的最長公共子序列。而這兩個子問題都包含一個公共子問題，即計算X_m-1和Y_n-1的最長公共子序列。

    與矩陣連乘積最優計算次序問題類似，我們來建立子問題的最優值的遞歸關系。用c[i,j]記錄序列X_i和Y_j的最長公共子序列的長度。其中X_i=<x₁, x₂, …, x_i>，Y_j=<y₁, y₂, …, y_j>。當i=0或j=0時，空序列是X_i和Y_j的最長公共子序列，故c[i,j]=0。其他情況下，由定理可建立遞歸關系如下：

3、3.計算最優值

    直接利用上節節末的遞歸式，我們將很容易就能寫出一個計算c[i,j]的遞歸算法，但其計算時間是隨輸入長度指數增長的。由于在所考慮的子問題空間中，總共只有θ(m*n)個不同的子問題，因此，用動態規劃算法自底向上地計算最優值能提高算法的效率。

    計算最長公共子序列長度的動態規劃算法LCS_LENGTH(X,Y)以序列X=<x₁, x₂, …, x_m>和Y=<y₁, y₂, …, y_n>作為輸入。輸出兩個數組c[0..m ,0..n]和b[1..m ,1..n]。其中c[i,j]存儲X_i與Y_j的最長公共子序列的長度，b[i,j]記錄指示c[i,j]的值是由哪一個子問題的解達到的，這在構造最長公共子序列時要用到。最后，X和Y的最長公共子序列的長度記錄于c[m,n]中。

    由算法LCS_LENGTH計算得到的數組b可用于快速構造序列X=<x₁, x₂, …, x_m>和Y=<y₁, y₂, …, y_n>的最長公共子序列。首先從b[m,n]開始，沿著其中的箭頭所指的方向在數組b中搜索。

• 當b[i,j]中遇到"↖"時（意味著xi=yi是LCS的一個元素），表示X_i與Y_j的最長公共子序列是由X_i-1與Y_j-1的最長公共子序列在尾部加上x_i得到的子序列；
• 當b[i,j]中遇到"↑"時，表示X_i與Y_j的最長公共子序列和X_i-1與Y_j的最長公共子序列相同；
• 當b[i,j]中遇到"←"時，表示X_i與Y_j的最長公共子序列和X_i與Y_j-1的最長公共子序列相同。

    這種方法是按照反序來找LCS的每一個元素的。由于每個數組單元的計算耗費Ο(1)時間，算法LCS_LENGTH耗時Ο(mn)。

3、4.構造最長公共子序列

    下面的算法LCS(b,X,i,j)實現根據b的內容打印出X_i與Y_j的最長公共子序列。通過算法的調用LCS(b,X,length[X],length[Y])，便可打印出序列X和Y的最長公共子序列。

在算法LCS中，每一次的遞歸調用使i或j減1，因此算法的計算時間為O(m+n)。

例如，設所給的兩個序列為X=<A，B，C，B，D，A，B>和Y=<B，D，C，A，B，A>。由算法LCS_LENGTH和LCS計算出的結果如下圖所示：

 我來說明下此圖（參考算法導論）。在序列X={A，B，C，B，D，A，B}和 Y={B，D，C，A，B，A}上，由LCS_LENGTH計算出的表c和b。第i行和第j列中的方塊包含了c[i，j]的值以及指向b[i，j]的箭頭。在c[7,6]的項4，表的右下角為X和Y的一個LCS<B，C，B，A>的長度。對于i，j>0，項c[i，j]僅依賴于是否有xi=yi，及項c[i-1，j]和c[i，j-1]的值，這幾個項都在c[i，j]之前計算。為了重構一個LCS的元素，從右下角開始跟蹤b[i，j]的箭頭即可，這條路徑標示為陰影，這條路徑上的每一個“↖”對應于一個使xi=yi為一個LCS的成員的項（高亮標示）。

    所以根據上述圖所示的結果，程序將最終輸出：“B C B A”。

3、5.算法的改進

    對于一個具體問題，按照一般的算法設計策略設計出的算法，往往在算法的時間和空間需求上還可以改進。這種改進，通常是利用具體問題的一些特殊性。

    例如，在算法LCS_LENGTH和LCS中，可進一步將數組b省去。事實上，數組元素c[i,j]的值僅由c[i-1,j-1]，c[i-1,j]和c[i,j-1]三個值之一確定，而數組元素b[i,j]也只是用來指示c[i,j]究竟由哪個值確定。因此，在算法LCS中，我們可以不借助于數組b而借助于數組c本身臨時判斷c[i,j]的值是由c[i-1,j-1]，c[i-1,j]和c[i,j-1]中哪一個數值元素所確定，代價是Ο(1)時間。既然b對于算法LCS不是必要的，那么算法LCS_LENGTH便不必保存它。這一來，可節省θ(mn)的空間，而LCS_LENGTH和LCS所需要的時間分別仍然是Ο(mn)和Ο(m+n)。不過，由于數組c仍需要Ο(mn)的空間，因此這里所作的改進，只是在空間復雜性的常數因子上的改進。

    另外，如果只需要計算最長公共子序列的長度，則算法的空間需求還可大大減少。事實上，在計算c[i,j]時，只用到數組c的第i行和第i-1行。因此，只要用2行的數組空間就可以計算出最長公共子序列的長度。更進一步的分析還可將空間需求減至min(m, n)。

第四節、編碼實現LCS問題

    動態規劃的一個計算最長公共子序列的方法如下，以兩個序列 X、Y 為例子：

設有二維數組 f[i][j] 表示 X 的 i 位和 Y 的 j 位之前的最長公共子序列的長度，則有：

f[1][1] = same(1,1)

f[i][j] = max{f[i − 1][j − 1] +same(i,j), f[i − 1][j] ,f[i][j − 1]}

其中，same(a,b)當 X 的第 a 位與 Y 的第 b 位完全相同時為“1”，否則為“0”。

此時，f[i][j]中最大的數便是 X 和 Y 的最長公共子序列的長度，依據該數組回溯，便可找出最長公共子序列。

該算法的空間、時間復雜度均為O(n²)，經過優化后，空間復雜度可為O(n)，時間復雜度為O(nlogn)。

以下是此算法的java代碼：

第五節、改進的算法

    下面咱們來了解一種不同于動態規劃法的一種新的求解最長公共子序列問題的方法,該算法主要是把求解公共字符串問題轉化為求解矩陣L(p,m)的問題，在利用定理求解矩陣的元素過程中（1）while(i<k),L(k,i)=null，
                  （2）while(L(k,i)=k),L(k,i+1)=L(k,i+2)=…L(k,m)=k；

    求出每列元素，一直到發現第p+1 行都為null 時退出循環，得出矩陣L(k,m)后，B[L(1,m-p+1)]B[L(2,m-p+2)]…B[L(p,m)]即為A 和B 的LCS，其中p 為LCS 的長度。

6.1 主要定義及定理

• 定義 1 子序列(Subsequence)：給定字符串A=A[1]A[2]…A[m]，(A[i]是A 的第i 個字母，A[i]∈字符集Σ，l<= i<m = A ， A 表示字符串A 的長度)，字符串B 是A 的子序列是指B=A[ 1 i ]A[ 2 i ]…A[ k i ],其中1 i < 2 i <…< k i 且k<=m.
• 定義2 公共子序列(Common Subsequence)：給定字符串A、B、C，C 稱為A 和B 的公共子序列是指C 既是A 的子序列，又是B 的子序列。
• 定義3 最長公共子序列(Longest Common Subsequence 簡稱LCS)：給定字符串A、B、C，C 稱為A 和B 的最長公共子序列是指C 是A 和B 的公共子序列，且對于A 和B 的任意公共子序列D，都有D <= C 。給定字符串A 和B，A =m，B =n，不妨設m<=n，LCS 問題就是要求出A 和B 的LCS。
• 定義4 給定字符串A=A[1]A[2]…A[m]和字符串B=B[1]B[2]…[n]，A( 1:i)表示A 的連續子序列A[1]A[2]…A[i]，同樣B(1:j)表示B 的連續子序列B[1]B[2]…[j]。Li(k)表示所有與字符串A(1:i) 有長度為k 的LCS 的字符串B(l:j) 中j 的最小值。用公式表示就是Li(k)=Minj(LCS(A(1:i)，B(l:j))=k) [3]。
  
  
  定理1 ∀ i∈[1，m]，有Li(l)<Li(2)<Li(3)<…<Li(m) .
  定理2 ∀i∈[l，m-1]，∀k∈[l，m]，有i 1 L + (k)<= i L (k).
  定理3 ∀ i∈[l，m-1]， ∀ k∈[l，m-l]，有i L (k)< i 1 L + (k+l).
  以上三個定理都不考慮Li(k)無定義的情況。
  定理4[3] i 1 L + (k)如果存在，那么它的取值必為: i 1 L + (k)=Min(j, i L (k))。這里j 是滿足以下條件的最小整數:A[i+l]=B[j]且j> i L (k-1)。
  
  
  

   矩陣中元素L(k，i)=Li(k)，這里(1<i<=m，1<k<=m)，null 表示L(k,i)不存在。當i<k 時，顯然L(k，i)不存在。
      設p=Maxk(L(k ， m) ≠ null) ， 可以證明L 矩陣中L(p,m) 所在的對角線,L(1,m-p+1),L(2,m-p+2)…L(p-1,m-1),L(p,m) 所對應的子序列B[L(1,m-p+1)]B[L(2,m-p+2)]…B[L(p,m)]即為A 和B 的LCS，p 為該LCS 的長度。這樣，LCS 問題的求解就轉化為對m m L × 矩陣的求解。
  
  6.2 算法思想

      根據定理,第一步求出第一行元素,L(1,1),L(1,2),…L(1,m),第二步求第二行,一直到發現第p+1 行都為null 為止。在計算過程中遇到i<k 時,L(k,i)=null, 及L(k,i)=k時,L(k,i+1)=L(k,i+2)=…L(k,m)=k。這樣,計算每行的時間復雜度為O(n),則整個時間復雜度為O(pn)。在求L 矩陣的過程中不用存儲整個矩陣,只需存儲當前行和上一行即可。空間復雜度為O(m+n)。

      下面給出一個例子來說明:給定字符串A 和B，A=acdabbc，B=cddbacaba，(m= A =7，n= B =9)。按照定理給出的遞推公式，求出A 和B 的L 矩陣如圖2，其中的$表示NULL。
  
  

  則A 和B 的LCS 為B[1]B[2]B[4]B[6]=cdbc,LCS 的長度為4。

  6.3 算法偽代碼
  算法 L(A,B,L)
  輸入 長度分別為m,n 的字符串A,B
  輸出 A,B 的最長公共子序列LCS

  1. L(A,B,L){//字符串A，B，所求矩陣L  
  2.   for(k=1;k<=m;k++){ //m 為A 的長度  
  3.     for(i=1;i<=m;i++){  
  4.       if(i<k) L[k][i]=N;//i<k 時,L(k,i)=null，N 代表無窮大  
  5.       if(L[k][i]==k)//L(k,i)=k 時,L(k,i+1)=L(k,i+2)=…L(k,m)=k  
  6.       for(l=i+1;l<=m;l++)  
  7.        { L[k][l]=k;  
  8.          Break;}  
  9.       for(j=1;j<=n;j++){//定理4 的實現  
  10.        if(A[i+1]==B[j]&&j>L[k-1][i]){  
  11.         L[k][i+1]=(j<L[k][i]?j:L[k][i]);  
  12.         break;  
  13.       }  
  14.       if(L[k][i+1]==0)  
  15.         L[k][i]=N;  
  16.      }  
  17.      if(L[k][m]==N)  
  18.       {p=k-1;break;}  
  19.   }  
  20.   p=k-1;  
  21. }  

  6.4 結語
      本節主要描述區別于動態規劃法的一種新的求解最長公共子序列問題的方法，在不影響精確度的前提下，提高序列匹配的速度，根據定理i 1 L + (k)=Min(j, i L (k))得出矩陣，在求解矩陣的過程中對最耗時的L(p,m)進行條件約束優化。我們在Intel(R) Core(TM)2 Quad 雙核處理器、1G 內存，軟件環境：windows xp 下試驗結果證明，本文算法與其他經典的比對算法相比,不但能夠取得準確的結果,而且速度有了較大的提高（本節參考了劉佳梅女士的論文）。

      若有任何問題，懇請不吝指正。謝謝各位。完。

  
  
  

作者：July、狂想曲創作組。
出處：http://blog.csdn.net/v_JULY_v 。

前奏
    有這樣一個問題：在一條左右水平放置的直線軌道上任選兩個點，放置兩個機器人，請用如下指令系統為機器人設計控制程序，使這兩個機器人能夠在直線軌道上相遇。（注意兩個機器人用你寫的同一個程序來控制）。
    指令系統：只包含4條指令，向左、向右、條件判定、無條件跳轉。其中向左（右）指令每次能控制機器人向左（右）移動一步；條件判定指令能對機器人所在的位置進行條件測試，測試結果是如果對方機器人曾經到過這里就返回true，否則返回false；無條件跳轉，類似匯編里面的跳轉，可以跳轉到任何地方。

    ok，這道很有意思的趣味題是去年微軟工程院的題，文末將給出解答（如果急切想知道此問題的答案，可以直接跳到本文第三節）。同時，我們看到其實這個題是一個典型的追趕問題，那么追趕問題在哪種面試題中比較常見?對了，鏈表追趕。本章就來闡述這個問題。有不正之處，望不吝指正。

第一節、求鏈表倒數第k個結點
第13題、題目描述：
輸入一個單向鏈表，輸出該鏈表中倒數第k個結點,
鏈表的倒數第0個結點為鏈表的尾指針。

分析：此題一出，相信，稍微有點 經驗的同志，都會說到：設置兩個指針p1,p2，首先p1和p2都指向head，然后p2向前走k步，這樣p1和p2之間就間隔k個節點，最后p1和p2同時向前移動，直至p2走到鏈表末尾。

    前幾日有朋友提醒我說，讓我講一下此種求鏈表倒數第k個結點的問題。我想，這種問題，有點經驗的人恐怕都已了解過，無非是利用兩個指針一前一后逐步前移。但他提醒我說，如果參加面試的人沒有這個意識，它怎么也想不到那里去。

    那在平時準備面試的過程中如何加強這一方面的意識呢?我想，除了平時遇到一道面試題，盡可能用多種思路解決，以延伸自己的視野之外，便是平時有意注意觀察生活。因為，相信，你很容易了解到，其實這種鏈表追趕的問題來源于生活中長跑比賽，如果平時注意多多思考，多多積累，多多發現并體味生活，相信也會對面試有所幫助。

    ok，扯多了，下面給出這個題目的主體代碼，如下：

struct ListNode
{
    char data;
    ListNode* next;
};
ListNode* head,*p,*q;
ListNode *pone,*ptwo;

//@heyaming, 第一節,求鏈表倒數第k個結點應該考慮k大于鏈表長度的case。
ListNode* fun(ListNode *head,int k)
{
 assert(k >= 0);
 pone = ptwo = head;
 for( ; k > 0 && ptwo != NULL; k--)
  ptwo=ptwo->next;
 if (k > 0) return NULL;
 
 while(ptwo!=NULL)
 {
  pone=pone->next;
  ptwo=ptwo->next;
 }
 return pone;
} 

 

擴展：
這是針對鏈表單項鏈表查找其中倒數第k個結點。試問，如果鏈表是雙向的，且可能存在環呢?請看第二節、編程判斷兩個鏈表是否相交。

第二節、編程判斷兩個鏈表是否相交
題目描述：給出兩個單向鏈表的頭指針（如下圖所示）

比如h1、h2，判斷這兩個鏈表是否相交。這里為了簡化問題，我們假設兩個鏈表均不帶環。

分析：這是來自編程之美上的微軟亞院的一道面試題目。請跟著我的思路步步深入（部分文字引自編程之美）：

1. 直接循環判斷第一個鏈表的每個節點是否在第二個鏈表中。但，這種方法的時間復雜度為O(Length(h1) * Length(h2))。顯然，我們得找到一種更為有效的方法，至少不能是O（N^2）的復雜度。
2. 針對第一個鏈表直接構造hash表，然后查詢hash表，判斷第二個鏈表的每個結點是否在hash表出現，如果所有的第二個鏈表的結點都能在hash表中找到，即說明第二個鏈表與第一個鏈表有相同的結點。時間復雜度為為線性：O(Length(h1) + Length(h2))，同時為了存儲第一個鏈表的所有節點，空間復雜度為O(Length(h1))。是否還有更好的方法呢，既能夠以線性時間復雜度解決問題，又能減少存儲空間？
3. 進一步考慮“如果兩個沒有環的鏈表相交于某一節點，那么在這個節點之后的所有節點都是兩個鏈表共有的”這個特點，我們可以知道，如果它們相交，則最后一個節點一定是共有的。而我們很容易能得到鏈表的最后一個節點，所以這成了我們簡化解法的一個主要突破口。那么，我們只要判斷倆個鏈表的尾指針是否相等。相等，則鏈表相交；否則，鏈表不相交。
   所以，先遍歷第一個鏈表，記住最后一個節點。然后遍歷第二個鏈表，到最后一個節點時和第一個鏈表的最后一個節點做比較，如果相同，則相交，否則，不相交。這樣我們就得到了一個時間復雜度，它為O((Length(h1) + Length(h2))，而且只用了一個額外的指針來存儲最后一個節點。這個方法時間復雜度為線性O（N），空間復雜度為O（1），顯然比解法三更勝一籌。
4. 上面的問題都是針對鏈表無環的，那么如果現在，鏈表是有環的呢?還能找到最后一個結點進行判斷么?上面的方法還同樣有效么?顯然，這個問題的本質已經轉化為判斷鏈表是否有環。那么，如何來判斷鏈表是否有環呢?

總結：
所以，事實上，這個判斷兩個鏈表是否相交的問題就轉化成了：
1.先判斷帶不帶環
2.如果都不帶環，就判斷尾節點是否相等
3.如果都帶環，判斷一鏈表上倆指針相遇的那個節點，在不在另一條鏈表上。
如果在，則相交，如果不在，則不相交。

    1、那么，如何編寫代碼來判斷鏈表是否有環呢?因為很多的時候，你給出了問題的思路后，面試官可能還要追加你的代碼，ok，如下（設置兩個指針(p1, p2)，初始值都指向頭，p1每次前進一步，p2每次前進二步，如果鏈表存在環，則p2先進入環，p1后進入環，兩個指針在環中走動，必定相遇）：

 

1. //copyright@ KurtWang  
2. //July、2011.05.27。  
3. struct Node  
4. {  
5.     int value;  
6.     Node * next;  
7. };  
8.   
9. //1.先判斷帶不帶環  
10. //判斷是否有環，返回bool，如果有環，返回環里的節點  
11. //思路：用兩個指針，一個指針步長為1，一個指針步長為2，判斷鏈表是否有環  
12. bool isCircle(Node * head, Node *& circleNode, Node *& lastNode)  
13. {  
14.     Node * fast = head->next;  
15.     Node * slow = head;  
16.     while(fast != slow && fast && slow)  
17.     {  
18.         if(fast->next != NULL)  
19.             fast = fast->next;  
20.           
21.         if(fast->next == NULL)  
22.             lastNode = fast;  
23.         if(slow->next == NULL)  
24.             lastNode = slow;  
25.           
26.         fast = fast->next;  
27.         slow = slow->next;  
28.           
29.     }  
30.     if(fast == slow && fast && slow)  
31.     {  
32.         circleNode = fast;  
33.         return true;  
34.     }  
35.     else  
36.         return false;  
37. }  

 

    2&3、如果都不帶環，就判斷尾節點是否相等，如果都帶環，判斷一鏈表上倆指針相遇的那個節點，在不在另一條鏈表上。下面是綜合解決這個問題的代碼：

 

1. //判斷帶環不帶環時鏈表是否相交  
2. //2.如果都不帶環，就判斷尾節點是否相等  
3. //3.如果都帶環，判斷一鏈表上倆指針相遇的那個節點，在不在另一條鏈表上。  
4. bool detect(Node * head1, Node * head2)  
5. {  
6.     Node * circleNode1;  
7.     Node * circleNode2;  
8.     Node * lastNode1;  
9.     Node * lastNode2;  
10.       
11.     bool isCircle1 = isCircle(head1,circleNode1, lastNode1);  
12.     bool isCircle2 = isCircle(head2,circleNode2, lastNode2);  
13.       
14.     //一個有環，一個無環  
15.     if(isCircle1 != isCircle2)  
16.         return false;  
17.     //兩個都無環，判斷最后一個節點是否相等  
18.     else if(!isCircle1 && !isCircle2)  
19.     {  
20.         return lastNode1 == lastNode2;  
21.     }  
22.     //兩個都有環，判斷環里的節點是否能到達另一個鏈表環里的節點  
23.     else  
24.     {  
25.         Node * temp = circleNode1->next;  //updated，多謝蒼狼 and hyy。  
26.         while(temp != circleNode1)    
27.         {  
28.             if(temp == circleNode2)  
29.                 return true;  
30.             temp = temp->next;  
31.         }  
32.         return false;  
33.     }  
34.       
35.     return false;  
36. }  

 

擴展2：求兩個鏈表相交的第一個節點
思路：在判斷是否相交的過程中要分別遍歷兩個鏈表，同時記錄下各自長度。

    @Joshua：這個算法需要處理一種特殊情況，即：其中一個鏈表的頭結點在另一個鏈表的環中，且不是環入口結點。這種情況有兩種意思：1)如果其中一個鏈表是循環鏈表，則另一個鏈表必為循環鏈表，即兩個鏈表重合但頭結點不同；2)如果其中一個鏈表存在環(除去循環鏈表這種情況)，則另一個鏈表必在此環中與此環重合，其頭結點為環中的一個結點，但不是入口結點。在這種情況下我們約定，如果鏈表B的頭結點在鏈表A的環中，且不是環入口結點，那么鏈表B的頭結點即作為A和B的第一個相交結點；如果A和B重合(定義方法時形參A在B之前)，則取B的頭結點作為A和B的第一個相交結點。 

    代碼如下：

    關于判斷單鏈表是否相交的問題，還可以看看此篇文章：http://m.shnenglu.com/humanchao/archive/2008/04/17/47357.html。ok，下面，回到本章前奏部分的那道非常有趣味的智力題。

第三節、微軟工程院面試智力題
題目描述：
    在一條左右水平放置的直線軌道上任選兩個點，放置兩個機器人，請用如下指令系統為機器人設計控制程序，使這兩個機器人能夠在直線軌道上相遇。（注意兩個機器人用你寫的同一個程序來控制）
    指令系統：只包含4條指令，向左、向右、條件判定、無條件跳轉。其中向左（右）指令每次能控制機器人向左（右）移動一步；條件判定指令能對機器人所在的位置進行條件測試，測試結果是如果對方機器人曾經到過這里就返回true，否則返回false；無條件跳轉，類似匯編里面的跳轉，可以跳轉到任何地方。

分析：我盡量以最清晰的方式來說明這個問題（大部分內容來自ivan，big等人的討論）：
      1、首先題目要求很簡單，就是要你想辦法讓A最終能趕上B，A在后，B在前，都向右移動，如果它們的速度永遠一致，那A是永遠無法追趕上B的。但題目給出了一個條件判斷指令，即如果A或B某個機器人向前移動時，若是某個機器人經過的點是第二個機器人曾經經過的點，那么程序返回true。對的，就是抓住這一點，A到達曾經B經過的點后，發現此后的路是B此前經過的，那么A開始提速兩倍，B一直保持原來的一倍速度不變，那樣的話，A勢必會在|AB|/move_right個單位時間內，追上B。ok，簡單偽代碼如下：

start:
if(at the position other robots have not reached)
    move_right
if(at the position other robots have reached)
    move_right
    move_right
goto start

再簡單解釋下上面的偽代碼（@big）：
A------------B
|                  |
在A到達B點前，兩者都只有第一條if為真，即以相同的速度向右移動，在A到達B后，A只滿足第二個if，即以兩倍的速度向右移動，B依然只滿足第一個if，則速度保持不變，經過|AB|/move_right個單位時間，A就可以追上B。

     2、有個細節又出現了，正如ivan所說，

if(at the position other robots have reached)
    move_right
    move_right

上面這個分支不一定能提速的。why?因為如果if條件花的時間很少，而move指令發的時間很大（實際很可能是這樣），那么兩個機器人的速度還是基本是一樣的。

那作如何修改呢?:

start:
if(at the position other robots have not reached)
    move_right
    move_left
    move_right
if(at the position other robots have reached)
    move_right
goto start

-------

這樣改后，A的速度應該比B快了。

      3、然要是說每個指令處理速度都很快，AB豈不是一直以相同的速度右移了?那到底該作何修改呢?請看：

go_step()
{
   向右
   向左
   向右
}
--------
三個時間單位才向右一步

go_2step()
{
   向右
}
------

    一個時間單向右一步向左和向右花的時間是同樣的，并且會占用一定時間。 如果條件判定指令時間比移令花的時間較少的話，應該上面兩種步法，后者比前者快。至此，咱們的問題已經得到解決。

作者：July。
出處：http://blog.csdn.net/v_JULY_v 。

前奏

    有關虛函數的問題層出不窮，有關虛函數的文章千篇一律，那為何還要寫這一篇有關虛函數的文章呢?看完本文后，相信能懂其意義之所在。同時，原狂想曲系列已經更名為程序員編程藝術系列，因為不再只專注于“面試”，而在“編程”之上了。ok，如果有不正之處，望不吝賜教。謝謝。

第一節、一道簡單的虛函數的面試題
題目要求：寫出下面程序的運行結果?

    我想，這道面試題應該是考察虛函數相關知識的相對簡單的一道題目了。然后，希望你碰到此類有關虛函數的面試題，不論其難度是難是易，都能夠舉一反三，那么本章的目的也就達到了。ok，請跟著我的思路，咱們步步深入（上面程序的輸出結果為A B）。

第二節、有無虛函數的區別
      1、當上述程序中的函數p()不是虛函數，那么程序的運行結果是如何?即如下代碼所示：

class A
{
public:
 void p() 
 { 
  cout << "A" << endl; 
 }
 
};

class B : public A
{
public:
 void p() 
 { 
  cout << "B" << endl;
 }
};

對的，程序此時將輸出兩個A，A。為什么?
我們知道，在構造一個類的對象時，如果它有基類，那么首先將構造基類的對象，然后才構造派生類自己的對象。如上，A* a=new A，調用默認構造函數構造基類A對象，然后調用函數p()，a->p();輸出A，這點沒有問題。
    然后，A * b = new B;，構造了派生類對象B，B由于是基類A的派生類對象，所以會先構造基類A對象，然后再構造派生類對象，但由于當程序中函數是非虛函數調用時，B類對象對函數p()的調用時在編譯時就已靜態確定了，所以，不論基類指針b最終指向的是基類對象還是派生類對象，只要后面的對象調用的函數不是虛函數，那么就直接無視，而調用基類A的p()函數。

      2、那如果加上虛函數呢?即如最開始的那段程序那樣，程序的輸出結果，將是什么?
在此之前，我們還得明確以下兩點：
    a、通過基類引用或指針調用基類中定義的函數時，我們并不知道執行函數的對象的確切類型，執行函數的對象可能是基類類型的，也可能是派生類型的。
    b、如果調用非虛函數，則無論實際對象是什么類型，都執行基類類型所定義的函數（如上述第1點所述）。如果調用虛函數，則直到運行時才能確定調用哪個函數，運行的虛函數是引用所綁定的或指針所指向的對象所屬類型定義的版本。

根據上述b的觀點，我們知道，如果加上虛函數，如上面這道面試題，

class A
{
public:
 virtual void p() 
 { 
  cout << "A" << endl; 
 }
 
};

class B : public A
{
public:
 virtual void p() 
 { 
  cout << "B" << endl;
 }
};

int main() 
{
 A * a = new A;
 A * b = new B;
 a->p();
 b->p();
 delete a;
 delete b;
    return 0;
}

 

那么程序的輸出結果將是A B。

所以，至此，咱們的這道面試題已經解決。但虛函數的問題，還沒有解決。

第三節、虛函數的原理與本質
    我們已經知道，虛（virtual）函數的一般實現模型是：每一個類（class）有一個虛表（virtual table），內含該class之中有作用的虛（virtual）函數的地址，然后每個對象有一個vptr，指向虛表（virtual table）的所在。

請允許我援引自深度探索c++對象模型一書上的一個例子：

class Point { 
public: 
   virtual ~Point();  

   virtual Point& mult( float ) = 0; 

   float x() const { return _x; }     //非虛函數，不作存儲
   virtual float y() const { return 0; }  
   virtual float z() const { return 0; }  
   // ...

protected: 
   Point( float x = 0.0 ); 
   float _x; 
};

      1、在Point的對象pt中，有兩個東西，一個是數據成員_x，一個是_vptr_Point。其中_vptr_Point指向著virtual table point，而virtual table（虛表）point中存儲著以下東西：

• virtual ~Point()被賦值slot 1，
• mult() 將被賦值slot 2.
• y() is 將被賦值slot 3
• z() 將被賦值slot 4.

class Point2d : public Point { 
public: 
   Point2d( float x = 0.0, float y = 0.0 )  
      : Point( x ), _y( y ) {} 
   ~Point2d();   //1

   //改寫base class virtual functions 
   Point2d& mult( float );  //2
   float y() const { return _y; }  //3

protected: 
   float _y; 
};

      2、在Point2d的對象pt2d中，有三個東西，首先是繼承自基類pt對象的數據成員_x，然后是pt2d對象本身的數據成員_y，最后是_vptr_Point。其中_vptr_Point指向著virtual table point2d。由于Point2d繼承自Point，所以在virtual table point2d中存儲著：改寫了的其中的~Point2d()、Point2d& mult( float )、float y() const，以及未被改寫的Point::z()函數。

class Point3d: public Point2d { 
public: 
   Point3d( float x = 0.0, 
            float y = 0.0, float z = 0.0 ) 
      : Point2d( x, y ), _z( z ) {} 
   ~Point3d();

   // overridden base class virtual functions 
   Point3d& mult( float ); 
   float z() const { return _z; }

   // ... other operations ... 
protected: 
   float _z; 
};

      3、在Point3d的對象pt3d中，則有四個東西，一個是_x，一個是_vptr_Point，一個是_y，一個是_z。其中_vptr_Point指向著virtual table point3d。由于point3d繼承自point2d，所以在virtual table point3d中存儲著：已經改寫了的point3d的~Point3d()，point3d::mult()的函數地址，和z()函數的地址，以及未被改寫的point2d的y()函數地址。

ok，上述1、2、3所有情況的詳情，請參考下圖。

本文，日后可能會酌情考慮增補有關內容。ok，更多，可參考深度探索c++對象模型一書第四章。
最近幾章難度都比較小，是考慮到狂想曲有深有淺的原則，后續章節會逐步恢復到相應難度。

第四節、虛函數的布局與匯編層面的考察

      ivan、老夢的兩篇文章繼續對虛函數進行了一番深入，我看他們已經寫得很好了，我就不饒舌了。ok，請看：1、VC虛函數布局引發的問題，2、從匯編層面深度剖析C++虛函數、http://blog.csdn.net/linyt/archive/2011/04/20/6336762.aspx。

第五節、虛函數表的詳解

    本節全部內容來自淄博的共享，非常感謝。注@molixiaogemao：只有發生繼承的時候且父類子類都有virtual的時候才會出現虛函數指針，請不要忘了虛函數出現的目的是為了實現多態。
 

 一般繼承（無虛函數覆蓋）
 下面，再讓我們來看看繼承時的虛函數表是什么樣的。假設有如下所示的一個繼承關系：

請注意，在這個繼承關系中，子類沒有重載任何父類的函數。那么，在派生類的實例中，

 對于實例：Derive d; 的虛函數表如下：

我們從表中可以看到下面幾點，
 1）覆蓋的f()函數被放到了虛表中原來父類虛函數的位置。
 2）沒有被覆蓋的函數依舊。
 
 這樣，我們就可以看到對于下面這樣的程序，
 Base *b = new Derive();

b->f();

由b所指的內存中的虛函數表的f()的位置已經被Derive::f()函數地址所取代，
于是在實際調用發生時，是Derive::f()被調用了。這就實現了多態。

多重繼承（無虛函數覆蓋）

下面，再讓我們來看看多重繼承中的情況，假設有下面這樣一個類的繼承關系（注意：子類并沒有覆蓋父類的函數）：

我們可以看到：
1） 每個父類都有自己的虛表。
2） 子類的成員函數被放到了第一個父類的表中。（所謂的第一個父類是按照聲明順序來判斷的）

這樣做就是為了解決不同的父類類型的指針指向同一個子類實例，而能夠調用到實際的函數。

多重繼承（有虛函數覆蓋）
下面我們再來看看，如果發生虛函數覆蓋的情況。
下圖中，我們在子類中覆蓋了父類的f()函數。

我們可以看見，三個父類虛函數表中的f()的位置被替換成了子類的函數指針。
這樣，我們就可以任一靜態類型的父類來指向子類，并調用子類的f()了。如：

Derive d;
Base1 *b1 = &d;
Base2 *b2 = &d;
Base3 *b3 = &d;
b1->f(); //Derive::f()
b2->f(); //Derive::f()
b3->f(); //Derive::f()
b1->g(); //Base1::g()
b2->g(); //Base2::g()
b3->g(); //Base3::g()

 

安全性
每次寫C++的文章，總免不了要批判一下C++。
這篇文章也不例外。通過上面的講述，相信我們對虛函數表有一個比較細致的了解了。
水可載舟，亦可覆舟。下面，讓我們來看看我們可以用虛函數表來干點什么壞事吧。

一、通過父類型的指針訪問子類自己的虛函數
我們知道，子類沒有重載父類的虛函數是一件毫無意義的事情。因為多態也是要基于函數重載的。
雖然在上面的圖中我們可以看到Base1的虛表中有Derive的虛函數，但我們根本不可能使用下面的語句來調用子類的自有虛函數：

Base1 *b1 = new Derive();
b1->g1(); //編譯出錯

任何妄圖使用父類指針想調用子類中的未覆蓋父類的成員函數的行為都會被編譯器視為非法，即基類指針不能調用子類自己定義的成員函數。所以，這樣的程序根本無法編譯通過。
但在運行時，我們可以通過指針的方式訪問虛函數表來達到違反C++語義的行為。
（關于這方面的嘗試，通過閱讀后面附錄的代碼，相信你可以做到這一點）

二、訪問non-public的虛函數
另外，如果父類的虛函數是private或是protected的，但這些非public的虛函數同樣會存在于虛函數表中，
所以，我們同樣可以使用訪問虛函數表的方式來訪問這些non-public的虛函數，這是很容易做到的。
如：

class Base {
private: 
 virtual void f() { cout << "Base::f" << endl; } 
};

class Derive : public Base{ 
};
typedef void(*Fun)(void);
void main() {
 Derive d;
 Fun pFun = (Fun)*((int*)*(int*)(&d)+0);
 pFun(); 
}

對上面粗體部分的解釋（@a && x）：

1. (int*)(&d)取vptr地址，該地址存儲的是指向vtbl的指針
2. (int*)*(int*)(&d)取vtbl地址，該地址存儲的是虛函數表數組
3. (Fun)*((int*)*(int*)(&d) +0)，取vtbl數組的第一個元素，即Base中第一個虛函數f的地址
4. (Fun)*((int*)*(int*)(&d) +1)，取vtbl數組的第二個元素（這第4點，如下圖所示）。

下圖也能很清晰的說明一些東西（@5）：

ok，再來看一個問題，如果一個子類重載的虛擬函數為privete，那么通過父類的指針可以訪問到它嗎？

#include <IOSTREAM>   
class B   
{    
public:    
    virtual void fun()      
    {     
        std::cout << "base fun called";     
    };    
};  

class D : public B    
{    
private:   
    virtual void fun()      
    {     
        std::cout << "driver fun called";    
    };    
};  

int main(int argc, char* argv[])   
{       
    B* p = new D();    
    p->fun();    
    return 0;    
}  
運行時會輸出 driver fun called

從這個實驗，可以更深入的了解虛擬函數編譯時的一些特征:
在編譯虛擬函數調用的時候，例如p->fun(); 只是按其靜態類型來處理的, 在這里p的類型就是B，不會考慮其實際指向的類型（動態類型）。
    也就是說，碰到p->fun();編譯器就當作調用B的fun來進行相應的檢查和處理。
因為在B里fun是public的，所以這里在“訪問控制檢查”這一關就完全可以通過了。
然后就會轉換成(*p->vptr[1])(p)這樣的方式處理, p實際指向的動態類型是D，
    所以p作為參數傳給fun后(類的非靜態成員函數都會編譯加一個指針參數，指向調用該函數的對象，我們平常用的this就是該指針的值）, 實際運行時p->vptr[1]則獲取到的是D::fun()的地址，也就調用了該函數, 這也就是動態運行的機理。

為了進一步的實驗，可以將B里的fun改為private的，D里的改為public的，則編譯就會出錯。
C++的注意條款中有一條" 絕不重新定義繼承而來的缺省參數值" 
（Effective C++ Item37， never redefine a function's inherited default parameter value) 也是同樣的道理。

可以再做個實驗
class B   
{    
public:   
    virtual void fun(int i = 1)      
    {     
        std::cout << "base fun called, " << i;     
    };    
};  

class D : public B    
{    
private:    
    virtual void fun(int i = 2)      
    {     
        std::cout << "driver fun called, " << i;     
    };    
}; 

 

 

則運行會輸出driver fun called, 1

 

關于這一點，Effective上講的很清楚“virtual 函數系動態綁定， 而缺省參數卻是靜態綁定”，
也就是說在編譯的時候已經按照p的靜態類型處理其默認參數了,轉換成了(*p->vptr[1])(p, 1)這樣的方式。 

補遺

   一個類如果有虛函數，不管是幾個虛函數，都會為這個類聲明一個虛函數表，這個虛表是一個含有虛函數的類的，不是說是類對象的。一個含有虛函數的類，不管有多少個數據成員，每個對象實例都有一個虛指針，在內存中，存放每個類對象的內存區，在內存區的頭部都是先存放這個指針變量的（準確的說，應該是：視編譯器具體情況而定），從第n（n視實際情況而定）個字節才是這個對象自己的東西。

 

下面再說下通過基類指針，調用虛函數所發生的一切：
One *p;
p->disp();

1、上來要取得類的虛表的指針，就是要得到，虛表的地址。存放類對象的內存區的前四個字節其實就是用來存放虛表的地址的。
2、得到虛表的地址后，從虛表那知道你調用的那個函數的入口地址。根據虛表提供的你要找的函數的地址。并調用函數；你要知道，那個虛表是一個存放指針變量的數組，并不是說，那個虛表中就是存放的虛函數的實體。

本章完。

 程序員編程藝術：第七章、求連續子數組的最大和 

作者：July。
出處：http://blog.csdn.net/v_JULY_v 。

前奏

• 希望更多的人能和我一樣，把本狂想曲系列中的任何一道面試題當做一道簡單的編程題或一個實質性的問題來看待，在閱讀本狂想曲系列的過程中，希望你能盡量暫時放下所有有關面試的一切包袱，潛心攻克每一道“編程題”，在解決編程題的過程中，好好享受編程帶來的無限樂趣，與思考帶來的無限激情。--By@July_____。
• 原狂想曲系列已更名為：程序員編程藝術系列。原狂想曲創作組更名為編程藝術室。編程藝術室致力于以下三點工作：1、針對一個問題，不斷尋找更高效的算法，并予以編程實現。2、解決實際中會碰到的應用問題，如第十章、如何給10^7個數據量的磁盤文件排序。3、經典算法的研究與實現。總體突出一點：編程，如何高效的編程解決實際問題。歡迎有志者加入。

第一節、求子數組的最大和
3.求子數組的最大和
題目描述：
輸入一個整形數組，數組里有正數也有負數。
數組中連續的一個或多個整數組成一個子數組，每個子數組都有一個和。
求所有子數組的和的最大值。要求時間復雜度為O(n)。

例如輸入的數組為1, -2, 3, 10, -4, 7, 2, -5，和最大的子數組為3, 10, -4, 7, 2，
因此輸出為該子數組的和18。

分析：這個問題在各大公司面試中出現頻率之頻繁，被人引用次數之多，非一般面試題可與之匹敵。單憑這點，就沒有理由不入選狂想曲系列中了。此題曾作為本人之前整理的微軟100題中的第3題，至今反響也很大。ok，下面，咱們來一步一步分析這個題：
      1、求一個數組的最大子數組和，如此序列1, -2, 3, 10, -4, 7, 2, -5，我想最最直觀也是最野蠻的辦法便是，三個for循環三層遍歷，求出數組中每一個子數組的和，最終求出這些子數組的最大的一個值。
記Sum[i, …, j]為數組A中第i個元素到第j個元素的和（其中0 <= i <= j < n），遍歷所有可能的Sum[i, …, j]，那么時間復雜度為O（N^3）：

//本段代碼引自編程之美
int MaxSum(int* A, int n)
{
 int maximum = -INF; 
 int sum=0;   
 for(int i = 0; i < n; i++)
 {
  for(int j = i; j < n; j++)
  {
   for(int k = i; k <= j; k++)
   {
    sum += A[k];
   }
   if(sum > maximum)
    maximum = sum;

   sum=0;   //這里要記得清零，否則的話sum最終存放的是所有子數組的和。也就是編程之美上所說的bug。多謝蒼狼。
  }
 }
 return maximum;
} 

      2、其實這個問題，在我之前上傳的微軟100題，答案V0.2版[第1-20題答案]，便直接給出了以下O（N）的算法：

      3、不少朋友看到上面的答案之后，認為上述思路2的代碼，沒有處理全是負數的情況，當全是負數的情況時，我們可以讓程序返回0，也可以讓其返回最大的那個負數，下面便是前幾日重寫的，修改后的處理全是負數情況（返回最大的負數）的代碼：

      4、DP解法的具體方程：@ flyinghearts：設sum[i] 為前i個元素中，包含第i個元素且和最大的連續子數組，result 為已找到的子數組中和最大的。對第i+1個元素有兩種選擇：做為新子數組的第一個元素、放入前面找到的子數組。
sum[i+1] = max(a[i+1], sum[i] + a[i+1])
result = max(result, sum[i])
 

擴展：
1、如果數組是二維數組，同樣要你求最大子數組的和列?
2、如果是要你求子數組的最大乘積列?
3、如果同時要求輸出子段的開始和結束列?

第二節、Data structures and Algorithm analysis in C

下面給出《Data structures and Algorithm analysis in C》中4種實現。

本章完。

作者：上善若水、July、yansha。
出處：http://blog.csdn.net/v_JULY_v 。

前奏
    本章陸續開始，除了繼續保持原有的字符串、數組等面試題之外，會有意識的間斷性節選一些有關數字趣味小而巧的面試題目，重在突出思路的“巧”，和“妙”。本章親和數問題之關鍵字，“500萬”，“線性復雜度”。

第一節、親和數問題
題目描述：
求500萬以內的所有親和數
如果兩個數a和b，a的所有真因數之和等于b,b的所有真因數之和等于a,則稱a,b是一對親和數。
例如220和284，1184和1210，2620和2924。

分析：
    首先得明確到底是什么是親和數?

親和數問題最早是由畢達哥拉斯學派發現和研究的。他們在研究數字的規律的時候發現有以下性質特點的兩個數：
220的真因子是：1、2、4、5、10、11、20、22、44、55、110；
284的真因子是：1、2、4、71、142。
而這兩個數恰恰等于對方的真因子各自加起來的和（sum[i]表示數i 的各個真因子的和），即
220=1+2+4+71+142=sum[284],
284=1+2+4+5+10+11+20+22+44+55+110=sum[220]。
得284的真因子之和sum[284]=220，且220的真因子之和sum[220]=284，即有sum[220]=sum[sum[284]]=284。

如此，是否已看出絲毫端倪?

如上所示，考慮到1是每個整數的因子，把出去整數本身之外的所有因子叫做這個數的“真因子”。如果兩個整數，其中每一個真因子的和都恰好等于另一個數，那么這兩個數，就構成一對“親和數”（有關親和數的更多討論，可參考這：http://t.cn/hesH09）。

求解：
    了解了什么是親和數，接下來咱們一步一步來解決上面提出的問題（以下內容大部引自水的原話，同時水哥有一句原話，“在你真正弄弄懂這個范例之前，你不配說你懂數據結構和算法”）。

1. 看到這個問題后，第一想法是什么？模擬搜索+剪枝？回溯？時間復雜度有多大？其中bn為an的偽親和數，即bn是an的真因數之和大約是多少？至少是10^13（@iicup：N^1.5 對于5*10^6 , 次數大致 10^10 而不是 10^13.）的數量級的。那么對于每秒千萬次運算的計算機來說，大概在1000多天也就是3年內就可以搞定了（iicup的計算: 10^13 / 10^7 =1000000(秒) 大約 278 小時. ）。如果是基于這個基數在優化，你無法在一天內得到結果的。
2. 一個不錯的算法應該在半小時之內搞定這個問題，當然這樣的算法有很多。節約時間的做法是可以生成伴隨數組，也就是空間換時間，但是那樣，空間代價太大，因為數據規模龐大。
3. 在稍后的算法中，依然使用的伴隨數組，只不過，因為題目的特殊性，只是它方便和巧妙地利用了下標作為伴隨數組，來節約時間。同時，將回溯的思想換成遞推的思想（預處理數組的時間復雜度為logN（調和級數）*N，掃描數組的時間復雜度為線性O（N）。所以，總的時間復雜度為O（N*logN+N）（其中logN為調和級數）  ）。

第二節、伴隨數組線性遍歷
依據上文中的第3點思路，編寫如下代碼：

第三節、程序的構造與解釋
    我再來具體解釋下上述程序的原理，ok，舉個例子，假設是求10以內的親和數，求解步驟如下：

因為所有數的真因數都包含1，所以，先在各個數的下方全部置1

1. 然后取i=2,3,4,5（i<=10/2），j依次對應的位置為j=（4、6、8、10），（6、9）,（8）,（10）各數所對應的位置。
2. 依據j所找到的位置，在j所指的各個數的下面加上各個真因子i（i=2、3、4、5）。
   整個過程，即如下圖所示（如sum[6]=1+2+3=6，sum[10]=1+2+5=8.）：
   1  2  3  4  5  6  7  8  9  10
   1  1  1  1  1  1  1  1  1  1
              2      2      2      2
                      3          3 
                              4
                                      5
3. 然后一次遍歷i從220開始到5000000，i每遍歷一個數后，
   將i對應的數下面的各個真因子加起來得到一個和sum[i]，如果這個和sum[i]==某個i’，且sum[i‘]=i，
   那么這兩個數i和i’，即為一對親和數。
4. i=2；sum[4]+=2，sum[6]+=2，sum[8]+=2，sum[10]+=2，sum[12]+=2...
   i=3，sum[6]+=3，sum[9]+=3...
   ......
5. i=220時，sum[220]=284，i=284時，sum[284]=220；即sum[220]=sum[sum[284]]=284，
   得出220與284是一對親和數。所以，最終輸出220、284，...

最小二乘法（又稱最小平方法）是一種數學優化技術。它通過最小化誤差的平方和尋找數據的最佳函數匹配。利用最小二乘法可以簡便地求得未知的數據，并使得這些求得的數據與實際數據之間誤差的平方和為最小。最小二乘法還可用于曲線擬合。其他一些優化問題也可通過最小化能量或最大化熵用最小二乘法來表達。

最小二乘法原理

在我們研究兩個變量(x, y)之間的相互關系時，通常可以得到一系列成對的數據( x₁, y₁.  x₂, y₂.  …    x_m , y_m )；將這些數據描繪在x -y直角坐標系中，若發現這些點在一條直線附近，可以令這條直線方程如(式1-1)。

Y_計= a₀ + a₁ X                      (式1-1)

其中：a₀、a₁ 是任意實數

為建立這直線方程就要確定a₀和a₁，應用 最小二乘法原理 ，將實測值Y_i與利用(式1-1)計算值(Y_計=a₀+a₁X)的離差(Y_i-Y_計)的平方和〔∑(Y_i - Y_計)²〕最小為“優化判據”。

令： φ = ∑(Y_i - Y_計)²                 (式1-2)

把(式1-1)代入(式1-2)中得:

φ = ∑(Y_i - a₀ - a₁ X_i)²                (式1-3)

當∑(Y_i-Y_計)平方最小時，可用函數 φ 對a₀、a₁求偏導數，令這兩個偏導數等于零。

亦即：

m a₀ + (∑X_i ) a₁ = ∑Y_i                          (式1-6)

(∑X_i ) a₀ + (∑X_i² ) a₁ = ∑(X_i, Y_i)                    (式1-7)

得到的兩個關于a₀、 a₁為未知數的兩個方程組，解這兩個方程組得出：

a₀ = (∑Y_i) / m - a₁(∑X_i) / m                             (式1-8)

a₁ = [m∑X_i Y_i - (∑X_i ∑Y_i)] / [m∑X_i² - (∑X_i)² )]                 (式1-9)

這時把a₀、a₁代入(式1-1)中， 此時的(式1-1)就是我們回歸的元線性方程即：數學模型。

在回歸過程中，回歸的關聯式是不可能全部通過每個回歸數據點( x₁, y₁.  x₂, y₂.  …    x_m , y_m ),為了判斷關聯式的好壞，可借助相關系數“R”，統計量“F”，剩余標準偏差“S”進行判斷；“R”越趨近于 1 越好；“F”的絕對值越大越好；“S”越趨近于 0 越好。

R = [∑X_iY_i - m (∑X_i / m)(∑Y_i / m)]/ SQR{[∑X_i² - m (∑X_i / m)²][∑Y_i² - m (∑Y_i / m)²]}        (式1-10) *

在(式1-1)中，m為樣本容量，即實驗次數；X_i、Y_i分別任意一組實驗X、Y的數值。

一般情況下是1024，我們也可以通過ulimit –n命令來查看最大文件打開數，如下：

1024

2、  修改目標

我們的目標是：讓每一個用戶登錄系統后系統打開的最大文件數都是我們設定好的。

但我這里不得不說的是：非常遺憾，網上很多這方面關于ulimit設置修改資源限制的文章，但沒一篇文章管用。

把這個目標分解為兩個目標：

2.1、設置對root用戶登錄系統生效

這個目標可以實現起來不難

2.2、設置對所有用戶生效

這個就非常麻煩了，弄不好還會把你的系統給整壞，因為要重編譯Linux的內核才行！

所以權衡之下，我只實現了第一個目標，因為第二個目標的風險太大，我想如果我之前知道這點，那么我在裝系統的時候我會先做這個處理，但現在我覺得已經晚了。

3、  修改的地方

3.1、修改/etc/security/limits.conf

通過 vi /etc/security/limits.conf修改其內容，在文件最后加入（數值也可以自己定義）：

* soft  nofile = 32768

* hard  nofile = 65536

3.2、修改/etc/profile

通過vi /etc/profile修改，在最后加入以下內容

ulimit -n 32768

然后重新登錄即可生效了。

說明：

其實只修改/etc/profile就可以生效了，但我還是建議把/etc/security/limits.conf也修改一下。

最后強調的是，你如果要使得修改對所有用戶都生效，那么現在看來你只能重新編譯Linux的內核才行。

轉自：http://www.zihou.me/html/2010/06/12/2281.html