迷宫问题和农夫过河问题
内容摘要
程序设计的基本概念有程序、数据、子程序、子例程、协同例程、模块以及顺序性、并发性、并行性、和分布性等。程序是程序设计中最为基本的概念，子程序和协同例程都是为了便于进行程序设计而建立的程序设计基本单位，顺序性、并发性、并行性和分布性反映程序的内在特性。 程序设计规范是进行程序设计的具体规定。
程序设计是软件开发工作的重要部分，而软件开发是工程性的工作，所以要有规范。语言影响程序设计的功效以及软件的可靠性、易读性和易维护性。专用程序为软件人员提供合适的环境，便于进行程序设计工作。 关键词：程序设计；专用程序；环境；
目 录
一、引言 …………………………………………………………………1
（一）研究的缘起…………………………………………………… 1 （二）本文的研究思路、方法及意义……………………………… 1 （三）相关理论基础………………………………………………… 1
二、实验过程分析………………………………………………………1
（一）数据和函数说明 ……………………………………………1 （二）实验工具 ………………………………………………………3
三、结果与讨论 ………………………………………………… 3
（一）分析与讨论…………………………………………………… 3 （二）研究与结论…………………………………………………… 4
四、参考文献…………………………………………………………… 5
一、引言
（一）研究的缘起
1.迷宫问题的要求就是：从入口到出口的一个以空白方块构成的（无环）路径。
2. 一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西全部运到北岸。问题是他只有一条小船，船小的只能容下他和一件物品，当然，船只有农夫能撑。另外，因为狼能吃羊，而羊爱吃白菜，所以农夫不能留下羊和狼或者羊和白菜单独在河一边，自己离开。好在狼属于食肉动物，它不吃白菜。请问农夫该采取什么方案，才能将所有的东西安全运过河？
（二）本文的研究思路、方法及意义
1. 创建表头，定义创建空栈的函数，判断栈是否为空的函数，压栈的函数，取栈顶的函数，弹出栈顶元素的函数，mazePath 函数和主函数。
2. 创建表头，定义创建空队的函数，判断队列是否为空的函数，进队的函数，出队的函数，去队头元素的函数，判断农夫、狼、白菜和羊位置的函数，safe 函数和主函数。
（三）相关理论基础
1. if语句，for 循环语句和While 语句以及简单的输入和输出。 2. if 语句，for 循环语句和While 语句以及简单的输出。
二、实验过程分析
（一）数据和函数说明 1.
void mazePath(int *maze[],int *direction[],int x1,int y1,int x2,int y2,int M,int N)
//迷宫maze[M][N]中求从入口maze[x1][y1]到出口maze[x2][y2]的一条路径
//其中1
int i,j,k; int g,h;
PSeqStack st; PSeqStack ne;
DataType element;
st=createEmptyStack_seq(M*N); ne=createEmptyStack_seq(M*N);
maze[x1][y1]=2; //从入口开始进入，做标记 element.x=x1; element.y=y1; element.d=-1;
push_seq(st,element); //入口点进栈
while(!isEmptyStack_seq(st)) //走不通时，一步步退回 {
element=top_seq(st); pop_seq(st); i=element.x; j=element.y; k=element.d+1;
while(k
g=i+direction[k][0]; h=j+direction[k][1];
if(g==x2&&h==y2&&maze[g][h]==0) //走到出口点 {
element.x=i; element.y=j;
push_seq(st,element); element.x=g; element.y=h;
push_seq(st,element); printf("the path is:\n");
while(!isEmptyStack_seq(st)) {
element=top_seq(st); pop_seq(st);
push_seq(ne,element); }
while(!isEmptyStack_seq(ne)) {
element=top_seq(ne); pop_seq(ne);
printf("the node is:%d %d\n",element.x,element.y); } return; }
if(maze[g][h]==0) //走到没走过的点 {
maze[g][h]=2; //做标记 element.x=i; element.y=j; element.d=k;
push_seq(st,element); //进栈
i=g; //下一点转换为当前点 j=h; k=-1; }
k=k+1; } }
printf("The path has not been found.\n"); //打印路径上的每一点 }
2.
int main() {
int i,movers,location,newlocation;
int route[16]; //用于记录已考虑好的路径
PSeqQueue moveTo; //用于记录可以安全到达的中间状态 moveTo=createEmptyQueue_seq(M); //创建空队列 enQueue_seq(moveTo,0x00); //初始状态进队列 for(i=0;i
while(!isEmptyQueue_seq(moveTo)&&route[15]==-1) {
location=frontQueue_seq(moveTo);//去队头状态为当前状态 deQueue_seq(moveTo);
for(movers=1;movers
newlocation=location^(0x08|movers);//计算新状态 if(safe(newlocation)&&route[newlocation]==-1) { //新状态安全且未处理
route[location]=newlocation;//记录新状态的前驱 enQueue_seq(moveTo,newlocation);//新状态入队 } }
else
route[newlocation]=location; }
if(route[15]!=-1) //打印路径 {
printf("The path is:\n");
for(location=0;location
printf("the location is :%d\n",location); if(location==15) exit(0); } } else
printf("No solution.\n"); //问题无解 return 0; }
（二）实验工具：Microsoft Visual C++ 6.0和截图工具。
三、结果与讨论
（一）分析与讨论 1.
for (q=0;q
p2[p]=direction[p];
这两个for 循环将maze [q]和direction[p]的值分别复制到p1[q]和p2[p]
中。
int *p1[8],*p2[4];定义了整型的指针数组，是为了mazePath 函数能够引用。 2.
int safe(int location) {
if((goat(location)==cabbage(location))&&(goat(location)!=farmer(location))) return 0;
if((goat(location)==wolf(location))&&(goat(location)!=farmer(location)))
return 0; return 1; }
这个安全函数是农夫问题的限制条件，也就是题目中要求的狼吃羊，而羊爱吃白菜，所以农夫不能留下羊和狼或者羊和白菜单独在河一边，自己离开。
（二）研究结论 1. 运行结果：
分析：通过添加一个栈让路径正向输出。
2. 运行结果：
分析：如果通过添加一个栈让输出的路径为正向的话，那工程是很大的。要是再添加一个队列的话，还是做不到正向路径的输出。因此，我在主函数上进行修改，让反向路径变成正向路径输出。
四、参考文献
1、许卓群，张乃孝，杨冬青，等. 数据结构[M].北京：高等教育出版社，1987. 2、张乃孝. 数据结构体系分析[J].计算机研究与发展，1988，25（5）：36-40 3、张乃孝. 三叉树及其实现[J].计算机研究与发展，1993，30（1）：50-54 4、张乃孝，于晓迪. 有关C 语法形式化中若干问题的探讨[J].计算机工程与 应用，1985，2：1-5