資源描述：
《算法合集之《淺談類比思想》_免費下載》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。
1、淺談類比思想長沙市長郡中學周戈林【目錄】摘要2關(guān)鍵字2止文2引言2常見的類比模式3具休事物類比抽象模型3相似算法之間的類比6圖形類比數(shù)式8總結(jié)10感謝10參考文獻10附錄11【摘要】信息學是一門變幻莫測的藝術(shù)，它包含著海量的知識點。我們不能奢求掌握所有的知識，只能在已有知識的基礎(chǔ)上，盡可能的把不熟悉的問題轉(zhuǎn)化為熟悉的問題。類比思想，就是一種非常優(yōu)秀的轉(zhuǎn)化方法。本文嘗試詮釋一些常用的類比模式?！娟P(guān)鍵字】類比思想模型算法理性認識【正文】一、引言：類比是最有創(chuàng)造力的一種思維方法。它關(guān)注兩個對彖在某些方面的相同或相似
2、，從而推測它們在其它方而也可能存在相同或相似Z處。舉例來說，我們在小學一年級學到止確的握鉛筆方法是“筆桿放在拇指、食指和中指的三個指梢z間。食指在前，拇指在左后，中指在右下，食指應較拇指低些，手指尖應距筆尖約3厘米。筆桿與作業(yè)木保持六十度的傾斜，掌心虛圓，指關(guān)節(jié)略彎曲”。學會了握鉛筆，那么在三年級也可以用類似的方法使用鋼筆書寫。概括一下，這次握筆類比的形式為：對象A具有性質(zhì)P、Q；對象A，具冇性質(zhì)卩（P與P類似）；對象A，可能具有性質(zhì)Q（Q與Q類似）。拿握筆來說，鉛筆（對象A）筆桿比較細（性質(zhì)P）,所以我們采
3、用上述“筆桿放在三個指梢Z間”的方法握筆（性質(zhì)Q）；I佃鋼筆（對彖A，）筆桿也比較細（性質(zhì)P'）,所以我們采用同樣的方法握筆（性質(zhì)Q'）。很幸運，這次類比是正確的，我們成功地學會了寫字。但有些吋候就沒那么幸運了，譬如說，當面對一支毛筆時，以上的握筆方法寫出的字就會產(chǎn)生相當?shù)挠哪Ч?。為什么我們的握筆方法面對毛筆失敗了呢？這是因為毛筆是軟筆，并且筆桿粗細不同，因此類比失敗了。正確的握毛筆方法是用拇指和食指捏住筆的上端，用中指和無名指活動筆的卜?端，小指隨無名指口然活動。概括這次握筆方法的轉(zhuǎn)換，就是：對象A具有性
4、質(zhì)P、Q和關(guān)系R；對象A，具有性質(zhì)對彖A，具有性質(zhì)Q，和關(guān)系R具體到握毛筆這個例子，鉛筆（對象A）是筆（性質(zhì)P）,并月.是硬筆（關(guān)系R）,需耍用三根手指托筆（性質(zhì)Q）。而毛筆同樣是筆（性質(zhì)P'）,但卻是軟筆（關(guān)系R）,只需要兩根手指夾筆（性質(zhì)Q9）o這種類比形式考慮到了性質(zhì)之間的關(guān)系，因此準確性提高了?？偨Y(jié)一下對握筆的研究：第一次握筆類比關(guān)鍵在于鉛筆和鋼筆恰好都是碩筆，因此其成功具冇偶然性，它是基丁直觀上的感性認識，稱Z為簡單類比；第二次握筆類比注意到鉛筆與毛筆的不同點，其成功帶有某種必然性，它是基于邏輯上
5、的理性認識，稱之為科學類比。在信息學競賽中需要的類比，往往是科學類比。下文將試圖論述一些常見的類比模式：具休事物類比抽象模型；相似算法之間的類比；圖形類比數(shù)式。二.常見的類比模式：2.1具體事物類比抽象模型：這是一種最常見的類比。現(xiàn)實事物不是嚴格的數(shù)學模型，在研究它們的過程屮必須根據(jù)需要捉煉相應的數(shù)學模型，否則便失去了建模的意義。在建模屮要聯(lián)想具體事物的固有屈性和抽象模型的獨有特點，才能恰如其分地建立模型和解決問題。舉例來說：研究地球的公轉(zhuǎn)可以把地球看成質(zhì)點，這是因為相對于公轉(zhuǎn)半徑來說地球半徑極其微小，可以忽
6、略。但是研究地球的自轉(zhuǎn)時乂不能忽略地球半徑,這是因為地球半徑比起質(zhì)點來又遠遠大得多了。從卜?面這個例了也可以看到，建模的角度不同，效果便截然不同。例一：山頂問題?題口描述奶牛成群、土地眾多的FJ有一個地形狹長的農(nóng)場，農(nóng)場被分成了"塊土地,拜不超過1000。這些土地位于一條直線上，并從左到右編號為1至m每塊土地的面積都相同，但是高度不一-定相同。每塊土地都擁冇一個海拔高度值，這個值不超過1000000o如果一段相同高度土地的兩邊都比它低或者是農(nóng)場的邊界，那么這段土地將被稱之為“山頂”。FJ希望通過搬走泥土來降低
7、某些土地的海拔高度，使“山頂”的數(shù)目不超過匕其中12W25。在這一前捉下，F(xiàn)J希望搬運的泥土體積最小，也就是所有的土地減少的高度和最小。?解法分析題口屮要求了一個很奇怪的“削平山頂”的任務(wù)。一個或幾個“山頂”往往由一個“山脊”支撐。值得注意的是，“山頂”被削平后有可能會使“山脊”變成“山頂”。從解題的一般感覺上看，這似乎是一道動態(tài)規(guī)劃的題目，嘗試著用動態(tài)規(guī)劃來解這道題目。根據(jù)一般的狀態(tài)設(shè)計方法，我們用彳力丿表示前i塊土地留丿個“山頂”的需要搬走泥土的最小體積。但是光用這兩個值無法完全描述出當前土地的高度，因此
8、也無法得知它們對以后狀態(tài)的影響。為了能準確表述土地的高度，我們需耍記錄一個描述高度的序列集合，但存儲這個集合的費用是讓人無法忍受的。換一種思維看問題，不妨把整個農(nóng)場180度翻轉(zhuǎn)，使“山頂”朝下。以下是翻轉(zhuǎn)樣例得到的圖形：―塊十?地按照高度被剖分成了最多n個層面，每個層面按照高度被染成了不同的顏色。當然，較高的層面需要較低的層面支撐。而如果一個層面兩邊的層面都比它低，那么就是“山頂”。把層面看作結(jié)點，
