牧师与野人课程设计

1、数 据 结 构课程设计报告设计题目: 牧师和野人问题 院 系： 经济管理学院 专业班级： 电子商务2010-2 学生姓名：孙印民、王倩、续琳琳指导教师： 周长红 2012年7月6日指导教师评语 指导教师： 年 月 日成绩评定学 号姓 名任务分工成绩1001060423孙印民概要、详细设计、调试分析、测试结果1001060429王倩设计内容、总结、排版1001060433续琳琳需求分析、设计成果展示、总结、排版目录1. 设计内容11.1问题描述11.2设计要求11.3开发环境11.4研究思路12. 设计步骤42.1需求分析42.2概要设计42.3详细设计62.4调试分析142.5测试结果163.

2、设计成果展示163.1用户手册163.2程序运行部分截图174.总结与心得体会20附 录22牧师与野人问题1. 设计内容1.1问题描述有三个牧师和三个野人过河，只有一条能装下两个人的船，在河的任一方或者船上，如果野人的人数大于牧师的人数，那么牧师就会有危险。你能不能找出一种安全的渡河方法呢？这个问题还可以扩展为N1个牧师和N2个野人，而船一次可以装下M个人的情况。1.2设计要求（1） 给出可能的方法总数，并描述每种方法的具体实现过程；（2） 当输入N1，N2，M的值时，输出程序的运行结果。1.3开发环境C-free1.4研究思路有N1个牧师和N2个野人来到河边准备渡河，河岸有一条船，每次至多可

