《牧师与野人课程设计》由会员分享，可在线阅读，更多相关《牧师与野人课程设计（16页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计报告设计题目:牧师和野人问题院 系：经济管理学院专业班级：电子商务2010-2学生姓名：孙印民、王倩、续琳琳指导教师：周长红2012年7月6日指导教师评语指导教师：年 月 日成绩评定学号姓名任务分工成绩1001060423孙印民概要、详细设计、调试分析、测试结果1001060429王倩设计内容、总结、排版1001060433续琳需求分析、设计成果展示、总结、排版目录1设计内容1.11.4研究思路有N1个牧师和N2个野人来到河边准备渡河，河岸有一条船，每次至多 可供M人乘渡。问牧师为了安全起见，应如何规划摆渡方案，使得任何时 刻，在河的两岸以及船上的野人数目总是不超过牧师的数目。
2、即求解牧师 和野人从左岸全部摆渡到右岸的过程中，任何时刻满足N1 （牧师数）$N2 （野人数）和N1 + N2WM的摆渡方案。首先从比较简单的入手，先设N1=N2 = 3, M=2,则给定的问题可用图1.2 表示，图中L和R表示左岸和右岸，B=1或0分别表示有船或无船。约束 条件是：两岸上N12N2，船上N1 + N2W2。LRN10溝N203M01L.RXI30N230BL0图1.2 N1-N2问题实例由于牧师和野人数是一个常数，所以知道了一岸的情况，另一岸的情况 也就知道了。因此为了简便起见，在描述问题时，只描述一岸（如左岸）的 情况就可以了。另外，该问题我们最关心的是在摆渡过程中，两岸状
3、态的变化情况，因 此船上的情况并不需要直接表达出来。在一次摆渡过程中，船上究竟有几 个牧师和野人，可以通过两个相连的状态简单得到。这样表达更简练，突 出了问题的重点。（1）综合数据库：用三元组表示左岸的情况，即（Nl, N2, B）,其中 0WN1, N2W3, Be 0，1，其中N1表示在左岸的牧师人数，N2表示在左 岸的野人数，B=1表示船在左岸，B = 0表示船在右岸。则此时问题描述可 以简化为：（3, 3, 1）-（0, 0, 0） N = 3的N1-N2问题，状态空间的总 状态数为4X4X2 = 32，根据约束条件的要求，可以看出只有20个合法状 态。再进一步分析后，又发现有4个合法
4、状态实际上是不可能达到的。因 此实际的问题空间仅由16个状态构成。下表列出分析的结果：(N1N2 B)(N1N2 B)(001）达不到(00 0)（牧师均在右，船在左）(01 0)(01 1)(02 0)(02 1)(030）达不到(03 1)(10 0）不合法（右岸野人多）(101）不合法（右岸野人多）(11 0)(11 1)(12 0）不合法（左岸野人多）(121）不合法（左岸野人多）(13 0）不合法（左岸野人多）(131)不合法(左岸野人多)(2 01)不合法(右岸野人多)(211)不合法(右岸野人多)(2 2 1)(2 31)不合法(左岸野人多)(301)达不到(311)(321)(
5、331)(2 0 0)不合法(右岸野人多)(21 0)不合法(右岸野人多)(2 30)不合法(右岸野人多)(30 0)(2 2 0)(310)(320)(330)达不到(2) 规则集合：由摆渡操作组成。该问题主要有两种操作：从左岸划 向右岸从右岸划向左岸。每次摆渡操作，船上人数有五种组合,因而组成 有10条规则的集合。(3) 初始和目标状态：即(3,3,1 )和(0,0,0),建立了产生式系统描述之 后,就可以通过控制策略,对状态空间进行搜索,求得一个摆渡操作序列，使 其实现目标状态。2设计步骤2.1需求分析本程序主要实现提供在给定野人和牧师人数、船可以容纳人数的情况 下，野人和牧师同时使用船
6、只渡河时成功渡河的方法，并且自动给出渡河 的具体过程。(一) 输入：本程序的设计考虑到了野人和牧师的人数、船可以容纳人 数的动态设计，按照题目的要求，首先输入3个野人、3个牧师和船只容纳 2人，也可以根据个人的需求动态输入其他数据,输入的数据限定为正整数。（二）输出：输出时野人和牧师每一次过河的过程都会进行输出，若动 态输入的野人、牧师和船可以容纳人数无法满足安全渡河，则输出“无法 成功渡河，牧师好郁闷！”（三）程序所能够达到的功能：在程序运行成功之后，程序能够根据输 入的野人和牧师的人数、船可以容纳人数控制野人和牧师的渡河方式以实 现成功渡河。（四）测试数据:程序运行成功之后电脑根据输入的野
7、人和牧师的人数、 船只数进行设计渡船方式，如第一次输入的3个野人、3个牧师、船可容纳 2人，会自动给出成功渡船的乘船方式及一共有多少种渡河方式，但是如果 输入的人数和船可容纳人数无法实现成功渡河则渡河失败。2.2概要设计此程序主要是通过函数的调用实现的，程序中用了很多次的函数调用， 程序中包含的函数有vlinsertson在邻接表中插入儿子结点；insertbro 在邻接表中插入兄弟结点，而且所有的兄弟结点都指向他们右边的结点； findfa生成在船上牧师仍安全的几种情况；jiancha安全性检查，检 查在当前的情况下，牧师是否安全；print打印安全渡河的过程；work 进行广度搜素，搜索可
8、以渡河的过程。数据结构typedef structint ms; /mushi 牧师的人数；int yr; /yeren野人的人数；int cw; /chuanwei船的状态（1表示船在甲岸，0表示船在乙岸）;DataType; /定义结构体的名称；DataType fa50000; /定义一个 DataTypa 类型的数组；typedef struct nodeDataType data; /数据域；struct node *son; / 儿子结点；struct node *bro; / 兄弟结点；struct node *par; / 父亲结点；struct node *next; /指针
9、域，指向下一个结点；Ltable; 定义结构体的名称。主要函数vlmain /主函数，控制输入以及函数的调用；insertson 在邻接表中插入儿子结点；insertbro 在邻接表中插入兄弟结点，而且所有的兄弟结点都指向他们 右边的结点；findfa 生成在船上牧师仍安全的几种情况；jiancha 安全性检查，检查在当前的情况下，牧师是否安全；print 打印安全渡河的过程；work 进行广度搜素，搜索可以渡河的过程。函数之间的调用过程2.4调试分析（1）遇到的的问题如何进行广度搜索，而且保证搜索的路径不重复。解决办法是：定义一个结构体 Ltable: typedef struct node
10、DataType data; struct node*son, *bro ,*par, *next;Ltable;其中包括数据域、儿子结点、兄弟结点、父亲 结点以及指针域，开始从head结点开始，然后找到它的儿子结点，判断是 否牧师安全，是否可行，如果可行则找儿子结点的next域；如果不可行则 找儿子结点的兄弟结点进行判定，如果可行则找其next域，不行则返回父 亲结点；重复进行这个判断，直到成功渡河或全部搜索完毕。如何设计船上的人数，使牧师一直保持安全状态。解决办法：定义一个 findfa函数一方面用t控制船上所载的人数，而且另一方面规定牧师人数不 小于野人人数或牧师人数等于0，最后输出所以
11、安全状态以便以后程序中的 调用。(2) 算法的时空分析时间复杂度：因为程序中用了很多循环语句while，而且在进行广度 搜索的时候要把每种情况都要运算一遍，在每进行一次渡河时都要每个进 行一遍搜索，所以时间复杂度很大，要进行很多步骤。空间复杂度因为在程序中用了动态分配空间，用的时候再去申请空间，所以节省 了很多不必要的空间，空间复杂度相对较小。(3) 改进设想由于每进行一次渡河过程的分析是都要把每中状态都要考虑一遍， 使时间复杂度变得很大，所以设想让程序拥有记忆功能，把每一个路径都记 录下了，以后在搜索其他渡河过程中直接调用，这样会大大降低时间复杂度；由于最后输出结果看起来不太清晰，不是那么直
12、接，所以设想可以 加入动态过程，动态的显示出渡河的方法。(4) 经验与体会这个程序用了很多的函数调用，通过函数的调用，使步骤减少了很多， 变得比较简单；再有就是使用了链表与指针，大大减低了空间复杂度。12011223110 AAAAAAAAAAA 野野野野野野野野野野野 E - E - I，E -TE - E - I，E -TE - E - E -TE - E -口-口- 口-口-口- 口-口-口- 口-口-口AAAAAAAAAAA 野野野野野野野野野野野 E - E - E -TE - E - E -TE - E - E -TE - E - 0 0 0 0 I I I -口-口-口- 口-n
13、l:-m:-nl:-ml- 口-口-m:AAAAAAAAAAAA 野野野野野野野野野野野野 E - E - E - E - E - E - E - E - E - E - E - E - 33333120001 0 XNU-巾-口-口 - 口-口-口 - 口-口-口 - 口-口-口 工个野人，再运两个野人到乙岸这个程序说明开始先运两个野人然后回来然后回来一个野人，再运两个牧师然后回来一个牧师一个野人，再运两个 牧师回来一个野人，再运两个野人然后回来一个牧师，最后运一个牧师一 个野人到乙岸，渡河成功！（2）当没有成功渡河方法是，输出“无法成功渡河，牧师好郁闷！”4总结与心得体会两周的课程设计已经
14、接近尾声了，在这两周中我们学到了很多，开始拿到题目时, 我们三人分开查找资料，网上的资料真是五花八门，找了很多的资料，之后我们三人 将所有的资料汇总研究，在研究的过程中，许多课本上不是很熟悉的知识也慢慢变得 熟悉了，甚至还学到了许多课本上没有的知识。分析看懂程序的过程是艰难的，因为 程序不是自己写的，所以对于程序的思想以及所用的结构之类的都要重新思考和学 习，废了很大的劲才弄懂，这让我们都知道了一个道理，那就是自己写程序才能更容 易理解，因为思想是自己的，讲解起来也会很容易。之后，我们分工报告的写作，大 家一人一部分，之后汇总，分工合作的速度和效率都是个人所远远比不上的，不管最 后的结果怎样，这次的课程设计让我们不仅懂得了更多的知识，而且也认识到了合作 的重要性。经过这次的课程设计，让我学到了不少，首先让我对编写程序的环境更 加的熟悉了，对于编写程序也变得更加的熟练，可以自己尝试着编写一些 独立程序了，对于课本上所学的知识也更加的印象深刻了。其次就是团队 合作的问题，这一次是团队合作共同来完成课题，在这个过程中，让我更 加的意识到了团队的力量以及在团队合作中所获得的乐 趣。王倩以前接触过此类的题目，不过没有用程序编译过，刚刚接触
