算法設(shè)計(jì)與分析常見(jiàn)題

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

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

以D(r,j)表示第r行第j個(gè)數(shù)字(r，j都從1開(kāi)始算)，以MaxSum(r,j)代表從第r行的第j個(gè)數(shù)字終究邊的最正確路徑的數(shù)字之和，則此題是要求MaxSum(1,1)。從某個(gè)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)哪個(gè)更大了。程序如下：#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.馬的走法

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

算法思想：回溯法，馬當(dāng)前所在的位置是當(dāng)前擴(kuò)展結(jié)點(diǎn)，每個(gè)活結(jié)點(diǎn)可能有八個(gè)孩子結(jié)點(diǎn)。問(wè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.會(huì)餐交友

算法思想：

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

#include#defineMax500

intmain(){

//鄰接矩陣（對(duì)稱矩陣）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;}

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