算法合集之《類比思想在解題中的應(yīng)用》

1、類比思想在解題中的應(yīng)用【關(guān)鍵字】 思想；類比；相似性；對(duì)應(yīng)【摘要】： 類比，是一種試圖建立未知的問題與已知的問題之間的聯(lián)系，從而利用已知的解題方法去解決新的問題的思路。本文首先通過分析具體的例子，指出類比解題不僅僅是注意到了表面上的相似性，更是建立了已知問題和未知問題之間的對(duì)應(yīng)關(guān)系。然后，本文將通過另一個(gè)例子，論述表面相似性與內(nèi)在的對(duì)應(yīng)之間的關(guān)系，并且指出利用類比解題的過程是從表面相似性上升到一一對(duì)應(yīng)的過程。引：解題，從熟悉的地方開始 面對(duì)一個(gè)新的問題應(yīng)該如何著手去分析解決呢？ 從熟悉的地方開始著手。這是生活中人們常常采用的方法：希望面對(duì)的難題與以前解決過的某個(gè)問題是相同的，或者至少類似的；由

2、此就可以獲得值得借鑒的經(jīng)驗(yàn)。面對(duì)一個(gè)陌生的問題，試圖把它和某個(gè)熟悉的問題聯(lián)系起來，借助熟悉的知識(shí)和熟悉的方法來解決新問題，是自然的想法。 這種尋找未知問題和已知問題之間聯(lián)系的思想，可以稱為類比。更確切的說，“如果兩個(gè)系統(tǒng)的各自的各部分之間，存在某種一致的關(guān)系的話，則稱兩個(gè)系統(tǒng)是可以類比的。Page: 1” 引自參考書目i（數(shù)學(xué)與猜想）第二章。 如何理解定義中所說的“一致的關(guān)系”呢？ 如果只簡(jiǎn)單的把“存在某種一致的關(guān)系”理解成一種含糊的相似性。那么類比就完全歸結(jié)為人的主觀的感覺，這種主觀上的“似曾相識(shí)”是不能夠作為分析問題、解決問題的依據(jù)的。然而類比的思想的確被廣泛的應(yīng)用于解決各種問題，說明類比

3、的本質(zhì)是另一種比表面上的相似性更可靠和更有說服力的“一致關(guān)系”。事實(shí)上，類比是建立在兩個(gè)問題之間的一種一一對(duì)應(yīng)的映射關(guān)系。本文的第一部分，正是試圖闡述這一本質(zhì)上的“一致關(guān)系”。 然而兩個(gè)問題之間的本質(zhì)聯(lián)系并不是那么容易得到的。人們?cè)趯?duì)問題的最初的分析中，注意到的往往還是表面上（甚至只是文字上）的相似性。希望直接得到兩個(gè)問題之間相互對(duì)應(yīng)和相互轉(zhuǎn)化的關(guān)系是不現(xiàn)實(shí)的。因此，最初觀察到的表面上的相似性雖然有些不可靠，但是至少它能夠?yàn)榉治鰡栴}指出方向，由此嘗試著建立問題之間的對(duì)應(yīng)關(guān)系。正如本文第二部分將要闡述的，利用類比解題的過程是從模糊到清晰，從表面到本質(zhì)的分析過程。 接下來的兩個(gè)部分，就將探討類比過

4、程中，表面的相似和本質(zhì)的對(duì)應(yīng)之間的關(guān)系。類比的本質(zhì)，一一對(duì)應(yīng)的關(guān)系 類比作為一種分析問題的思想方法，目的是希望將不熟悉的知識(shí)轉(zhuǎn)化為熟悉的知識(shí)，將未知的問題轉(zhuǎn)化為已知的問題。 如何實(shí)現(xiàn)這一轉(zhuǎn)化，取決于如何對(duì)兩個(gè)問題進(jìn)行類比。如果僅考慮到兩個(gè)問題表面上的相似性，那么很可能會(huì)機(jī)械的模仿已知問題的解決方法，來解決新問題。這種想法缺乏嚴(yán)謹(jǐn)可靠的支持，難以保證在實(shí)際解題中能夠成功。即使成功了，也是知其然而不知其所以然，沒有發(fā)現(xiàn)問題之間本質(zhì)的聯(lián)系，往往得不到最好的解決方法。而當(dāng)類比過程中兩個(gè)問題之間存在一種對(duì)應(yīng)關(guān)系，未知問題中的所有描述對(duì)象和操作，在已知問題中都有與之一一對(duì)應(yīng)的內(nèi)容，那么整個(gè)未知的問題就可以