3、供M人乘渡。问牧师为了安全起见，应如何规划摆渡方案，使得任何时刻，在河的两岸以及船上的野人数目总是不超过牧师的数目。即求解牧师和野人从左岸全部摆渡到右岸的过程中，任何时刻满足N1（牧师数）N2（野人数）和N1N2M的摆渡方案。 首先从比较简单的入手，先设N1=N23，M2，则给定的问题可用图1.2表示，图中L和R表示左岸和右岸，B1或0分别表示有船或无船。约束条件是：两岸上N1N2，船上N1N22。图1.2 N1N2问题实例 由于牧师和野人数是一个常数，所以知道了一岸的情况，另一岸的情况也就知道了。因此为了简便起见，在描述问题时，只描述一岸(如左岸）的情况就可以了。另外，该问题我们最关心的是在

4、摆渡过程中，两岸状态的变化情况，因此船上的情况并不需要直接表达出来。在一次摆渡过程中，船上究竟有几个牧师和野人，可以通过两个相连的状态简单得到。这样表达更简练，突出了问题的重点。（1）综合数据库：用三元组表示左岸的情况，即（N1，N2，B），其中0N1，N23，B0，1，其中N1表示在左岸的牧师人数，N2表示在左岸的野人数，B1表示船在左岸，B0表示船在右岸。则此时问题描述可以简化为：（3，3，1）（0，0，0）N3的N1N2问题，状态空间的总状态数为4×4×232，根据约束条件的要求，可以看出只有20个合法状态。再进一步分析后，又发现有4个合法状态实际上是不可能达到的。因

5、此实际的问题空间仅由16个状态构成。下表列出分析的结果：（N1 N2 B） （ 001）达不到（牧师均在右，船在左）（ 011） （ 021） （ 031） （ 101）不合法（右岸野人多） （ 111） （ 121）不合法（左岸野人多）（ 131）不合法（左岸野人多）（ 201）不合法（右岸野人多）（ 211）不合法（右岸野人多）（ 221） （ 231）不合法（左岸野人多）（ 301）达不到 （ 311） （ 321） （ 331） （N1 N2 B）（ 000）（ 010）（ 020）（ 030）达不到（ 100）不合法（右岸野人多）（ 110） （ 120）不合法（左岸野人多）（ 13

6、0）不合法（左岸野人多）（ 200）不合法（右岸野人多）（ 210）不合法（右岸野人多）（ 230）不合法（右岸野人多）（ 300） （ 220） （ 310） （ 320） （ 330）达不到 （2）规则集合:由摆渡操作组成。该问题主要有两种操作:从左岸划向右岸从右岸划向左岸。每次摆渡操作,船上人数有五种组合,因而组成有10条规则的集合。（3）初始和目标状态:即(3,3,1)和(0,0,0)，建立了产生式系统描述之后,就可以通过控制策略,对状态空间进行搜索,求得一个摆渡操作序列,使其实现目标状态。 2. 设计步骤2.1需求分析本程序主要实现提供在给定野人和牧师人数、船可以容纳人数的情况下，野

7、人和牧师同时使用船只渡河时成功渡河的方法，并且自动给出渡河的具体过程。（一）输入：本程序的设计考虑到了野人和牧师的人数、船可以容纳人数的动态设计，按照题目的要求，首先输入3个野人、3个牧师和船只容纳2人，也可以根据个人的需求动态输入其他数据，输入的数据限定为正整数。（二）输出：输出时野人和牧师每一次过河的过程都会进行输出，若动态输入的野人、牧师和船可以容纳人数无法满足安全渡河，则输出“无法成功渡河，牧师好郁闷！”（三）程序所能够达到的功能：在程序运行成功之后，程序能够根据输入的野人和牧师的人数、船可以容纳人数控制野人和牧师的渡河方式以实现成功渡河。（四）测试数据：程序运行成功之后电脑根据输入的

8、野人和牧师的人数、船只数进行设计渡船方式，如第一次输入的3个野人、3个牧师、船可容纳2人，会自动给出成功渡船的乘船方式及一共有多少种渡河方式，但是如果输入的人数和船可容纳人数无法实现成功渡河则渡河失败。2.2概要设计此程序主要是通过函数的调用实现的，程序中用了很多次的函数调用，程序中包含的函数有<1>insertson在邻接表中插入儿子结点；<2>insertbro在邻接表中插入兄弟结点，而且所有的兄弟结点都指向他们右边的结点；<3>findfa生成在船上牧师仍安全的几种情况；<4>jiancha安全性检查，检查在当前的情况下，牧师是否安全；&l

9、t;5>print打印安全渡河的过程；<6>work进行广度搜素，搜索可以渡河的过程。数据结构 typedef struct int ms; /mushi牧师的人数； int yr; /yeren 野人的人数； int cw; /chuanwei 船的状态（1表示船在甲岸，0表示船在乙岸）；DataType; / 定义结构体的名称；DataType fa50000; /定义一个DataTypa类型的数组；typedef struct node DataType data; / 数据域； struct node *son; / 儿子结点； struct node *bro; /

10、 兄弟结点； struct node *par; / 父亲结点； struct node *next; / 指针域，指向下一个结点；Ltable; /定义结构体的名称。主要函数<1>main /主函数，控制输入以及函数的调用；<2>insertson /在邻接表中插入儿子结点；<3>insertbro /在邻接表中插入兄弟结点，而且所有的兄弟结点都指向他们右边的结点；<4>findfa /生成在船上牧师仍安全的几种情况；<5>jiancha /安全性检查，检查在当前的情况下，牧师是否安全；<6>print /打印安全渡河的

11、过程；<7>work /进行广度搜素，搜索可以渡河的过程。函数之间的调用过程Main函数：输入牧师也野人的人数，与船可容纳的人数Ltableinit函数Insertson函数findfa函数Jiancha函数Insertson函数Insertbro函数Print函数Work函数，进行广度搜索返回主函数，从新下一个新的运行2.3详细设计（1）主函数int main() Ltable *p; DataType tem; Ltableinit(&p); /初始化邻接表; int n,c; printf("本程序由电子商务10级2班孙印民、续琳琳、王倩共同开发，欢迎使用！

12、n") ; while (1) /函数无限的循环，当一次运行结束以后可以重新输入数值，开始新的运算 printf("请输入牧师与野人的人数n:n"); scanf("%d",&n); if (n=0) break; printf("请输入船可容纳的人数c:n"); scanf("%d",&c); tem.ms=n; tem.yr=n; tem.cw=1; /开始赋值，1表示船在甲岸，0表示船在乙岸 insertson(p, tem); /将初始状态作为头结点的孩子结点；调用insertso

13、n函数 work(p,n,c); /进行广度搜索；调用work函数 return 1; /程序结束时返回1，以便下次程序的运行（2） void insertson(Ltable *head, DataType x) /在邻接表中插入儿子结点的操作 Ltable *q,*s; q=(Ltable *)malloc(sizeof (Ltable); q->data=x; head->son=q; s=head; while (s->next!=NULL) s=s->next; q->par=head; q->son=NULL; q->bro=NULL; s

14、->next=q; q->next=NULL;（3）void insertbro(Ltable *head,DataType x) /在邻接表中插入兄弟结点的操作，所有的兄弟结点都指向他们右边的结点； Ltable *q,*s; q=(Ltable *)malloc(sizeof (Ltable); s=head->son; q->data=x; while (s->bro!=NULL) s=s->bro; s->bro=q; s->next=q; q->next=NULL; q->bro=NULL; q->par=head;

15、q->son=NULL;（4）int findfa(DataType x,int n) /生成在船上牧师仍安全的几种情况； int i=0,a,b,t=0; /a表示船上牧师的人数，b表示船上野人的人数，t用来判断船上一共几个人 if(x.cw) /如果x.cw=1，即船在甲岸 a=0;b=n-a; while (a+b>=1) /船上有人 t+; while (b>=0) /野人的人数不小于0 fai.ms=a; fai.yr=b; /给fa数组赋值 i+; a+; b-; a=0; b=n-a-t; else / 船在乙岸 a=1;b=0;t=0; while (a+b&

16、lt;=n) /船上的人数小于等于船可以容纳的人数 t+; while (a>=0) /牧师人数大于等于0 fai.ms=a*(-1); fai.yr=b*(-1); /因为这是从乙岸到甲岸所以乘以（1） i+; a-; b+; a=fa0.ms*(-1)+t; b=0; return i; /返回i的值（5）jiancha(DataType x,int n)函数 /安全性检测，检查当前情况下，牧师是否安全 if (x.ms>=x.yr|x.ms=0)&&(n-x.ms)>=(n-x.yr)|x.ms=n)&&x.ms>=0&&a

17、mp;x.ms<=n&&x.yr>=0&&x.yr<=n)甲岸的牧师人数不小于野人，或牧师人数为0；乙岸牧师人数不小于野人人数，或牧师人数为0 return 1;牧师安全 else return 0;牧师不安全（6）print(Ltable *q,Ltable *p)函数 /打印安全渡河的过程 DataType a100; int i=1; a0.cw=0; a0.ms=0; a0.yr=0; /初始赋值 while (q!=p) /当p=q时一个渡河过程完成 ai+=q->data; q=q->par; while (-i)>

18、;-1) /一次渡河来回完成 printf("【 牧师%d 野人%d 船%d 】",ai.ms,ai.yr,ai.cw); if (!(ai.ms=0&&ai.yr=0&&ai.cw=0) /牧师的人数和野人的人数以及船在乙岸不同时成立 if (ai.cw=1) /船在甲岸 printf(" -> 【 牧师%d 野人%d 】 -> 【 牧师%d 野人%d 船0 】n",ai.ms-ai-1.ms,ai.yr-ai-1.yr,ai-1.ms,ai-1.yr); else /船在乙岸printf(" &l

19、t;- 【 牧师%d 野人%d 】 <- 【 牧师%d 野人%d 船1 】n",(ai.ms-ai-1.ms)*(-1),(-1)*(ai.yr-ai-1.yr),ai-1.ms,ai-1.yr); else printf("n"); /甲岸人数为0且船在乙岸 printf("渡河成功!n");（7）work(Ltable *p,int n,int c)函数 /进行广度搜索，搜索所有符合要求的渡河过程 Ltable *q,*t; DataType tem; int i,flag,flag1,g=0,j,count=0; / count表示

20、渡河的方法数 q=p->son; /把p的儿子结点赋值给q while (q!=NULL) / q为空说明没有孩子结点，即甲岸状态为0个牧师0个野人，渡船成功 flag=0; j=findfa(q->data,c);调用findfa函数，把findfa返回值i赋值给j； for (i=0;i<j;i+) tem.ms=q->data.ms-fai.ms; tem.yr=q->data.yr-fai.yr; tem.cw=1-q->data.cw; /赋值，其中数组fai为findfa函数中推出的牧师在船上安全的状态 t=q; if (jiancha (tem

21、,n) 调用jiancha函数，判断当前状态下牧师是否安全 flag1=1; while (t!=p) if(tem.ms=t->data.ms&&tem.yr=t->data.yr&&tem.cw=t->data.cw) flag1=0; break; t=t->par; /把t的父亲结点赋值给t if(flag1=1) if (flag=0) insertson(q, tem); /调用insertson函数，插入儿子结点flag=1; else insertbro(q,tem); /调用insertson函数，插入兄弟结点 if (

22、tem.ms=0&&tem.yr=0&&tem.cw=0) print(q,p); /调用print函数，输出渡河过程 count+; /运行一次加一表示一共有几种渡河的方法 q=q->next; /进行下一步的广度搜索 if (count=0) printf("无法成功渡河，牧师好郁闷!n"); else printf("有%d种渡河方式。n",count);2.4调试分析（1）遇到的的问题 <1>如何进行广度搜索，而且保证搜索的路径不重复。解决办法是：定义一个结构体Ltable： typedef st

23、ruct nodeDataType data; struct node *son, *bro ,*par, *next;Ltable;其中包括数据域、儿子结点、兄弟结点、父亲结点以及指针域，开始从head结点开始，然后找到它的儿子结点，判断是否牧师安全，是否可行，如果可行则找儿子结点的next域；如果不可行则找儿子结点的兄弟结点进行判定，如果可行则找其next域，不行则返回父亲结点；重复进行这个判断，直到成功渡河或全部搜索完毕。<2>如何设计船上的人数，使牧师一直保持安全状态。解决办法：定义一个findfa函数一方面用t控制船上所载的人数，而且另一方面规定牧师人数不小于野人人数或牧

24、师人数等于0，最后输出所以安全状态以便以后程序中的调用。（2）算法的时空分析 <1>时间复杂度：因为程序中用了很多循环语句while，而且在进行广度搜索的时候要把每种情况都要运算一遍，在每进行一次渡河时都要每个进行一遍搜索，所以时间复杂度很大，要进行很多步骤。 <2>空间复杂度 因为在程序中用了动态分配空间，用的时候再去申请空间，所以节省了很多不必要的空间，空间复杂度相对较小。（3）改进设想<1>由于每进行一次渡河过程的分析是都要把每中状态都要考虑一遍，使时间复杂度变得很大，所以设想让程序拥有记忆功能,把每一个路径都记录下了,以后在搜索其他渡河过程中直接调用

25、,这样会大大降低时间复杂度;<2>由于最后输出结果看起来不太清晰，不是那么直接，所以设想可以加入动态过程，动态的显示出渡河的方法。（4）经验与体会 这个程序用了很多的函数调用，通过函数的调用，使步骤减少了很多，变得比较简单；再有就是使用了链表与指针，大大减低了空间复杂度。2.5测试结果（1）当可以安全渡河时，会输出所有的渡河方法，并输出渡河成功的提示。例如这个程序说明开始先运两个野人然后回来一个野人，再运两个野人到乙岸然后回来一个野人，再运两个牧师然后回来一个牧师一个野人，再运两个牧师回来一个野人，再运两个野人然后回来一个牧师，最后运一个牧师一个野人到乙岸，渡河成功！ （2）当没有

26、成功渡河方法是，输出“无法成功渡河，牧师好郁闷！” 3.设计成果展示3.1用户手册（1）运行程序（2）程序运行成功后输入需要渡河的野人和牧师的人数、船可容纳人数，即可得到渡河的具体乘船方法。（3）若输入的野人和牧师的人数、船可容纳人数不能满足成功渡河，则渡河失败。3.2程序运行部分截图264.总结与心得体会两周的课程设计已经接近尾声了，在这两周中我们学到了很多，开始拿到题目时，我们三人分开查找资料，网上的资料真是五花八门，找了很多的资料，之后我们三人将所有的资料汇总研究，在研究的过程中，许多课本上不是很熟悉的知识也慢慢变得熟悉了，甚至还学到了许多课本上没有的知识。分析看懂程序的过程是艰难的，因

27、为程序不是自己写的，所以对于程序的思想以及所用的结构之类的都要重新思考和学习，废了很大的劲才弄懂，这让我们都知道了一个道理，那就是自己写程序才能更容易理解，因为思想是自己的，讲解起来也会很容易。之后，我们分工报告的写作，大家一人一部分，之后汇总，分工合作的速度和效率都是个人所远远比不上的，不管最后的结果怎样，这次的课程设计让我们不仅懂得了更多的知识，而且也认识到了合作的重要性。经过这次的课程设计，让我学到了不少，首先让我对编写程序的环境更加的熟悉了，对于编写程序也变得更加的熟练，可以自己尝试着编写一些独立程序了，对于课本上所学的知识也更加的印象深刻了。其次就是团队合作的问题，这一次是团队合作共

28、同来完成课题，在这个过程中，让我更加的意识到了团队的力量以及在团队合作中所获得的乐趣。                                           

29、;                                                  

30、;                   王倩以前接触过此类的题目，不过没有用程序编译过，刚刚接触这个程序对于野人和牧师如何过河能想出来，但是用程序实现有点困难，不知道从什么地方下手。但是通过在网上查找资料、同组员的一块讨论对这个程序的具体设计思想有了深入的了解。再者在这个过程中每个组员都是发挥自己所长让我们的课程设计更加完善，而且每次讨论过后我们都有自己新的收获，或是程序设计上的或是新的思想。在这次课程设计

31、中不仅提高了自己的程序编写能力，更加提高了我们彼此之间的合作意识。 续琳琳 通过这次的课程设计，一方面使我发现自己在基础知识方面掌握的还够好，还有很多方面要提高，在组织设计方面应该多去思考，想一想程序的结构，通过设计也发现了函数调用以及运用指针、链表可以使程序变得简洁方便；另一方面就是团队合作的重要性，有很多任务单凭自己的能力在有限的时间内是无法完成的，需要整个团队的努力，而且还可以弥补自己思路与方法上的不足之处，使任务更好的完成。 孙印民附 录一、主函数代码int main() Ltable *p; DataType tem; Ltableinit(&p); /初始化邻接表

32、; int n,c; printf("本程序由电子商务10级2班孙印民、续琳琳、王倩共同开发，欢迎使用！n") ; while (1) printf("请输入牧师与野人的人数n:n"); scanf("%d",&n); if (n=0) break; printf("请输入船可容纳的人数c:n"); scanf("%d",&c); tem.ms=n; tem.yr=n; tem.cw=1; insertson(p, tem); work(p,n,c); return 1;二、进行广度搜索void work(Ltable *p,int n,int c) Ltable *q,*t; DataType tem; int i,flag,flag1,g=0,j,count=0; q=p->son; while (q!=NULL) flag=0; j=findfa(q->data,c); for