《算法設(shè)計(jì)的基本方法實(shí)例》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《算法設(shè)計(jì)的基本方法實(shí)例（6頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、算法設(shè)計(jì)的基本方法實(shí)例 算法設(shè)計(jì)的基本方法 為用計(jì)算機(jī)解決實(shí)際問(wèn)題而設(shè)計(jì)的算法，即是計(jì)算機(jī)算法。 通常的算法設(shè)計(jì)有如下幾種： （1）列舉法 列舉法的基本思想是，根據(jù)提出的問(wèn)題，列舉出所有可能的情況，并用問(wèn)題中給定的條件檢驗(yàn)?zāi)男┦菨M(mǎn)足條件的，哪些是不滿(mǎn)足條件的。列舉法通常用于解決“是否存在”或“有哪些可能”等問(wèn)題。 例如，我國(guó)古代的趣味數(shù)學(xué)題：“百錢(qián)買(mǎi)百雞”、“雞兔同籠”等，均可采用列舉法進(jìn)行解決。 示例：百錢(qián)買(mǎi)百雞 公雞3元每只，母雞5元每只，小雞1元3只，一百元錢(qián)買(mǎi)一百只雞。請(qǐng)求出公雞，母雞和小雞的數(shù)目。 編程簡(jiǎn)析 我們做最極端的假設(shè)，公雞可能是0-100，母雞也可能是

2、0-100，小雞還可能是0-100，將這三種情況用循環(huán)套起來(lái)，那就是1000000種情況。這就是列舉法。為了將題目再簡(jiǎn)化一下，我們還可以對(duì)上述題目進(jìn)行一下優(yōu)化處理： 假設(shè)公雞數(shù)為x,母雞數(shù)為y，則小雞數(shù)是100-x-y，也就有了下面的方程式： 3*x+5*y+(100-x-y)/3=100 從這個(gè)方程式中，我們不難看出大體的情況：公雞最多有33只，最少是沒(méi)有，即x的范圍是0-33；母雞最多20只，最少0只，即母雞的范圍是0-20；有了公雞母雞，小雞數(shù)自然就是100-x-y只?？赡艿姆桨敢还灿?4*21種，在這么多的方案中，可能有一種或幾種正好符合相等的條件。 電腦怎樣工作呢？計(jì)算機(jī)

3、事實(shí)上就是將上述34*21種方案全部過(guò)濾一遍，找出符合百錢(qián)買(mǎi)百雞條件的（也即上式），只要符合，這就是我們要的輸出結(jié)果。 這就是列舉法，將可能的情況一網(wǎng)打盡；不過(guò)在應(yīng)用過(guò)程中，我們最好還是做些優(yōu)化，不然，要浪費(fèi)好多沒(méi)必要浪費(fèi)的時(shí)間。 使用列舉法時(shí)，要對(duì)問(wèn)題進(jìn)行詳細(xì)的分析，將與問(wèn)題有關(guān)的知識(shí)條理化、完備化、系統(tǒng)化，從中找出規(guī)律。 （2）歸納法 歸納法的基本思想是，通過(guò)列舉少量的特殊情況，經(jīng)過(guò)分析，最后找出一般的關(guān)系。歸納是一種抽象，即從特殊現(xiàn)象中找出一般規(guī)律。但由于在歸納法中不可能對(duì)所有的情況進(jìn)行列舉，因此，該方法得到的結(jié)論只是一種猜測(cè)，還需要進(jìn)行證明。 例如，使用歸納法在如下特殊的

4、命題中： 冰是冷的。 在擊打球桿的時(shí)候彈子球移動(dòng)。 推斷出普遍的命題如： 所有冰都是冷的，或： 在太陽(yáng)下沒(méi)有冰。 對(duì)于所有動(dòng)作，都有相同和相反的重做動(dòng)作。 人們?cè)跉w納時(shí)往往加入自己的想法，而這恰恰幫助了人們的記憶。 物理學(xué)研究方法之一。通過(guò)樣本信息來(lái)推斷總體信息的技術(shù)。要做出正確的歸納，就要從總體中選出的樣本，這個(gè)樣本必須足夠大而且具有代表性。 比如在我們買(mǎi)葡萄的時(shí)候就用了歸納法，我們往往先嘗一嘗，如果都很甜，就歸納出所有的葡萄都很甜的，就放心的買(mǎi)上一大串。 歸納推理也可稱(chēng)為歸納方法.完全歸納推理，也叫完全歸納法.不完全歸納推理，也叫不完全歸納法.歸納方法，還包括提高歸納前提

5、對(duì)結(jié)論確證度的邏輯方法，即求因果五法，求概率方法，統(tǒng)計(jì)方法，收集和整理經(jīng)驗(yàn)材料的方法等. （3）遞推 遞推，即是從已知的初始條件出發(fā)，逐次推出所要求的各個(gè)中間環(huán)節(jié)和最后結(jié)果。其中初始條件或問(wèn)題本身已經(jīng)給定，或是通過(guò)對(duì)問(wèn)題的分析與化簡(jiǎn)而確定。 遞推的本質(zhì)也是一種歸納，遞推關(guān)系式通常是歸納的結(jié)果。 例如，裴波那契數(shù)列，是采用遞推的方法解決問(wèn)題的。 1,1,2,3,5,8,13,21，。。。。。。。 遞推——猴子分食桃子 五只猴子採(cǎi)得一堆桃子，猴子彼此約定隔天早起後再分食。不過(guò)，就在半夜裏，一隻猴子偷偷起來(lái)，把桃子均分成五堆後，發(fā)現(xiàn)還多一個(gè)，它吃掉這桃子，並拿走了其中一堆

