數(shù)據(jù)結(jié)構課程設計報告(農(nóng)夫過河)

1、目錄引言21 問題描述3基本要求32.1為農(nóng)夫過河問題抽象數(shù)據(jù)模型體會數(shù)據(jù)模型在問題求解中的重要性；32.2設計一個算法求解農(nóng)夫過河問題，并輸出過河方案；33 概要設計33.1 數(shù)據(jù)結(jié)構的設計。33.1.1農(nóng)夫過河問題的模型化33.1.2 算法的設計44、運行與測試65、總結(jié)與心得7附錄7參考文獻12引言所謂農(nóng)夫過河問題是指農(nóng)夫帶一只狼、一只羊和一棵白菜在河南岸, 需要安全運到北岸。一條小船只能容下他和一件物品, 只有農(nóng)夫能撐船。問農(nóng)夫怎么能安全過河, 當然狼吃羊, 羊吃白菜, 農(nóng)夫不能將這兩種或三種物品單獨放在河的一側(cè), 因為沒有農(nóng)夫的照看, 狼就要吃羊, 而羊可能要吃白菜? 這類問題的實質(zhì)

2、是系統(tǒng)的狀態(tài)問題, 要尋求的是從初始狀態(tài)經(jīng)一系列的安全狀態(tài)到達系統(tǒng)的終止狀態(tài)的一條路徑。1 問題描述一個農(nóng)夫帶一只狼、一棵白菜和一只羊要從一條河的南岸過到北岸，農(nóng)夫每次只能帶一樣東西過河，但是任意時刻如果農(nóng)夫不在場時，狼要吃羊、羊要吃白菜，請為農(nóng)夫設計過河方案。2基本要求2.1為農(nóng)夫過河問題抽象數(shù)據(jù)模型體會數(shù)據(jù)模型在問題求解中的重要性；2.2設計一個算法求解農(nóng)夫過河問題，并輸出過河方案；3 概要設計3.1 數(shù)據(jù)結(jié)構的設計。3.1.1農(nóng)夫過河問題的模型化分析這類問題會發(fā)現(xiàn)以下特征: 有一組狀態(tài)( 如農(nóng)夫和羊在南, 狼和白菜在北) ; 從一個狀態(tài)可合法地轉(zhuǎn)到另外幾個狀態(tài)( 如農(nóng)夫自己過河或農(nóng)夫帶著

3、羊過河) ; 有些狀態(tài)不安全( 如農(nóng)夫在北, 其他東西在南) ; 有一個初始狀態(tài)( 都在南) ; 結(jié)束狀態(tài)集( 這里只有一個, 都在北) 。問題表示: 需要表示問題中的狀態(tài), 農(nóng)夫等位于南P北( 每個有兩種可能) ?？梢圆捎梦幌蛄? 4 個二進制位的0P1 情況表示狀態(tài), 顯而易見, 共24= 16種可能狀態(tài)。從高位到低位分別表示農(nóng)夫、狼、白菜和羊。0000( 整數(shù)0) 表示都在南岸, 目標狀態(tài)1111( 即整數(shù)15) 表示都到了北岸。有些狀態(tài)0011,0101, 0111, 0001, 1100, 1001 是不允許出現(xiàn)的, 因為這些狀態(tài)是不安全狀態(tài)。根據(jù)上述條件可以畫出系統(tǒng)的狀態(tài)圖如圖1

4、所示。 圖1 系統(tǒng)狀態(tài)轉(zhuǎn)換圖其中雙向的箭頭表示狀態(tài)可逆, 即農(nóng)夫可以帶著某種東西過去, 也可以帶著該東西回來。箭頭上的字母表示農(nóng)夫所攜帶的東西: f( farmer) , w(wolf) , g(goat) , c( cabbage) 分別表示農(nóng)夫自己、農(nóng)夫攜帶狼、農(nóng)夫攜帶羊、農(nóng)夫攜帶菜過河?，F(xiàn)在的問題轉(zhuǎn)化為: 找一條合法路徑( 相鄰狀態(tài)之間的轉(zhuǎn)移合法) , 從開始狀態(tài)到某個結(jié)束狀態(tài), 途中不經(jīng)過不安全狀態(tài)。3.1.2 算法的設計求農(nóng)夫、狼、白菜和羊的當前狀態(tài)的函數(shù)為每一種狀態(tài)做測試, 狀態(tài)安全則返回0, 否則返回1。安全性判斷函數(shù), 若狀態(tài)安全則返回0 int farmer(int loca

5、tion) /判斷農(nóng)夫位置對0做與運算，還是原來的數(shù)字，用來判斷位置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) / 若狀態(tài)安全則返回

