算法設計的基本方法實例 算法設計的基本方法 為用計算機解決實際問題而設計的算法，即是計算機算法。 通常的算法設計有如下幾種： （1）列舉法 列舉法的基本思想是，根據(jù)提出的問題，列舉出所有可能的情況，并用問題中給定的條件檢驗哪些是滿足條件的，哪些是不滿足條件的。列舉法通常用于解決“是否存在”或“有哪些可能”等問題。 例如，我國古代的趣味數(shù)學題：“百錢買百雞”、“雞兔同籠”等，均可采用列舉法進行解決。 示例：百錢買百雞 公雞3元每只，母雞5元每只，小雞1元3只，一百元錢買一百只雞。請求出公雞，母雞和小雞的數(shù)目。 編程簡析 我們做最極端的假設，公雞可能是0-100，母雞也可能是0-100，小雞還可能是0-100，將這三種情況用循環(huán)套起來，那就是1000000種情況。這就是列舉法。為了將題目再簡化一下，我們還可以對上述題目進行一下優(yōu)化處理： 假設公雞數(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只。可能的方案一共有34*21種，在這么多的方案中，可能有一種或幾種正好符合相等的條件。 電腦怎樣工作呢？計算機事實上就是將上述34*21種方案全部過濾一遍，找出符合百錢買百雞條件的（也即上式），只要符合，這就是我們要的輸出結(jié)果。 這就是列舉法，將可能的情況一網(wǎng)打盡；不過在應用過程中，我們最好還是做些優(yōu)化，不然，要浪費好多沒必要浪費的時間。 使用列舉法時，要對問題進行詳細的分析，將與問題有關的知識條理化、完備化、系統(tǒng)化，從中找出規(guī)律。 （2）歸納法 歸納法的基本思想是，通過列舉少量的特殊情況，經(jīng)過分析，最后找出一般的關系。歸納是一種抽象，即從特殊現(xiàn)象中找出一般規(guī)律。但由于在歸納法中不可能對所有的情況進行列舉，因此，該方法得到的結(jié)論只是一種猜測，還需要進行證明。 例如，使用歸納法在如下特殊的命題中： 冰是冷的。 在擊打球桿的時候彈子球移動。 推斷出普遍的命題如： 所有冰都是冷的，或： 在太陽下沒有冰。 對于所有動作，都有相同和相反的重做動作。 人們在歸納時往往加入自己的想法，而這恰恰幫助了人們的記憶。 物理學研究方法之一。通過樣本信息來推斷總體信息的技術。要做出正確的歸納，就要從總體中選出的樣本，這個樣本必須足夠大而且具有代表性。 比如在我們買葡萄的時候就用了歸納法，我們往往先嘗一嘗，如果都很甜，就歸納出所有的葡萄都很甜的，就放心的買上一大串。 歸納推理也可稱為歸納方法.完全歸納推理，也叫完全歸納法.不完全歸納推理，也叫不完全歸納法.歸納方法，還包括提高歸納前提對結(jié)論確證度的邏輯方法，即求因果五法，求概率方法，統(tǒng)計方法，收集和整理經(jīng)驗材料的方法等. （3）遞推 遞推，即是從已知的初始條件出發(fā)，逐次推出所要求的各個中間環(huán)節(jié)和最后結(jié)果。其中初始條件或問題本身已經(jīng)給定，或是通過對問題的分析與化簡而確定。 遞推的本質(zhì)也是一種歸納，遞推關系式通常是歸納的結(jié)果。 例如，裴波那契數(shù)列，是采用遞推的方法解決問題的。 1,1,2,3,5,8,13,21，。。。。。。。 遞推——猴子分食桃子 五只猴子採得一堆桃子，猴子彼此約定隔天早起後再分食。不過，就在半夜裏，一隻猴子偷偷起來，把桃子均分成五堆後，發(fā)現(xiàn)還多一個，它吃掉這桃子，並拿走了其中一堆。第二隻猴子醒來，又把桃子均分成五堆後，還是多了一個，它也吃掉這個桃子，並拿走了其中一堆。第三隻，第四隻，第五隻猴子都依次如此分食桃子。那麼桃子數(shù)最少應該有幾個呢？ 我們列方程求解：設原有桃子x個， 第一隻猴子吃掉1個桃子，再拿走餘下桃子的五分之一，剩下桃子數(shù)： 第二隻猴子吃掉1個桃子，再拿走餘下桃子的五分之一，剩下桃子數(shù)： 第三隻猴子吃掉1個桃子，再拿走餘下桃子的五分之一，剩下桃子數(shù)： 第三隻猴子吃掉1個桃子，再拿走餘下桃子的五分之一，剩下桃子數(shù)： 第四隻猴子吃掉1個桃子，再拿走餘下桃子的五分之一，剩下桃子數(shù)： 最後一隻猴子也吃掉1個桃子，再拿走餘下桃子的五分之一﹔假設第五隻猴子拿走的桃子數(shù)是y個，則按題意可以列式得 經(jīng)過化簡、整理，得  256x－3125y=2101  ，其中 12y+8 是整數(shù)，所以 是整數(shù)。因為53與256互質(zhì)，因此 y=255 時可滿足要求。這時 x = 3121。原來問題有無窮多解，上面求出的只是滿足條件的最小正整數(shù)解，也就是說最少有桃子3121個。 以上是解不定元，此外，有一個巧思妙想的解法，：假若我們借來4個桃子，這樣桃子數(shù)就可以連續(xù)5次平均分成5堆了，所以桃子數(shù)最少應該是55－4=3121(個)。 （4）遞歸 在解決一些復雜問題時，為了降低問題的復雜程序，通常是將問題逐層分解，最后歸結(jié)為一些最簡單的問題。這種將問題逐層分解的過程，并沒有對問題進行求解，而只是當解決了最后的問題那些最簡單的問題后，再沿著原來分解的逆過程逐步進行綜合，這就是遞歸的方法。 遞歸分為直接遞歸和間接遞歸兩種方法。如果一個算法直接調(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.程序分析：利用遞歸的方法，遞歸分為回推和遞推兩個階段。要想知道第五個人歲數(shù)，需知道  7    　　　　　　第四人的歲數(shù)，依次類推，推到第一人（10歲），再往回推。  8  */  9 #include<stdio.h> 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 int 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）減半遞推技術 減半遞推即將問題的規(guī)模減半，然后，重復相同的遞推操作。 例如，一元二次方程的求解。 （6）回溯法 有些實際的問題很難歸納出一組簡單的遞推公式或直觀的求解步驟，也不能使用無限的列舉。對于這類問題，只能采用試探的方法，通過對問題的分析，找出解決問題的線索，然后沿著這個線索進行試探，如果試探成功，就得到問題的解，如果不成功，再逐步回退，換別的路線進行試探。這種方法，即稱為回溯法。 如人工智能中的機器人下棋(八皇后問題)。