狼羊过河课程设计.pdf

课课 程程 设设 计计 设计题目 设计题目 农夫带一头狐狸 一只兔子和一棵蔬菜过河农夫带一头狐狸 一只兔子和一棵蔬菜过河 题目要求 题目要求 如果没有农夫看管 则狐狸会吃掉兔子 兔子如果没有农夫看管 则狐狸会吃掉兔子 兔子 会吃掉蔬菜 由于船只很小 每次最多只能带狐狸 兔子 蔬会吃掉蔬菜 由于船只很小 每次最多只能带狐狸 兔子 蔬菜菜 三者中的一个过河 判断农民是否能顺利过河三者中的一个过河 判断农民是否能顺利过河 若能怎样过 若能怎样过 学院 学院 合肥工大合肥工大计算机与信息学院计算机与信息学院 姓名 姓名 刘文辉刘文辉 班级 班级 计算机计算机 06 306 306 306 3 班班 时间 时间 2008200820082008 年年 6 6 6 6 月月 30303030 日日 实现功能 实现功能 实现对过河问题的求解 有几种方案 就找到几种方案 并显示出来 设计思考 设计思考 将狐狸 蔬菜 兔子 运送到河对岸 且保证它们不会互相吃掉 即实现 它们从状态一变为状态二 用 states 函数来存储它们的状态 用 0 表示它们 在河此岸 用1 表示它们在小河彼岸 由于每次最多只能运一个东西 所以若每 次状态变化最多只有农民和一个东西的变化 若可以顺利过河 则他们四个的状态均由 0 变化为 1 不能过河的限制条件为 1 农民不和狐狸在一块 且狐狸和兔子在一块 2 农民不和兔子在一块 且兔子和蔬菜在一块 则 1 狐狸吃掉兔子 2 兔子吃掉蔬菜 设计思路 设计思路 为了数据的封装安全 清晰期间 将整个实现代码用类封装起来 其中定 义一下函数 1 定义状态数组 states 用 i 表示其下标从 0 开始 2 定义过河步骤数组 action 100 用字符型是为了显示的明朗 直接用 汉字来显示 用 i 表示其下标从 0 开始 3 定义过河状态函数 over inti 过河和 back inti 返回 其中 表示该动物的英文名称i表示状态变化的下标从 0 开始 4 定义判断能否过河的判断解决函数 solve int i 判断具体实现问题求解 的方案 5 定义方案输出函数 solution int i 选择具体实现的方案 实现代码 实现代码 main main main main include include include include usingusingusingusing namespacenamespacenamespacenamespace std std std std structstructstructstruct StatesStatesStatesStates int int int int farmer fox rabbit cabbage farmer fox rabbit cabbage farmer fox rabbit cabbage farmer fox rabbit cabbage structstructstructstruct StatesStatesStatesStates statesstatesstatesstates 20 20 20 20 定义状态并开辟空间定义状态并开辟空间 char char char char action 100 action 100 action 100 action 100 定义过河步骤定义过河步骤 classclassclassclass OverriverOverriverOverriverOverriver public public public public Overriver Overriver Overriver Overriver voidvoidvoidvoid foxover intfoxover intfoxover intfoxover int i i i i 农民带狐狸过河农民带狐狸过河 voidvoidvoidvoid foxback intfoxback intfoxback intfoxback int i i i i 农民带狐狸回来农民带狐狸回来 voidvoidvoidvoid rabbitover intrabbitover intrabbitover intrabbitover int i i i i 农民带兔子过河农民带兔子过河 voidvoidvoidvoid rabbitback intrabbitback intrabbitback intrabbitback int i i i i 农民带兔子回来农民带兔子回来 voidvoidvoidvoid cabbageover intcabbageover intcabbageover intcabbageover int i i i i 农民带蔬菜过河农民带蔬菜过河 voidvoidvoidvoid cabbageback intcabbageback intcabbageback intcabbageback int i i i i 农民带蔬菜回来农民带蔬菜回来 voidvoidvoidvoid over alone intover alone intover alone intover alone int i i i i 农民独自过河农民独自过河 voidvoidvoidvoid back alone intback alone intback alone intback alone int i i i i 农民独自回来农民独自回来 voidvoidvoidvoid solution intsolution intsolution intsolution int i i i i 判断方案是否可行判断方案是否可行 输出可执行方案输出可执行方案 voidvoidvoidvoid solve intsolve intsolve intsolve int i i i i 判断实现问题的具体方法判断实现问题的具体方法 Overriver Overriver Overriver Overriver Overriver Overriver Overriver Overriver 初始化初始化 states 0 farmerstates 0 farmerstates 0 farmerstates 0 farmer 0 0 0 0 states 0 foxstates 0 foxstates 0 foxstates 0 fox 0 0 0 0 states 0 rabbitstates 0 rabbitstates 0 rabbitstates 0 rabbit 0 0 0 0 states 0 cabbage states 0 cabbage states 0 cabbage states 0 cabbage 0 0 0 0 在河的出始位置的状态设为在河的出始位置的状态设为0 0 0 0 过河后设为过河后设为1 1 1 1 voidvoidvoidvoid Overriver foxover intOverriver foxover intOverriver foxover intOverriver foxover int i i i i 农民带狐狸过河农民带狐狸过河 action i action i action i action i 农民带狐狸过河农民带狐狸过河 states i 1 fox 1 states i 1 fox 1 states i 1 fox 1 states i 1 fox 1 states i 1 rabbit states i rabbit states i 1 rabbit states i rabbit states i 1 rabbit states i rabbit states i 1 rabbit states i rabbit states i 1 cabbage states i cabbage states i 1 cabbage states i cabbage states i 1 cabbage states i cabbage states i 1 cabbage states i cabbage voidvoidvoidvoid Overriver foxback intOverriver foxback intOverriver foxback intOverriver foxback int i i i i 农民带狐狸回来农民带狐狸回来 action i action i action i action i 农民带狐狸回来农民带狐狸回来 states i 1 fox 0 states i 1 fox 0 states i 1 fox 0 states i 1 fox 0 states i 1 rabbit states i rabbit states i 1 rabbit states i rabbit states i 1 rabbit states i rabbit states i 1 rabbit states i rabbit states i 1 cabbage states i cabbage states i 1 cabbage states i cabbage states i 1 cabbage states i cabbage states i 1 cabbage states i cabbage voidvoidvoidvoid Overriver rabbitover intOverriver rabbitover intOverriver rabbitover intOverriver rabbitover int i i i i 农民带兔子过河农民带兔子过河 action i action i action i action i 农民带兔子过河农民带兔子过河 states i 1 fox states i fox states i 1 fox states i fox states i 1 fox states i fox states i 1 fox states i fox states i 1 rabbit 1 states i 1 rabbit 1 states i 1 rabbit 1 states i 1 rabbit 1 states i 1 cabbage states i cabbage states i 1 cabbage states i cabbage states i 1 cabbage states i cabbage states i 1 cabbage states i cabbage voidvoidvoidvoid Overriver rabbitback intOverriver rabbitback intOverriver rabbitback intOverriver rabbitback int i i i i 农民带兔子回来农民带兔子回来 action i action i action i action i 农民带兔子回来农民带兔子回来 states i 1 fox states i fox states i 1 fox states i fox states i 1 fox states i fox states i 1 fox states i fox states i 1 rabbit 0 states i 1 rabbit 0 states i 1 rabbit 0 states i 1 rabbit 0 states i 1 cabbage states i cabbage states i 1 cabbage states i cabbage states i 1 cabbage states i cabbage states i 1 cabbage states i cabbage voidvoidvoidvoid Overriver cabbageover intOverriver cabbageover intOverriver cabbageover intOverriver cabbageover int i i i i 农民带蔬菜过河农民带蔬菜过河 action i action i action i action i 农民带蔬菜过河农民带蔬菜过河 states i 1 fox states i fox states i 1 fox states i fox states i 1 fox states i fox states i 1 fox states i fox states i 1 rabbit states i rabbit states i 1 rabbit states i rabbit states i 1 rabbit states i rabbit states i 1 rabbit states i rabbit states i 1 cabbage 1 states i 1 cabbage 1 states i 1 cabbage 1 states i 1 cabbage 1 voidvoidvoidvoid Overriver cabbageback intOverriver cabbageback intOverriver cabbageback intOverriver cabbageback int i i i i 农民带蔬菜回来农民带蔬菜回来 action i action i action i action i 农民带蔬菜回来农民带蔬菜回来 states i 1 fox states i fox states i 1 fox states i fox states i 1 fox states i fox states i 1 fox states i fox states i 1 rabbit states i rabbit states i 1 rabbit states i rabbit states i 1 rabbit states i rabbit states i 1 rabbit states i rabbit states i 1 cabbage 0 states i 1 cabbage 0 states i 1 cabbage 0 states i 1 cabbage 0 voidvoidvoidvoid Overriver over alone intOverriver over alone intOverriver over alone intOverriver over alone int i i i i 农民独自过河农民独自过河 action i action i action i action i 农民独自过河农民独自过河 states i 1 fox states i fox states i 1 fox states i fox states i 1 fox states i fox states i 1 fox states i fox states i 1 rabbit states i rabbit states i 1 rabbit states i rabbit states i 1 rabbit states i rabbit states i 1 rabbit states i rabbit states i 1 cabbage states i cabbage states i 1 cabbage states i cabbage states i 1 cabbage states i cabbage states i 1 cabbage states i cabbage voidvoidvoidvoid Overriver back alone intOverriver back alone intOverriver back alone intOverriver back alone int i i i i 农民独自回来农民独自回来 action i action i action i action i 农民独自回来农民独自回来 states i 1 fox states i fox states i 1 fox states i fox states i 1 fox states i fox states i 1 fox states i fox states i 1 rabbit states i rabbit states i 1 rabbit states i rabbit states i 1 rabbit states i rabbit states i 1 rabbit states i rabbit states i 1 cabbage states i cabbage states i 1 cabbage states i cabbage states i 1 cabbage states i cabbage states i 1 cabbage states i cabbage voidvoidvoidvoid Overriver solution intOverriver solution intOverriver solution intOverriver solution int i i i i 判断方案是否可行判断方案是否可行 输出可执行方案输出可执行方案 intintintint c flag flag 1 staticc flag flag 1 staticc flag flag 1 staticc flag flag 1 static m 1 m 1 m 1 m 1 cout endl cout endl cout endl cout endl cout cout cout cout 解决方案解决方案 m endl m endl m endl m endl cout endl cout endl cout endl cout endl cout cout cout cout 具体实现步骤如下 具体实现步骤如下 endl endl endl endl cout endl cout endl cout endl cout i if c i if c i if c i cout cout cout cout 无解决方案 不能顺利过河无解决方案 不能顺利过河 endl endl endl endl elseelseelseelse for for for for c i c i c i c i c c c c cout cout cout cout 第第 c 1 c 1 c 1 c 1 步步 action c endl action c endl action c endl action c endl m m m m cout cout cout cout 农民 狐狸 兔子 蔬菜顺利过河农民 狐狸 兔子 蔬菜顺利过河 endl endl endl endl cout endl cout endl cout endl cout endl voidvoidvoidvoid Overriver solve intOverriver solve intOverriver solve intOverriver solve int i i i i 判断实现问题的具体方法判断实现问题的具体方法 intintintint m m m m intintintint p p p p if states i farmer 1 solution i solution i solution i 只有顺利过河 才可以说方案可以执行 因此调用只有顺利过河 才可以说方案可以执行 因此调用solutiosolutiosolutiosolution n n n 函数函数 return return return return 返回实现具体步骤返回实现具体步骤 if if if if states i farmer states i fox states i farmer states i fox states i farmer states i fox states i farmer states i fox 或如果农民和兔子或如果农民和兔子 不在一块 且兔子和蔬菜在一块不在一块 且兔子和蔬菜在一块 狐狸会吃掉兔子 或兔子会吃掉蔬菜 狐狸会吃掉兔子 或兔子会吃掉蔬菜 states i farmer states i rabbit return return return 返回上一状态返回上一状态 由于只有两种状态 要么被吃 要么顺利过河 因此一旦不成功 则返由于只有两种状态 要么被吃 要么顺利过河 因此一旦不成功 则返回回 上一状态 继续查找上一状态 继续查找 forforforfor m 0 m 0 m 0 m 0 m i m i m i m i m m m m if if if if states m farmer states i farmer return return return 当他们都在河的一岸的时候 要么都过去了 要么都没有当他们都在河的一岸的时候 要么都过去了 要么都没有 过去 则返回 说明没有方案或者是已经成功 过去 则返回 说明没有方案或者是已经成功 p i 1 p i 1 p i 1 p i 1 if states i farmer 0 if states i farmer 0 if states i farmer 0 if states i farmer 0 states p farmer 1 states p farmer 1 states p farmer 1 states p farmer 1 让农民一个人过河让农民一个人过河 over alone i over alone i over alone i over alone i solve p solve p solve p solve p 递归调用递归调用 农民分别带东西过河农民分别带东西过河 if states i fox 0 if states i fox 0 if states i fox 0 if states i fox 0 狐狸没有过河 带狐狸过河 调用递归算法狐狸没有过河 带狐狸过河 调用递归算法 foxover i foxover i foxover i foxover i solve p solve p solve p solve p if states i rabbit 0 if states i rabbit 0 if states i rabbit 0 if states i rabbit 0 兔子没有过河 带兔子过河 调用递归算法兔子没有过河 带兔子过河 调用递归算法 rabbitover i rabbitover i rabbitover i rabbitover i solve p solve p solve p solve p if states i cabbage 0 if states i cabbage 0 if states i cabbage 0 if states i cabbage 0 蔬蔬没有过河 带蔬蔬过河 调用递归算法蔬蔬没有过河 带蔬蔬过河 调用递归算法 cabbageover i cabbageover i cabbageover i cabbageover i solve p solve p solve p solve p elseelseelseelse states p farmer 0 states p farmer 0 states p farmer 0 states p farmer 0 back alone i back alone i back alone i back alone i 让农民一个人回来让农民一个人回来 solve p solve p solve p solve p 农民分别带东西返回农民分别带东西返回 if states i fox 1 if states i fox 1 if states i fox 1 if states i fox 1 狐狸过河 带狐狸回来 调用递归算法狐狸过河 带狐狸回来 调用递归算法 foxback i foxback i foxback i foxback i solve p solve p solve p solve p if states i rabbit 1 if states i rabbit 1 if states i rabbit 1 if states i rabbit 1 rabbitback i rabbitback i rabbitback i rabbitback i solve p solve p solve p solve p if states i cabbage 1 if states i cabbage 1 if states i cabbage 1 if states i cabbage 1 cabbageback i cabbageback i cabbageback i cabbageback i solve p solve p solve p solve p voidvoidvoidvoid main main main main OverriverOverriverOverriverOverriver o o o o cout cout cout cout 问题如下问题如下 endl endl endl endl cout cout cout cout 有一个农夫带一头狐狸 一只兔子和一棵蔬菜过河有一个农夫带一头狐狸 一只兔子和一棵蔬菜过河 endl endl endl endl cout cout cout cout 要求如下要求如下 endl endl endl endl cout cout cout cout 如果没有农夫看管 则狐狸会吃掉兔子 兔子会吃掉蔬菜如果没有农夫看管 则狐狸会吃掉兔子 兔子会吃掉蔬菜 endl endl endl endl cout cout cout cout 由于船只很小 每次最多只能带狐狸 兔子 蔬菜三者中的一个由于船只很小 每次最多只能带狐狸 兔子 蔬菜三者中的一个过过 河河 endl endl endl endl cout cout cout cout 该农民怎样才能顺利过河该农民怎样才能顺利过河 endl endl endl endl o solve 0 o solve 0 o solve 0 o solve 0 运行结果 运行结果 动态演示 动态演示 为了直观的显示出过河的方法 采用动态演示的方法来实现可视 化的过河步骤 其代码如下 include include windows h include using namespace std void main int i cout endl cout 由于只有两种方案 endl cout 所以输入 1 表示演示方案 1 输入 2 表示演示方案 2 endl cout 请输入你要演示的方案代码 i switch i case 1 switch i F fox C cabbage P peasant R rabbit case 1 带兔子过河 cout 演示说明如下 endl cout F 代表狐狸 fox C 代表蔬菜 cabbage P 代表农民 peasant R 代表兔子 rabbit endl cout 下面开始方案一的动态演示过程 endl Sleep 8000 char A 50 A 0 F A 1 A 2 C A 3 P A 4 R for int j 5 j 50 j A j for j 0 j 50 j cout A j Sleep 100 system cls for j 3 j 47 j A j A j 1 P A j 2 A j 3 R for int i 0 i 50 i cout A i Sleep 100 system cls case 2 农民独自返回 char B 50 B 0 F B 1 B 2 C B 47 P B 48 B 49 R for int i 3 i 47 i B i for i 0 i 50 i cout 4 i B i B i 1 P for int i 0 i 50 i cout B i Sleep 100 system cls case 3 带狐狸过河 char C 50 C 0 C C 1 C 2 F C 3 C 4 P C 49 R for int i 5 i 49 i C i for i 0 i 50 i cout C i Sleep 100 system cls for i 2 i 45 i C i C i 1 F C i 2 C i 3 P for int i 0 i 50 i cout C i Sleep 100 system cls case 4 带兔子回来 char D 50 D 0 C D 45 P D 46 D 47 R D 48 D 49 F for int i 1 i 45 i D i for i 0 i 50 i cout 4 i D i D i 1 R D i 2 D i 3 P for int i 0 i 50 i cout D i Sleep 100 system cls case 5 带蔬菜过河 char E 50 E 0 R E 1 E 2 P E 3 E 4 C E 49 F for int i 5 i 49 i E i for i 0 i 50 i cout E i Sleep 100 system cls for i 1 i 45 i E i E i 1 P E i 2 E i 3 C for int i 0 i 50 i cout E i Sleep 100 system cls case 6 农民独自返回 char F 50 F 0 R F 45 P F 46 F 47 C F 48 F 49 F for int i 1 i 45 i F i for i 0 i 50 i cout 2 i F i F i 1 P for int i 0 i 50 i cout F i Sleep 100 system cls case 7 带兔子过河 char F 50 F 0 R F 1 F 2 P F 47 C F 48 F 49 F for int i 3 i 47 i F i for i 0 i 50 i cout F i Sleep 100 system cls for i 0 i 43 i F i F i 1 R F i 2 F i 3 P for int i 0 i 50 i cout F i Sleep 100 system cls case 8 方案一演示完毕 char G 50 G 43 R G 44 G 45 P G 46 G 47 C G 48 G 49 F for int i 0 i 43 i G i for int j 0 j 50 j cout G j cout endl cout 方案一演示完毕 endl case 2 switch i F fox C cabbage P peasant R rabbit case 2 带兔子过河 cout 演示说明如下 endl cout F 代表狐狸 fox C 代表蔬菜 cabbage P 代表农民 peasant R 代表兔子 rabbit endl cout 下面开始方案二的动态演示过程 endl Sleep 8000 char A 50 A 0 F A 1 A 2 C A 3 P A 4 R for int j 5 j 50 j A j for j 0 j 50 j cout A j Sleep 100 system cls for j 3 j 47 j A j A j 1 P A