suanfafenxi.txt

算法设计与分析的实验指导

X.X.XX.....X
X.X.XX.XXX.X
X.X.....X..X
X.XXXXXXXXXX
X...X.X....X
X.XXX...XXXX
X.....X....X
XXX.XXXX.X.X
XXXXXXX..XXX
XXXXXXXXXXXX
注：测试数据可在运行时粘贴上去（点击窗口最左上角按钮，在菜单中选则“编辑”/“粘贴”即可）。
想一想：此程序都存在哪些问题，如果openlen太小程序会不会出错，加入代码使程序能自动报出此类错误。
3.	跳马
给一个200×200的棋盘，问国际象棋的马从给定的起点到给定的终点最少需要几步。
Sample Input  0 0 1 1  Sample output  4
	状态：马所在的行、列。
程序如下：
#include<stdio.h>
void readdata();                //读入数据
void init();                    //初始化
int search();                   //广度优先搜索
int emptyopen();                //判栈是否为空：空：1；非空：0。
long takeoutofopen();           //从栈中取出一个元素，并把该元素从栈中删除
int canmoveto(int,int,int*,int*,int);    //判能否移动到该方向，并带回坐标(r,c)
int isaim(int row, int col);             //判断该点是否是目标
int used(int,int);                       //判断该点是否已经走过
void addtoopen(int,int);                 //把该点加入到open表
int a[200][200],n=200;                   //a存放棋盘，n为迷宫边长
long open[2000],head,tail,openlen=2000;  //open表1367
long s,t;                                //起点和终点
int search()
{
	long u;
	int row, col, r, c, i, num;
	while(!emptyopen())         //当栈非空
	{
		u=takeoutofopen();      //从栈中取出一个元素，并把该元素从栈中删除
		row=u/n;              //计算该点所在的行
		col=u%n;             //计算该点所在的列
		num=a[row][col];      //取得该点的步数
		for(i=0;i<8;i++)
		{
			if(canmoveto(row,col,&r,&c,i))   //判能否移动到该方向，并带回坐标(r,c)
			{
				if(isaim(r,c))              //如果是目标结点
					return(num+1);       //返回最小步数
				if(!used(r,c))              //如果(r,c)还未到达过
				{
					a[r][c]=num+1;       //记录该点的最小步数
					addtoopen(r,c);       //把该点加入到open表
				}
			}
		}
	}
	return -1;
}
int main()                //为了让search()显示在一页内和main函数换了以下
{                       //一般的算法程序main函数写在最上面读起来更方便
	int number;
	readdata();           //读取数据
	init();               //初始化
	number=search();     //广搜并返回最小步数
	printf("%d",number);  //打印结果
}
int emptyopen()
{
	if(head==tail)
		return(1);
	else
		return(0);
}
long takeoutofopen()
{
	long u;
	if(head==tail)
	{
		printf("errer: stack is empty");
		return(-1);
	}
	u=open[head++];
	head=head%openlen;
	return(u);
}
int used(int row, int col)
{
	if(a[row][col]==0)
		return(0);
	else
		return(1);
}
void addtoopen(int row, int col)
{
	int u;
	if((head-tail)%openlen==1)
		printf("open table overflow");
	u=row;
	u=u*n+col;
	open[tail++]= u;
	tail=tail%openlen;
}
void readdata()
{
	long row,col;
	scanf("%ld%ld",&row,&col);  //起点坐标
	s=row*n+col;
	scanf("%ld%ld",&row,&col);  //终点坐标
	t=row*n+col;
}
void init()
{
	head=0;
	tail=1;
	open[0]=s;
}
int isaim(int row, int col)
{
	if(row*n+col==t)
		return(1);
	else
		return(0);
}
思考：参考第4题，改为用结构体表示状态写此程序。
4.	独轮车
独轮车的轮子上有5种颜色，每走一格颜色变化一次，独轮车只能往前推，也可以在原地旋转，每走一格，需要一个单位的时间，每转90度需要一个单位的时间，转180度需要两个单位的时间。现给定一个20×20的迷宫、一个起点、一个终点和到达终点的颜色，问独轮车最少需要多少时间到达。
状态：独轮车所在的行、列、当前颜色、方向。
另外为了方便在结点中加上到达该点的最小步数。
	程序如下：
