數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)-農(nóng)夫過河問題

1、農(nóng)夫過河問題一、實(shí)驗(yàn)?zāi)康恼莆諒V度優(yōu)先搜索策略，并用隊(duì)列求解農(nóng)夫過河問題二、實(shí)驗(yàn)內(nèi)容問題描述：一農(nóng)夫帶著一只狼，一只羊和一顆白菜，身處河的南岸，他要把這些東西全部運(yùn)到北岸，遺憾的是他 只有一只小船，小船只能容下他和一件物品。這里只能是農(nóng)夫來撐船，同時(shí)因?yàn)槔浅匝颉⒀虺园撞?、所?農(nóng)夫不能留下羊和狼或羊和白菜在河的一邊，而自己離開；好在狼屬肉食動(dòng)物，不吃白菜。農(nóng)夫怎么才能 把所有的東西安全運(yùn)過河呢？實(shí)驗(yàn)要求如下：(1) 設(shè)計(jì)物品位置的表示方法和安全判斷算法；(2) 設(shè)計(jì)隊(duì)列的存儲結(jié)構(gòu)并實(shí)現(xiàn)隊(duì)列的基本操作(建立空隊(duì)列、判空、入隊(duì)、出隊(duì)、取對頭元素)，也可以使用STL中的隊(duì)列進(jìn)行代碼的編寫；(3) 采用

2、廣度優(yōu)先策略設(shè)計(jì)可行的過河算法；(4) 輸出要求：按照順序輸出一種可行的過河方案；提示：可以使用 STL中的隊(duì)列進(jìn)行代碼編寫。程序運(yùn)行結(jié)果：The reuers path is：Th。 location is ：15The location is ：6|The location is ： 14Th。 location is ：2The location is ： 11The location is ： 1Th© location is ：9 The location is :。Press ang keg to continue二進(jìn)制表不':111101101110001010

3、11000110010000三、農(nóng)夫過河算法流程Step1 :初始狀態(tài)0000入隊(duì)Step2 :當(dāng)隊(duì)列不空且沒有到達(dá)結(jié)束狀態(tài)1111時(shí)，循環(huán)以下操作:隊(duì)頭狀態(tài)出隊(duì)按照農(nóng)夫一個(gè)人走、農(nóng)夫分別帶上三個(gè)物品走，循環(huán)以下操作：農(nóng)夫和物品如果在同一岸，則計(jì)算新的狀態(tài) 如果新狀態(tài)是安全的并且是沒有處理過的，則更新 path當(dāng)狀態(tài)為1111時(shí)，逆向輸出path口 數(shù)組附錄一：STL中隊(duì)列的使用注：隊(duì)列，可直接用標(biāo)準(zhǔn)模板庫（ STL）中的隊(duì)列。需要#include<queue> STL中的queue,里面的一些成員函數(shù)如下（具體可以查找msdn,搜索front : Returns a refere

4、nce to the first element at the front of the queue.pop: Removes an element from the front of the queue push : Adds an element to the back of the queue empty: Tests if the queue is empty,并將新狀態(tài)入隊(duì)queue class ):三、實(shí)驗(yàn)代碼教育資料判斷狀態(tài)是否安全，安全返回1,否則返回0FarmerRiver.H#ifndef FARMERRIVER_H#define FARMERRIVER_Hint Farm

5、erOnRight(int status); /int WorfOnRight(int status); /int CabbageOnRight(int status); /int GoatOnRight(int status); /int IsSafe(int status); / void FarmerRiver();農(nóng)夫，在北岸返回1,否則返回0狼白菜羊#endifSeqQueue.h#ifndef SEQQUEUE_H#define SEQQUEUE_Htypedef int DataType;struct Queueint Max;int f;int r;DataType *elem

6、;；typedef struct Queue *SeqQueue;SeqQueue SetNullQueue_seq(int m);int IsNullQueue_seq(SeqQueue squeue);void EnQueue_seq(SeqQueue squeue, DataType x);void DeQueue_seq(SeqQueue);DataType FrontQueue_seq(SeqQueue);#endifFarmerRiver.c#include <stdio.h>#include <stdlib.h>#include "SeqQueu

