算法设计与分析常见题

本文格式为Word版，下载可任意编辑——算法设计与分析常见题1.数字三角形

这道题目可以用递归的方法解决。基本思路是：

以D(r,j)表示第r行第j个数字(r，j都从1开始算)，以MaxSum(r,j)代表从第r行的第j个数字终究边的最正确路径的数字之和，则此题是要求MaxSum(1,1)。从某个D(r,j)出发，显然下一步只能走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的棋盘上已知马的起始坐标(x,y)，求马能够返回到起始位置的不重复的所有不同走法的总数。

算法思想：回溯法，马当前所在的位置是当前扩展结点，每个活结点可能有八个孩子结点。问题所在：如何记录马行走的路径？程序如下：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.会餐交友

算法思想：

构造一个对称邻接矩阵Friend[Max][Max]，第i行第j列的值为1代表i和j认识。具体步骤很简单。统计每一行值为1的个数，找出个数最大的行k，记录下来，然后把第k行和第k列的元素全置为0（对称矩阵）。循环执行以上描述的步骤，直到邻接矩阵所有元素为0跳出循环。程序如下：

#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;}

//每次计算记录每行的非零个数intcount[Max]={0};