C語(yǔ)言經(jīng)典算法詳解

一分而治之算法分而治之方法與軟件設(shè)計(jì)的模塊化方法非常相似。為了解決一個(gè)大的問(wèn)題，可以：1）把它分成兩個(gè)或多個(gè)更小的問(wèn)題；2）分別解決每個(gè)小問(wèn)題；3）把各小問(wèn)題的解答組合起來(lái)，即可得到原問(wèn)題的解答。小問(wèn)題通常與原問(wèn)題相似，可以遞歸地使用分而治之策略來(lái)解決。下列通過(guò)實(shí)例加以說(shuō)明。例：利用分而治之算法求一個(gè)整數(shù)數(shù)組中的最大值。#include<stdio.h>//文件包含預(yù)處理命令，printf()函數(shù)在其中聲明intMax(inta口，intn);//求a[0],a[1],...,a[n-1]中的最大值intmain(void){inta[8]={9,3,8,1,10,5,190,180};inti;printf("數(shù)組a:");for(i=0;i<n;i++)printf("%d",a[i]);printf("\n最大值為%d.\n",Max(a,8));return0;//返回值0}/*用分而治之算法求一個(gè)整數(shù)數(shù)組中的最大值*/intMax(inta[],intn){intmax1,max2;if(n==1){//遞歸結(jié)束條件成立，結(jié)束遞歸returna[0];else{//遞歸結(jié)束條件不成立，繼續(xù)遞歸maxi=Max(a,n-1);/*求a[0],a[1],...,a[n-1]的最大值maxi*//*求maxi和a[n-1]的最大值*/if(maxi>a[n-1])max2=max1;elsemax2=a[n-1];returnmax2;))練習(xí)：［找出偽幣］給你一個(gè)裝有16個(gè)硬幣的袋子。16個(gè)硬幣中有一個(gè)是偽造的，并且那個(gè)偽造的硬幣比真的硬幣要輕一些。你的任務(wù)是找出這個(gè)偽造的硬幣。二貪心算法貪心算法(又稱(chēng)貪婪算法)是指，在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇。也就是說(shuō)，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。貪心算法不是對(duì)所有問(wèn)題都能得到整體最優(yōu)解，但對(duì)范圍相當(dāng)廣泛的許多問(wèn)題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。貪心算法(Greedyalgorithm)是一種對(duì)某些求最優(yōu)解問(wèn)題的更簡(jiǎn)單、更迅速的設(shè)計(jì)技術(shù)。用貪婪法設(shè)計(jì)算法的特點(diǎn)是一步一步地進(jìn)行，常以當(dāng)前情況為基礎(chǔ)根據(jù)某個(gè)優(yōu)化測(cè)度作最優(yōu)選擇，而不考慮各種可能的整體情況，它省去了為我最優(yōu)解要窮盡所有可能而必須耗費(fèi)的大量時(shí)間，它采用自頂向下，以迭代的方法做出相繼的貪心選擇，每做一次貪心選擇就將所求問(wèn)題簡(jiǎn)化為一個(gè)規(guī)模更小的子問(wèn)題，通過(guò)每一步貪心選擇，可得到問(wèn)題的一個(gè)最優(yōu)解，雖然每一步上都要保證能獲得局部最優(yōu)解，但由此產(chǎn)生的全局解有時(shí)不一定是最優(yōu)的，所以貪婪法不要回溯。貪心算法是一種改進(jìn)了的分級(jí)處理方法。其核心是根據(jù)題意選取一種量度標(biāo)準(zhǔn)。然后將這多個(gè)輸入排成這種量度標(biāo)準(zhǔn)所要求的順序，按這種順序一次輸入一個(gè)量。如果這個(gè)輸入和當(dāng)前已構(gòu)成在這種量度意義下的部分最佳解加在一起不能產(chǎn)生一個(gè)可行解，則不把此輸入加到這部分解中。這種能夠得到某種量度意義下最優(yōu)解的分級(jí)處理方法稱(chēng)為貪婪算法。對(duì)于一個(gè)給定的問(wèn)題，往往可能有好幾種量度標(biāo)準(zhǔn)。初看起來(lái)，這些量度標(biāo)準(zhǔn)似乎都是可取的，但實(shí)際上，用其中的大多數(shù)量度標(biāo)準(zhǔn)作貪婪處理所得到該量度意義下的最優(yōu)解并不是問(wèn)題的最優(yōu)解，而是次優(yōu)解。因此，選擇能產(chǎn)生問(wèn)題最優(yōu)解的最優(yōu)量度標(biāo)準(zhǔn)是使用貪婪算法的核心。一般情況下，要選出最優(yōu)量度標(biāo)準(zhǔn)并不是一件容易的事，但對(duì)某問(wèn)題能選擇出最優(yōu)量度標(biāo)準(zhǔn)后，用貪婪算法求解則特別有效。最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇即貪婪選擇來(lái)達(dá)到根據(jù)當(dāng)前狀態(tài)做出在當(dāng)前看來(lái)是最好的選擇，即局部最優(yōu)解選擇，然后再去解做出這個(gè)選擇后產(chǎn)生的相應(yīng)的子問(wèn)題。每做一次貪婪選擇就將所求問(wèn)題簡(jiǎn)化為一個(gè)規(guī)模更小的子問(wèn)題，最終可得到問(wèn)題的一個(gè)整體最優(yōu)解。貪心算法特性貪心算法可解決的問(wèn)題通常大部分都有如下的特性：(1)有一個(gè)以最優(yōu)方式來(lái)解決的問(wèn)題。為了構(gòu)造問(wèn)題的解決方案，有一個(gè)候選的對(duì)象的集合：比如不同面值的硬幣。(2)隨著算法的進(jìn)行，將積累起其它兩個(gè)集合：一個(gè)包含已經(jīng)被考慮過(guò)并被選出的候選對(duì)象，另一個(gè)包含已經(jīng)被考慮過(guò)但被丟棄的候選對(duì)象。(3)有一個(gè)函數(shù)來(lái)檢查一個(gè)候選對(duì)象的集合是否提供了問(wèn)題的解答。該函數(shù)不考慮此時(shí)的解決方法是否最優(yōu)。(4)還有一個(gè)函數(shù)檢查是否一個(gè)候選對(duì)象的集合是可行的，也即是否可能往該集合上添加更多的候選對(duì)象以獲得一個(gè)解。和上一個(gè)函數(shù)一樣，此時(shí)不考慮解決方法的最優(yōu)性。(5)選擇函數(shù)可以指出哪一個(gè)剩余的候選對(duì)象最有希望構(gòu)成問(wèn)題的(6)最后，目標(biāo)函數(shù)給出解的值。為了解決問(wèn)題，需要尋找一個(gè)構(gòu)成解的候選對(duì)象集合，它可以?xún)?yōu)化目標(biāo)函數(shù)，貪婪算法一步一步的進(jìn)行。起初，算法選出的候選對(duì)象的集合為空。接下來(lái)的每一步中，根據(jù)選擇函數(shù)，算法從剩余候選對(duì)象中選出最有希望構(gòu)成解的對(duì)象。如果集合中加上該對(duì)象后不可行，那么該對(duì)象就被丟棄并不再考慮；否則就加到集合里。每一次都擴(kuò)充集合，并檢查該集合是否構(gòu)成解。如果貪婪算法正確工作，那么找到的第一個(gè)解通常是最優(yōu)的。貪心算法的基本思路1,建立數(shù)學(xué)模型來(lái)描述問(wèn)題。2,把求解的問(wèn)題分成若干個(gè)子問(wèn)題。.對(duì)每一子問(wèn)題求解，得到子問(wèn)題的局部最優(yōu)解。.把子問(wèn)題的解局部最優(yōu)解合成原來(lái)解問(wèn)題的一個(gè)解。實(shí)現(xiàn)該算法的過(guò)程：從問(wèn)題的某一初始解出發(fā)；while能朝給定總目標(biāo)前進(jìn)一步do求出可行解的一個(gè)解元素；由所有解元素組合成問(wèn)題的一個(gè)可行解。下面是一個(gè)可以試用貪心算法解的題目，貪心解的確不錯(cuò)，可惜不是最優(yōu)解例題分析［背包問(wèn)題］有一個(gè)背包，背包容量是M=150。有7個(gè)物品，物品不可以分割成任意大小。要求盡可能讓裝入背包中的物品總價(jià)值最大，但不能超過(guò)總?cè)萘?。物品ABCDEFG重量35306050401025價(jià)值10403050354030分析：目標(biāo)函數(shù)：Epi最大約束條件是裝入的物品總重量不超過(guò)背包容量：Iwi<=M(M=150)(1)根據(jù)貪心的策略，每次挑選價(jià)值最大的物品裝入背包，得到的結(jié)果是否最優(yōu)？(2)每次挑選所占重量最小的物品裝入是否能得到最優(yōu)解？(3)每次選取單位重量?jī)r(jià)值最大的物品，成為解本題的策略。值得注意的是，貪心算法并不是完全不可以使用，貪心策略一旦經(jīng)過(guò)證明成立后，它就是一種高效的算法。貪心算法還是很常見(jiàn)的算法之一，這是由于它簡(jiǎn)單易行，構(gòu)造貪心策略不是很困難?？上У氖?，它需要證明后才能真正運(yùn)用到題目的算法中。般來(lái)說(shuō)，貪心算法的證明圍繞著：整個(gè)問(wèn)題的最優(yōu)解一定由在貪心策略中存在的子問(wèn)題的最優(yōu)解得來(lái)的對(duì)于例題中的3種貪心策略，都是無(wú)法成立(無(wú)法被證明)的，解釋如下：(1)貪心策略：選取價(jià)值最大者。反例：W=30物品：ABC重量：281212價(jià)值：302020根據(jù)策略，首先選取物品A,接下來(lái)就無(wú)法再選取了，可是，選取B、C則更好。(2)貪心策略：選取重量最小。它的反例與第一種策略的反例差不多。(3)貪心策略：選取單位重量?jī)r(jià)值最大的物品。反例：W=30物品：ABC重量：282010價(jià)值：282010根據(jù)策略，三種物品單位重量?jī)r(jià)值一樣，程序無(wú)法依據(jù)現(xiàn)有策略作出判斷，如果選擇A,則答案錯(cuò)誤?！咀⒁猓喝绻锲房梢苑指顬槿我獯笮?，那么策略3可得最優(yōu)解】對(duì)于選取單位重量?jī)r(jià)值最大的物品這個(gè)策略，可以再加一條優(yōu)化的規(guī)則：對(duì)于單位重量?jī)r(jià)值一樣的，則優(yōu)先選擇重量小的！這樣，上面的反例就解決了。但是，如果題目是如下所示，這個(gè)策略就也不行了。W=40物品：ABC重量：252015價(jià)值：252015附：本題是個(gè)NP問(wèn)題，用貪心法并不一定可以求得最優(yōu)解，以后了解了動(dòng)態(tài)規(guī)劃算法后本題就有了新的解法。備注：貪心算法當(dāng)然也有正確的時(shí)彳求最小生成樹(shù)的Prim算法和Kruskal算法都是漂亮的貪心算法。貪心法的應(yīng)用算法有Dijkstra的單源最短路徑和Chvatal的貪心集合覆蓋啟發(fā)式所以需要說(shuō)明的是，貪心算法可以與隨機(jī)化算法一起使用，具體的例子就不再多舉了。（因?yàn)檫@一類(lèi)算法普及性不高，而且技術(shù)含量是非常高的，需要通過(guò)一些反例確定隨機(jī)的對(duì)象是什么，隨機(jī)程度如何，但也是不能保證完全正確，只能是極大的幾率正確）#include<stdlib.h>#include<conio.h>#include<stdio.h>#include<math.h>#include<time.h>TOC\o"1-5"\h\zdefineK10defineN10/*從小到大創(chuàng)建物品k?voidcreate(longarray口,intn,intk){inti,j;array[0]=1;for(i=1;i<n;i++){longt=0;for(j=0;j<i;j++)t=t+array[j];array[i]=t+rand()+1;}}/voidcreate(longarray口,intn){inti;array[0]=1;for(i=1;i<n;i++){array[i]=2*i;}}voidoutput(longarray口,intn){inti;for(i=0;i<n;i++){if(i%5==0)printf("\n");printf("%14ld",array[i]);))voidbeibao(longarray[],intcankao[],longvalue,intcount){inti;longr=value;for(i=count-1;i>=0;i--){if(r>=array[i]){r=r-array[i];cankao[i]=1;)elsecankao[i]=0;))intbeibao1(longarray[],intcankao[],longvalue,intn){/*貪婪算法*/inti;longvalue1=0;for(i=n-1;i>=0;i--)/*先放大的物體，再考慮小的物體*/if((value1+array[i])<=value)/*如果當(dāng)前物體可以放入*/{cankao[i]=1;/*1表示放入*/value1+=array[i];/*背包剩余容量減少*/)elsecankao[i]=0;if(value1==value)return1;return0;)voidmain(){longarray[N];intcankao[N]={0};intcankao1[N]={0};inti;longvalue,value1=0;system("cls");srand((unsigned)time(NULL));create(array,N);output(array,N);printf("\nInputthevalueofbeibao:\n");scanf("%ld",&value);beibao(array,cankao,value,N);for(i=0;i<N;i++)if(cankao[i]==1)value1+=array[i];if(value==value1){printf("\nWehavegotasolution,thatis:\n");for(i=0;i<N;i++)if(cankao[i]==1){if(i%5==0)printf("\n");printf("%13ld",array[i]);}}elseprintf("\nSorry.Wehavenotgotasolution.\n");printf("\nSecondmethod:\n");if(beibao1(array,cankao1,value,N)==1){for(i=0;i<N;i++)if(cankao1[i]==1){if(i%5==0)printf("\n");printf("%13ld",array[i]);}}elseprintf("\nSorry.Wehavenotgotasolution.\n");)練習(xí)：馬的遍歷問(wèn)題。在8X8方格的棋盤(pán)上，從任意指定方格出發(fā),為馬尋找一條走遍棋盤(pán)每一格并且只經(jīng)過(guò)一次的一條最短路徑。三.回朔算法在程序設(shè)計(jì)中，有這樣一類(lèi)問(wèn)題：求一類(lèi)解，或求全部解，或求最優(yōu)解的問(wèn)題(例如八皇后問(wèn)題),不是根據(jù)某種確定的算法設(shè)計(jì)法則，而是利用試探和回朔的搜索技術(shù)求解.回朔還是設(shè)計(jì)遞歸算法的重要方法，其求解過(guò)程實(shí)質(zhì)：是一個(gè)先序遍歷一棵"狀態(tài)樹(shù)"但是這棵樹(shù)不是在遍歷前預(yù)先建立的，而是隱含在遍歷過(guò)程中.回朔算法的解題思路大體如下：假設(shè)問(wèn)題的解為n元組(x1,x2,x3,x4,-xn)，其中xi取值于集合Seti,n元組的子組(x1,x2,x3,x4,-xi)(i<n)為部分解，應(yīng)滿(mǎn)足一定的約束條件。對(duì)于已求得的部分解(x1,x2,x3,x4,…漢)，再添加xi+1屬于Seti+1之后仍滿(mǎn)足約束條件，則可得到一個(gè)新的部分解(x1,x2,x3,x4,???xi+1),繼續(xù)添加xi+2屬于Seti+2,并檢查是否滿(mǎn)足約束條件，直到添加到xn屬于Setn為止。如果對(duì)于所有取值與集合Seti的xi+1都不能得到新的滿(mǎn)足約束條件的部分解(x1,x2,x3,x4,???xi+1),則從當(dāng)前子組中刪去xi,回朔到前一個(gè)部分解(x1,x2,x3,x4,-xi-1),重新添加Seti中未考察過(guò)的xi,看其是否滿(mǎn)足約束條件。如此反復(fù)進(jìn)行，直到求到滿(mǎn)足條件的問(wèn)題的解，或者證明問(wèn)題無(wú)解。例：迷宮問(wèn)題，只能從一個(gè)空白位置走到另一個(gè)與它相鄰的空白位置(上，下，左，右)，但不能重復(fù)路線(xiàn)。代碼如下:#include<stdio.h>#include<stdlib.h>#defineW80//迷宮寬的最大值#defineH60//迷宮高的最大值//迷宮單元格狀態(tài)：VIA:已經(jīng)過(guò)，BLOCK:阻塞(陰影)，EMPTY:空typedefenum{VIA,BLOCK,EMPTY}MazeCellStatus;typedefstruct{intx,y;//迷宮單元格的坐標(biāo)}CellType;typedefstruct{CellTypepath[W*H];〃經(jīng)過(guò)路徑intlength;//經(jīng)過(guò)長(zhǎng)度}MazePathType;〃迷宮路線(xiàn)類(lèi)型、voidOutSolution(MazePathTypemazepath);〃輸出迷宮問(wèn)題的解voidTrySolution(MazeCellStatusmaze[[W],intw,inth,CellTypeexit,CellTypecur,MazePathTypemazePath);//試探求解下一位置voidMazeSolution(MazeCellStatusmaze[][W],intw,inth,CellTypeentry,CellTypeexit);//迷宮問(wèn)題voidmain(){MazeCellStatusmaze[H][W]={{EMPTY,BLOCK,BLOCK,BLOCK,BLOCK,BLOCK,BLOCK,BLOCK,BLOCK,BLOCK},{EMPTY,BLOCK,EMPTY,EMPTY,BLOCK,EMPTY,EMPTY,EMPTY,BLOCK,BLOCK},{EMPTY,EMPTY,EMPTY,BLOCK,BLOCK,EMPTY,BLOCK,EMPTY,EMPTY,BLOCK},{EMPTY,BLOCK,BLOCK,EMPTY,EMPTY,EMPTY,BLOCK,BLOCK,EMPTY,BLO

