本文實例講述了基于C++的農夫過河問題算法設計與實現方法。分享給大家供大家參考，具體如下：
問題描述：
一個農夫帶著—只狼、一只羊和—棵白菜，身處河的南岸。他要把這些東西全部運到北岸。他面前只有一條小船，船只能容下他和—件物品，另外只有農夫才能撐船。如果農夫在場，則狼不能吃羊，羊不能吃白菜，否則狼會吃羊，羊會吃白菜，所以農夫不能留下羊和白菜自己離開，也不能留下狼和羊自己離開，而狼不吃白菜。請求出農夫將所有的東西運過河的方案。
實現上述求解的搜索過程可以采用兩種不同的策略：一種廣度優先搜索，另一種深度優先搜索。這里介紹在廣度優先搜索方法中采用的數據結構設計。
程序源碼：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
|
/*********************************************** * 農夫過河問題（P64 隊列的應用） * 約定：用四位二進制數分別順序表示農夫、狼、白菜和羊的狀態 * 即：{dddd} <=> {Farmer, Wolf, Cabbage, Goat} 其中：d={0,1} * 說明：0表示在東岸 1表示在西岸，初始狀態為0000，終止狀態為1111************************************************/#include<stdio.h>#include<stdlib.h>#define MAXSIZE 16typedef 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，否則返回0int 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++程序設計有所幫助。
原文鏈接：http://blog.csdn.net/u011889952/article/details/44805069
