野人和传教士过河问题的C语言源代码

  1 //问题：有3个传教士和3个野人要过河，只有一艘船，这艘船每次
  2 //只能载2个人过河，且无论哪边野人的数量大于传教士的数量时，
  3 //野人就会吃掉传教士。怎样让他们都安全过河？
  4
  5 #include <stdio.h>
  6 #include <string.h>
  7
  8 #define STEP_MAX 20 //来回过河的次数
  9 #define KIND_NUM 3 //每个种类的数量
 10 #define BOAT_NUM 2 //船的载重量
 11
 12 typedef enum
 13 {
 14     BOAT_THIS,//船在本岸
 15     BOAT_THAT,//船在对岸
 16 } boat_t;
 17
 18 typedef enum
 19 {
 20     ROAD_GO,//过河
 21     ROAD_COME,//回来
 22 } road_t;
 23
 24 typedef struct
 25 {
 26     int ye;//对岸野人数量
 27     int man;//对岸传教士数量
 28     boat_t boat;//船是否在对岸
 29 } state_t;//一种局面
 30
 31 typedef struct
 32 {
 33     int ye;//野人过河数量
 34     int man;//传教士过河的数量
 35     road_t road;//回来或过河
 36 } step_t;//一个步骤
 37
 38
 39 state_t states[STEP_MAX] = { 0 };
 40 step_t steps[STEP_MAX] = { 0 };
 41
 42
 43 //判断所有的野人和传教士是否都到了对岸
 44 bool final(state_t s)
 45 {
 46     const state_t cs =
 47     {
 48        KIND_NUM,
 49        KIND_NUM,
 50        BOAT_THAT
 51     };
 52     if (memcmp(&cs, &s, sizeof(state_t)) == 0)
 53     {
 54         return true;
 55     }
 56     return false;
 57 }
 58
 59 //是否会发生野人杀传教士
 60 bool bad(state_t s)
 61 {
 62     if (((KIND_NUM - s.ye) > (KIND_NUM - s.man)
 63         && (KIND_NUM - s.man) > 0)
 64         || (s.ye > s.man&& s.man > 0))
 65     {
 66         return true;
 67     }
 68     return false;
 69 }
 70
 71 //第n种局面是否跟前面的相重复
 72 bool repeat(state_t s[], int n)
 73 {
 74     int i;
 75
 76     for (i = 0; i < n; i++)
 77     {//已经有这种情况了
 78         if (memcmp(&states[i], &states[n], sizeof(states[i])) == 0)
 79         {
 80             return true;
 81         }
 82     }
 83     return false;
 84 }
 85
 86 void output(step_t steps[STEP_MAX], int n)
 87 {
 88     const char* kinds[KIND_NUM] = { "野人","传教士" };
 89     const char* roads[2] = { "过河.","回来." };
 90     int i;
 91
 92     for (i = 0; i < n; i++)
 93     {
 94         if ((steps[i].ye * steps[i].man) > 0)
 95         {
 96             printf("%d个%s和%d个%s%s\n", steps[i].ye, kinds[0],
 97                 steps[i].man, kinds[1], roads[steps[i].road]);
 98         }
 99         else if (steps[i].ye > 0)
100         {
101             printf("%d个%s%s\n", steps[i].ye, kinds[0],
102                 roads[steps[i].road]);
103         }
104         else if (steps[i].man > 0)
105         {
106             printf("%d个%s%s\n", steps[i].man, kinds[1],
107                 roads[steps[i].road]);
108         }
109     }
110     printf("\n");
111 }
112
113 //搜索过河方案(n表示过河次数)
114 void search(int n)
115 {
116     int i, j;
117
118     if (n > STEP_MAX)
119     {//步数限制太少了
120         printf("Step Overflow!");
121         return;
122     }
123     if (final(states[n]))
124     {//都到对岸了
125         output(steps, n);
126         return;
127     }
128     if (bad(states[n]))
129     {//发生了野人杀传教士了
130         return;
131     }
132     if (repeat(states, n))
133     {//与前面的局面相重复了
134         return;
135     }
136     if (states[n].boat == BOAT_THIS)
137     {//船在本岸
138         for (i = 0; i <= BOAT_NUM && i <= (KIND_NUM - states[n].ye); i++)
139             for (j = 0; j <= BOAT_NUM - i && j <= (KIND_NUM - states[n].man); j++)
140             {
141                 if (i == 0 && j == 0)
142                 {
143                     continue;
144                 }
145                 steps[n].ye = i;
146                 steps[n].man = j;
147                 steps[n].road = ROAD_GO;
148                 memcpy(&states[n + 1], &states[n], sizeof(state_t));
149                 states[n + 1].ye += i;
150                 states[n + 1].man += j;
151                 states[n + 1].boat = BOAT_THAT;
152                 search(n + 1);
153             }
154     }
155     else
156     {
157         for (i = 0; i <= BOAT_NUM && i <= states[n].ye; i++)
158         {
159             for (j = 0; j <= BOAT_NUM - i && j <= states[n].man; j++)
160             {
161                 if (i == 0 && j == 0)
162                 {
163                     continue;
164                 }
165                 steps[n].ye = i;
166                 steps[n].man = j;
167                 steps[n].road = ROAD_COME;
168                 memcpy(&states[n + 1], &states[n], sizeof(state_t));
169                 states[n + 1].ye -= i;
170                 states[n + 1].man -= j;
171                 states[n + 1].boat = BOAT_THIS;
172                 search(n + 1);
173             }
174         }
175     }
176 }
177
178 int main()
179 {
180     search(0);
181     return 0;
182 }

1个野人和1个传教士过河.
1个传教士回来.
2个野人过河.
1个野人回来.
2个传教士过河.
1个野人和1个传教士回来.
2个传教士过河.
1个野人回来.
2个野人过河.
1个传教士回来.
1个野人和1个传教士过河.

1个野人和1个传教士过河.
1个传教士回来.
2个野人过河.
1个野人回来.
2个传教士过河.
1个野人和1个传教士回来.
2个传教士过河.
1个野人回来.
2个野人过河.
1个野人回来.
2个野人过河.

2个野人过河.
1个野人回来.
2个野人过河.
1个野人回来.
2个传教士过河.
1个野人和1个传教士回来.
2个传教士过河.
1个野人回来.
2个野人过河.
1个传教士回来.
1个野人和1个传教士过河.

2个野人过河.
1个野人回来.
2个野人过河.
1个野人回来.
2个传教士过河.
1个野人和1个传教士回来.
2个传教士过河.
1个野人回来.
2个野人过河.
1个野人回来.
2个野人过河.