精选优质文档-倾情为你奉上合肥学院计算机科学与技术系课程设计报告2009 2010 学年第二学期课程 数据结构与算法课程设计名称农夫携物过河问题学生姓名程梦云学号专业班级08计科(2)指导教师王昆仑 张贯虹2010年5月题目：农夫携物过河问题内容：有一农夫要将自己的兔子、蔬菜和狐狸等3件物品运过河。但农夫过河时所用的船每次最多只能装其中的一件物品，而这3件物品之间又存在一定的制约关系：兔子不能单独和狐狸以及不能和蔬菜在一起，因为狐狸要吃兔子，兔子也能吃蔬菜。试构造出问题模式以编程实现这一问题的求解。一、问题分析和任务定义根据对象的状态分为过河（1）和不过河（0），此对象集合就构成了一个状态空间。问题就是在这个状态空间内搜索一条从开始状态到结束状态的安全路径。显然，其初始状态为四对象都不过河，结束状态为四对象全部过河。这里利用图的广度优先算法思想处理，并采用队列存储，灵活运用二进制的特点完美解决问题。对于农夫，狐狸，兔子，蔬菜组成一个4位二进制
