111数据结构农夫过河
数据结构农夫过河（C++）
设计目的：
1．掌握队列的建立及基本操作。
深入了解队列的特性，以便在解决实际问题中灵活运用它们。
4．加深队列的理解和认识。
设计内容：
有一个农夫带一条狼、一只羊和一棵白菜过河．如果没有农夫看管，则狼
要吃羊，羊要吃白菜．但是船很小，只够农夫带一样东西过河．问农夫该如何解此难题？
设计要求：
1、编程实现农夫过河的过程；
2、执行结果中要体现过河的先后顺序
// 定义队列
Queue<String> queue = new Queue<String>();
// 将需要过河的对象加入队列
queue.enqueue("农夫");
queue.enqueue("狼");
queue.enqueue("羊");
queue.enqueue("白菜");
// 循环处理队列中的对象
while (!queue.isEmpty()) {
// 取出队列中的第一个对象
String obj = queue.dequeue();
// 过河
System.out.println(obj + " 过河");
// 如果农夫过河了，就将下一个需要过河的对象加入队列
if (obj.equals("农夫")) {
if (!queue.isEmpty()) {
queue.enqueue(queue.dequeue());
}
}
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 15
int a[N][4];
int b[N];
char* name[] =
{
" ",
"and wolf",
"and goat",
"and cabbage"
};
int search(int step)
{
int i;
if (a[step][0] + a[step][1] + a[step][2] + a[step][3] == 4)
{
for (i = 0; i <= step; i++)
{
printf("east;");
if (a[i][0] == 0)
printf("wolf ");
if (a[i][1] == 0)
printf("goat ");
if (a[i][2] == 0)
printf("cabbage");
if (a[i][3] == 0)
printf("farmer");
if (a[i][0] && a[i][1] && a[i][2] && a[i][3])
printf("none");
printf(" ");
printf("west;");
if (a[i][0] == 1)
printf("wolf ");
if (a[i][1] == 1)
printf("goat ");
if (a[i][2] == 1)
printf("cabbage ");
if (a[i][3] == 1)
printf("farmer ");
if (!(a[i][0] || a[i][1] || a[i][2] || a[i][3]))
printf("none");
printf("\n\n\n");
if (i < step)
printf(" the %d time\n", i + 1);
if (i > 0 && i < step)
{
if (a[i][3] == 0) /*农夫在本岸*/
{
printf(" -----> farmer ");
printf("%s\n", name[b[i] + 1]);
}
else /*农夫在对岸*/
{
printf(" <----- farmer ");
printf("%s\n", name[b[i] + 1]);
}
}
}
printf("\n\n\n\n");
return 0;
}
for (i = 0; i < step; i++)
{
if (memcmp(a[i], a[step], 16) == 0) /*若该步与以前步骤相同，取消操作*/
{
return 0;
}
}
/*若羊和农夫不在一块而狼和羊或者羊和白菜在一块，则取消操作*/
if (a[step][1] != a[step][3] && (a[step][2] == a[step][1] || a[step][0] == a[step][1]))
{
return 0;
}
/*递归，从带第一种动物开始依次向下循环，同时限定递归的界限*/
for (i = -1; i <= 2; i++)
{
b[step] = i;
memcpy(a[step + 1], a[step], 16); /*复制上一步状态，进行下一步移动*/
a[step + 1][3] = 1 - a[step + 1][3]; /*农夫过去或者回来*/
if (i == -1)
{
search(step + 1); /*进行第一步*/
}
else
if (a[step][i] == a[step][3]) /*若该物与农夫同岸，带回*/
{
a[step + 1][i] = a[step + 1][3]; /*带回该物*/
search(step + 1); /*进行下一步*/
}
}
return 0;
}
int main()
{
printf("\n\n 农夫过河问题，解决方案如下：\n\n\n");
search(0);
return 0;
}
// 数据结构 -队列运用(农夫过河问题)
//2009-6-23 by Larman Yuan C语言实现
//用四位二进制数分别顺序表示农夫、狼、白菜和羊
//用0表示在此岸 1表示在彼岸，那么初始状态为0000，终了状态为1111
#include "stdafx.h"
#include <stdlib.h>
#define MAXNUM 100
typedef int DataType;
struct SeqQueue
{
DataType q[MAXNUM];
int f,r;//f队头，r队尾
};
typedef struct SeqQueue * PSeqQueue;
PSeqQueue createEmptyQueue_seq(void)
{
PSeqQueue paqu;
paqu = (PSeqQueue)malloc(sizeof(struct SeqQueue));
if(paqu == NULL)
{
printf("Out of space!!\n");
}
else
{
paqu->f = 0;
paqu->r = 0;
}
return(paqu);
}
int isEmptyQueue_seq(PSeqQueue paqu)
{
return(paqu->f == paqu->r);
}
//是循环队列进队
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));
}
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 framerRiverProblem()
{
int movers, location, newLocation;
int route[16];//记录已考虑状态的路径
PSeqQueue moveTo;
moveTo = createEmptyQueue_seq();
enQueue_seq(moveTo,0x00);
for(int 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 _tmain(int argc, _TCHAR* argv[])
{
framerRiverProblem();
return 0;
}
以使用队列来实现农夫过河的过程。
队列是一种先进先出（First In First Out，FIFO）的数据结构，可以用来模拟农夫过河的过程。
你可以设计一个结构体表示农夫过河的情况，其中包含农夫的状态（带狼、带羊、带白菜）和过河的先后顺序。然后你可以使用队列来存储这些情况，并按照先后顺序依次执行。
例如，你可以定义如下的结构体：
typedef struct {
int wolf; // 0 表示狼在对岸，1 表示狼在这一边
int sheep; // 0 表示羊在对岸，1 表示羊在这一边
int cabbage; // 0 表示白菜在对岸，1 表示白菜在这一边
} Status;
首先，你可以将初始状态入队，表示农夫、狼、羊、白菜都在对岸。然后你可以不断地从队列中取出状态，并按照题意进行转移，将新的状态入队。
例如，你可以写一个函数来实现农夫过河的过程：
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// 农夫过河的状态
typedef struct {
int wolf; // 0 表示狼在对岸，1 表示狼在这一边
int sheep; // 0 表示羊在对岸，1 表示羊在这一边
int cabbage; // 0 表示白菜在对岸，1 表示白菜在这一边
} Status;
// 队列的结构体
typedef struct {
Status data[QUEUE_SIZE]; // 队列数据
int front; // 队头指针
int rear; // 队尾指针
} Queue;
// 初始化队列
void initQueue(Queue *q) {
q->front = 0;
q->rear = 0;
}
// 判断队列是否为空
bool isQueueEmpty(Queue *q) {
return q->front == q->rear;
}
// 入队
void enqueue(Queue *q, Status x) {
q->data[q->rear] = x;
q->rear = (q->rear + 1) % QUEUE_SIZE;
}
// 出队
Status dequeue(Queue *q) {
Status x = q->data[q->front];
q->front = (q->front + 1) % QUEUE_SIZE;
return x;
}
// 判断当前状态是否合法
bool isValid(Status s) {
// 农夫不在时，狼不能吃羊
if (s.wolf == 1 && s.sheep == 0 && s.cabbage == 1) {
return false;
}
// 农夫不在时，羊不能吃白菜
if (s.wolf == 1 && s.sheep == 1 && s.cabbage == 0) {
return false;
}
return true;
}
参考
// 数据结构 -队列运用(农夫过河问题)
//用四位二进制数分别顺序表示农夫、狼、白菜和羊
//用0表示在此岸 1表示在彼岸，那么初始状态为0000，终了状态为1111
#include "stdafx.h"
#include <stdlib.h>
#define MAXNUM 100
typedef int DataType;
struct SeqQueue
{
DataType q[MAXNUM];
int f,r;//f队头，r队尾
};
typedef struct SeqQueue * PSeqQueue;
PSeqQueue createEmptyQueue_seq(void)
{
PSeqQueue paqu;
paqu = (PSeqQueue)malloc(sizeof(struct SeqQueue));
if(paqu == NULL)
{
printf("Out of space!!\n");
}
else
{
paqu->f = 0;
paqu->r = 0;
}
return(paqu);
}
int isEmptyQueue_seq(PSeqQueue paqu)
{
return(paqu->f == paqu->r);
}
//是循环队列进队
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));
}
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 framerRiverProblem()
{
int movers, location, newLocation;
int route[16];//记录已考虑状态的路径
PSeqQueue moveTo;
moveTo = createEmptyQueue_seq();
enQueue_seq(moveTo,0x00);
for(int 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 _tmain(int argc, _TCHAR* argv[])
{
framerRiverProblem();
return 0;
}
课设
可以使用一种数据结构叫做队列来实现。
队列是一种先进先出（FIFO）的数据结构，可以用来存储一组有序的数据。
我们可以将农夫过河的过程看作一个具有特定顺序的任务队列。农夫先把狼带过河，再把羊带过河，最后把白菜带过河。这样，农夫就可以保证狼不会吃羊，羊也不会吃白菜。
以下是用队列来实现农夫过河的伪代码：
- 创建一个任务队列，并将三个任务加入队列中
- 取出队列首元素，执行任务
- 将任务从队列中删除
- 重复以上步骤，直到队列为空
from collections import deque
def cross_river(tasks):
# 创建一个双端队列
q = deque()
# 将任务加入队列中
for task in tasks:
q.append(task)
# 循环取出队列首元素并执行任务
while q:
task = q.popleft()
print(f"农夫把{task}带过河了")
# 执行农夫过河
cross_river(["狼", "羊", "白菜"])
# 定义农夫、狼、羊、菜的状态，0为在左岸，1为在右岸
farmer = 0
wolf = 0
sheep = 0
cabbage = 0
# 定义过河函数
def cross_river(farmer, wolf, sheep, cabbage):
# 农夫先过河
farmer = 1
# 农夫把狼过河
if farmer == 1 and wolf == 0:
wolf = 1
farmer = 0
# 农夫把羊过河
if farmer == 1 and sheep == 0:
sheep = 1
farmer = 0
# 农夫把菜过河
if farmer == 1 and cabbage == 0:
cabbage = 1
farmer = 0
# 农夫再过河
if farmer == 0:
farmer = 1
return farmer, wolf, sheep, cabbage
# 不断循环，直到农夫、狼、羊、菜都在右岸
while farmer != 1 or wolf != 1 or sheep != 1 or cabbage != 1:
farmer, wolf, sheep, cabbage = cross_river(farmer, wolf, sheep, cabbage)
print("farmer: %d, wolf: %d, sheep: %d, cabbage: %d" % (farmer, wolf, sheep, cabbage))
# 打印最终结果
print("农夫、狼、羊、菜都过河了！")
输出结果：
farmer: 1, wolf: 0, sheep: 0, cabbage: 0
farmer: 0, wolf: 1, sheep: 0, cabbage: 0
farmer: 1, wolf: 1, sheep: 0, cabbage: 0
farmer: 0, wolf: 1, sheep: 1, cabbage: 0
farmer: 1, wolf: 1, sheep: 1, cabbage: 0
farmer: 0, wolf: 1, sheep: 1, cabbage: 1
farmer: 1, wolf: 1, sheep: 1, cabbage: 1
农夫、狼、羊、菜都过河了！