1、數學思想助你一臂之力復旦大學附屬中學邵烜程2003年1月1 數學和計算機原本就是密不可分的學科。有許多計算機編程問題如果不利用數學思想則很難甚至無法達到預期的效果。 有些問題，利用這座橋可以更方便地往返于河兩岸，而還有一些問題，如果不利用這座橋，可能根本無法到達河對岸。問題編程實現 如果把問題和編程實現看成是河的兩岸，那么數學思想就是連接河兩岸的一座橋梁，有了這座橋，從河的一岸到另一岸便不再是件難事了。2 也就是說，有些問題利用數學思想可以走捷徑（例如NOI2002的“荒島野人”），而還有一些問題，如果不利用數學思想，就根本無法解決（例如NOI2002的“機器人M號”）。今天，我們將從四個方面

2、探討利用數學思想提高算法效率，簡化問題的例子：利用數學思想直接找出解的一般規律利用數學模型化繁為簡通過數學分析化未知為已知利用數學結論優化算法3一利用數學思想直接找出解的一般規律 有些問題，如果直接用動態規劃或是圖論的方法來解決效率可能會并不理想；這時，我們首先應該想到的是優化，而如果優化無法達到預期的效果，那我們只有重新尋找算法了。于是，我們就試圖找出問題的一般規律、或是該問題所用到的一個小問題的一般規律，這樣，時間效率將會大大提高。 我們首先來看一個直接找出原問題的一般規律的例子4例題一 最優分解方案 把正整數N分解成若干個互不相等的自然數的和，且使這些自然數的乘積最大。 輸入 只有一行，

3、包括數N（3=N=1000）。 輸出 第一行輸出最優分解方案，相鄰兩數之間用單個空格隔隔開；第二行輸出最大的乘積。5算法分析 初看本題，發覺很顯然可以用動態規劃解決，但我們并不滿足直覺告訴我們，應該可以找到最優分解方案的一般規律，而一旦找到，時間效率將大大提高。 我們的直覺告訴我們，將N分解成的m個數應盡量接近，而且m應該盡量得大。 更一般地說，就是把N寫成連續自然數2，3，k之和（當然，由于自然數1不影響乘積，自然不將其加入），然后，將剩下的數依次平均分配到k，k-1，s上，讓這些數都加1。例如，當N=55時由于55=2+3+101，將多余的1分配到10上，就得到 552389116 對于一

4、些較小的數，我們發覺這個猜想是完全正確的。這促使我們躍躍欲試：證明這個猜想的正確性。 我們先來明確一下拆分方案的幾種情況：N=23s（s2）k（如N=55)N=34k（如122343345）N=34k（k2）（如132344346） 由此，我們可以把證明過程分為四步：7 實際上，對每一步的證明過程并不難。總的來說，是利用反證法和調整的思想先假設命題不正確，然后構造出另一列和為N的自然數，但乘積更大，從而導出矛盾。下面簡單說一下每一步的證明：89 至此，我們的問題應該已經得到了圓滿的解答。 讓我們再回顧一下解題過程，對于較原始的動態規劃算法，我們覺得里面顯然有許多不必要的計算，從而提出：能否直接