#include<stdio.h>
struct colornode
{
	int row;                        //该状态的行
	int col;                         //        列
	int color;                       //        颜色
	int direction;                    //        方向
	int num;                       //        最小步数
};
int search();                        //广搜返回目标结点的最小步数
void readdata();                     //读入数据
void init();                         //初始化
struct colornode moveahead(struct colornode u);  //返回u向前走一格得到的结点
int used(struct colornode v);        //判断该结点是否是到达过的结点
void addtoopen(struct colornode v);  //加入到open表
int islegal(struct colornode v);      //如果该结点是合法的结点(未越界且是空格)
int isaim(struct colornode v);       //判断该结点是否是目标结点
struct colornode takeoutofopen();    //从open表中取出一个结点并把该结点从open表中删除
struct colornode turntoleft(struct colornode u);     //u向左转得到新结点v
struct colornode turntoright(struct colornode u);    //u向左转得到新结点v
struct colornode s,t;                //s:起始结点；t目标结点
struct colornode open[200];          //open表
int head,tail,openlen=200;           //open表相关数据
int direct[4][2]={{0,-1},{1,0},{0,1},{-1,0}};//向左、下、右、上四个方向转时，行列的增加值
int a[20][20],n=20;                  //a数组表示迷宫；n为迷宫边长
int b[20][20][5][4];                 //b数组表示搜索时的所有状态(0：未访问；1：已访问)
int main()
{
	int number;
	readdata();
	init();
	number=search();
	printf("%d\n",number);
}
int search()                        //广搜返回目标结点的最小步数
{
	struct colornode u,v;
	while(head!=tail)
	{
		u=takeoutofopen();
		v=moveahead(u);          //u向前走一格得到新结点v
		if(islegal(v))                  //如果该结点是合法的结点(未越界且是空格)
		{
			if(isaim(v))               //判是否是目标结点
				return(v.num);
			if(!used(v))               //如果是未到达过的结点
				addtoopen(v);        //加入到open表
		}
		v=turntoleft(u);           //u向左转得到新结点v
		if(!used(v))
			addtoopen(v);
		v=turntoright(u);         //u向右转得到新结点v
		if(!used(v))
			addtoopen(v);
	}
}
int used(struct colornode v)        //判断该结点是否是到达过的结点
{
	if(b[v.row][v.col][v.color][v.direction]==0)
		return(0);
	else
		return(1);
}
void addtoopen(struct colornode v)  //加入到open表
{
	open[tail++]=v;
	tail=tail%openlen;
	b[v.row][v.col][v.color][v.direction]=1;
}
struct colornode takeoutofopen()    //从open表中取出一个结点并把该结点从open表中删除
{
	struct colornode v;
	v=open[head++];
	head=head%openlen;
	return(v);
}
void init()                         //初始化
{
	int i,j,k,l;
	for(i=0;i<n;i++)                //所有状态初始化
		for(j=0;j<n;j++)
			for(k=0;k<5;k++)
				for(l=0;l<4;l++)
					b[i][j][k][l]=0;
	head=0;
	tail=0;
	addtoopen(s);                   //把起始点加入到open表
}
void readdata()                     //读入数据
{
	char str[50];	int i,j;
	for(i=0;i<n;i++)
	{
		gets(str);
		for(j=0;j<n;j++)
			if(str[j]=='.')          //读入数据'.'表示空格
				a[i][j]=0;           //存储时  0：表示空格
			else
				a[i][j]=1;           //        1：表示墙
	}
	scanf("%d%d%d%d",&s.row,&s.col,&s.color,&s.direction);  //读入起始结点信息
	scanf("%d%d%d",&t.row,&t.col,&t.color);                 //读入目标结点信息
}
int isaim(struct colornode v)       //判断该结点是否是目标结点
{
	if(v.row==t.row&&v.col==t.col&&v.color==t.color)
		return 1;
	else
		return 0;
}
int islegal(struct colornode v)     //如果该结点是合法的结点(未越界且是空格)
{
	if(v.row<0||v.row>=n||v.col<0||v.col>=n)  //若越界
		return 0;
	if(a[v.row][v.col]==0)                 //0：表示空格
		return 1;
	return 0;
}
struct colornode moveahead(struct colornode u)  //返回u向前走一格得到的结点
{
	struct colornode v;
	v.row=u.row+direct[u.direction][0];
	v.col=u.col+direct[u.direction][1];
	v.color=(u.color+1)%5;
	v.direction=u.direction;
	v.num=u.num+1;
	return(v);
}
struct colornode turntoleft(struct colornode u)     //u向左转得到新结点v
{
	struct colornode v;
	v=u;
	v.direction=(v.direction+1)%4;
	v.num=v.num+1;
	return(v);
}
struct colornode turntoright(struct colornode u)     //u向左转得到新结点v
{
	struct colornode v;
	v=u;
	v.direction=(v.direction+3)%4;
	v.num=v.num+1;
	return(v);
}
	测试数据：
