logo资料库

数据结构农夫过河问题.doc

发布时间：2022-05-29 发布人：admin 分类：说明书 资料大小：0.15M 资料格式：doc 举报 版权申诉
第1页 / 共8页
第2页 / 共8页
第3页 / 共8页
第4页 / 共8页
第5页 / 共8页
第6页 / 共8页
第7页 / 共8页
第8页 / 共8页
资料共8页，全文预览结束
    华立学院 课 程 设 计 课程名称______数据结构_______ 题目名称____农夫过河问题__ 学生系别_____管理系____ 专业班级_08 信息管理与信息系统(2)班__ 学 号______15040802036_______ 学生姓名________冯定军_________ 指导教师________张稼_________
    2009 年 12 月 22 日 农夫过河问题 一. 问题描述 设一个农夫过河带着一条狼、一只羊和一棵白菜，身处河的南岸。现在他要把 这些西全部运到北岸,现在问题是他面前只有一条小船，船小到只能容下他和一 件物品，另外只有农夫能撑船。当农夫在场的时候,这三样东西相安无事.一旦 农夫不在,狼会吃羊,羊会吃白菜。根据原题的描述我们知道，单独留下白菜和 羊，或单独留下狼和羊在某一岸的状态是不安全的。白菜和狼相处没事,把它看 作个重要关系的,通过位置分布的代码来判断状态是否安全。然后设计一个方案, 模拟农夫能安全地将这三样东西带过河。 二．基本要求 以队列解决农夫过河问题，用广度优先搜索实现求解的过程。用这个方法来搜 索过程中总是首先搜索下面一步的所有可能状态，然后再进一步考虑更后面的 各种情况。要实现广度优先搜索，一般都采用队列作为辅助结构。把下一步所 有可能达到的状态都列举出来，放在这个队列中，然后顺序取出来分别进行处 理，处理过程中把再下一步的状态放在队列里。由于队列的操作遵循先进先出 的原则，在这个处理过程中，只有在前一步的所有情况都处理完后，才能开始 后面一步各情况的处理。为了实现广度优先搜索，算法中需要使用了一个整数 队列 moveTo，它的每个元素表示一个可以安全到达的中间状态。另外还需要一 个数据结构记录已被访问过的各个状态，以及已被发现的能够到达当前这个状 态的路径。由于在这个问题的解决过程中需要列举的所有状态(二进制 0000 ~ 1111)一共 16 种，所以可以构造一个包含 16 个元素的整数顺序表来满足以上的 要求。 三．测试数据 要模拟农夫过河问题，首先需要选择一个对问题中每个角色的位置进行描述的 方法。一个很方便的办法是用四位二进制数顺序分别表示农夫、狼、白菜和羊 的位置。例如用 0 表示农夫或者某东西在河的南岸，1 表示在河的北岸。因此整 数 5(其二进制表示为 0101) 表示农夫和白菜在河的南岸，而狼和羊在北岸。确 定每个角色位置的函数,用整数 location 表示上述四位二进制描述的状态，用 下面的四个函数从上述状态中得到每个角色所在位置的代码。函数返回值为真 表示所考察的人或物在河的北岸，否则在南岸。从初始状态二进制 0000(全部在 河的南岸) 出发，寻找一种全部由安全状态构成的状态序列，它以二进制 1111(全部到达河的北岸) 为最终目标，并且在序列中的每一个状态都可以从前 一状态通过农夫（可以带一样东西）划船过河的动作到达。
    四．流程 确定每个角色位置，,用整数 location 表示狼、羊、农夫、白菜的二进制来描述所在位置的代码． 初始状态二进制 0000(全部在河的南岸) 出发。 寻找一种全部由安全状态构成的状态序列 。 在寻找安全路径的同时，要考虑其他安全状态，若出现相同状态路径要记录 下来，防止重复。 本程序不断寻找安全的状态，它以二进制 1111(全部到达河的北岸) 为最终目 标，程序结束。 代码如下：/* 用队列解决农夫过河问题的算法*/ #include #include #define MAXNUM 20 typedef int DataType; struct int DataType q[MAXNUM]; SeqQueue { f, r; }; /* 顺序队列类型定义 */ typedef struct SeqQueue *PSeqQueue; /* 顺序队列类型的指针类型 */ PSeqQueue createEmptyQueue_seq( void ) { PSeqQueue paqu = (PSeqQueue)malloc(sizeof(struct SeqQueue)); if (paqu == NULL) printf("Out of space!! \n");
    else paqu->f = paqu->r = 0; return (paqu); } int isEmptyQueue_seq( PSeqQueue paqu ) { return paqu->f == paqu->r; } /* 在队列中插入一元素x */ void enQueue_seq( PSeqQueue paqu, DataType x ) { if ( (paqu->r + 1) % MAXNUM == paqu->f ) printf( "Full queue.\n" ); else { paqu->q[paqu->r] = x; paqu->r = (paqu->r + 1) % MAXNUM; } } /* 删除队列头部元素 */ void deQueue_seq( PSeqQueue paqu ) { if( paqu->f == paqu->r ) printf( "Empty Queue.\n" ); else paqu->f = (paqu->f + 1) % MAXNUM; } /* 对非空队列,求队列头部元素 */ DataType frontQueue_seq( PSeqQueue paqu ) { return (paqu->q[paqu->f]); } int farmer(int location) { return 0 != (location & 0x08); } int wolf(int location) { return 0 != (location & 0x04); } int cabbage(int location) { return 0 != (location & 0x02); } int goat(int location) {
    return 0 !=(location & 0x01); } /* 若状态安全则返回true */ 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; /* 其他状态是安全的 */ } void farmerProblem( ) { /*记录已考虑的状态路径*/ int movers, i, location, newlocation; int route[16]; PSeqQueue moveTo; /*准备初值*/ moveTo = createEmptyQueue_seq( ); enQueue_seq(moveTo, 0x00); for (i = 0; i < 16; i++) route[i] = -1; route[0]=0; /*开始移动*/ while (!isEmptyQueue_seq(moveTo)&&(route[15] == -1)) { /*得到现在的状态*/ location = frontQueue_seq(moveTo); deQueue_seq(moveTo); for (movers = 1; movers <= 8; movers <<= 1) { */ { /* 农夫总是在移动，随农夫移动的也只能是在农夫同侧的东西 if ((0 != (location & 0x08)) == (0 != (location & movers))) newlocation = location^(0x08|movers); if (safe(newlocation) && (route[newlocation] == -1)) { route[newlocation] = location; enQueue_seq(moveTo, newlocation); } } }
    } /* 打印出路径 */ if(route[15] != -1) { printf("The reverse path is : \n"); for(location = 15; location >= 0; location = route[location]) { } printf("The location is : %d\n",location); if (location == 0) return; } } else printf("No solution.\n"); int main() { farmerProblem( ); return 0; } 截图：
    } 心 得 体 会 教 师 评 语 成 绩 及 签 名 对于农夫过河问题的设计，很明显突出了自己能力不足！在这个 过程中花费了大量时间找资料来弥补自己的缺乏的知识，自己对重新 进得书本的学习，尽量使自己做得更！ 从做课程设计的过程中，我的体会挺多的。只要有信心与耐心， 没有做不到的事情。因为在这个过程中写代码与调试的过程中确实需 要耐心与信心，否则就不可能写完整。我也知道该课题还存在很多的 漏洞，也不是很完整。由于自己本身能力的原因，也不能使之更完整。 但是我已经尽我的努力写的了，同时在这些的设计中享受到了很多乐 趣和知识。 、 2010 年 12 月 22 日 0 年 月 日 年 月 日
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料