算法設(shè)計與分析常見題

本文格式為Word版，下載可任意編輯——算法設(shè)計與分析常見題1.數(shù)字三角形

這道題目可以用遞歸的方法解決?；舅悸肥牵?/p>

以D(r,j)表示第r行第j個數(shù)字(r，j都從1開始算)，以MaxSum(r,j)代表從第r行的第j個數(shù)字終究邊的最正確路徑的數(shù)字之和，則此題是要求MaxSum(1,1)。從某個D(r,j)出發(fā)，顯然下一步只能走D(r+1,j)或者D(r+1,j+1)。

i.假使走D(r+1,j)，那么得到的MaxSum(r,j)就是MaxSum(r+1,j)+D(r,j)；

ii.假使走D(r+1,j+1)，那么得到的MaxSum(r,j)就是MaxSum(r+1,j+1)+D(r,j)。

所以，選擇往哪里走，就看MaxSum(r+1,j)和MaxSum(r+1,j+1)哪個更大了。程序如下：#include

#defineMAX_NUM100

intD[MAX_NUM+10][MAX_NUM+10];intN;

intMaxSum(intr,intj){if(r==N)

returnD[r][j];

intnSum1=MaxSum(r+1,j);intnSum2=MaxSum(r+1,j+1);if(nSum1>nSum2)

returnnSum1+D[r][j];returnnSum2+D[r][j];}

main(){intm;

scanf(\

for(inti=1;i#include

#defineMAX_NUM100

intD[MAX_NUM+10][MAX_NUM+10];intN;

intaMaxSum[MAX_NUM+10][MAX_NUM+10];main(){inti,j;

scanf(\for(i=1;i1;i--)for(j=1;jaMaxSum[i][j+1])

aMaxSum[i-1][j]=aMaxSum[i][j]+D[i-1][j];else

aMaxSum[i-1][j]=aMaxSum[i][j+1]+D[i-1][j];

}

printf(\}

2.馬的走法

問題描述：在4×5的棋盤上已知馬的起始坐標(biāo)(x,y)，求馬能夠返回到起始位置的不重復(fù)的所有不同走法的總數(shù)。

算法思想：回溯法，馬當(dāng)前所在的位置是當(dāng)前擴(kuò)展結(jié)點(diǎn)，每個活結(jié)點(diǎn)可能有八個孩子結(jié)點(diǎn)。問題所在：如何記錄馬行走的路徑？程序如下：classHorse{private:

intchess[5][6];

intd[2][8]={{1,2,2,1-1,-2,-2,-1},{2,1,-1,-2,-2,-1,1,2}};intsx,sy;intcount;public:

Horse(intx,inty){sx=x;sy=y;

for(inti=0;i=6||sy>=5)return;backtrack(sx,sy);returncount;}

Privatestaticvoidbacktrack(intp1,intp2);};

PrivatestaticvoidHorse::backtrack(intp1,intp2){

intpi,pj;

for(inti=0;i=0backtrack(pi,pj);chess[pi][pj]=0;}elseif(pi==sx}};

3.會餐交友

算法思想：

構(gòu)造一個對稱鄰接矩陣Friend[Max][Max]，第i行第j列的值為1代表i和j認(rèn)識。具體步驟很簡單。統(tǒng)計每一行值為1的個數(shù)，找出個數(shù)最大的行k，記錄下來，然后把第k行和第k列的元素全置為0（對稱矩陣）。循環(huán)執(zhí)行以上描述的步驟，直到鄰接矩陣所有元素為0跳出循環(huán)。程序如下：

#include#defineMax500

intmain(){

//鄰接矩陣（對稱矩陣）intFriend[Max][Max]={0};intn;cin>>n;

inti=-1,j=-1;while(i!=0||j!=0){cin>>i;cin>>j;Friend[i][j]=Friend[j][i]=1;}

//每次計算記錄每行的非零個數(shù)intcount[Max]={0};