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

时间：2025-07-05

1. 中国象棋中马的走法

回溯法！

马当前所在的位置是当前扩展结点！

每个活结点可能有八个孩子结点！

如何记录马行走的路径？

class Horse{

private:

int chess[5][6];

int d[2][8]={(1,2,2,1-1,-2,-2,-1),(2,1,-1,-2,-2,-1,1,2)};

int sx,sy;

int count;

public:

Horse(int x,int y) {

sx=x; sy=y;

for(int i=0;i<6;i++)

for(int j=0;j<5;j++) chess[i][j]=0;

}

static long computer(){

count=0;

if(sx<0||sy<0||sx>=6||sy>=5) return ;

backtrack(sx,sy);

return count;

}

Private static void backtrack(int p1,int p2);

};

Private static void Horse:: backtrack(int p1,int p2){

int pi,pj;

for(int i=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;

} else if(pi==sx&&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]个括号，则：

public static int kh(char []x)

{ int n=x.length-1;

int [][]m=new int [m+1][n+1];

for(int i=1; i<=n; i++) m[i][i-1]=0;

for(int i=1; i<=n; i++) m[i][i]=1;

for(int r=2; i<=n; r++)

for(int i=1; i<=n-r+1; i++)

{ int j=i+r-1; m[i][j]=MaxINT;

if(x[i]==‘(‘&&x[j]==‘)’ || x[i]==‘[‘&&x[j]==‘]’ )

m[i][j]=min(m[i][j], m[i+1][j-1]);

if(x[i]==‘(‘ || x[i]==‘[’)

m[i][j]=min(m[i][j], m[i+1][j])+1;

if(x[j]==‘)‘ || x[j]==‘]’)

m[i][j]=min(m[i][j], m[i][j-1])+1;

for(int k=i; k<j; k++)

m[i][j]=min(m[i][j], m[i][k]+m[k+1][j])

return m[1][n];

}

3. 棋盘的最优分割

问题描述：

一个8×8的棋盘中每个格子里均有一个分值。对棋盘沿着任意一条格子线进行一次分割，将使棋盘成为两块矩形棋盘。给定n<15，对原棋盘进行n-1次分割，就把棋盘分割成了n块矩形棋盘。一块矩形棋盘的总分是他的所有格子的分值之和。请设计算法，给出把原棋盘分割成n块矩形棋盘的方案，使得各矩形棋盘总分的平方和最小。其中xi是第i块棋盘的总分。

动态规划！

假设左上角为(x1,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. 多边形游戏