這篇文章給大家分享的是有關(guān)基于C++如何解決農(nóng)夫過河問題的內(nèi)容。小編覺得挺實用的,因此分享給大家做個參考,一起跟隨小編過來看看吧。
目前創(chuàng)新互聯(lián)已為1000+的企業(yè)提供了網(wǎng)站建設(shè)、域名、雅安服務(wù)器托管、成都網(wǎng)站托管、企業(yè)網(wǎng)站設(shè)計、廣平網(wǎng)站維護等服務(wù),公司將堅持客戶導(dǎo)向、應(yīng)用為本的策略,正道將秉承"和諧、參與、激情"的文化,與客戶和合作伙伴齊心協(xié)力一起成長,共同發(fā)展。
問題描述:
一個農(nóng)夫帶著—只狼、一只羊和—棵白菜,身處河的南岸。他要把這些東西全部運到北岸。他面前只有一條小船,船只能容下他和—件物品,另外只有農(nóng)夫才能撐船。如果農(nóng)夫在場,則狼不能吃羊,羊不能吃白菜,否則狼會吃羊,羊會吃白菜,所以農(nóng)夫不能留下羊和白菜自己離開,也不能留下狼和羊自己離開,而狼不吃白菜。請求出農(nóng)夫?qū)⑺械臇|西運過河的方案。
實現(xiàn)上述求解的搜索過程可以采用兩種不同的策略:一種廣度優(yōu)先搜索,另一種深度優(yōu)先搜索。這里介紹在廣度優(yōu)先搜索方法中采用的數(shù)據(jù)結(jié)構(gòu)設(shè)計。
程序源碼:
/*********************************************** * 農(nóng)夫過河問題(P64 隊列的應(yīng)用) * 約定:用四位二進制數(shù)分別順序表示農(nóng)夫、狼、白菜和羊的狀態(tài) * 即:{dddd} <=> {Farmer, Wolf, Cabbage, Goat} 其中:d={0,1} * 說明:0表示在東岸 1表示在西岸,初始狀態(tài)為0000,終止?fàn)顟B(tài)為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; // 創(chuàng)建空隊列 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); } // 若狀態(tài)相容(安全)則返回1,否則返回0 int is_safe(int state) { if((is_goat_crossed(state) == is_cabbage_crossed(state)) && (is_goat_crossed(state) != is_farmer_crossed(state))) // 羊菜同岸且農(nóng)夫不在場 return(0); if((is_goat_crossed(state) == is_wolf_crossed(state)) && (is_goat_crossed(state) != is_farmer_crossed(state))) // 狼羊同岸且農(nóng)夫不在場 return(0); return(1); } void river_crossing_problem() { int route[16]; // 記錄已經(jīng)考慮過的狀態(tài) int state; // 記錄當(dāng)前時刻的狀態(tài)(狀態(tài)編號的二進制形式即狀態(tài)本身) int aftercross; // 記錄漁夫當(dāng)前的選擇(渡河對象)會導(dǎo)致的結(jié)果狀態(tài) int passenger; // 臨時變量,用于表達農(nóng)夫的選擇(對應(yīng)二進制位為1表示選中該乘客) int results[16]={0}; // 輸出結(jié)果 int counter, i; SeqQueuePtr states_que; // states_que = create_sequeue(); // 創(chuàng)建“狀態(tài)”隊列 enqueue(states_que,0x00); // 初始狀態(tài)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"); } // 依次考慮農(nóng)夫可能的選擇:攜帶羊、白菜和狼,以及農(nóng)夫只身渡河 for( passenger = 1; passenger<= 8; passenger <<= 1 ) { // 由于農(nóng)夫總是在過河,隨農(nóng)夫過河的也只能是與農(nóng)夫同側(cè)的東西 if(((state & 0x08) != 0) == ((state & passenger) != 0)){ // 如果農(nóng)夫與當(dāng)前乘客在河岸的同一側(cè) aftercross = state^( 0x08|passenger ); // 渡河后的情況 if(is_safe(aftercross) && (route[aftercross] == -1)){ // 如果渡河后狀態(tài)安全,則將其狀態(tài)入隊 route[aftercross] = state; // 將當(dāng)前狀態(tài)的索引記錄到路徑數(shù)組中(下標(biāo)索引為后續(xù)狀態(tài)值) enqueue(states_que, aftercross); } } }//end for() }//end while() // 輸出過河策略:0表示在東岸 1表示在西岸,初始狀態(tài)為0000,終止?fàn)顟B(tài)為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("農(nóng)夫從東岸到西岸:"); } else{ printf("農(nóng)夫從西岸到東岸:"); } 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; }
運行結(jié)果:
感謝各位的閱讀!關(guān)于“基于C++如何解決農(nóng)夫過河問題”這篇文章就分享到這里了,希望以上內(nèi)容可以對大家有一定的幫助,讓大家可以學(xué)到更多知識,如果覺得文章不錯,可以把它分享出去讓更多的人看到吧!
當(dāng)前題目:基于C++如何解決農(nóng)夫過河問題
URL鏈接:http://chinadenli.net/article16/ihoegg.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供企業(yè)網(wǎng)站制作、營銷型網(wǎng)站建設(shè)、網(wǎng)站設(shè)計、定制網(wǎng)站、網(wǎng)站收錄、電子商務(wù)
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請盡快告知,我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場,如需處理請聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時需注明來源: 創(chuàng)新互聯(lián)