算法设计与分析_2014期末考试题目

《算法设计与分析_2014期末考试题目》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1.中国象棋中马的走法回溯法！马当前所在的位置是当前扩展结点！每个活结点可能有八个孩子结点！如何记录马行走的路径？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;i++)for(intj=0;j<5;j++)chess[i][j]=0;}staticlongcomputer(){count=0;if(sx<0

2、

3、sy<0

4、

5、sx>

6、=6

7、

8、sy>=5)return;backtrack(sx,sy);returncount;}Privatestaticvoidbacktrack(intp1,intp2);};PrivatestaticvoidHorse::backtrack(intp1,intp2){intpi,pj;for(inti=0;i<7;i++){pi=p1+d[0][i];pj=p2+d[1][j];if(pi>=0&&pi<6&&pj>=0&&pj<5&&ch[pi][pj]==0){chess[pi][pj]=1;backtrack(pi,pj);chess[pi][pj]=0;}elseif(pi==s

9、x&&pj==sy)count++;}};2.合法的括号序列问题描述：定义合法的括号序列：1.空序列是合法的括号序列；2.如果符号串S是合法的括号序列，则(S)和[S]均是合法的括号序列；3.如果符号串A和B是合法的括号序列，则AB也是合法的括号序列。现有由(，)，[，]组成的任意符号串X=x1x2…xn，请添加尽可能少的四种括号，使其成为一个合法的括号序列。动态规划！分析：假设子问题Xij=xixi+1…xkxk+1…xj-1xj最少需要添加m[i][j]个括号，则：publicstaticintkh(char[]x){intn=x.length-1;int[][]m=newint[m+1

10、][n+1];for(inti=1;i<=n;i++)m[i][i-1]=0;for(inti=1;i<=n;i++)m[i][i]=1;for(intr=2;i<=n;r++)for(inti=1;i<=n-r+1;i++){intj=i+r-1;m[i][j]=MaxINT;if(x[i]==‘(‘&&x[j]==‘)’

11、

12、x[i]==‘[‘&&x[j]==‘]’)m[i][j]=min(m[i][j],m[i+1][j-1]);if(x[i]==‘(‘

13、

14、x[i]==‘[’)m[i][j]=min(m[i][j],m[i+1][j])+1;if(x[j]==‘)‘

15、

16、x[j]==‘]’

17、)m[i][j]=min(m[i][j],m[i][j-1])+1;for(intk=i;k

18、,y1)、右下角为(x2,y2)的棋盘的总分为：s[x1,y1,x2,y2]，被切割k次后得到的k+1块矩形的总分平方和的最小值是：d[k,x1,y1,x2,y2]则：d[k,x1,y1,x2,y2]=min{min{d[k-1,x1,y1,a,y2]+s[a+1,y1,x2,y2],d[k-1,a+1,y1,x2,y2]+s[x1,y1,a,y2]}(x1≤a＜x2),min{d[k-1,x1,y1,x2,b]+s[x1,b+1,x2,y2],d[k-1,x1,b+1,x2,y2]+s[x1,y1,x2,b]}(y1≤b＜y2),我们最终需要的是：d[n][1][1][8][8]4.多边形

19、游戏问题描述：a任意画了一个凸n边形，并任意对其n个顶点进行1到n的编号。A又再这个多边形上画了m条不会相交于多边形内部的弦。现在a以(i,j)的方式把这n条边和m条弦告诉给b，让b说出n边形的n个顶点的编号顺序。其中(i,j)是编号为i、j的两个顶点之间的一条边或者弦。问题分析：“m条不会相交与多边形内部的弦”表明：a画的n边形中至少有两个顶点不是任何弦的端点，而交于这个顶点的必定是多边形的边。这样的顶点的