CK),{EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,BLOCK),{EMPTY,BLOCK,BLOCK,BLOCK,BLOCK,BLOCK,BLOCK,BLOCK,EMPTY,EMPTY),)；CellTypeentry={0,0);//入口位置CellTypeexit={9,5);//出口位置inth=6;〃迷宮高intw=10;//迷宮寬MazeSolution(maze,w,h,entry,exit);)voidMazeSolution(MazeCellStatusmaze[][W],intw,inth,CellTypeentry,CellTypeexit){MazePathTypemazePath;mazePath.length=0;//迷宮路線(xiàn)初始長(zhǎng)度為0mazePath.path[mazePath.length].x=entry.x;mazePath.path[mazePath.length].y=entry.y;mazePath.length++;//路徑自增1TrySolution(maze,w,h,exit,entry,mazePath);)voidTrySolution(MazeCellStatusmaze[[W],intw,inth,CellTypeexit,CellTypecur,MazePathTypemazePath){//相鄰位置相對(duì)于當(dāng)前位置//相鄰位置相對(duì)于當(dāng)前位置x的坐標(biāo)//相鄰位置相對(duì)于當(dāng)前位置y的坐標(biāo)//當(dāng)前位置的相鄰位置intxshift[4]={0,0,-1,1);intyshift[4]={-1,1,0,0);CellTypeadjCell;if(cur.x==exit.x&&cur.y==exit.y){〃已達(dá)到出口，輸出解OutSolution(mazePath);)else{for(i=0;i<4;i++){adjCell.x=cur.x+xshift[i];//求相鄰位置的x坐標(biāo)adjCell.y=cur.y+yshift[i];//求相鄰位置的y坐標(biāo)if(adjCell.x>=0&&adjCell.x<=w&&adjCell.y>=0&&adjCell.y<=h&&(maze[adjCell.y][adjCell.x]==EMPTY)){//相鄰位置在迷宮內(nèi)并且為空白，將相鄰位置存于路徑中mazePath.path[mazePath.length].x=adjCell.x;mazePath.path[mazePath.length].y=adjCell.y;mazePath.length++;maze[adjCell.y][adjCell.x]=VIA;TrySolution(maze,w,h,exit,adjCell,mazePath);〃對(duì)相鄰位置進(jìn)行遞mazePath.length--;//從路徑中去掉adjCell,路徑長(zhǎng)度將自減1maze[adjCell.y][adjCell.x]=EMPTY;}}}}voidOutSolution(MazePathTypemazepath){staticintnum=0;inti;printf("第％d條路徑：",++num);//num表示當(dāng)前以求的解得個(gè)數(shù)for(i=0;i<mazepath.length;i++){printf("(%d,%d)”,mazepath.path[i].x,mazepath.path[i].y);}printf("\n");}練習(xí)：皇后問(wèn)題求解：在n*n的棋盤(pán)上放置n個(gè)皇后，這些皇后中任意兩個(gè)皇后不能在同一行，同一列，同一條對(duì)角線(xiàn)（包括主對(duì)角線(xiàn)和次對(duì)角線(xiàn)）上。如有解則輸出所有合理的解四.窮舉法窮舉法是一種針對(duì)于密碼的破譯方法。這種方法很像數(shù)學(xué)上的完全歸納