5、通過這種一一對(duì)應(yīng)的映射關(guān)系，轉(zhuǎn)化為已知的問題，也就可以應(yīng)用已知問題的解決方法來解決它。 下面的例子就是如此?！尽罢麛?shù)拆分”與“因數(shù)分解”】 整數(shù)拆分：將一個(gè)正整數(shù)n，拆分為一組小于n的正整數(shù)的和（不考慮這組正整數(shù)排列的先后次序）。求總共有多少組可能的拆分。 問題來自參考書目ii（算法設(shè)計(jì)）4.2.4。 這是一道眾所周知的組合計(jì)數(shù)問題。解決的方法有兩種： 利用遞歸的枚舉解題模型。(對(duì)應(yīng)程序名DIVIDE1.PAS) 將問題描述為：求滿足等式 的所有正整數(shù)組（a1，a2，a3，a4，am）的總數(shù)。為此，可以采用遞歸枚舉的方法逐個(gè)確定每一個(gè)ai從而求出所有的解，并統(tǒng)計(jì)總數(shù)。 設(shè)D(k,n)為將n拆分

6、成一組不小于k的正整數(shù)的和的解的數(shù)目。 例如，a1可以選取1n/2之間的任意整數(shù)，剩下的n-a1可以拆分成不小于a1的若干個(gè)整數(shù)的和。于是對(duì)于a1，有； 而對(duì)a2，有 由此不難得出問題的遞歸求解式 ; 問題的解等價(jià)于 ( 減一以除去n = n的拆分方案 )。 由于原問題只要給出解的總數(shù)，而這一算法在計(jì)算過程中求出了所有的解，所以枚舉算法的效率在n較大的時(shí)候是很低的。 母函數(shù)解題模型。(對(duì)應(yīng)程序名DIVIDE2.PAS) 設(shè)拆分的這組正整數(shù)中1出現(xiàn)的次數(shù)為x1，2出現(xiàn)的次數(shù)為x2，等等，那么問題可以描述為：求不定方程 的整數(shù)解的總數(shù)。于是就可以利用構(gòu)造母函數(shù)，來求不定方程的整數(shù)解的個(gè)數(shù)。方法如下

7、： 利用母函數(shù)計(jì)算不定方程整數(shù)解的總數(shù)的一般方法，請(qǐng)參見參考書目iii（組合數(shù)學(xué)及其在計(jì)算機(jī)科學(xué)中的應(yīng)用）。 拆分中不選取1可以表示為x0=1，取一個(gè)1表示為x，取兩個(gè)1為x*x=x2，取k個(gè)1為xk。由加法原理得到選取1的所有方案為 ； 不選取2可以表示為1，取一個(gè)2表示為x2，取兩個(gè)2為x2*x2=x4，取k個(gè)為x2k，由加法原理得到選取2的所有方案為 ； 同理，對(duì)于正整數(shù)r，選取k個(gè)表示為xk*r，由加法原理得到選取r的所有方案為 ； 再由乘法原理，同時(shí)選取1,2,n-1的方案可以表示為 由于要使最后的和等于n，所以g(x)展開式中的系數(shù)，就是問題的解。對(duì)于這類母函數(shù)，無法直接用通項(xiàng)公式

