六種常用算法

六種常用算法有條不紊 遞推法破解難題問：“我對(duì)數(shù)據(jù)結(jié)構(gòu)有了一定了解，但還是不太懂程序。從經(jīng)典公式“程序=算法+數(shù)據(jù)結(jié)構(gòu)”得知，是因?yàn)椴涣私馑惴āＤ懿荒芙榻B幾種簡(jiǎn)單的算法，當(dāng)然從最容易懂的那種開始了？”答：“算法就是能夠證明正確的解題步驟，算法有許多種，最簡(jiǎn)單的無非下面的六種：遞推法、貪心法、列舉法、遞歸法、分治法和模擬法。剛聽名字挺嚇人的，其實(shí)有好多程序我們平常都見過。這些算法當(dāng)中，最最簡(jiǎn)單的莫過于遞推算法了。下面舉例說明?！笔裁词沁f推法遞推法這種解題方法其實(shí)在我們編程的過程中用的很多，只不過沒有將其上升到理論的高度罷了。所謂遞推法，就是找出和時(shí)間先后相聯(lián)系或和數(shù)的大小相聯(lián)系的步驟，上一步和下一步和數(shù)字的增大或減小有一定的聯(lián)系。我們要么從前向后（或從小到大）推導(dǎo)，也可從后向前（或從大到小）推導(dǎo)。由此得出兩種推導(dǎo)方法：順推法和倒推法。請(qǐng)看下面的示例。示例：猴子分食桃子五只猴子采得一堆桃子，猴子彼此約定隔天早起后再分食。不過，就在半夜里，一只猴子偷偷起來，把桃子均分成五堆后，發(fā)現(xiàn)還多一個(gè)，它吃掉這桃子，并拿走了其中一堆。第二只猴子醒來，又把桃子均分成五堆后，還是多了一個(gè)，它也吃掉這個(gè)桃子，并拿走了其中一堆。第三只，第四只，第五只猴子都依次如此分食桃子。那么桃子數(shù)最少應(yīng)該有幾個(gè)呢？編程簡(jiǎn)析怎樣編程呢？先要找一下第N只猴子和其面前桃子數(shù)的關(guān)系。如果從第1只開始往第5只找，不好找，但如果思路一變，從第N到第1去，可得出下面的推導(dǎo)式：第N只猴第N只猴前桃子數(shù)目5 s5=x4 s4=s5*5/4+13 s3=s4*5/4+12 s2=s3*5/4+11 s1=s2*5/4+1si即為所求。上面的規(guī)律中只要將s1-s5的下標(biāo)去掉：s=xs=s*5/4+1s=s*5/4+1s=s*5/4+1s=s*5/4+1所以可以用循環(huán)語(yǔ)句加以解決。綜觀程序的整體結(jié)構(gòu)，最外是一個(gè)循環(huán)，因?yàn)檠h(huán)次數(shù)不定，可以使用While循環(huán)，其結(jié)束條件則是找到第一個(gè)符合條件的數(shù)。為了做出上面while循環(huán)的結(jié)束條件，還需進(jìn)一步分析上述規(guī)律的特點(diǎn)，要符合題目中的要求，s1-s4四個(gè)數(shù)必須全部為整數(shù)，這個(gè)可作為條件。具體實(shí)現(xiàn)請(qǐng)參看源程序。語(yǔ)言、界面、源程序（1）語(yǔ)言程序中通過VirualBASIC6.0語(yǔ)言來實(shí)現(xiàn)。界面界面非常簡(jiǎn)單，建立一標(biāo)準(zhǔn)EXE工程，其caption設(shè)為“猴子分食桃子”，一切OK。我們將代碼加給Form_Click()即窗體的單擊事件，將來運(yùn)行時(shí)，我們只要用鼠標(biāo)單擊一下窗體，程序就執(zhí)行了。源程序OptionExplicitPrivateSubForm_Click()Dimx,s,k,iAsInteger'聲明變量x=6k=0'整除標(biāo)志W(wǎng)hilek<>4s=x'第5只猴子時(shí)總數(shù)k=0Fori=4To1Step-1'第4-1只時(shí)的數(shù)量s=s*5/4+1IfInt(s)=sThen'符合情況則將整除標(biāo)志加1k=k+1EndIfNextix=x+5'第次增5WendPrints'輸出EndSub（上程序在VB60Win2000下調(diào)試通過）小結(jié)上面應(yīng)用的推導(dǎo)方法就是倒推法。生活中的更多問題采用順推法就可得到，也即從1-N，但不論倒推還是順推，能遞推出并解出問題是我們的本意。穩(wěn)扎穩(wěn)打 貪心法破解難題問：“算法除了遞推法，該輪到貪心法了吧，從字面上理解，這種方法有些貪得無厭還是…？”答：“基本算法中的遞推法是我們最常使用的，貪心法是另一種有意思的算法。貪心法不僅僅是貪婪，而且是每一步都貪婪！下面舉例說明。”什么是貪心法貪心法就是做一種目前最貪婪的行動(dòng)，一步步解決問題。貪心法和遞推法有相似之外，也是從問題的某一個(gè)初始解出發(fā)，向給定的目標(biāo)遞推，但不同的是每一步不是依據(jù)某一個(gè)固定的遞推式，而是做一個(gè)當(dāng)時(shí)看似最佳的貪心選擇，不斷地將問題歸結(jié)為更小的相似的問題。示例：刪數(shù)問題鏈盤輸入一個(gè)高精度的數(shù)N,去掉任意S個(gè)數(shù)字后剩下的數(shù)字按原左右次序組成一個(gè)新的正整數(shù)，編程對(duì)于給定的N和S，尋找一種方案使得剩下的數(shù)字組成的新數(shù)最小。為了便于操作，將N做為字符串的形式輸入，可以使用盡可能逼近目標(biāo)的貪心算法來完成，刪數(shù)的過程中是一個(gè)一個(gè)進(jìn)行刪除的，為了保證最后得到的數(shù)最小，每一步總是要?jiǎng)h除使剩下的數(shù)最小的數(shù)字。之所以做出這樣貪心的選擇，是因?yàn)閯hS個(gè)數(shù)字的最優(yōu)解，包含了刪除一個(gè)數(shù)字的子問題的最優(yōu)解。為了實(shí)現(xiàn)上述目的，我們可以進(jìn)行S次選擇，每次都選擇N中最大的數(shù)字，此數(shù)字選擇后將不再參與下次的選擇。具體實(shí)現(xiàn)請(qǐng)看源程序。語(yǔ)言、界面、源程序（1） 語(yǔ)言程序中通過VirualBASIC6.0語(yǔ)言來實(shí)現(xiàn)。（2） 界面界面非常簡(jiǎn)單，建立一標(biāo)準(zhǔn)EXE工程，其caption設(shè)為“刪數(shù)問題”。放入三個(gè)文本框和兩個(gè)按鈕，文本框起到輸入兩個(gè)數(shù)和輸出結(jié)果的作用，按鈕用來控制執(zhí)行，再放入三個(gè)標(biāo)簽起到說明的作用。（3） 源程序PrivateSubCmdDelnum_Click（）'開始刪數(shù)按鈕DimiAsIntegerDimjAsIntegerDimnAsString'原數(shù)DimsAsInteger'刪數(shù)的個(gè)數(shù)DimnlengthAsInteger'N的長(zhǎng)度Dima()AsInteger'放位數(shù)數(shù)組DimkAsInteger'記錄最大值位置TxtOutput.Text=""n=TxtNum.Texts=Val(TxtS.Text)nlength=Len(n)ReDima(nlength-1)'將各位的值放入數(shù)組Fori=0Tonlength-1a(i)=Mid(n,i+1,1)Nexti'執(zhí)行貪心算法s步Forj=1Tosk=0Fori=1Tonlength-jIfa(k)<a(i)Thenk=iEndIfNextid=a(k)Fori=kTonlength-1-ja(i)=a(i+1)Nextia(nlength-j)=dNextj'輸出結(jié)果Fori=nlength-1Tonlength-sStep-1'刪數(shù)過程TxtOutput.Text=TxtOutput.Text+"刪除的第”+Str(nlength-i)+"個(gè)數(shù)”+Str(a(i))+vbCr+vbLfNexti'最后的數(shù)Fori=0Tonlength-s-1TxtOutput.Text=TxtOutput.Text+Str(a(i))NextiEndSub(上程序在VB60Win2000下調(diào)試通過)小結(jié)這就是有趣的貪心算法，說是貪得無厭可以，說是守住當(dāng)前的既得利益，以此為基礎(chǔ)，再穩(wěn)扎穩(wěn)打地進(jìn)行下一步也行！滴水不漏一列舉法破解難題問：“列舉法是種什么樣子的算法呢？”答：咧舉法是比貪心法還要貪得多的算法，歹U舉法也是一種比較笨但卻很有效的算法，他想要的東東，一種情況他都不想落下，大有寧可錯(cuò)殺一千，不可放過一個(gè)的陣勢(shì)。下面舉例說明。”什么是列舉法列舉是針對(duì)問題所有的可能一一查看是不是符合條件，有些“寧肯錯(cuò)殺一千，不可放過一個(gè)”的作風(fēng)。下面的老題最能說明這種情況。示例：百錢買百雞公雞3元每只，母雞5元每只，小雞1元3只，一百元錢買一百只雞。請(qǐng)求出公雞，母雞和小雞的數(shù)目。編程簡(jiǎn)析我們做最極端的假設(shè)，公雞可能是0-100，母雞也可能是0-100，小雞還可能是0-100，將這三種情況用循環(huán)套起來，那就是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只。可能的方案一共有34*21種，在這么多的方案中，可能有一種或幾種正好符合相等的條件。電腦怎樣工作呢？計(jì)算機(jī)事實(shí)上就是將上述34*21種方案全部過濾一遍，找出符合百錢買百雞條件的(也即上式)，只要符合，這就是我們要的輸出結(jié)果。程序?qū)崿F(xiàn)我們?cè)鯓訉⑦@34*21種方案羅列出呢？這么多的方案，最好的辦法是還是用循環(huán)。可用循環(huán)和循環(huán)的嵌套，一個(gè)關(guān)于公雞數(shù)和一個(gè)關(guān)于母雞數(shù)的循環(huán)套起來，就能將所有的方案都遍歷。后面的問題成了怎樣判斷哪一個(gè)方案是我們尋找的符合條件和方案呢？只能根據(jù)百錢買百雞了，即3*x+5*y+(100-x-y)/3=100作為條件，在條件成立的一方輸出x,y,和100-x-y的值就行了，這是分支要解決的問題，程序的整體結(jié)構(gòu)有了，兩個(gè)嵌套循環(huán)中套分支。界面源程序界面非常簡(jiǎn)單，建立一標(biāo)準(zhǔn)EXE工程，其caption設(shè)為“百錢買百雞”，一切OK。我們將代碼加給Form_Click()，即窗體的單擊事件，將來運(yùn)行時(shí)，我們只要用鼠標(biāo)單擊一下窗體，程序就執(zhí)行了。源程序如下：OptionExplicitPrivateSubForm_Click()Dimx,yAsInteger'聲明變量Forx=0To33Fory=0To20If3*x+5*y+(100-x-y)/3=100ThenPrint"公雞，母雞和小雞數(shù)分別為：”;x,y,100-x-yEndIfNextyNextxEndSub(上程序在VB60Win2000下調(diào)試通過)題目的結(jié)果有多組，正和我們剛開始的所想相符。小結(jié)這就是列舉法，將可能的情況一網(wǎng)打盡；不過在應(yīng)用過程中，我們最好還是做些優(yōu)化，不然，要浪費(fèi)好多沒必要浪費(fèi)的時(shí)間。鏡里照鏡一遞歸法破解難題問：“前幾種辦法的確名如其法，比較笨。有沒有比較瀟灑一點(diǎn)的算法？遞歸屬不屬于些類算法呀？”答：“遞歸一種非常奇妙和美妙的算法形式，奇妙美妙的背后是比較難理解。但用起來卻異常簡(jiǎn)潔?！笔裁词沁f歸說白了遞歸就象我們講的那個(gè)故事：山上有座廟，廟里有個(gè)老和尚，老和尚在講故事，它講的故事是：山上有座廟，廟里有個(gè)老和尚，老和尚在講故事，它講的故事是：......也就是直接或間接地調(diào)用了其自身。就象上面的故事那樣，故事中包含了故事本身。因?yàn)閷?duì)自身進(jìn)行調(diào)用，所以需對(duì)程序段進(jìn)行包裝，也就出現(xiàn)了函數(shù)。函數(shù)的利用是對(duì)數(shù)學(xué)上函數(shù)定義的推廣，函數(shù)的正確運(yùn)用有利于簡(jiǎn)化程序，也能使某些問題得到迅速實(shí)現(xiàn)。對(duì)于代碼中功能性較強(qiáng)的、重復(fù)執(zhí)行的或經(jīng)常要用到的部分，將其功能加以集成，通過一個(gè)名稱和相應(yīng)的參數(shù)來完成，這就是函數(shù)或子程序，使用時(shí)只需對(duì)其名字進(jìn)行簡(jiǎn)單調(diào)用就能來完成特定功能。函數(shù)又可分為自定義的和系統(tǒng)附帶的，但不管是自定義的還是系統(tǒng)的，他們都對(duì)相應(yīng)的功能進(jìn)行了封裝，以利于我們經(jīng)常性地使用。例如我們的對(duì)一個(gè)小數(shù)取整數(shù)INT()函數(shù)，不論什么樣的小數(shù)，往()中一放，將來得到的值就自動(dòng)將小數(shù)去除了。函數(shù)執(zhí)行完將返回一個(gè)值，當(dāng)然這個(gè)值可以是各種類型的，子程序僅僅執(zhí)行一個(gè)過程，不返回?cái)?shù)值。函數(shù)和子程序是執(zhí)行遞歸的干將。示例：小猴吃棗小猴第一天摘下若干棗子，當(dāng)即吃掉了一半，不過癮又多吃了一個(gè)；第二天吃了剩下的一半又多吃了一個(gè)；以后每一天都吃了前一天剩下的一半多一個(gè)。到第十天小猴再想吃時(shí)，見到只剩下一只棗子了。問第一天這堆棗子有多少？從上題中我們可看到一個(gè)令人欣喜的規(guī)律，第十天為1，第九到第一天中后一天與1的和的兩倍與前一天相等。下面就對(duì)這一規(guī)律做了描述：PrivateFunctionmonkey(ByValxAsInteger)AsIntegerIfx>=10Thenmonkey=1Elsemonkey=2*(monkey(x+1)+1)EndIfEndFunction我們定義monkey()函數(shù)的時(shí)候通過monkey()自身來進(jìn)行了定義，這就是遞歸。遞歸是個(gè)特殊的循環(huán)，是一個(gè)有著非常美妙的循環(huán)規(guī)則的循環(huán)。上題中我們只要將monkey(1)，即第一天打印出來，一切OK。而這中間究竟是怎么工作的，我們可以不管。正是有了monkey()函數(shù)，在對(duì)其自身調(diào)用的過程中實(shí)現(xiàn)了我們的所求，關(guān)于函數(shù)、子程序和他們之間發(fā)生的故事還有很多，僅僅列舉了其中奇妙的幾點(diǎn)，還有許多東東等著您的發(fā)現(xiàn)和利用。小結(jié)函數(shù)和子程序是程序瘦身計(jì)劃的一部分，通過它們可以使程序中的代碼適當(dāng)減肥，長(zhǎng)度維持在一個(gè)更合理的位置。這種作用和循環(huán)的瘦身作用一起，使一個(gè)執(zhí)行很長(zhǎng)的代碼可以變得很簡(jiǎn)潔。這也更適合我們利用計(jì)算機(jī)作為工具的目的：人類做盡量少的工作，計(jì)算機(jī)仍能解決原先的問題。另一個(gè)奇妙之處是：他們創(chuàng)造了遞歸！各個(gè)擊破一分治法破解難題問：“問題不能一下子解決，難道不能分開解決嗎，有沒有算法能實(shí)現(xiàn)各個(gè)擊破以求解決問題呢？”答：“可以的，通過各個(gè)擊破的方法解決問題的算法叫做分治法。下面我們通過示例來看一下。”什么是分治法為了解決一個(gè)問題，算法有時(shí)需不止一次地對(duì)自身進(jìn)行調(diào)用，來解決相類似的子問題。這樣的算法通常稱為分治法：將原問題分成n個(gè)規(guī)模較小而結(jié)構(gòu)與原問題相似的子問題。下面通過排序的一種方法來看一下。希爾排序即是采用分治法來進(jìn)行排序的，又稱做縮小增量排序，其思想是：把已經(jīng)在數(shù)組中的數(shù)據(jù)按下標(biāo)的一定增量分組，對(duì)分出的每一小組使用插入排序，隨著增量逐漸減小，所分成的組包含的數(shù)據(jù)越來越多，直到減小到1時(shí)，整個(gè)數(shù)據(jù)合并成一組，構(gòu)成一組有序數(shù)，則完成排序。示例：十個(gè)數(shù)，從大到小排序。數(shù)據(jù)放在一個(gè)數(shù)組a(10)中，假如原始數(shù)據(jù)如下：70.53.57.28.30.77.1.76.81.70，則排序過程如下：增量值5:77.53.76.81.70.70.1.57.28.30.2:77.81.76.70.70.57.28.53.1.30.1:81.77.76.70.70.57.53.30.28.1.其中上面三個(gè)增量值對(duì)應(yīng)的都是以該增量完成本輪排序后的情況，看增量為5時(shí)要和原始數(shù)據(jù)比較，增量為2的情況要和5比較，1要和2比較，這樣其中的規(guī)律就清楚了。子程序如下要用實(shí)現(xiàn)希爾排序，關(guān)鍵是把握好增量的變化情況和最終結(jié)束的控制，設(shè)置變量gap為增量，其值取要排序的所有數(shù)據(jù)的個(gè)數(shù)的二分之一(本例中為5)，比較時(shí)先將第1個(gè)數(shù)同第6個(gè)比，較大的放到前面，較小的放到后面，2同7,直至全部比較完成；下一次用現(xiàn)在的gap的二分之一作為增量，再進(jìn)行增量大小轉(zhuǎn)換；…；當(dāng)其為0時(shí)結(jié)束。原無序序列排成了有序序列了。從上面分析中不難看出，通過和gap增量有關(guān)的兩重嵌套循環(huán)就能將排序功能實(shí)現(xiàn)。詳細(xì)源程序如下：Subshellsort(ByValnAsInteger)'希爾排序子程序Dimi,j,gapAsInteger喜tf申測(cè)，(乙/d詬)mi=d詬!1xqnPUQMJIPUH0=19813