6、 true if (goat(location) = cabbage(location) && (goat(location) != farmer(location) ) return 0; if (goat(location) = wolf(location) && (goat(location) != farmer(location) return 0;return 1; /其他狀態(tài)是安全的借助于位向量和按位運算符, 很容易描述過河動作, 這種問題表示的設計使得程序的實現(xiàn)比較容易。算法的基本思想: 利用隊列moveTo 記錄可到的尚未向前探試的狀態(tài), 數(shù)組元

7、素route i 記錄狀態(tài)i的路徑 前一狀態(tài) , - 1 表示尚未訪問。則算法的高級抽象可描速為:初始狀態(tài)出發(fā)點入隊列;所有其他點狀態(tài)標記為未訪問;while ( ! isEmptyQueue seq ( moveTo) &&( route 15 = - 1) )從moveTo 取出一個狀態(tài);試探所有由這個狀態(tài)出發(fā)可能到達的狀態(tài);if( 能到達的狀態(tài)安全且未訪問過)記錄到它的路徑;壓入隊列;精化上速算法得到問題的具體算法如下:void farmerProblem( ) int movers, i, location, newlocation; int route16; /記錄已

8、考慮的狀態(tài)路徑 int printMAXNUM; PSeqQueue moveTo; moveTo = createEmptyQueue_seq( );/新的隊列判斷路徑 enQueue_seq(moveTo, 0x00); /初始狀態(tài)為0 for (i = 0; i < 16; i+) routei = -1; /-1表示沒有記錄過路徑 route0=0; while (!isEmptyQueue_seq(moveTo)&&(route15= -1)/隊列不為空，路徑未滿時循環(huán) location = frontQueue_seq(moveTo); /從隊頭出隊，loca

9、tion表示位置，0為北岸，1為南岸 deQueue_seq(moveTo);/已出隊的刪除 for (movers = 1; movers <= 8; movers<<= 1) /向左移位，movers分別0001，0010，0100，1000,也就是依次判斷過河的可行性 if (0 != (location & 0x08) = (0 != (location & movers)/判斷農(nóng)夫和要移動的物品是否在同岸 newlocation = location(0x08|movers);/過岸 if (safe(newlocation) &&

10、(routenewlocation = -1)/判斷是否安全，以及路徑是否可用 routenewlocation = location; enQueue_seq(moveTo, newlocation);/記錄路徑并入隊，位置改變4、運行與測試5、總結(jié)與心得“紙上得來終覺淺，絕知此事要躬行?！蓖ㄟ^這兩周的課程設計，使我對書上的的理論知識有了更深的理解，也使我對于團隊合作有了新的認識，意識到團隊的力量。課程設計是一個必須經(jīng)歷的過程，是我們理解書本知識、熟悉所學專業(yè)的一次很好實踐。 在這次設計過程中，體現(xiàn)出自己單獨設計程序的能力以及綜合運用知識的能力，體會了學以致用、突出自己勞動成果的喜悅心情，從

11、中發(fā)現(xiàn)自己平時學習的不足和薄弱環(huán)節(jié)，從而加以彌補。附錄#include<iostream.h>#include<stdio.h>#define MAXNUM 20 typedef struct /順序隊列類型定義 int f, r; /f表示頭，r 表示尾int qMAXNUM;/順序隊SeqQueue ,*PSeqQueue;PSeqQueue createEmptyQueue_seq( ) /創(chuàng)建隊列 PSeqQueue paqu = new SeqQueue; if (paqu = NULL) cout<<"Out of space!&quo

12、t;<<endl; else paqu->f=paqu->r=0; return (paqu); int isEmptyQueue_seq( PSeqQueue paqu ) /判斷 paqu 所指是否是空隊列 return paqu->f=paqu->r; void enQueue_seq(PSeqQueue paqu,int x) /在隊列中插入一元素 xif (paqu->r+1)%MAXNUM=paqu->f) cout<<"隊列已滿."<<endl;else paqu->qpaqu-&g

13、t;r=x;paqu->r=(paqu->r+1)%MAXNUM; void deQueue_seq(PSeqQueue paqu) /刪除隊列頭部元素 if( paqu->f=paqu->r) cout<<"隊列為空"<<endl; else paqu->f=(paqu->f+1)%MAXNUM; int frontQueue_seq( PSeqQueue paqu ) /對非空隊列,求隊列頭部元素 return (paqu->qpaqu->f); int farmer(int location) /

14、判斷農(nóng)夫位置對0做與運算，還是原來的數(shù)字，用來判斷位置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) / 若狀態(tài)安全則返回 true i

15、f (goat(location) = cabbage(location) && (goat(location) != farmer(location) ) return 0; if (goat(location) = wolf(location) && (goat(location) != farmer(location) return 0;return 1; /其他狀態(tài)是安全的 void farmerProblem( ) int movers, i, location, newlocation; int route16; /記錄已考慮的狀態(tài)路徑 int pr

16、intMAXNUM; PSeqQueue moveTo; moveTo = createEmptyQueue_seq( );/新的隊列判斷路徑 enQueue_seq(moveTo, 0x00); /初始狀態(tài)為0 for (i = 0; i < 16; i+) routei = -1; /-1表示沒有記錄過路徑 route0=0; while (!isEmptyQueue_seq(moveTo)&&(route15= -1)/隊列不為空，路徑未滿時循環(huán) location = frontQueue_seq(moveTo); /從隊頭出隊，location表示位置，0為北岸，

17、1為南岸 deQueue_seq(moveTo);/已出隊的刪除 for (movers = 1; movers <= 8; movers<<= 1) /向左移位，movers分別0001，0010，0100，1000,也就是依次判斷過河的可行性 if (0 != (location & 0x08) = (0 != (location & movers)/判斷農(nóng)夫和要移動的物品是否在同岸 newlocation = location(0x08|movers);/過岸 if (safe(newlocation) && (routenewlocat

18、ion = -1)/判斷是否安全，以及路徑是否可用 routenewlocation = location; enQueue_seq(moveTo, newlocation);/記錄路徑并入隊，位置改變 /* 打印出路徑 */ if(route15 != -1) cout<<"過河步驟是 : "<<endl; i=0; for(location = 15; location >= 0; location = routelocation) printi=location; i+; if (location = 0) break; int num=

19、i-1; int temp204; int j; for(i=num;i>=0;i-) for(j=3;j>=0;j-) tempnum-ij=printi%2; printi/=2; temp0j=0; tempnum+1j=1; /* for(i=0;i<=num;i+) for(j=0;j<4;j+) cout<<tempij<<" " cout<<endl; */ for(i=1;i<=num;i+) cout<<"tttNO . "<<i<<"t" if(i%2=1) if(tempi3!=tempi-13) cout<<"農(nóng)夫帶羊過南岸" if(tempi2!=tempi-12) cout<<&q