8、計(jì)算其展開式的系數(shù)，但是可以通過逐次進(jìn)行的多項(xiàng)式的乘法求解展開式。這在程序?qū)崿F(xiàn)中相當(dāng)于一個(gè)線性表的歸并算法，而計(jì)算過程中也不必求出方程實(shí)際的解，速度較上一種方法快得多。（程序和運(yùn)行效率的比較，請(qǐng)見附錄） 因數(shù)分解：將一個(gè)正整數(shù)n，分解為除1和它本身的因數(shù)的乘積的形式，不考慮因數(shù)的先后順序，求所有可能的分解方案的總數(shù)。 將一個(gè)正整數(shù)分成若干個(gè)正整數(shù)，這種表述是熟悉的。事實(shí)上，這和整數(shù)拆分中的表述是相似的。雖然兩個(gè)問題之間的區(qū)別是顯然的：一個(gè)是拆成乘積的形式；一個(gè)是拆成和的形式。但是兩個(gè)問題都是計(jì)算一個(gè)整數(shù)分成若干個(gè)整數(shù)的方案數(shù)目。 于是，在注意到了兩個(gè)問題表面上的相似后，確定“因數(shù)分解”的問題也

9、可以用枚舉法來解決。不妨著手模仿整數(shù)拆分的解題模型，將問題描述為：求滿足等式的所有正整數(shù)組（a1，a2，a3，a4，am）的總數(shù)?？梢园l(fā)現(xiàn)，兩個(gè)問題的描述是非常相似的，只是把加號(hào)換成了乘號(hào)?？梢灾苯幼鲞@樣的變換而不改動(dòng)其它內(nèi)容的關(guān)鍵在于：加法和乘法都滿足交換律和結(jié)合律。它們是兩種非常相似的運(yùn)算。由以上的描述出發(fā)，模仿“整數(shù)拆分”的D(k,n)，同樣可以定義F(k,n)為將n分解成一組不小于k的正整數(shù)的積的解的數(shù)目， 則容易推導(dǎo)出 ; 而 F(2,n)-1 就是問題的解。 由于采用的是枚舉法，在n的因子很多時(shí)，程序的速度是非常慢的。(對(duì)應(yīng)程序名P1.PAS) 以上的解題模型和“整數(shù)拆分”的方法是

10、出奇的類似的。然而，機(jī)械的模仿所能做到的也只有這些了。它無法解釋兩個(gè)問題為什么如此類似。 然而，有一點(diǎn)已經(jīng)被提了出來：兩者之所以是相似的，關(guān)鍵在于加法和乘法是相似的。那么加法和乘法之間，究竟是怎樣的關(guān)系呢？ 為了回答這個(gè)問題，要引入同構(gòu)的定義： 設(shè)有兩個(gè)集合A，B，“”和“”為分別定義在兩個(gè)集合上的（二元）運(yùn)算。那么稱A和運(yùn)算“”構(gòu)成一個(gè)代數(shù)系統(tǒng)A，B和運(yùn)算“”構(gòu)成代數(shù)系統(tǒng)B，。 如果存在一個(gè)一一對(duì)應(yīng)的映射，使得對(duì)于所有的xA，yA， 都有，則稱代數(shù)系統(tǒng)A，和B，是同構(gòu)的。 如果兩個(gè)代數(shù)系統(tǒng)是同構(gòu)的，那么顯然其中一個(gè)系統(tǒng)中的問題總可以轉(zhuǎn)化為另一個(gè)系統(tǒng)中的問題。 現(xiàn)在借助簡(jiǎn)單的中學(xué)知識(shí)，就可以知

11、道R，+與R+，*是同構(gòu)的： 設(shè)，則有恒有成立。 對(duì)數(shù)函數(shù)ln(x)就是把乘法轉(zhuǎn)化為加法的工具。 有了這些作為基礎(chǔ)，我們就可以很有信心的利用母函數(shù)解決因數(shù)分解問題。 首先假設(shè)整數(shù)n有除1和n以外因數(shù)共m個(gè)，為p1、p2、p3pm，而設(shè)每個(gè)因數(shù)pi在分解的式子中出現(xiàn)次數(shù)分別為xi，那么問題可以描述成：求方程 的非負(fù)整數(shù)解的數(shù)目。接著，利用ln(x)把乘法轉(zhuǎn)化為加法，對(duì)等式兩邊取對(duì)數(shù)，就得到對(duì)應(yīng)的線性方程；欲求它的非負(fù)整數(shù)解的個(gè)數(shù)，利用加法原理和乘法原理構(gòu)造母函數(shù)（推導(dǎo)過程參見“整數(shù)拆分”的相應(yīng)段落）， 則g(x)展開式的項(xiàng)的系數(shù)就是問題的解。與整數(shù)拆分的求解方法類似的，利用線性表的歸并算法，就可

