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

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

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

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

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

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

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

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

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

9、遞歸的方法，遞歸分為回推和遞推兩個階段。要想知道第五個人歲數(shù)，需知道 ?7??? 　　　　　　第四人的歲數(shù)，依次類推，推到第一人（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ù) 減半遞推即將問題的規(guī)模減半，然后，重復(fù)相同的遞推操作。 例如，一元二次方程的求解。 （6）回溯法 有些實(shí)際的問題很難歸納出一組簡單的遞推公式或直觀的求解步驟，也不能使用無限的列舉。對于這類問題，只能采用試探的方法，通過對問題的分析，找出解決問題的線索，然后沿著這個線索進(jìn)行試探，如果試探成功，就得到問題的解，如果不成功，再逐步回退，換別的路線進(jìn)行試探。這種方法，即稱為回溯法。 如人工智能中的機(jī)器人下棋(八皇后問題)。