算法設(shè)計(jì)的基本方法實(shí)例

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

2、，將這三種情況用循環(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只，最少是沒有，即x的范圍是0-33；母雞最多20只，最少 0只，即母雞的范圍是0-20；有了公雞母雞，小雞數(shù)自然就是 100-x-y只?？赡艿姆桨敢还灿?4*21種，在這么多的方案中， 可能有一種或幾種正好符合相等的條件。電腦怎樣工作呢？計(jì)算機(jī)事實(shí)上就是將上述34*21種方案 全部過(guò)濾一

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

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

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

6、此分食桃子。那麼桃子敷最少雁言亥有幾固呢？我仍列方程求解：言殳原有桃子x固，第一蔓猴子吃掉1固桃子，再拿走食余下桃子的五分之一，剩 下桃子數(shù)：第二蔓猴子吃掉1固桃子，再拿走余下桃子的五分之一，剩下桃子數(shù)：第三蔓猴子吃掉1固桃子，再拿走余下桃子的五分之一，剩下桃子數(shù):第三蔓猴子吃掉1彳固桃子，再拿走食余下桃子的五分之一，剩 下桃子數(shù):第四蔓猴子吃掉1固桃子，再拿走余下桃子的五分之一，剩 下桃子數(shù):最彳菱一蔓猴子也吃掉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。原來(lái)冏題有照穿多解，上面求出的 只是滿足倏件的最小正整敷解，也就是最少有桃子3121固。以上是解不定元，此外，有一固巧思妙想的解法，：假若我 仍借來(lái)4固桃子，逼檬桃子敷就可以速 5次平均分成5堆了， 所以桃子敷最少雁言亥是554=3121(固)。遞歸在解決一些復(fù)雜問題時(shí)，為了降低問題的復(fù)雜程序，通常是將問題逐層分解，最 后歸結(jié)為一些最簡(jiǎn)單的問題。這種將問題逐層分解的過(guò)程，并沒有對(duì)問題進(jìn)行求 解，而只是當(dāng)解決了最后的問題那些最簡(jiǎn)單的問題后

8、，再沿著原來(lái)分解的逆過(guò)程 逐步進(jìn)行綜合，這就是遞歸的方法。遞歸分為直接遞歸和間接遞歸兩種方法。如果一個(gè)算法直接調(diào)用自己，稱為直接 遞歸調(diào)用；如果一個(gè)算法A調(diào)用另一個(gè)算法B，而算法B又調(diào)用算法A，則此種 遞歸稱為間接遞歸調(diào)用。題目：有5個(gè)人坐在一起，問第五個(gè)人多少歲？他說(shuō)比第4個(gè)人大2歲。問第4個(gè)人歲數(shù)， 他說(shuō)比第33個(gè)人大2歲。問第三個(gè)人，又說(shuō)比第2人大兩歲。問第2個(gè)人，說(shuō)比第一個(gè)人大兩歲。最后4問第一個(gè)人，他說(shuō)是10歲。請(qǐng)問第五個(gè)人多大？ 51.程序分析：利用遞歸的方法，遞歸分為回推和遞推兩個(gè)階段。要想知道第五個(gè)人歲數(shù)， 需知道第四人的歲數(shù)，依次類推，推到第一人(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）減半遞推技術(shù) 減半遞推即將問題的規(guī)模減半，然后，重復(fù)相同的遞推操作。例如，一元二次方程的求解。（6）回溯法有些實(shí)際的問題很難歸納出一組簡(jiǎn)單的遞推公式