12、以求出解來。(對(duì)應(yīng)程序名P2.PAS) 與遞歸枚舉算法相比，算法的效率同樣也大大的提高了。（程序和運(yùn)行效率的比較，請(qǐng)見附錄）如果僅僅憑借表面上觀察到的相似性，而不清楚乘法和加法代數(shù)系統(tǒng)之間存在著同構(gòu)的關(guān)系，是不容易得出利用母函數(shù)的解題模型的。這個(gè)例子中最有啟發(fā)性的，莫過于同構(gòu)概念的引入。為了說明兩個(gè)同構(gòu)的代數(shù)系統(tǒng)之間的關(guān)系，借助了一個(gè)一一映射，這個(gè)映射使兩個(gè)系統(tǒng)的不同運(yùn)算之間產(chǎn)生了一種對(duì)應(yīng)關(guān)系：；這樣A集合中關(guān)于運(yùn)算的每一個(gè)問題，都與B集合中關(guān)于運(yùn)算的一個(gè)問題相對(duì)應(yīng)。于是可以把A，中的問題轉(zhuǎn)化為B，中的問題來解決。實(shí)現(xiàn)這種轉(zhuǎn)化正是利用類比思想解題的目的，而尋找這種一一對(duì)應(yīng)的關(guān)系則是類比的實(shí)質(zhì)。

13、只要發(fā)現(xiàn)了這種一一對(duì)應(yīng)的關(guān)系，就能夠應(yīng)用解決已知問題的方法去解決新問題。同構(gòu)只是代數(shù)系統(tǒng)中的概念，然而對(duì)應(yīng)的關(guān)系可以應(yīng)用到其它問題中，因此用類比解題是不局限于代數(shù)系統(tǒng)之內(nèi)的。下面的例子就屬于另一個(gè)不同方面。目的是在進(jìn)一步說明類比的表象和它的本質(zhì)之間的關(guān)系。從表面的相似到內(nèi)在的對(duì)應(yīng) 類比的本質(zhì)是揭示已知問題與未知問題之間一一對(duì)應(yīng)的關(guān)系。但是，正如引言中說的，本質(zhì)往往不容易被發(fā)現(xiàn)，而表面的相似性卻首先被觀察到。所以，不應(yīng)該忽視表面的相似性；相反，應(yīng)該沿著相似性所指出的方向開始分析，嘗試發(fā)現(xiàn)問題之間的本質(zhì)聯(lián)系。 在分析下面這個(gè)例子的過程中，將著重說明這一點(diǎn)?！酒矫娣指羁臻g問題】 一個(gè)平面把空間分成獨(dú)

14、立的兩個(gè)部分，兩個(gè)平面把空間分成4個(gè)部分。n個(gè)平面，最多能把整個(gè)空間分割成多少個(gè)部分。 問題來自參考書目i（數(shù)學(xué)與猜想）第三章。 立體空間的情況是陌生的，而且不容易描述。雖然同樣是“分割”問題。但是正常情況下，不會(huì)把它和“整數(shù)拆分”聯(lián)系起來，因?yàn)閮烧咛幚淼膶?duì)象（整數(shù)和空間平面）是完全不同的。那么，究竟如何把這個(gè)問題和已知的知識(shí)聯(lián)系起來呢？這個(gè)時(shí)候，即使是表面的相似性，也能夠?yàn)榻忸}提供一條線索。 類比的目的是將未知的、復(fù)雜的東西化為已知的、簡(jiǎn)單的東西?？臻g上的問題是復(fù)雜的，而平面上的問題則是簡(jiǎn)單的。而且空間和平面的關(guān)系，與平面和直線的關(guān)系，是相似的。平面把空間分割成兩個(gè)部分，直線也把平面分割成兩