5、導出一般規律？通過大膽的猜想和嚴密的證明，這一點得到了肯定，而算法的時間復雜度也從動態規劃的O(N2），下降到了現在的O(N)。而這一切都應該歸功于數學思想的大膽和合理的應用。10二利用數學模型化繁為簡。 能夠對原題導出數學結論無疑是最直接地運用了數學思想，而在很多情況下，往往沒有那么簡單。在有些實際應用中，我們需要將原來的實際問題抽象成數學模型，然后加以解決。而在某些程序設計競賽的試題中，建立數學模型也需要一定的技巧，需要運用一定的數學思想。 下面，我們來考慮一個利用數學思想“建模”的例子11例題二 三角形燈塔 有一個N行（0N=50）的三角形燈塔，它的第1行有1個燈，第2行有2個燈，第N行

6、有N個燈。我們用（I，j）表示從上至下第i行，從左至右第j個燈。 每個燈有明、暗兩種狀態，第i行（1=IN）的任一個燈（I，j）的狀態由下一行的兩個燈（I+1，j）和（I1，j1）的狀態決定（1=j=0）個燈的狀態出發，推出最底一行N個燈的所有可能的狀態總數。12輸入 第一行行首為三角形燈塔的行數N，從第2行開始每行為一個已知狀態的編號為（I，j）的燈的信息（1=I=N，1=j0）個未知數，則由于隨意確定其中的p-1個未知數的值，都將唯一確定另一個的值，故解數為2p-1。15 這樣，我們就找到了一個較為高效的算法。 在本題中，我們先是由燈的亮暗所遵循的規律發覺了一個較為一般的遞推關系，而下面一

7、步才是非常關鍵的把遞推關系中的邏輯運算轉換成數學運算，這一步，為我們構造方程組這一數學模型提供了極大的方便，使問題迎刃而解。 數學思想在本題的應用，使我們方便地構造出了數論模型，使問題圓滿地解決。16三. 通過數學分析化未知為已知。 有些構造性地問題本身就是由數學問題衍生而來，但正因為問題的“構造性”，使這類問題的解法讓人捉摸不透，很難想到。在這種情況下，我們可以試著先從數學的角度分析問題，若能得出對問題直接有益的結論則是最好，如果不能，我們也可以從分析問題的過程中啟發思維，從而巧妙地構造算法。 下面來看一個具體的例子體會一下數學分析對解題的幫助17例題三 配鎖問題 某機要部門安裝了電子鎖。M

8、個工作人員每人發一張磁卡，卡上有開鎖的密碼特征。為了確保安全，規定至少要有N個人同時使用各自的磁卡才能將鎖打開，并且任意N個人在一起都能將鎖打開。現在需要你計算一下，電子鎖上至少要有多少種特征，每個人的磁卡上至少有幾個特征。如果特征的編號用從1開始的自然數表示，將每個人的磁卡的特征編號打印出來。要求輸出的電子鎖的總特征數最少。 為了使問題簡單，規定： 3=M=7，1=N=4，N=M18算法分析輸入 只有一行，包括兩個由空格隔開的正整數M，N。輸出 輸出包括M行，第i行有若干個遞增的正整數，表示第i個工作人員所持磁卡上的全部特征的編號。 初看本題，也許會覺得毫無思路，但我們肯定能意識到：“至少要

9、有N個人同時使用各自的磁卡才能將鎖打開，并且任意N個人在一起都能將鎖打開”，這個條件是本題的突破口。19 讓我們先利用這個條件進行一番分析： 由于“至少要有N個人同時使用各自磁卡才能將鎖打開”，意即任意N-1個人在一起，都無法將鎖打開，從而必然缺少一種開鎖的密碼特征A；并且在其余的M-（N-1）個人中，任意一人加入到N-1個人中，他們就能將鎖打開，故這其余的M-（N-1）個人必同時擁有密碼特征A。而容易證明：每N-1個人在一起，他們缺少的一種密碼特征A不能和其他一組N-1個人一起缺少的密碼特征相同（否則，由于這兩組至少有N個不同的人，且他們都缺少密碼特征A，故這些至少N個人在一起無法將鎖打開，

10、矛盾）。從而電子鎖上特征數tot應滿足20 另外，對于每一個工作人員T來說，在其余M-1個人中，任選N-1個人在一起，都會因為缺少某種特征而無法開鎖，而這缺少的特征必須是T所具備的。故每個工作人員的磁卡上的特征數per應滿足 在上面的證明過程中，我們最感興趣的并不是得到的結論（因為本題要求打印方案，故tot和per的值完全可以在打印過程中累加），而是在證明的“過程”中用到的：“每N-1個人都缺少一種密碼特征，而每M-（N-1）=M-N+1個人都同時具備該密碼特征，并且這個密碼特征對從M個人中選出不同的M-N+1個人的組合來說是不同的”。這句話為我們打開了思路，由此，一個有效算法便應運而生了21

11、 初始時，特征數置為1，在M個人中每選取M-N+1個人的組合，就為組合中每個工作人員配備當前特征，并將特征數+1。這樣，枚舉出了所有的組合后，便得出了所有工作人員磁卡上特征的方案了。 在本題中，我們通過數學分析，盡管也得出了結論，但由于本題要求輸出所有方案，它的用處并不大，但分析過程中所用到的一個思路卻直接導致了算法的形成。如果沒有進行數學分析，或者沒有考慮到這一思路，本題似乎就很難完成了。22四利用數學結論優化算法。 在上面的例題中，我們清晰地看到：數學思想的 火花孕育了解題的算法。綜合上面的三個例題，數學方法、思想的巧妙使用，破解了一個個難題。最后，我們將通過一個并不難的搜索題，通過優化前

12、和優化后算法時間效率的比較，來體會一下數學在優化算法方面的應用。23例題四 骨牌覆蓋問題 對于任意一個m*n的矩陣，求L形骨牌覆蓋后所剩方格數最少的一個方案。 下圖為L形骨牌的八種形態：輸入 輸入包括一行，有由空格隔開的正整數m，n，表示矩陣的大小。24輸出 輸出是一個m*n的矩陣，矩陣中元素的值表示該格所在的骨牌編號（若該格不被骨牌覆蓋，則值為0），骨牌編號為從1開始的連續正整數。算法分析 對于搜索題，我們應該把注意力集中在優化算法上。對于本題，顯然在回溯搜索時，不能讓已經“浪費”了的方格數太多，這樣再繼續搜索下去也是做無用功，于是我們就需要一個“浪費”方格數的上界，也就是最優方案中，最多能

13、覆蓋的骨牌數目的下界；而事實上，我們完全可以求出它的確切值。25 下面將簡單證明這個引理，而對于最大值能夠取到，也是可以用數學歸納法證明的，由于時間關系，這里從略。2627 由此，我們得到了優化后算法的大致流程（回溯法）： 自左而右、自上而下搜索每一個方格的覆蓋情況，如果可以以該方格為左上角放置骨牌，則試著放置該骨牌，設置相應的方格被覆蓋標志；然后設置該方格不被覆蓋標志，搜索下一方格。搜索過程中，一旦已經產生的空格數超出空格數的上界，則回溯。 對比優化前和優化后算法的時效，我們發現，由于加入了檻值，使得優化后的算法減少了很多不必要的搜索，算法的效率自然提高了不少。 本題給了我們這樣的啟示：數學思想不僅僅能直接提供解題思路和方法，在更多的場合，它只是以一種輔助工具的形式出現