基于C++的农夫过河问题算法设计与实现方法
更新时间:2020年4月25日 17:29 点击:1918
本文实例讲述了基于C++的农夫过河问题算法设计与实现方法。分享给大家供大家参考,具体如下:
问题描述:
一个农夫带着—只狼、一只羊和—棵白菜,身处河的南岸。他要把这些东西全部运到北岸。他面前只有一条小船,船只能容下他和—件物品,另外只有农夫才能撑船。如果农夫在场,则狼不能吃羊,羊不能吃白菜,否则狼会吃羊,羊会吃白菜,所以农夫不能留下羊和白菜自己离开,也不能留下狼和羊自己离开,而狼不吃白菜。请求出农夫将所有的东西运过河的方案。
实现上述求解的搜索过程可以采用两种不同的策略:一种广度优先搜索,另一种深度优先搜索。这里介绍在广度优先搜索方法中采用的数据结构设计。
程序源码:
/*********************************************** * 农夫过河问题(P64 队列的应用) * 约定:用四位二进制数分别顺序表示农夫、狼、白菜和羊的状态 * 即:{dddd} <=> {Farmer, Wolf, Cabbage, Goat} 其中:d={0,1} * 说明:0表示在东岸 1表示在西岸,初始状态为0000,终止状态为1111 ************************************************/ #include<stdio.h> #include<stdlib.h> #define MAXSIZE 16 typedef int EntryType; typedef struct queue { EntryType data[MAXSIZE]; int front,rear; //front队头,rear队尾 }SeqQueue, * SeqQueuePtr; // 创建空队列 SeqQueuePtr create_sequeue(void) { SeqQueuePtr pque; pque = (SeqQueuePtr)malloc(sizeof(SeqQueue)); if(pque){ pque->front = 0; pque->rear = 0; } else{ printf("Error: malloc() failed, out of memory!\n"); } return(pque); } int is_queEmpty(SeqQueuePtr pque) { return( pque->front == pque->rear ); } int is_queFull(SeqQueuePtr pque) { return( (pque->rear+1)%MAXSIZE == pque->front); } // 入队 int enqueue(SeqQueuePtr pque, EntryType x) { if(is_queFull(pque)){ printf("Queue Overflow Error: trying to add an element onto a full queue\n"); return 1; } else{ pque->data[pque->rear] = x; pque->rear = (pque->rear + 1) % MAXSIZE; return 0; } } // 队首元素出队(返回0表示出队异常,出队操作前队列为空) int dequeue(SeqQueuePtr pque, EntryType * e) { if(is_queEmpty(pque)){ printf("Empty Queue.\n"); return 0; } else{ *e = pque->data[pque->front]; pque->front = (pque->front + 1) % MAXSIZE; return 1; } } int is_farmer_crossed(int state) { return ((state & 0x08) != 0); } int is_wolf_crossed(int state) { return ((state & 0x04) != 0); } int is_cabbage_crossed(int state) { return ((state & 0x02) != 0); } int is_goat_crossed(int state) { return ((state & 0x01) != 0); } // 若状态相容(安全)则返回1,否则返回0 int is_safe(int state) { if((is_goat_crossed(state) == is_cabbage_crossed(state)) && (is_goat_crossed(state) != is_farmer_crossed(state))) // 羊菜同岸且农夫不在场 return(0); if((is_goat_crossed(state) == is_wolf_crossed(state)) && (is_goat_crossed(state) != is_farmer_crossed(state))) // 狼羊同岸且农夫不在场 return(0); return(1); } void river_crossing_problem() { int route[16]; // 记录已经考虑过的状态 int state; // 记录当前时刻的状态(状态编号的二进制形式即状态本身) int aftercross; // 记录渔夫当前的选择(渡河对象)会导致的结果状态 int passenger; // 临时变量,用于表达农夫的选择(对应二进制位为1表示选中该乘客) int results[16]={0}; // 输出结果 int counter, i; SeqQueuePtr states_que; // states_que = create_sequeue(); // 创建“状态”队列 enqueue(states_que,0x00); // 初始状态0000入队 for(int i = 0; i < 16; i++){ route[i] = -1; } //route[0] = 0; while(!is_queEmpty(states_que) && (route[15] == -1)) { if( !dequeue(states_que, &state) ){ printf("Error: dequeue() - the queue is empty\n"); } // 依次考虑农夫可能的选择:携带羊、白菜和狼,以及农夫只身渡河 for( passenger = 1; passenger<= 8; passenger <<= 1 ) { // 由于农夫总是在过河,随农夫过河的也只能是与农夫同侧的东西 if(((state & 0x08) != 0) == ((state & passenger) != 0)){ // 如果农夫与当前乘客在河岸的同一侧 aftercross = state^( 0x08|passenger ); // 渡河后的情况 if(is_safe(aftercross) && (route[aftercross] == -1)){ // 如果渡河后状态安全,则将其状态入队 route[aftercross] = state; // 将当前状态的索引记录到路径数组中(下标索引为后续状态值) enqueue(states_que, aftercross); } } }//end for() }//end while() // 输出过河策略:0表示在东岸 1表示在西岸,初始状态为0000,终止状态为1111 if(route[15] != -1) { //printf("The reverse path is:\n"); counter = 0; for(state = 15; state != 0; state = route[state]){ //printf("The state is: %d \n",state); results[counter] = state; counter++; //if(state == 0) return; } for(i = 0; i< counter; i++){ state= results[i]; aftercross = results[i+1]; if(state & 0x08){ printf("农夫从东岸到西岸:"); } else{ printf("农夫从西岸到东岸:"); } switch(state^aftercross ){ case 12: printf("把狼带过河\n"); break; case 10: printf("把菜带过河\n"); break; case 9: printf("把羊带过河\n"); break; default: printf("什么也不带\n"); break; } } } else{ printf("No solution for this problem.\n"); } } int main(void) { river_crossing_problem(); system("pause"); return 0; }
运行结果:
希望本文所述对大家C++程序设计有所帮助。
上一篇: C,C++中常用的操作字符串的函数
下一篇: c++ 写注册表方式让程序开机自启动
相关文章
- vector是表示可以改变大小的数组的序列容器,本文主要介绍了C++STL标准库std::vector的使用详解,文中通过示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2022-03-06
- 这篇文章主要介绍了C++中取余运算的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 作者:Sabine 【导读】本文介绍了C#的四种排序算法:冒泡排序、选择排序、插入排序和希尔排序 冒泡排序 using System; namespace BubbleSorter { public class Bubb...2020-06-25
- 这篇文章主要介绍了C++ string常用截取字符串方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本文通过例子,讲述了C++调用C#的DLL程序的方法,作出了以下总结,下面就让我们一起来学习吧。...2020-06-25
- 这篇文章主要用实例讲解C#递归算法的概念以及用法,文中代码非常详细,帮助大家更好的参考和学习,感兴趣的朋友可以了解下...2020-06-25
- 本篇文章主要介绍了C++中四种加密算法之AES源代码,小编觉得挺不错的,现在分享给大家,也给大家做个参考。...2020-04-25
- 整数拆分,指把一个整数分解成若干个整数的和。本文重点给大家介绍C++ 整数拆分方法详解,非常不错,感兴趣的朋友一起学习吧...2020-04-25
- 这篇文章主要介绍了C++中Sort函数详细解析,sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变...2022-08-18
- 这篇文章主要介绍了C++万能库头文件在vs中的安装步骤(图文),文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ bitset用法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本篇文章小编并不是为大家讲解string类型的用法,而是讲解我个人比较好奇的问题,就是string 类型占几个字节...2020-04-25
- 这篇文章主要为大家详细介绍了C++ Eigen库计算矩阵特征值及特征向量,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- 这篇文章主要介绍了C++ pair的用法实例详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了VSCode C++多文件编译的简单使用方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-03-29
- 虽然C++11引入了智能指针的,但是开发人员在与内存的斗争问题上并没有解放,如果我门实用不当仍然有内存泄漏问题,其中智能指针的循环引用缺陷是最大的问题。下面通过实例代码给大家介绍c++中的循环引用,一起看看吧...2020-04-25
- 这篇文章主要给大家介绍了关于C++随机点名生成器的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- map容器是C++ STL中的重要一员,删除map容器中value为指定元素的问题是我们经常与遇到的一个问题,下面这篇文章主要给大家介绍了关于利用C++如何删除map容器中指定值的元素的相关资料,需要的朋友可以参考借鉴,下面来一起看看吧。...2020-04-25
- 这篇文章主要介绍了C++ 约瑟夫环问题案例详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-08-15
- 这篇文章主要介绍了C++中cin的用法详细,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25