15、個(gè)部分。 于是得到了另一個(gè)與例題相類似的問題：n條直線，最多能把整個(gè)平面分割成多少個(gè)部分。 這實(shí)際上是本屆（第五屆）分區(qū)聯(lián)賽初賽的一道填空題。 這道題容易解決得多。它的解決方法是利用數(shù)學(xué)歸納法（如圖）：一條直線，把平面分割為兩個(gè)部分（A和B）；增加一條直線，它與第一條直線相交，被分為兩段射線，每一段射線又把所在的區(qū)域（例如A）分成兩部分（A1和A2）；因此增加了2個(gè)部分；共有2+2=4個(gè)部分。 再增加一條直線，它與前兩條直線相交，被分為三段，每一段又把所在區(qū)域（例如B1）分成兩部分(B11和B12)；總共增加了3個(gè)部分；共有4+3=7個(gè)部分； 由此類推，設(shè)前k-1條直線共把平面分為Ak-1個(gè)部

16、分。加入第k條直線，與前k-1條直線相交，被分為k段，每一段把所在區(qū)域分為兩部分；總共增加了k部分；總共有Ak-1+k個(gè)部分。 于是得到了遞推關(guān)系 A1=2； Ak=Ak-1+k； 由此不難計(jì)算出通項(xiàng)公式： ； 于是直線分割平面的問題就解決了。 解決這一問題對(duì)“平面分割空間問題”有何幫助？既然空間和平面，與平面和直線的關(guān)系相似，那么直接把平面換成空面，把直線換成平面，就可以直接用以上的過程來證明未知的問題了嗎？顯然是不可以的。這僅僅是根據(jù)主觀的相似得出的機(jī)械的模仿，是錯(cuò)誤的。 但是如果仔細(xì)分析一下錯(cuò)誤的原因，將會(huì)發(fā)現(xiàn)問題的關(guān)鍵：線線相交得到的是交點(diǎn)，面面相交得到的是直線，k個(gè)點(diǎn)把直線分成k+1

17、個(gè)部分，而k條直線則不是簡(jiǎn)單的把平面分成k+1個(gè)部分。 事實(shí)上，k條直線最多把平面分成 Ak個(gè)部分！ 因此兩個(gè)問題真正的相似之處在于，一個(gè)為了計(jì)算直線把平面分割成幾部分，先計(jì)算這條直線被點(diǎn)（線線交點(diǎn)）分割成幾部分，把二維的問題化為一維的問題；另一個(gè)要計(jì)算平面把空間分割成幾部分，先計(jì)算這個(gè)平面被線（面面交線）分割成幾部分，把三維的問題化為二維的問題。而二維的問題是已經(jīng)被解決了的；于是反過來，三維的問題也解決了。 同樣是利用數(shù)學(xué)歸納法： 一個(gè)平面把空間分割成兩部分； 設(shè)前k-1個(gè)平面共把空間分割成Bk-1個(gè)部分。加入第k個(gè)平面后，與前k-1個(gè)平面相交，共有k-1條交線。k-1條交線把這個(gè)平面被分為

18、幾個(gè)塊呢？這實(shí)際上就是剛剛解決過的問題：k-1條直線，把平面分割成部分。這塊平面，分別把所在原來空間一分為二，總共增加了個(gè)部分；于是，k個(gè)平面總共把空間分割成個(gè)部分。 于是得到了遞推關(guān)系 B1=2； 利用這一遞推關(guān)系來編寫程序，不難求出Bn，而且即便對(duì)很大的n，程序的運(yùn)算速度仍然是很快的。（當(dāng)然，也可以計(jì)算出Bn的通項(xiàng)公式，這實(shí)際上是一個(gè)二階等差數(shù)列的和：） 在這個(gè)例子中的一一對(duì)應(yīng)的關(guān)系，雖然不如同構(gòu)的概念中那么容易地用式子表達(dá)出來，但還是很清楚的：n個(gè)平面中的任意一個(gè)平面，截其它n-1個(gè)平面得到的所有n-1條交線，把這個(gè)平面分成An-1部分，而這正對(duì)應(yīng)于是第n個(gè)平面分割空間得到的增量?；蛘哒f