dt?§-f=fX=(dB§+f)B(dB§+f)B=(f)B("xuaqi(d詬+貝0<[anWdB§-1=fUO【[+dB§=TIOJ0<d優(yōu)anw?段黑，(乙/u)mi=dB§igSajujsyx'nuitqTxtList.Text=TxtList.Text+Str(gap)+":"Fork=1TonTxtList.Text=TxtList.Text+Str(a(k))+"."NextkTxtList.Text=TxtList.Text+vbCr+vbLfWendEndSub其他源程序希爾排序按鈕對(duì)應(yīng)的源程序如下：PrivateSubCmdShell_Click(),希爾排序DimiAsIntegerTxtList.Text=""Txtorigin.Text=""Fori=1To10'輸入原始數(shù)據(jù)a(i)=Int(Rnd*100)Txtorigin.Text=Txtorigin.Text+Str(a(i))+Nexti'調(diào)用子程序排序并輸出中間結(jié)果Callshellsort(10)EndSub小結(jié)在進(jìn)行希爾排序時(shí)，需注意增量序列的取值方法，并且使這些序列中的值沒有除1之外的公因子，且最后一個(gè)增量值必須為1。能解決問題的辦法都是好辦法，問題不一定整體解決才好。這就是分治的思想。亂打誤撞一模擬法破解難題問：“電腦解決確定問題可做到手到擒來，對(duì)于電腦中實(shí)現(xiàn)一個(gè)不確定的問題，例如彩票或抽獎(jiǎng)，怎樣做呢？”答：“算法的美妙在于其準(zhǔn)確和確定，而另有一種價(jià)值則在于其不確定，象我們的抽獎(jiǎng)程序和彩票程序。確定的問題電腦可以處理，不確定的問題電腦也能處理，隨機(jī)函數(shù)就是實(shí)現(xiàn)電腦中不確定事件的重要砝碼。下面我們通過示例來看一下?！彪S機(jī)函數(shù)的出現(xiàn)通過語(yǔ)言編程一般來說對(duì)事物的認(rèn)識(shí)是很確定的了，是一就是一，是二就是二，還有一個(gè)問題，有一些不那么確定的事情該如何處理，象我們的彩票抽獎(jiǎng)，如果是確定的了，那也就不用抽了，恐怕也就沒人玩了。對(duì)于這一類的事情，該怎么辦呢？語(yǔ)言中為我們提供