XXXXXXXXXXXXXXXXXXXX
.....XXXX......X.XXX
X.........X.XX.....X
X.XXX.XX..X.XX.XXX.X
X.........X.XX.....X
X.XXX.XX..X.XX.XXX.X
.X.....XX.X.....X..X
X....X..X...X.X....X
...XXXX.X.XXX...XXXX
...........X.......X
XXXXXX....XXXXXX..XX
...........X.......X
.X.....XX.X.....X..X
XXXXXX....XXXXXXXX.X
X....X..X...X.X....X
...XXXX.X.XXX...XXXX
...........X.......X
XXX.X.XXXXX.XXXX.X.X
....X.XX....XXX.....
XXXX.....XX.........
1 1 1 1 4 8 1
5.	皇宫小偷
有一个小偷要到皇宫里偷取宝物，经过仔细的侦察，他发现皇宫实际上是一个20×20的迷宫，并且有一名卫兵巡逻，卫兵巡逻的路线是固定的，每单位时间移动一格，每4个单位时间循环一次。小偷每单位时间移动一格或在原地不动。任何时刻，小偷和卫兵在同一格，或卫兵能看到小偷，小偷将会被卫兵杀死。现在小偷已经得到了皇宫的地图，卫兵巡逻的起点，卫兵连续四次移动的方向和宝物的位置，请你设计一个程序判断小偷能否偷得宝物。
提示：参考第3题、第4题
6.	分酒问题
有一酒瓶装有8斤酒，没有量器，只有分别装5斤和3斤的空酒瓶。设计一程序将8斤酒分成两个4斤，并以最少的步骤给出答案。
7.	*找倍数
对于每个输入的数字（如：2），则要求 给出一个由1，0构成的十进制整数，且该整数为输入数字的某个倍数（如2对应的10，6的倍数100100100100100100）。
8.	*8数码难题
由左图变到右图最少需要几步，并演示移动过程。
 
 
实验四：动态规划
实验目的：理解动态规划的基本思想，理解动态规划算法的两个基本要素最优子结构性质和子问题的重叠性质。熟练掌握典型的动态规划问题。掌握动态规划思想分析问题的一般方法，对较简单的问题能正确分析，设计出动态规划算法，并能快速编程实现。
实验内容：编程实现讲过的例题：最长公共子序列问题、矩阵连乘问题、凸多边形最优三角剖分问题、电路布线问题等。本实验中的问题，设计出算法并编程实现。
习题
1．	最长公共子序列
一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列X=<x1, x2,…, xm>，则另一序列Z=<z1, z2,…, zk>是X的子序列是指存在一个严格递增的下标序列 <i1, i2,…, ik>，使得对于所有j=1,2,…,k有
 
解答如下：
a) 最长公共子序列的结构
若用穷举搜索法，耗时太长，算法需要指数时间。
易证最长公共子序列问题也有最优子结构性质
设序列X=<x1, x2, …, xm>和Y=<y1, y2, …, yn>的一个最长公共子序列Z=<z1, z2, …, zk>，则：
i.	若xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列； 
ii.	若xm≠yn且zk≠xm ，则Z是Xm-1和Y的最长公共子序列； 
iii.	若xm≠yn且zk≠yn ，则Z是X和Yn-1的最长公共子序列。 
其中Xm-1=<x1, x2, …, xm-1>，Yn-1=<y1, y2, …, yn-1>，Zk-1=<z1, z2, …, zk-1>。
最长公共子序列问题具有最优子结构性质。
b) 子问题的递归结构
由最长公共子序列问题的最优子结构性质可知，要找出X=<x1, x2, …, xm>和Y=<y1, y2, …, yn>的最长公共子序列，可按以下方式递归地进行：当xm=yn时，找出Xm-1和Yn-1的最长公共子序列，然后在其尾部加上xm(=yn)即可得X和Y的一个最长公共子序列。当xm≠yn时，必须解两个子问题，即找出Xm-1和Y的一个最长公共子序列及X和Yn-1的一个最长公共子序列。这两个公共子序列中较长者即为X和Y的一个最长公共子序列。
由此递归结构容易看到最长公共子序列问题具有子问题重叠性质。例如，在计算X和Y的最长公共子序列时，可能要计算出X和Yn-1及Xm-1和Y的最长公共子序列。而这两个子问题都包含一个公共子问题，即计算Xm-1和Yn-1的最长公共子序列。
我们来建立子问题的最优值的递归关系。用c[i,j]记录序列Xi和Yj的最长公共子序列的长度。其中Xi=<x1, x2, …, xi>，Yj=<y1, y2, …, yj>。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列，故c[i,j]=0。建立递归关系如下：
 

c) 计算最优值
由于在所考虑的子问题空间中，总共只有θ(m*n)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。
计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X=<x1, x2, …, xm>和Y=<y1, y2, …, yn>作为输入。输出两个数组c[0..m ,0..n]和b[1..m ,1..n]。其中c[i,j]存储Xi与Yj的最长公共子序列的长度，b[i,j]记录指示c[i,j]的值是由哪一个子问题的解达到的，这在构造最长公共子序列时要用到。最后，X和Y的最长公共子序列的长度记录于c[m,n]中。
程序如下：
#include<stdio.h>
#include<string.h>
int lcs_length(char x[], char y[]);
int main()
{
	char x[100],y[100];
	int len;
	while(1)
	{
		scanf("%s%s",x,y);
		if(x[0]=='0')           //约定第一个字符串以‘0’开始表示结束
			break;
		len=lcs_length(x,y);
		printf("%d\n",len);
	}
}
int lcs_length(char x[], char y[] )
{