19、， ； 在這個(gè)例子中，最初找不到什么熟悉的類似問題，但是從簡(jiǎn)單和便于分析的角度著手，構(gòu)造了一個(gè)平面上的與之相似的問題。此時(shí)，相似性可以說是“立體”和“平面”的類比，這是非常模糊的。因?yàn)閹缀鯖]有確切的理由，能表明這樣的類比可以使問題相互轉(zhuǎn)化；這種相似性主要依據(jù)的是以往解決問題的經(jīng)驗(yàn)（化空間問題為平面問題，在中學(xué)的立體幾何中是經(jīng)常用到的手法），另一個(gè)原因則是為了簡(jiǎn)化問題。 接著，在解決平面的問題之后，面對(duì)的困難是：如何把解決平面上問題的經(jīng)驗(yàn)應(yīng)用到空間的問題中。如果僅僅根據(jù)表面的相似性，機(jī)械的模仿將導(dǎo)出一種錯(cuò)誤的方法。然而這種嘗試卻不是沒有價(jià)值的。通過比較正確的論證和錯(cuò)誤的論證之間的差別，原來的簡(jiǎn)單

20、而模糊的類比得到了完善和澄清：把“三維降低到二維的過程”和“二維降低到一維的過程”做類比。由此，兩個(gè)問題之間的聯(lián)系變得很清楚，于是得出了完整的推算過程。 事實(shí)上，這道例題的解決，和近年來不少三維的計(jì)數(shù)問題的思考方法是非常類似的：先考慮把二維化為一維的情況；再用相同的方法（類比），把三維的問題化為二維的問題來解決。這種策略被形象的稱為“降維”的策略。 CTSC99的論文隱蔽化、多維化、開放化（石潤(rùn)婷）中做了十分詳細(xì)的分析。 以上“因數(shù)分解”和“平面分割空間問題”的例子，都是借助類比解決的。而且在最初，都把探究問題之間的某種相似性作為分析問題的線索，這樣做的目的是希望能夠把未知的問題和熟悉的知識(shí)聯(lián)

21、系起來，以提供我們解決問題的可能性。然而正如在這兩個(gè)例子中見到的，這種從問題的表面上得出的相似性，往往不是本質(zhì)的，并且可能是有缺陷的。所以，這種表面現(xiàn)象上的類比只是為解題指出了可行的方向。為了最終能夠把未知的問題轉(zhuǎn)化為已知的問題，需要揭示兩個(gè)問題之間更深層的類比，即建立從一個(gè)問題到另一個(gè)問題的對(duì)應(yīng)關(guān)系。 在利用類比解題的整個(gè)過程中，表面的相似和內(nèi)在的對(duì)應(yīng)是緊密的聯(lián)系在一起的。相似性在淺層，對(duì)應(yīng)關(guān)系在深層。對(duì)應(yīng)關(guān)系是解決問題的關(guān)鍵，而發(fā)現(xiàn)對(duì)應(yīng)關(guān)系的途徑是從表面的相似性出發(fā)的?？偨Y(jié) 信息學(xué)競(jìng)賽涉及到大量的不同算法，對(duì)于每一種算法的特點(diǎn)和應(yīng)用技巧，老師和前輩們都已經(jīng)進(jìn)行了大量的分析和研究，并且總結(jié)出

22、了許多完整的理論。那么，在分析問題和解決問題的思路方面，是否也有一定的規(guī)律和方法呢？出于這樣的考慮，本文沒有就某種具體的算法進(jìn)行分析，而是希望能夠在分析問題的思想方法上有所探討。在這方面，許多數(shù)學(xué)上的技巧（例如構(gòu)造、化歸、歸納法）都是值得借鑒的，本文所主要分析的類比思想，也是其中之一。 本文的第一部分，通過利用類比解題的例子，首先指出僅僅表面的相似性并不能真正體現(xiàn)兩個(gè)問題之間的實(shí)質(zhì)性聯(lián)系；然后，從代數(shù)系統(tǒng)的同構(gòu)的定義中提取出類比的本質(zhì)，即兩個(gè)系統(tǒng)的各個(gè)部分之間一一對(duì)應(yīng)的關(guān)系。這種一一對(duì)應(yīng)的關(guān)系，使一個(gè)系統(tǒng)中的一個(gè)操作（運(yùn)算）對(duì)應(yīng)于另一個(gè)系統(tǒng)中的另一個(gè)操作（運(yùn)算）。由此，可以把關(guān)于一個(gè)陌生的系統(tǒng)

