logo资料库

修道士与野人问题课程设计报告.doc

发布时间：2022-06-08 发布人：admin 分类：说明书 资料大小：0.30M 资料格式：doc 举报 版权申诉
第1页 / 共16页
第2页 / 共16页
第3页 / 共16页
第4页 / 共16页
第5页 / 共16页
第6页 / 共16页
第7页 / 共16页
第8页 / 共16页
资料共16页，剩余部分请下载后查看
    6．修道士与野人问题 这是一个古典问题。假设有 n 个修道士和 n 个野人准备渡河，但只有一条能容纳 c 人的 小船，为了防止野人侵犯修道士，要求无论在何处，修道士的个数不得少于野人的人数（除 非修道士个数为 0）。如果两种人都会划船，试设计一个算法，确定他们能否渡过河去，若 能，则给出一个小船来回次数最少的最佳方案。 要求： （1）用一个三元组（x1,x2,x3）表示渡河过程中各个状态。其中，x1 表示起始岸上修 道士个数，x2 表示起始岸上野人个数，x3 表示小船位置（0——在目的岸，1——在起始岸）。 例如（2,1,1）表示起始岸上有两个修道士，一个野人，小船在起始岸一边。 采用邻接表做为存储结构，将各种状态之间的迁移图保存下来。 （2）采用广度搜索法，得到首先搜索到的边数最少的一条通路。 （3）输出数据 若问题有解（能渡过河去），则输出一个最佳方案。用三元组表示渡河过程中的状态， 并用箭头指出这些状态之间的迁移： 目的状态←…中间状态←…初始状态。 若问题无解，则给出“渡河失败”的信息。 （4）求出所有的解。 1．需求分析 有 n 个修道士和 n 个野人准备渡河，但只有一条能容纳 c 人的小船，为了防止野人侵犯 修道士，要求无论在何处，修道士的个数不得少于野人的人数,否则修道士就会有危险，设 计一个算法，确定他们能否渡过河去，若能，则给出一个小船来回次数最少的最佳方案。用 三元组（x1,x2,x3）来表示渡河过程中各个状态，其中，x1 表示起始岸上修道士个数，x2 表示起始岸上野人个数，x3 表示小船位置（0——在目的岸，1——在起始岸）。若问题有解 （能渡过河去），则输出一个最佳方案。用三元组表示渡河过程中的状态，并用箭头指出这 些状态之间的迁移：目的状态←…中间状态←…初始状态，若问题无解，则给出“渡河失败” 的信息。 2．设计 2.1 设计思想 （1）数据结构设计 逻辑结构设计: 图型结构 存储结构设计: 链式存储结构 采用这种数据结构的好处：便于采用广度搜索法，得到首先搜索到的边数最少的一条 通路，输出一个最佳方案，采用图的邻接表存储结构搜索效率较高。 （2）算法设计 算法设计的总体设计思路为：在得到修道士人数和小船的容纳人数后，用 boatcase 得到
    所有情况，然后再进行安全性检查，以减去修道士少于野人的情况，接着用孩子兄弟结点表 示法，将去对面的路作为孩子结点，路与路是兄弟关系，到达另一边时，同样以这种方法， 直到找到（0，0,0）。主要分为 4 个模块:boatcase 生成所有情况，BFS 得到边数最少的最佳 方案，safe 安全性检测，print 输出安全渡河的全过程。 各个模块要完成的主要功能分别为： 生成模块：生成所有的可能渡河情况 安全检测模块：对所有的可能渡河情况进行安全检测，，以减去修道士少于野人的情况 广度搜索模块：采用广度搜索法，得到首先搜索到的边数最少的一条通路 输出模块：输出所有安全渡河的全过程 主程序的流程图: 建立邻接表 调用函数 Linkinit( )来进行初始化 把 初 始 状 态 插 入邻接表中 调用函数 Insertson( )来插入结点 进行广搜找到成 功的方案 调用函数 guangdu( ) 打印输出各种方 案 调用函数 print( ) 2.2 设计表示 （1）函数调用关系图 guangdu boatcase safe insertson print insertbro
    （2）函数接口规格说明 void Linkinit(Link **head) void insertson(Link *head, DataType x) void insertbro(Link *head,DataType x) int boatcase(DataType x,int n) void guangdu(Link *p,int n,int c) int safe(DataType x,int n) void print(Link *q,Link *p) 2.3 详细设计  生成模块 int boatcase(DataType x,int n) { int i=0,a,b,t=0; { if(x.cw) a=0;b=n-a; while (a+b>=1) { } t++; while (b>=0) { array[i].xds=a; array[i].yr=b; i++; a++; b--; } a=0; b=n-a-t; } else { a=1;b=0;t=0; while (a+b<=n) { t++; while (a>=0) { array[i].xds=a*(-1); array[i].yr=b*(-1); i++;
    a--; b++; } a=array[0].xds*(-1)+t; b=0; } } return i; }  安全检测模块 int safe(DataType x,int n) { if ((x.xds>=x.yr||x.xds==0)&&((n-x.xds)>=(n-x.yr)||x.xds==n)&&x.xds>=0&&x.xds<=n&& x.yr>=0&&x.yr<=n) return 1; else return 0; }  广度搜索模块 void guangdu(Link *p,int n,int c) { Link *q,*t; DataType tem; int i,flag1,flag2,g=0,j,count=0; q=p->son; while (q!=NULL)/ { flag1=0; j=boatcase(q->data,c); for (i=0;idata.xds-array[i].xds; tem.yr=q->data.yr-array[i].yr; tem.cw=1-q->data.cw; t=q; if (safe(tem,n)) { flag2=1;//1 while (t!=p) {
    t->data.xds&&tem.yr==t->data.yr&&tem.cw==t->data.cw) if(tem.xds== { flag2=0; break; } t=t->par; } if(flag2==1) { if (flag1==0) { insertson(q, tem); flag1=1; } else insertbro(q,tem); if (tem.xds==0&&tem.yr==0&&tem.cw==0) { print(q,p); count++; } } } } q=q->next; } if (count==0) printf("无法成功渡河!\n"); printf("有%d 种渡河方式。\n",count); else }  输出模块 void print(Link *q,Link *p) { DataType a[100]; int i=1; a[0].cw=0; a[0].xds=0; a[0].yr=0; while (q!=p) {
    a[i++]=q->data; q=q->par; } while ((--i)>-1) { printf("( %d %d %d )",a[i].xds,a[i].yr,a[i].cw); if (!(a[i].xds==0&&a[i].yr==0&&a[i].cw==0)) { if(a[i].cw==1) printf("-->(%d %d)-->(%d %d 0)\n",a[i].xds-a[i-1].xds,a[i].yr-a[i-1].yr,a[i-1].xds,a[i-1].yr); else printf(" <-- ( %d %d ) <-- ( %d %d 1 )\n",(a[i].xds-a[i-1].xds)*(-1),(-1)*(a[i].yr-a[i-1].yr),a[i-1].xds,a[i-1].yr) ; } } printf("渡河成功!\n"); } 3．调试分析 （1）本题是采用邻接表做为存储结构，将各种状态之间的迁移图保存下来，并用孩子兄弟 表示法，以实现广度搜索；刚编好程序时出现死循环的现象，例如：带过去 2 个野人又带回 来 2 个野人，在和其他同学讨论后，采用了 2 个标志位来避免出现死循环的现象，在进行运 行的时候，曾出现了打印输出错误，经过一步一步调试，发现在插入结点的时候出现了插入 错误，即没有考虑到 pre 的改变，通过改正，重新运行检测，运行结果正确，在排版时通过 一步步调试，参考了课本和老师的课件，并与和其他同学讨论后，终于通过调试和改正，， 能够使输出结果很明显的渡河方案。 （2）可改进内容：显示表示哪些是渡河次数最短的，最佳渡河方案一共有几种，并输出每 种最佳渡河方案，另外，可尝试用深度优先搜索算法来找最佳方案。 4．用户手册 本程序在 VC++6.0 环境下运行，根据提示输入相应的渡河人数和小船能容纳的人数即可。 5．测试数据及测试结果 测试用例 1 测试输入： n=3,c=2 测试目的： 检验程序运行时是否会陷入死循环 正确输出： 见截屏 1,2 实际输出： 见截屏 3,4 错误原因： 未正确设置标志位，出现死循环现象 当前状态： 已改正
    截屏 1
    截屏 2
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料