subject_64125.htm

vc

<p>
序号：64125 发表者：紫语 发表日期：2003-12-09 00:22:09
<br>主题：编一个程序！！数据结构的！帮帮忙！
<br>内容：问题描述]农夫过河问题：一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西全部运到北岸。问题是他前面只有一条小船，船小到只能容下他和一件物品，另外只有农夫能撑船。而且在农夫不在时，狼会吃羊，羊会吃白菜。请问农夫该采取什么方案才能将所有东西运过河？<BR>[问题解决方案提示]<BR>（1）&nbsp;&nbsp;&nbsp;&nbsp;该问题可以抽象为一个图，图中的每个结点表示问题可能的一种状态，边表示为一种移动过程，则问题为搜索一条从开始结点到结束结点的一条路径。<BR>（2）&nbsp;&nbsp;&nbsp;&nbsp;搜索过程可采用两种不同的策略：1 广度优先搜索（依赖的数据结构为队列） 2深度优先搜索（依赖的数据结构为栈）<BR>（3）&nbsp;&nbsp;&nbsp;&nbsp;要模拟农夫过河问题，首先需要选择一个对问题中每个角色的位置进行描述的方法。采用4为二进制数分别表示农夫、狼、白菜和羊的位置，0表示在南岸，1表示在北岸，例如，整数5（二进制数0101）表示农夫和白菜在南岸，而狼和羊在北岸，由于农夫不在，狼可以吃样，因此是一种不安全状态。<BR>（4）&nbsp;&nbsp;&nbsp;&nbsp;下面四个函数从状态location中得出每个角色所在的位置，函数返回值为真表示其对象在河的北岸，否则在南岸<BR>int farmer(int location) {<BR>&nbsp;&nbsp;&nbsp;&nbsp;return (0 != (location &amp; 0x08));<BR>}<BR><BR>int wolf(int location) {<BR>&nbsp;&nbsp;&nbsp;&nbsp;return (0 != (location &amp; 0x04));<BR>}<BR><BR>int cabbage(int location) {<BR>&nbsp;&nbsp;&nbsp;&nbsp;return (0 != (location &amp; 0x02));<BR>}<BR><BR>int goat(int location) {<BR>&nbsp;&nbsp;&nbsp;&nbsp;return (0 !=(location &amp; 0x01));<BR>}<BR>（5）&nbsp;&nbsp;&nbsp;&nbsp;下面函数判断当前状态是否安全<BR>int safe(int location)<BR>{&nbsp;&nbsp;&nbsp;&nbsp;// 若状态安全则返回true<BR>&nbsp;&nbsp;&nbsp;&nbsp; // 羊吃白菜<BR>&nbsp;&nbsp;&nbsp;&nbsp; if ((goat(location) == cabbage(location)) &amp;&amp;&nbsp;&nbsp;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(goat(location) != farmer(location)) )&nbsp;&nbsp;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return (0);<BR>&nbsp;&nbsp;&nbsp;&nbsp; // 狼吃羊<BR>&nbsp;&nbsp;&nbsp;&nbsp; if ((goat(location) == wolf(location)) &amp;&amp;&nbsp;&nbsp;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(goat(location) != farmer(location)))&nbsp;&nbsp;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return (0);<BR>&nbsp;&nbsp;&nbsp;&nbsp; return (1);&nbsp;&nbsp;&nbsp;&nbsp; // 其他状态是安全的<BR>}<BR>[基本要求] <BR>编写一个程序模拟农夫过河过程，输出结果。建议使用队列先完成，然后可用栈改写。<BR>
<br><a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p>
<hr size=1>
<blockquote><p>
<font color=red>答案被接受</font><br>回复者：bird 回复日期：2003-12-09 08:59:01
<br>内容：http://www.vchelp.net/cndevforum/subject_view.asp?subject_id=46614&amp;forum_id=55<BR><BR><BR><BR>可以向前辈学习!
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>
<hr size=1>
<blockquote><p>
回复者：紫语 回复日期：2003-12-10 15:09:18
<br>内容：太谢谢你了！
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>