23、中的新問題，轉(zhuǎn)化為熟悉的問題來解決。 一一對(duì)應(yīng)的關(guān)系是類比本質(zhì)的一面，而主觀上的相似性則是類比的表象。同時(shí)，正如在本文的第二部分所闡述的，這兩者不是完全對(duì)立，而是互相聯(lián)系的。沒有主觀的相似性的引導(dǎo)，類比的本質(zhì)很難被發(fā)現(xiàn)。整個(gè)類比的過程，從含糊（主觀上的）的相似到清晰的（概念上的）對(duì)應(yīng)關(guān)系，把已知的問題與未知問題逐漸聯(lián)系起來，最后使兩個(gè)問題之間能夠互相轉(zhuǎn)化，從而把已知問題的解題模型應(yīng)用到未知問題的解決中去。 利用類比解題并不是某種固定的算法，而是分析問題時(shí)的一種思考方法，因此沒有什么定式，但也有規(guī)律可循。類比的目的，是希望化復(fù)雜的問題為簡(jiǎn)單的問題，化陌生的問題為熟悉的問題。為了實(shí)現(xiàn)這一轉(zhuǎn)化，最初

24、，可能是按照某種相似性，把兩個(gè)不同的問題聯(lián)系起來，并嘗試著模仿解決已知問題的方法，來解決新問題。在這一模仿的過程中，如果能夠明晰兩個(gè)問題之間存在的對(duì)應(yīng)關(guān)系，就能夠?qū)崿F(xiàn)兩個(gè)問題之間的轉(zhuǎn)化；否則，如果僅僅是機(jī)械的模仿，往往是難以解決問題的。 類比，是一種把已知的種種信息和知識(shí)，與陌生的問題聯(lián)系起來的思路。這既依靠選手解題時(shí)發(fā)散思維的能力，又取決于選手在平時(shí)的學(xué)習(xí)和訓(xùn)練中所接觸知識(shí)的深度和廣度；而類比解題的基礎(chǔ)也要求選手擁有與未知問題相類似的知識(shí)，這就需要選手在平時(shí)的學(xué)習(xí)和訓(xùn)練中既有扎實(shí)的基本功，又有廣泛的知識(shí)面。 因此，類比這種解題思路，對(duì)選手的要求正是“能力”+“基本功”。參考書目i. 數(shù)學(xué)與猜

25、想(Mathematics and plausible reasoning)，G·Polya著，李心燦、王日爽、李志堯譯，科學(xué)出版社，1984。ii. 算法設(shè)計(jì)，蔣新兒著，全國(guó)青少年計(jì)算機(jī)課外活動(dòng)輔導(dǎo)員培訓(xùn)教材編委會(huì)，1996。iii. 組合數(shù)學(xué)及其在計(jì)算機(jī)科學(xué)中的應(yīng)用，莊心谷，西安電子科技大學(xué)出版社，1989。附錄“整數(shù)拆分”問題利用不同算法的程序的效率比較： N 問題的解 遞歸枚舉算法(divide1.pas)的耗時(shí)(秒)利用母函數(shù)的多項(xiàng)式乘法算法(divide2.pas)的耗時(shí)(秒) 5 7 0.00 0.00 10 42 0.00 0.00 50 204226 0.05 0.

26、00 80 15796476 7.14 0.00 90 56634173 25 0.00 95 47 0.00 100 120 0.05“因數(shù)分解”問題不同算法的效率比較： N 問題的解 遞歸枚舉算法(p1.pas)的耗時(shí)（秒）利用母函數(shù)的多項(xiàng)式乘法(p2.pas)算法的耗時(shí)(秒) 12 3 0.00 0.00 24 6 0.00 0.00 1048576 626 0.05 0.05 9261000 27035 0.22 0.49 5603 0.33 0.11 558189 10.05 3.19 2787809 16.65 2.25 2756006 18.19 3.68 6348742 45.

27、12 4.84程序清單：DIVIDE1.PAS:PROGRAM Divide_1; 整數(shù)拆分的遞歸枚舉算法的程序 VAR n :INTEGER; total :LONGINT; 解的總數(shù) PROCEDURE init; 初始化，讀入n BEGIN readln(n); total:=0;END;PROCEDURE D(k,l:INTEGER); 遞歸過程 VAR i:INTEGER;BEGIN FOR i:=k TO l div 2 DO D(i,l-i); 把l-i拆分為不小于i的若干個(gè)整數(shù)的和 Inc(total); 若l不再拆分為更小的整數(shù)，則得到一個(gè)解 END; 主程序 BEGIN i

