六種常用算法遞推法、貪心法、列舉法、遞歸法、分治法、模擬法。遞推法：就是找出和時間先后相聯系或和數的大小相聯系的步驟，上一步和下一步和數字的增大或減小有一定的聯系。我們要么從前向后（或從小到大）推導，也可從后向前（或從大到小）推導。由此得出兩種推導方法：順推法和倒推法。請看下面的示例。示例：猴子分食桃子五只猴子采得一堆桃子，猴子彼此約定隔天早起后再分食。不過，就在半夜里，一只猴子偷偷起來，把桃子均分成五堆后，發現還多一個，它吃掉這桃子，并拿走了其中一堆。第二只猴子醒來，又把桃子均分成五堆后，還是多了一個，它也吃掉這個桃子，并拿走了其中一堆。第三只，第四只，第五只猴子都依次如此分食桃子。那么桃子數最少應該有幾個呢？編程簡析怎樣編程呢？先要找一下第N只猴子和其面前桃子數的關系。如果從第1只開始往第5只找，不好找，但如果思路一變，從第N到第1去，可得出下面的推導式：第N只猴第N只猴前桃子數目54321s5=xs4=s5*5/4+1s3=s4*5/4+1s2=s3*5/4+1s1=s2*5/4+1s1即為所求。上面的規律中只要將s1-s5的下標去掉：s=xs=s*5/4+1s=s*5/4+1s=s*5/4+1s=s*5/4+1所以可以用循環語句加以解決。綜觀程序的整體結構，最外是一個循環，因為循環次數不定，可以使用While循環，其結束條件則是找到第一個符合條件的數。為了做出上面while循環的結束條件，還需進一步分析上述規律的特點，要符合題目中的要求，s1-s4四個數必須全部為整數，這個可作為條件。貪心法：就是做一種目前最貪婪的行動，一步步解決問題。貪心法和遞推法有相似之外，也是從問題的某一個初始解出發，向給定的目標遞推，但不同的是每一步不是依據某一個固定的遞推式，而是做一個當時看似最佳的貪心選擇，不斷地將問題歸結為更小的相似的問題。示例：刪數問題鏈盤輸入一個高精度的數N，去掉任意S個數字后剩下的數字按原左右次序組成一個新的正整數，編程對于給定的N和S，尋找一種方案使得剩下的數字組成的新數最小。為了便于操作，將N做為字符串的形式輸入，可以使用盡可能逼近目標的貪心算法來完成，刪數的過程中是一個一個進行刪除的，為了保證最后得到的數最小，每一步總是要刪除使剩下的數最小的數字。之所以做出這樣貪心的選擇，是因為刪S個數字的最優解，包含了刪除一個數字的子問題的最優解。為了實現上述目的，我們可以進行S次選擇，每次都選擇N中最大的數字，此數字選擇后將不再參與下次的選擇。列舉法：列舉是針對問題所有的可能一一查看是不是符合條件，有些“寧肯錯殺一千，不可放過一個”的作風。下面的老題最能說明這種情況。示例：百錢買百雞公雞3元每只，母雞5元每只，小雞1元3只，一百元錢買一百只雞。請求出公雞，母雞和小雞的數目。我們做最極端的假設，公雞可能是0-100，母雞也可能是0-100，小雞還可能是0-100，將這三種情況用循環套起來，那就是1000000種情況。這就是列舉法。為了將題目再簡化一下，我們還可以對上述題目進行一下優化處理：假設公雞數為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只。可能的方案一共有34*21種，在這么多的方案中，可能有一種或幾種正好符合相等的條件。電腦怎樣工作呢？計算機事實上就是將上述34*21種方案全部過濾一遍，找出符合百錢買百雞條件的（也即上式），只要符合，這就是我們要的輸出結果。程序實現：我們怎樣將這34*21種方案羅列出呢？這么多的方案，最好的辦法是還是用循環?？捎醚h和循環的嵌套，一個關于公雞數和一個關于母雞數的循環套起來，就能將所有的方案都遍歷。后面的問題成了怎樣判斷哪一個方案是我們尋找的符合條件和方案呢？只能根據百錢買百雞了，即3*x+5*y+(100-x-y)/3=100作為條件，在條件成立的一方輸出x,y,和100-x-y的值就行了，這是分支要解決的問題，程序的整體結構有了，兩個嵌套循環中套分支。列舉法將可能的情況一網打盡；不過在應用過程中，我們最好還是做些優化，不然，要浪費好多沒必要浪費的時間。遞歸法：說白了遞歸就象我們講的那個故事：山上有座廟，廟里有個老和尚，老和尚在講故事，它講的故事是：山上有座廟，廟里有個老和尚，老和尚在講故事，它講的故事是：……也就是直接或間接地調用了其自身。就象上面的故事那樣，故事中包含了故事本身。因為對自身進行調用，所以需對程序段進行包裝，也就出現了函數。函數的利用是對數學上函數定義的推廣，函數的正確運用有利于簡化程序，也能使某些問題得到迅速實現。對于代碼中功能性較強的、重復執行的或經常要用到的部分，將其功能加以集成，通過一個名稱和相應的參數來完成，這就是函數或子程序，使用時只需對其名字進行簡單調用就能來完成特定功能。函數又可分為自定義的和系統附帶的，但不管是自定義的還是系統的，他們都對相應的功能進行了封裝，以利于我們經常性地使用。例如我們的對一個小數取整數INT()函數，不論什么樣的小數，往（）中一放，將來得到的值就自動將小數去除了。函數執行完將返回一個值，當然這個值可以是各種類型的，子程序僅僅執行一個過程，不返回數值。函數和子程序是執行遞歸的干將。示例：小猴吃棗小猴第一天摘下若干棗子，當即吃掉了一半，不過癮又多吃了一個；第二天吃了剩下的一半又多吃了一個；以后每一天都吃了前一天剩下的一半多一個。到第十天小猴再想吃時，見到只剩下一只棗子了。問第一天這堆棗子有多少？從上題中我們可看到一個令人欣喜的規律，第十天為1，第九到第一天中后一天與1的和的兩倍與前一天相等。下面就對這一規律做了描述：PrivateFunctionmonkey(ByValxAsInteger)AsIntegerIfx>=10Thenmonkey=1Elsemonkey=2*(monkey(x+1)+1)EndIfEndFunction我們定義monkey()函數的時候通過monkey()自身來進行了定義，這就是遞歸。遞歸是個特殊的循環，是一個有著非常美妙的循環規則的循環。上題中我們只要將monkey(1)，即第一天打印出來，一切OK。而這中間究竟是怎么工作的，我們可以不管。正是有了monkey()函數，在對其自身調用的過程中實現了我們的所求，關于函數、子程序和他們之間發生的故事還有很多，僅僅列舉了其中奇妙的幾點，還有許多東東等著您的發現和利用。小結函數和子程序是程序瘦身計劃的一部分，通過它們可以使程序中的代碼適當減肥，長度維持在一個更合理的位置。這種作用和循環的瘦身作用一起，使一個執行很長的代碼可以變得很簡潔。這也更適合我們利用計算機作為工具的目的：人類做盡量少的工作，計算機仍能解決原先的問題。另一個奇妙之處是：他們創造了遞歸！分治法：為了解決一個問題，算法有時需不止一次地對自身進行調用，來解決相類似的子問題。這樣的算法通常稱為分治法：將原問題分成n個規模較小而結構與原問題相似的子問題。下面通過排序的一種方法來看一下。希爾排序即是采用分治法來進行排序的，又稱做縮小增量排序，其思想是：把已經在數組中的數據按下標的一定增量分組，對分出的每一小組使用插入排序，隨著增量逐漸減小，所分成的組包含的數據越來越多，直到減小到1時，整個數據合并成一組，構成一組有序數，則完成排序。示例：十個數，從大到小排序。數據放在一個數組a(10)中，假如原始數據如下：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.其中上面三個增量值對應的都是以該增量完成本輪排序后的情況，看增量為5時要和原始數據比較，增量為2的情況要和5比較，1要和2比較，這樣其中的規律就清楚了。子程序如下要用實現希爾排序，關鍵是把握好增量的變化情況和最終結束的控制，設置變量gap為增量，其值取要排序的所有數據的個數的二分之一（本例中為5），比較時先將第1個數同第6個比，較大的放到前面，較小的放到后面，2同7，直至全部比較完成；下一次用現在的gap的二分之一作為增量，再進行增量大小轉換；…；當其為0時結束。原無序序列排成了有序序列了。從上面分析中不難看出，通過和gap增量有關的兩重嵌套循環就能將排序功能實現。詳細源程序如下：Subshellsort(ByValnAsInteger)'希爾排序子程序Dimi,j,gapAsIntegerDimk,xAsIntegergap=Int(n/2)'置初值Whilegap>0Fori=gap+1Tonj=i-gapWhilej>0Ifa(j)<a(j+gap)Thenx=a(j)a(j)=a(j+gap)a(j+gap)=xj=j-gapElsej=0EndIfWendNextigap=Int(gap/2)’減小增量‘輸出結果TxtList.Text=TxtList.Text+Str(gap)+":"Fork=1TonTxtList.Text=TxtList.Text+Str(a(k))+"."NextkTxtList.Text=TxtList.Text+vbCr+vbLfWendEndSub其他源程序希爾排序按鈕對應的源程序如下：PrivateSubCmdShell_Click()'希爾排序DimiAsIntegerTxtList.Text=""Txtorigin.Text=""Fori=1To10'輸入原始數據a(i)=Int(Rnd*100)Txtorigin.Text=Txtorigin.Text+Str(a(i))+"."Nexti'調用子程序排序并輸出中間結果Callshellsort(10)EndSub小結在進行希爾排序時，需注意增量序列的取值方法，并且使這些序列中的值沒有除1之外的公因子，且最后一個增量值必須為1。能解決問題的辦法都是好辦法，問題不一定整體解決才好。這就是分治的思想。模擬法:問：“電腦解決確定問題可做到手到擒來，對于電腦中實現一個不確定的問題，例如彩票或抽獎，怎樣做呢？”答：“算法的美妙在于其準確和確定，而另有一種價值則在于其不確定，象我們的抽獎程序和彩票程序。確定的問題電腦可以處理，不確定的問題電腦也能處理，隨機函數就是實現電腦中不確定事件的重要砝碼。下面我們通過示例來看一下?！彪S機函數的出現通過語言編程一般來說對事物的認識是很確定的了，是一就是一，是二就是二，還有一個問題，有一些不那么確定的事情該如何處理，象我們的彩票抽獎，如果是確定的了，那也就不用抽了，恐怕也就沒人玩了。對于這一類的事情，該怎么辦呢？語言中為我們提供了隨機函數，也就是說通過它得到的一個值將是不能確定的。隨機函數產生的秘密計算機常常需要模擬隨機選擇的數目，有多種不同的方法可以產生具有隨機性質的數，由于通過此種系統的方法產生的不是真正的隨機數，所以一般稱做偽隨機數。最常用的產生偽隨機數的方法稱為線性同余法。公式如下，選擇四個數：模數m，乘數a，增量c和種數x0，使2≤a<m,0≤c<m,0≤x0<m,可以生成一個偽隨機序列{xn}，使得對于所有的n，0≤x0<m。生成的辦法是逐次同余：xn+1=(axn+c)modm應用和變通隨機函數有一個范圍，即Rnd函數返回小于1但大于或等于0的小數值。但通常我們要解的問題不在這個范圍內，如何解決呢？示例：最簡單的抽獎程序，做一個猜1-100之間數的游戲。因為隨機函數的范圍是一個0-1之間的小數，和題目要求的范圍相差很大。所以，當我們用到的值不在這個范圍之內時，我們可以想點變通的辦法。要想做到從1-100之間進行取數，必須擴大100倍才行。不難計算RND*100的范圍卻不是1-100，而是0-100,不包括0和100，怎樣就是1-100了呢？加上一就有了,范圍成了1-101，不包括1和101，只要對得到的數只取整數，這個數只要這樣