常用算法設(shè)計方法

常用算法設(shè)計方法然后再根據(jù)算法編寫程序。計算機程序要對問題的每個對象和處理規(guī)則給出正確詳盡的描述，其中程序的數(shù)據(jù)結(jié)構(gòu)和變量用來描述問題的對象，程序結(jié)構(gòu)、函數(shù)和語句用來描述問的指令組成。指令正確地描述了要完成的任務(wù)和它們被執(zhí)行的順序。計算機按算法指令所描述的順序執(zhí)行算法的指令能在有限的步驟內(nèi)終止，或終止于給出問題的解，或終止于指通常求解一個問題可能會有多種算法可供選擇，選擇的主要標(biāo)準(zhǔn)是算法的正確性和可靠性，簡單性和易理解性。其次是算法所需要的存儲空間少和執(zhí)行更快等。迭代法是用于求方程或方程組近似根的一種常用的算法設(shè)計方法。設(shè)方程為f(x)=0，用某種數(shù)學(xué)方法導(dǎo)出等價的形式x=g(x)，然后按以下步驟執(zhí)行：}x[i]=初始近似根;}的條件下，測試由它們排成的如圖所示的三}}}}}}對一組數(shù)窮盡所有排列，還有更直接的方法。將一個排列看作一個長整數(shù)，對應(yīng)著一組整數(shù)。將這組整數(shù)按從小到大的順序排列排成一個整數(shù)，從對應(yīng)最始。按數(shù)列的遞增順序逐一列舉每個排列對應(yīng)的每個整數(shù)，這能更有舉。從一個排列找出對應(yīng)數(shù)列的下一個排列可在當(dāng)前排列的基礎(chǔ)上作部分調(diào)整數(shù)的排列。但為了順序從小到大列舉出所有的排列，不能立即調(diào)整得太大，選擇對應(yīng)最小整數(shù)的那個排列，為此還需將}}}}從上述問題解決的方法中，最重要的因素就是確定某種方法來確定所有的候【算法】}}}}遞推法是利用問題本身所具有的一種遞推關(guān)系求N=a[m]×10m-1+a[m-1]×10m-2+…+a[2]×101+a[1]×}}}}printf(“Enterthenum}}遞歸是設(shè)計和描述算法的一種有力的工具，由于它在復(fù)雜算法的描述中被經(jīng)常模較小的問題，然后從這些小問題的解方便地構(gòu)造出大問題的解，并且這些規(guī)模較小的問題也能采用同樣的分解和綜合方法，分解成規(guī)模更小的問題，并從這些更小問題的解構(gòu)造}遞歸算法的執(zhí)行過程分遞推和回歸兩個階段。在回歸階段，當(dāng)獲得最簡單情況的解后，逐級返回，依在編寫遞歸函數(shù)時要注意，函數(shù)中的局部變量和參數(shù)知入“簡單問題”層時，原來層次上的參數(shù)和局部變量便（4）5、3、2（5）5、3、1（6）5、2、1（7）4、3、2（8）4、3、1（9）4、2、1（10）3、2、1k，函數(shù)將確定組合的第一個數(shù)字放入數(shù)組后，有兩種可能的選擇，因還未去頂組合【程序】}}}}用遞歸尋找物品的選擇方案。設(shè)前面已有了多種選擇的方案，并保留了其中總價值最大的/*又一個完整方案，因為它比前面的方案好，以以當(dāng)前方案作為臨時最佳方案保存;}}就進一步找更好的佳。如能判定某個查找分支不會找到更好的解，算法不會在【程序】}}maxv=tv-a[i].value;}}}}作為對比，下面以同樣的解題思想，考慮非遞歸是簡單地逐一生成所有候選解，而是從每個物品對候當(dāng)該物品被包含在候選解中依舊滿足解的總重量的限繼續(xù)考慮的；反之，該物品不應(yīng)該包括在當(dāng)前正在形被包括在候選解中，還是有可能找到比目前臨時最佳不被包括在候選解中；反之，該物品不包括在當(dāng)前候}}}}}}}}}倘若當(dāng)前候選解除了還不滿足問題規(guī)模要求外，滿足所有解的規(guī)模，并繼續(xù)試探。如果當(dāng)前候選解滿足包括問題規(guī)一，則以（x1，x2，…，xj）為前綴的任何n元組它們?；厮莘ㄕ轻槍@類問題，利用這類問題的上述性質(zhì)而提出來的比枚（1）1、2、3（2）1、2、4（3）1、2（4）1、3、4（5）1、3、5（6）1、（7）2、3、4（8）2、3、5（9）2、的所有狀態(tài)結(jié)點，而跳過對肯定不含回答結(jié)點的所有地說，當(dāng)搜索按深度優(yōu)先策略到達一個滿足D中所有有關(guān)約束的狀態(tài)結(jié)點時，即“激活”該狀態(tài)結(jié)點，以便繼續(xù)往深層搜索；否則跳過對以該直到遇到其兒子結(jié)點未被搜索遍的祖先結(jié)點，在搜索過程中，只要所激活的狀態(tài)結(jié)點又滿足終結(jié)條件，般要用到棧的數(shù)據(jù)結(jié)構(gòu)。這時，不僅可以用棧來表示正在），}}}}}格填一個整數(shù)，似的所有相鄰兩個方格內(nèi)的兩個整數(shù)之和為質(zhì)數(shù)。試求出所并在當(dāng)前位置正確填入后，為下一方格尋找可填入的合個合理的可填證書，就要回退到前一方格，調(diào)整前一方格的填入數(shù)。當(dāng)?shù)诰藕侠淼恼麛?shù)后，就找到了一個解，將該解輸出，并順序）每次在當(dāng)前位置填入一個整數(shù)，然后檢查當(dāng)要求的情況下，繼續(xù)用同樣的方法為下一方格填入求，就改變填入的整數(shù)。如對當(dāng)前方格試盡所有可到前一方格，并調(diào)整前一方格填入的整數(shù)。如此重else調(diào)整;}}else擴展;}else調(diào)整;}為了確保程序能夠終止，調(diào)整時必須保證曾某種有許模型生成填數(shù)序列。給解的候選者設(shè)定一個候選者并檢驗。從小到大或從大到小，都是可以采用}}}}}}}}}}}改變之，形成下一個候選解;}}但仔細觀察就會發(fā)現(xiàn)，這種表示方法給調(diào)整候選解及檢查其合理性帶來困難。更好的方法乃是盡可能直接表示那些常用的信息。對于本題來說，“常用信息”并不是皇后的具體位置，而是“一個皇后是否已經(jīng)在某行和某條斜線合理地安置好了”。因在某一列上恰好放棋盤中同一右高左低斜線上的方格，他們的行號與列號之和相同；同一左高printf(“%3d\t%d\n”,a[col[m]]=b[m+col[m]]=c[n+m-co}}}a[col[m]]=b[m+col[m]]}}good=a[col[m]]&&b[m+col[m]]&&c[n}【程序】}printf(“%3d\t%d\n”,}}}采用遞歸方法找一個解與找全部解稍有不同，在找一個解的算法中，遞歸算候選解最終是否能成為解要有回答。當(dāng)它成為最終解時，遞歸函數(shù)就不}}}貪婪法是一種不追求最優(yōu)解，只希望得到較為滿意解的方法。貪婪法一般可以快速得到滿意的解，因為它省去了為找最優(yōu)解要窮盡所有可能而必須耗費的大量時間。貪婪法常以例如平時購物找錢時，為使找回的零錢的硬幣數(shù)最少，不考慮找零錢的所有各種發(fā)表方案，而是從最大面值的幣種開始，按遞減的順序考慮各幣種，先盡量用大面值的幣種，當(dāng)不足大面值幣種的金額時才去考慮下一種較小面值的幣種。這就是在使用貪婪法。這種方法在這里總是最優(yōu)，是因為銀行對其發(fā)行的硬幣種類和硬幣面值的巧妙安排。如只有面值受的。為此，對裝箱問題采用非常簡單的近似算法，第一個能放進去的箱子中，該算法雖不能保證找到最}}}若每只箱子所裝物品用鏈表來表示，鏈表首結(jié)點指針存于一個結(jié)構(gòu)中，結(jié)構(gòu)記【程序】A=(int*)malloc(sizeof(int)Printf(“請按體積從大到小順序輸入{j=(HNODE*)malloc(sizeof(HNODE));j->remainder=box_volume-a;j->head=NULL;if(box_h==NULL)box_h=box_t=j;elsebox_t=boix_t->next=j;j->next=NULL;box_count++;}elsej->remainder-=a;for(q=j->next;q!=NULL&&q->link!=NULL;q=q->link);{p->link=j->head;j->head=p;}q->link=p;}}printf(“各箱子裝物品情況如下：”);for(j=box_h,i=1;j!=NULL;j=j->next,i++)for(p=j->head;p!=NULL;p=p->link)}}問題描述：在8×8方格的棋盤上，從任意指定的方格出發(fā)，為馬尋找一條走遍棋盤每一格并且只經(jīng)過一次的一條路徑。馬在某個方格，可以在一步內(nèi)到達的不同位置最多有8個，如圖所示。如用二維數(shù)組（稱為著法）設(shè)定一個順序，如當(dāng)前位置在棋盤的ij）方格，下一個可能的位置依次），邊界的那些位置。為便于程序的同意處理，可以引入兩個數(shù)組，分別存儲各種可能走法對當(dāng)前位置的縱橫增量。馬其選擇下一出口的貪婪標(biāo)準(zhǔn)是在那些允許走的位置中，選擇出口最少的那個位置。如馬的2），如分別走到這些位置，這三個位置又分別會有不同的出口，假定這三個位置的出口個數(shù)分別為4、2、3，則程序就選擇讓馬走向-2，j+1）位置。由于程序采用的是一種貪婪法，整個找解過程是一直向前，沒有回溯，所以能非?？斓卣业浇?。但是，對于某些開始位置，實際上有解，而該算法不能找到解。對于找不到解的情況，程序只要改變8種可能出口的選擇順序，就能找到解。改變出口選擇順序，就是改變有相同出口時的選擇標(biāo)準(zhǔn)。以下程序考慮到這種情況，引入變sart，用于控制8種可能著法的選擇順序。開始時為0，當(dāng)不能找到解時，就讓start增1，【程序】intdelta_i[]={2,1,-1,-2,-2,-1,1,2};intdelta_j[]={1,2,2,1,-1,-2,-2,-1};intboard[8][8];intexitn(inti,intj,ints,inta[])for(count=k=0;k<8;k++)j1=i+delta_j[(s+k)%8];if(i1>=0&&i1<8&&j1>=0&&j1<8&&board[I1][j1]==0)a[count++]=(s+k)%8;}returncount;}{intm,k,mm,min,a[8],b[8],temp;m=exitn(i,j,s,a);for(min=9,k=0;k<m;k++){temp=exitn(I+delta_i[a[k]],j+delta_j[a[k]],s,b);kk=a[k];}}returnkk;}voidmain(){intsx,sy,i,j,step,no,start;board[j]=0;board[sx][sy]=1;For(step=2;step<64;step++){if((no=next(i,j,start))==-1)break;I+=delta_i[no];j+=delta_j[no];board[j]=step;}start++;}while(step<=64)printf(“%4d”,board[j]);}scanf(“%*c”);}}），的解求出原問題的解，那么這種分治法就是可行的。由分的較小模式，這就為使用遞歸技術(shù)提供了方便。在這種情解。這自然導(dǎo)致遞歸過程的產(chǎn)生。分治與遞歸像一對孿生上述的第一條特征是絕大多數(shù)問題都可以滿足的規(guī)模的增加而增加；第二條特征是應(yīng)用分治法的前提特征反映了遞歸思想的應(yīng)用；第三條特征是關(guān)鍵，能有第三條特征，如果具備了第一條和第二條特征，而法或動態(tài)規(guī)劃法。第四條特征涉及到分治法的效率，要做許多不必要的工作，重復(fù)地解公共的子問題，此））根據(jù)分治法的分割原則，原問題應(yīng)該分為多少個子問題才較適宜各個子問題的規(guī)模應(yīng)該怎樣才為適當(dāng)這些問題很難予以肯定的回答。但人們從大量實踐中發(fā)現(xiàn)，在用分治法設(shè)計算分治法的合并步驟是算法的關(guān)鍵所在。有些問題的合通常，在分析一個算法的計算復(fù)雜性時，都將加法和將執(zhí)行一次加法或乘法運算所需的計算時間當(dāng)作一個僅取這個假定僅在計算機硬件能對參加運算的整數(shù)直接若要精確地表示大整數(shù)并在計算結(jié)果中要求精確地XY=(A2n/2+B)(C2n/2+D)=AC2n+(AD+CB)2n），XY=AC2n+[(A-B)(D-C)+AC+BD]2n/2A=X的左邊n/2位;上述二進制大整數(shù)乘法同樣可應(yīng)用于十進制大在應(yīng)用中，常用諸如點、圓等簡單的幾何對象代表現(xiàn)實世這種方法主要計算時間花在排序上，因此如在排序算法中所證明的，然而這種方法無法直接推廣到二維的情形。因此，對這種一維的簡單情形，我們還是嘗試個基本要求是由此導(dǎo)出集合S的一個線性分割，即S=S1∪Floatpair（S）;}}選手的比賽日程表來決定。遞歸地用這種一分為二的策略（123）經(jīng)常會遇到復(fù)雜問題不能簡單地分解成幾個子地采用把大問題分解成子問題，并綜合子問題的解導(dǎo)【問題】求兩字符序列的最長公共字符子序列}}}printf(“LCS=%s\n”,build_lcs}任何思想方法都有一定的局限性，超出了特定條件，它就最優(yōu)化原理是動態(tài)規(guī)劃的基礎(chǔ)，任何問題，態(tài)規(guī)劃方法計算。根據(jù)最優(yōu)化原理導(dǎo)出的動態(tài)規(guī)劃基將各階段按照一定的次序排列好之后，對于某個給定的階段法直接影響它未來的決策，而只能通過當(dāng)前的這個動態(tài)規(guī)劃算法的關(guān)鍵在于解決冗余，這是動態(tài)規(guī)劃所以，能夠用動態(tài)規(guī)劃解決的問題還有一個顯著特征動態(tài)規(guī)劃適用的必要條件，但是如果該性質(zhì)無法滿轉(zhuǎn)移方程的動態(tài)規(guī)劃稱為標(biāo)準(zhǔn)動態(tài)規(guī)劃，這種標(biāo)準(zhǔn)導(dǎo)出來的，具有嚴(yán)格的數(shù)學(xué)形式，適合用于理論上成規(guī)模更小的子問題，并且原問題的最優(yōu)解中包含），動態(tài)規(guī)劃的實質(zhì)是分治思想和解決冗余，因此，經(jīng)作出的所有選擇，但不依賴于有待于做出的選不足的是，如果當(dāng)前選擇可能要依賴子問題的解最優(yōu)解；如果