28、nit; 初始化 D(1,n); 把n拆分為不小于1的若干整數(shù)的和 writeln(total-1); 解的總數(shù)減一，除去n=n的拆分情況 END.DIVIDE2.PAS:PROGRAM Divide_2; 整數(shù)拆分的母函數(shù)算法的程序 VAR n :INTEGER; total :LONGINT; 解的總數(shù) PROCEDURE init; 初始化，讀入n BEGIN readln(n); total:=0;END;PROCEDURE work; 主過程 TYPE TForm = array0.1000 of LONGINT; 多項(xiàng)式類型，數(shù)組下標(biāo)對(duì)應(yīng)于冪指數(shù) VAR X1,X2 : TForm

29、; i,j,k : INTEGER;BEGIN fillchar(X1,sizeof(X1),0); FOR i:=0 TO n DO X1i:=1; X1 = 1+x+x2+x3+.+xn FOR i:=2 TO n-1 DO 以下計(jì)算X1*（1+xi+x2i+x3i+.+xn/i）暫時(shí)存入X2，再保存到X1 BEGIN X2:=X1; X2 = 1*X1 j:=i; WHILE (j<=n) DO BEGIN 以下計(jì)算X2= X2 + xj * X1 FOR k:=0 TO n DO X2k+j:=X2k+j+X1k; j:=j+i; END; X1:=X2; END; total:

30、=X1n; xn 的系數(shù)就是問題的解的總數(shù) END; 主程序 BEGIN init; 初始化 work; 求解 writeln(total); 輸出 END.P1.PAS:PROGRAM p1; 因數(shù)分解的遞歸枚舉算法的程序 VAR n : LONGINT; total : LONGINT; 解的總數(shù) PROCEDURE init; 初始化，讀入n BEGIN readln(n);END;PROCEDURE P(k,l:LONGINT); 遞歸過程 VAR i:LONGINT;BEGIN FOR i:=k TO Trunc(Sqrt(l) DO IF l mod i=0 THEN 如果i是l的

31、約數(shù) P(i,l div i); 把l/i分解成不小于i的若干個(gè)整數(shù)的積 inc(total); 若l不再分解成更小的整數(shù)，則得到一個(gè)解 END; 主過程 BEGIN init; 初始化 P(2,n); 把n分解為不小于2的若干個(gè)整數(shù)的積 writeln(total-1); 輸出解的總數(shù)減一，除去 n=n 的情況 END.P2.PAS:PROGRAM p2; 因數(shù)分解的母函數(shù)算法的程序 VAR n : LONGINT; total : LONGINT; 解的總數(shù) PROCEDURE init; 初始化，讀入n BEGIN readln(n);END;PROCEDURE work; 主過程 TY

32、PE TForm = array1.1500 of RECORD 多項(xiàng)式類型 s,exp:LONGINT; s為系數(shù)，exp為冪指數(shù)上ln(x)的自變量x END;VAR i : LONGINT; F1,F2,F3 : TForm; top1,top2,top3 : INTEGER; 對(duì)應(yīng)于多項(xiàng)式F1，F(xiàn)2，F(xiàn)3的長(zhǎng)度 PROCEDURE AddForm(p:LONGINT); 計(jì)算F1 = F1 * （1+xln(p)+x2ln(p)+x3ln(p)+. ） 對(duì)于多項(xiàng)式F1所有項(xiàng)xln（p），只保存滿足p是n約數(shù)的項(xiàng) VAR j,k,l,m:LONGINT; BEGIN j:=1; j = pi m:=n; WHILE m mod p=0 DO 當(dāng)m含有因子p，j*p是n的約數(shù)的時(shí)候 BEGIN m:=m div p; j:=j*p; 以下計(jì)算多項(xiàng)式 F1*xln(j)，并把它與F2歸并（暫存在F3中） l:=1; top3:=0; fi