6、。第二隻猴子醒來(lái)，又把桃子均分成五堆後，還是多了一個(gè)，它也吃掉這個(gè)桃子，並拿走了其中一堆。第三隻，第四隻，第五隻猴子都依次如此分食桃子。那麼桃子數(shù)最少應(yīng)該有幾個(gè)呢？ 我們列方程求解：設(shè)原有桃子x個(gè)， 第一隻猴子吃掉1個(gè)桃子，再拿走餘下桃子的五分之一，剩下桃子數(shù)： 第二隻猴子吃掉1個(gè)桃子，再拿走餘下桃子的五分之一，剩下桃子數(shù)： 第三隻猴子吃掉1個(gè)桃子，再拿走餘下桃子的五分之一，剩下桃子數(shù)： 第三隻猴子吃掉1個(gè)桃子，再拿走餘下桃子的五分之一，剩下桃子數(shù)： 第四隻猴子吃掉1個(gè)桃子，再拿走餘下桃子的五分之一，剩下桃子數(shù)： 最後一隻猴子也吃掉1個(gè)桃子，再拿走餘下桃子

7、的五分之一﹔假設(shè)第五隻猴子拿走的桃子數(shù)是y個(gè)，則按題意可以列式得 經(jīng)過(guò)化簡(jiǎn)、整理，得? 256x－3125y=2101? ，其中 12y+8 是整數(shù)，所以 是整數(shù)。因?yàn)?3與256互質(zhì)，因此 y=255 時(shí)可滿(mǎn)足要求。這時(shí) x = 3121。原來(lái)問(wèn)題有無(wú)窮多解，上面求出的只是滿(mǎn)足條件的最小正整數(shù)解，也就是說(shuō)最少有桃子3121個(gè)。 以上是解不定元，此外，有一個(gè)巧思妙想的解法，：假若我們借來(lái)4個(gè)桃子，這樣桃子數(shù)就可以連續(xù)5次平均分成5堆了，所以桃子數(shù)最少應(yīng)該是55－4=3121(個(gè))。 （4）遞歸 在解決一些復(fù)雜問(wèn)題時(shí)，為了降低問(wèn)題的復(fù)雜程序，通常是將問(wèn)題逐層分解，最后歸結(jié)為一些最簡(jiǎn)單的問(wèn)題

8、。這種將問(wèn)題逐層分解的過(guò)程，并沒(méi)有對(duì)問(wèn)題進(jìn)行求解，而只是當(dāng)解決了最后的問(wèn)題那些最簡(jiǎn)單的問(wèn)題后，再沿著原來(lái)分解的逆過(guò)程逐步進(jìn)行綜合，這就是遞歸的方法。 遞歸分為直接遞歸和間接遞歸兩種方法。如果一個(gè)算法直接調(diào)用自己，稱(chēng)為直接遞歸調(diào)用；如果一個(gè)算法A調(diào)用另一個(gè)算法B，而算法B又調(diào)用算法A，則此種遞歸稱(chēng)為間接遞歸調(diào)用。 題目：有5個(gè)人坐在一起，問(wèn)第五個(gè)人多少歲？他說(shuō)比第4個(gè)人大2歲。問(wèn)第4個(gè)人歲數(shù)，他說(shuō)比第?3??? 　　　3個(gè)人大2歲。問(wèn)第三個(gè)人，又說(shuō)比第2人大兩歲。問(wèn)第2個(gè)人，說(shuō)比第一個(gè)人大兩歲。最后?4??問(wèn)第一個(gè)人，他說(shuō)是10歲。請(qǐng)問(wèn)第五個(gè)人多大？ ?5 ?6??? 1.程序分析：利用

9、遞歸的方法，遞歸分為回推和遞推兩個(gè)階段。要想知道第五個(gè)人歲數(shù)，需知道 ?7??? 　　　　　　第四人的歲數(shù)，依次類(lèi)推，推到第一人（10歲），再往回推。 ?8? */ ?9 #include 10 11 int age(int n) 12 { 13???? int c; 14 15???? if(n==1) 16???????? return 10; 17 18???? else 19???? { 20???????? c = age(n-1)+2; 21???????? return c; 22???? }??? 23 } 24 25 i

10、nt main() 26 { 27???? //int i; 28 29???? printf("his age is :%d\n",age(5)); 30 31???? //for(i=1;i<6;i++) 32???? //printf("the %d man is :%d\n",i,age(i)); 33 34???? return 0; 35 } （5）減半遞推技術(shù) 減半遞推即將問(wèn)題的規(guī)模減半，然后，重復(fù)相同的遞推操作。 例如，一元二次方程的求解。 （6）回溯法 有些實(shí)際的問(wèn)題很難歸納出一組簡(jiǎn)單的遞推公式或直觀的求解步驟，也不能使用無(wú)限的列舉。對(duì)于這類(lèi)問(wèn)題，只能采用試探的方法，通過(guò)對(duì)問(wèn)題的分析，找出解決問(wèn)題的線(xiàn)索，然后沿著這個(gè)線(xiàn)索進(jìn)行試探，如果試探成功，就得到問(wèn)題的解，如果不成功，再逐步回退，換別的路線(xiàn)進(jìn)行試探。這種方法，即稱(chēng)為回溯法。 如人工智能中的機(jī)器人下棋(八皇后問(wèn)題)。