7、e.h"#include "FarmerRiver.h"int FarmerOnRight(int status) /判斷當(dāng)前狀態(tài)下農(nóng)夫是否在北岸return (0!=(status & 0x08);int WorfOnRight(int status) return (0!=(status & 0x04);int CabbageOnRight(int status) return (0!=(status & 0x02);int GoatOnRight(int status) return (0!=(status & 0x01);i

8、nt IsSafe(int status) /判斷當(dāng)前狀態(tài)是否安全if (GoatOnRight(status)=CabbageOnRight(status) &&(GoatOnRight(status)!=FarmerOnRight(status) return (0); / 羊吃白菜if (GoatOnRight(status)=WorfOnRight(status) && (GoatOnRight(status)!=FarmerOnRight(status) return 0; / 狼吃羊return 1; / 其他狀態(tài)是安全的 void FarmerRi

9、ver() int i, movers, nowstatus, newstatus;int status16; / 用于記錄已考慮的狀態(tài)路徑SeqQueue moveTo;moveTo = SetNullQueue_seq(20); / 創(chuàng)建空列隊(duì)EnQueue_seq(moveTo, 0x00); / 初始狀態(tài)時(shí)所有物品在北岸，初始狀態(tài)入隊(duì) for (i=0; i<16; i+) /數(shù)組 status 初始化為-1status。 = -1; status0 = 0;/隊(duì)列非空且沒有到達(dá)結(jié)束狀態(tài) while (!IsNullQueue_seq(moveTo) && (st

10、atus15=-1) nowstatus = FrontQueue_seq(moveTo); / 取隊(duì)頭 DeQueue_seq(moveTo);for (movers=1; movers<=8; movers<<=1)/考慮各種物品在同一側(cè)if (0!=(nowstatus & 0x08) = (0!=(nowstatus & movers)/農(nóng)夫與移動(dòng)的物品在同一側(cè)newstatus = nowstatus A (0x08 | movers); /計(jì)算新狀態(tài)/如果新狀態(tài)是安全的且之前沒有出現(xiàn)過 if (IsSafe(newstatus)&&

11、(statusnewstatus = -1) statusnewstatus = nowstatus; /記錄新狀態(tài)EnQueue_seq(moveTo, newstatus); /新狀態(tài)入隊(duì) /輸出經(jīng)過的狀態(tài)路徑 if (status15!=-1) printf("The reverse path is: n");for (nowstatus=15; nowstatus>=0; nowstatus=statusnowstatus) printf("The nowstatus is: %dn", nowstatus);if (nowstatus =

12、 0) return; elseprintf("No solution.n");Sequeue.c#include <stdio.h>#include <stdlib.h>#include "SeqQueue.h"SeqQueue SetNullQueue_seq(int m) SeqQueue squeue;squeue = (SeqQueue)malloc(sizeof(struct Queue);if (squeue=NULL) printf("Alloc failure'n");return N

13、ULL;squeue->elem = (int *)malloc(sizeof(DataType) * m);if (squeue->elem!=NULL) squeue->Max = m;squeue->f = 0;squeue->r = 0;return squeue;else free(squeue);int IsNullQueue_seq(SeqQueue squeue)return (squeue->f=squeue->r);void EnQueue_seq(SeqQueue squeue, DataType x) / 入隊(duì) if (sque

14、ue->r+1) % squeue->Max=squeue->f) / 是否滿 printf("It is FULL Queue!");else squeue->elemsqueue->r = x;squeue->r = (squeue->r+1) % (squeue->Max); void DeQueue_seq(SeqQueue squeue) / 出隊(duì) if (IsNullQueue_seq(squeue)printf("It is empty queue!n");elsesqueue->f =

15、 (squeue->f+1) % (squeue->Max);DataType FrontQueue_seq(SeqQueue squeue) /求隊(duì)歹U元素if (squeue->f=squeue->r)printf("It is empty queue!n");elsereturn (squeue->elemsqueue->f);main.c#include <stdio.h>#include <stdlib.h>#include "FarmerRiver.hint main(void)FarmerRiver();r