算法設計的基本方法實例

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

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

3、遍，找出符合百錢買百雞條件的（也即上式），只要 符合，這就是我們要的輸出結果。這就是列舉法，將可能的情況一網打盡；不過在應用過程中， 我們最好還是做些優(yōu)化，不然，要浪費好多沒必要浪費的時間。使用列舉法時，要對問題進行詳細的分析，將與問題有關的知識條理化、完備化、 系統化，從中找出規(guī)律。（2）歸納法歸納法的基本思想是，通過列舉少量的特殊情況，經過分析，最后找出一般的關 系。歸納是一種抽象，即從特殊現象中找出一般規(guī)律。但由于在歸納法中不可能 對所有的情況進行列舉，因此，該方法得到的結論只是一種猜測，還需要進行證 明。例如，使用歸納法在如下特殊的命題中：冰是冷的。在擊打球桿的時候彈子球移動。推斷出普

4、遍的命題如：所有冰都是冷的，或：在太陽下沒有冰。對于所有動作，都有相同和相反的重做動作。人們在歸納時往往加入自己的想法，而這恰恰幫助了人們的記憶。物理學研究方法之一。通過樣本信息來推斷總體信息的技術。要做出正確的歸納， 就要從總體中選出的樣本，這個樣本必須足夠大而且具有代表性。比如在我們買葡萄的時候就用了歸納法，我們往往先嘗一嘗，如果都很甜， 就歸納出所有的葡萄都很甜的，就放心的買上一大串。歸納推理也可稱為歸納方法.完全歸納推理，也叫完全歸納法.不完全歸納推理， 也叫不完全歸納法.歸納方法，還包括提高歸納前提對結論確證度的邏輯方法， 即求因果五法，求概率方法，統計方法，收集和整理經驗材料的方法

5、等.遞推遞推，即是從已知的初始條件出發(fā)，逐次推出所要求的各個中間環(huán)節(jié)和最后結果。 其中初始條件或問題本身已經給定，或是通過對問題的分析與化簡而確定。遞推的本質也是一種歸納，遞推關系式通常是歸納的結果。例如，裴波那契數列，是采用遞推的方法解決問題的。1,1,2,3,5,8,13,21，。遞推一猴子分食桃子五只猴子探得一堆桃子，猴子彼此青勺定隔天早起彳度再分食。 不遏，就在半夜裹，一蔓猴子偷偷起來，把桃子均分成五堆彳度， 畿現遢多一彳固，它吃掉逼桃子，業(yè)拿走了其中一堆。第二蔓猴子 醒來，又把桃子均分成五堆彳度，遢是多了一固，它也吃掉逼固桃 子，業(yè)拿走了其中一堆。第三蔓，第四蔓，第五蔓猴子都依次如

6、此分食桃子。那麼桃子敷最少雁言亥有幾固呢？我仍列方程求解：言殳原有桃子x固，第一蔓猴子吃掉1固桃子，再拿走食余下桃子的五分之一，剩 下桃子數：第二蔓猴子吃掉1固桃子，再拿走余下桃子的五分之一，剩下桃子數：第三蔓猴子吃掉1固桃子，再拿走余下桃子的五分之一，剩下桃子數:第三蔓猴子吃掉1彳固桃子，再拿走食余下桃子的五分之一，剩 下桃子數:第四蔓猴子吃掉1固桃子，再拿走余下桃子的五分之一，剩 下桃子數:最彳菱一蔓猴子也吃掉1固桃子，再拿走余下桃子的五分之一 ；假言殳第五蔓猴子拿走的桃子敷是y固，則按題意可以列式得*保45-州+蜓化筒、整理，得256x_3125y + 2101 招，5淪 + 1卜312

7、5y=2101， 瓦 12y其中 12y+8 是整53(y+l)敷，所以二k是整敷。因舄53輿256互，因此y=255日寺 可滿足要求。逼日寺x = 3121。原來冏題有照穿多解，上面求出的 只是滿足倏件的最小正整敷解，也就是最少有桃子3121固。以上是解不定元，此外，有一固巧思妙想的解法，：假若我 仍借來4固桃子，逼檬桃子敷就可以速 5次平均分成5堆了， 所以桃子敷最少雁言亥是554=3121(固)。遞歸在解決一些復雜問題時，為了降低問題的復雜程序，通常是將問題逐層分解，最 后歸結為一些最簡單的問題。這種將問題逐層分解的過程，并沒有對問題進行求 解，而只是當解決了最后的問題那些最簡單的問題后

8、，再沿著原來分解的逆過程 逐步進行綜合，這就是遞歸的方法。遞歸分為直接遞歸和間接遞歸兩種方法。如果一個算法直接調用自己，稱為直接 遞歸調用；如果一個算法A調用另一個算法B，而算法B又調用算法A，則此種 遞歸稱為間接遞歸調用。題目：有5個人坐在一起，問第五個人多少歲？他說比第4個人大2歲。問第4個人歲數， 他說比第33個人大2歲。問第三個人，又說比第2人大兩歲。問第2個人，說比第一個人大兩歲。最后4問第一個人，他說是10歲。請問第五個人多大？ 51.程序分析：利用遞歸的方法，遞歸分為回推和遞推兩個階段。要想知道第五個人歲數， 需知道第四人的歲數，依次類推，推到第一人(10歲)，再往回推。*/#include10int age(int n)int c;14if(n=1)return 10;17else TOC o 1-5 h z c = age(n-1)+2;return c;24int main()/int i;2829 printf(his age is :%dn,age(5);30/for(i=1;i6;i+)/printf(the %d man is :%dn,i,age(i);33return 0;（5）減半遞推技術 減半遞推即將問題的規(guī)模減半，然后，重復相同的遞推操作。例如，一元二次方程的求解。（6）回溯法有些實際的問題很難歸納出一組簡單的遞推公式