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

《算法合集之《類比思想在解題中的應(yīng)用》》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、作者：張力1999.12.5類比思想在解題中的應(yīng)用第13頁共13頁類比思想在解題中的應(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è)新的問題

2、應(yīng)該如何著手去分析解決呢？從熟悉的地方開始著手。這是生活中人們常常采用的方法：希望面對(duì)的難題與以前解決過的某個(gè)問題是相同的，或者至少類似的；由此就可以獲得值得借鑒的經(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)系

3、”呢？如果只簡單的把“存在某種一致的關(guān)系”理解成一種含糊的相似性。那么類比就完全歸結(jié)為人的主觀的感覺，這種主觀上的“似曾相識(shí)”是不能夠作為分析問題、解決問題的依據(jù)的。然而類比的思想的確被廣泛的應(yīng)用于解決各種問題，說明類比的本質(zhì)是另一種比表面上的相似性更可靠和更有說服力的“一致關(guān)系”。事實(shí)上，類比是建立在兩個(gè)問題之間的一種一一對(duì)應(yīng)的映射關(guān)系。本文的第一部分，正是試圖闡述這一本質(zhì)上的“一致關(guān)系”。作者：張力1999.12.5類比思想在解題中的應(yīng)用第13頁共13頁然而兩個(gè)問題之間的本質(zhì)聯(lián)系并不是那么容易得到的。人們?cè)?/p>

4、對(duì)問題的最初的分析中，注意到的往往還是表面上（甚至只是文字上）的相似性。希望直接得到兩個(gè)問題之間相互對(duì)應(yīng)和相互轉(zhuǎn)化的關(guān)系是不現(xiàn)實(shí)的。因此，最初觀察到的表面上的相似性雖然有些不可靠，但是至少它能夠?yàn)榉治鰡栴}指出方向，由此嘗試著建立問題之間的對(duì)應(yīng)關(guān)系。正如本文第二部分將要闡述的，利用類比解題的過程是從模糊到清晰，從表面到本質(zhì)的分析過程。接下來的兩個(gè)部分，就將探討類比過程中，表面的相似和本質(zhì)的對(duì)應(yīng)之間的關(guān)系。類比的本質(zhì)，一一對(duì)應(yīng)的關(guān)系類比作為一種分析問題的思想方法，目的是希望將不熟悉的知識(shí)轉(zhuǎn)化為熟悉的知識(shí)，將未知的問

5、題轉(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è)未知的問題就可以通過這種一一對(duì)應(yīng)的映射關(guān)系，轉(zhuǎn)化為已知的問題，也就可以應(yīng)用已知問題的解

6、決方法來解決它。下面的例子就是如此。【“整數(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)為

7、將n拆分成一組不小于k的正整數(shù)的和的解的數(shù)目。例如，a1可以選取1…[n/2]之間的任意整數(shù)，剩下的n-a1可以拆分成不小于a1的若干個(gè)整數(shù)的和。于是對(duì)于a1，有；而對(duì)a2，有作者：張力1999.12.5類比思想在解題中的應(yīng)用第13頁共13頁由此不難得出問題的遞歸求解式;問題的解等價(jià)于(減一以除去n=n的拆分方案)。由于原問題只要給出解的總數(shù)，而這一算法在計(jì)算過程中求出了所有的解，所以枚舉算法的效率在n較大的時(shí)候是很低的。①母函數(shù)解題模型。(對(duì)應(yīng)程序名DIVIDE2.PAS)設(shè)拆分的這組正整數(shù)中1出現(xiàn)的次數(shù)為x

8、1，2出現(xiàn)的次數(shù)為x2，等等，那么問題可以描述為：求不定方程的整數(shù)解的總數(shù)。于是就可以利用構(gòu)造母函數(shù)，來求不定方程的整數(shù)解的個(gè)數(shù)。方法如下：利用母函數(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可以表