工具类服务
编辑部专用服务
作者专用服务
利用数组解决农夫过河问题
农夫过河问题是一类经典的数据结构问题,利用数组这种数据结构求解农夫过河问题,并给出了相应的C源程序.
作者单位：
湖州师范学院 信息与工程学院 浙江湖州313000
年，卷(期)：
机标分类号：
在线出版日期：
本文读者也读过
相关检索词
万方数据知识服务平台--国家科技支撑计划资助项目（编号：2006BAH03B01）(C)北京万方数据股份有限公司
万方数据电子出版社商人过河策略问题，我自己写的出了什么问题
[问题点数：100分]
商人过河策略问题，我自己写的出了什么问题
[问题点数：100分]
不显示删除回复
显示所有回复
显示星级回复
显示得分回复
只显示楼主
匿名用户不能发表回复！|
每天回帖即可获得10分可用分！小技巧：
你还可以输入10000个字符
(Ctrl+Enter)
请遵守CSDN，不得违反国家法律法规。
转载文章请注明出自“CSDN（www.csdn.net）”。如是商业用途请联系原作者。5671人阅读
C语言算法（6）
三人三鬼过河问题：
三个人和三个鬼在河边，都想要到河的对岸去；河边有一只船，只能搭载两个人、或者两个鬼、或者一人一鬼；如果在岸上或者在船上，鬼的数目多于人的数目，鬼就会把人吃掉。
怎样安排人和鬼的组合上船过河，才能使三个人和三个鬼都安全到河的对岸去呢？
程序思路：
人鬼过河问题实际上可以考虑为状态之间的迁移，或者是构建一个有向图，然后在图中寻找可行的路径。
我们把当前岸边作为左岸，河的对岸作为右岸。
那么状态包含两个因素，一个是左岸上人鬼的数量(右岸人鬼的数量可以由左岸人鬼数量计算得出)，另一个是船在左岸还是在右岸。
迁移表现为从人鬼从左岸渡船到右岸，或者人鬼从右岸渡船到左岸。
因为鬼多于人的时候会吃人，所以不是任意的人和鬼的数量的组合都是合理的状态。
程序中首先找到所有合理的状态，然后再找到所有状态到状态可行的迁移，最后深度搜索所有迁移，寻找到从开始状态到结束状态间的可行路径。
程序的输出也是按照这个步骤，分成了三个部分，分别是可行状态、可行迁移，可行路径。
G-ghost鬼
LB-left boat船在左边
RB-right boat船在右边
#include &stdio.h&
#include &stdlib.h&
#include &string.h&
#define LBOAT '*'
#define RBOAT ' '
typedef struct HGB_struct
int ARR_LEN;
int state_
HGB * //[ARR_LEN];
int * // [ARR_LEN][ARR_LEN];
int stack_
HGB * // [ARR_LEN];
#define transfer_ref(i, j) (transfer[i * ARR_LEN + j])
#define stack_init() (stack_sp = 0)
#define stack_push(hgb) (stack[stack_sp++] = (hgb))
#define stack_pop() (stack[--stack_sp])
#define stack_top(hgb) (stack[stack_sp - 1])
#define stack_find(hgb, result) for(result = stack_sp - 1; result &= 0; result--) { if(stack[result].H == hgb.H && stack[result].G == hgb.G && stack[result].B == hgb.B) }
#define state_find(hgb, result) for(result = state_count - 1; result &= 0; result--) { if(state[result].H == hgb.H && state[result].G == hgb.G && state[result].B == hgb.B) }
int search(HGB hgb, int n)
if((hgb.H == 0) && (hgb.G == 0) && (hgb.B == RBOAT))
stack_push(hgb);
printf(&=======================================================================================================\n&);
for(i = 0; i & stack_ i++)
printf(&H%dG%d[%c] &, stack[i].H, stack[i].G, stack[i].B);
printf(&\n&);
printf(&-------------------------------------------------------------------------------------------------------\n&);
printf( &H%dG%d
H%dG%d\n&,
stack[0].H, stack[0].G,
n - stack[0].H, n - stack[0].G);
for(i = 0; i & stack_sp - 1; i++)
&-H%dG%d--\n&
H%dG%d\n&,
stack[i + 1].H - stack[i].H, stack[i + 1].G - stack[i].G,
stack[i + 1].H, stack[i + 1].G,
n - stack[i + 1].H, n - stack[i + 1].G);
--H%dG%d-&\n&
H%dG%d\n&,
stack[i].H - stack[i + 1].H, stack[i].G - stack[i + 1].G,
stack[i + 1].H, stack[i + 1].G,
n - stack[i + 1].H, n - stack[i + 1].G);
printf(&=======================================================================================================\n&);
stack_pop();
return -1;
stack_find(hgb, index);
if(index &= 0)
state_find(hgb, index);
stack_push(hgb);
for(i = 0; i & state_ i++)
if(transfer_ref(index, i))
search(state[i], n);
stack_pop();
void human_ghost(int human_ghost_count, int boat_capacity)
int HL, GL, HR, GR;
stack = NULL; // [ARR_LEN];
state = NULL; //[ARR_LEN];
transfer = NULL; // [ARR_LEN][ARR_LEN];
ARR_LEN = (2 * (human_ghost_count + 1) * (human_ghost_count + 1));
state = (HGB *)malloc(ARR_LEN * sizeof(HGB));
if(state == NULL)
stack = (HGB *)malloc(ARR_LEN * sizeof(HGB));
if(stack == NULL)
transfer = (int *)malloc(ARR_LEN * ARR_LEN * sizeof(int));
if(transfer == NULL)
printf(&human_ghost:%d boat_capacity:%d\n&, human_ghost_count, boat_capacity);
state_count = 0;
for(i = 0; i & (human_ghost_count + 1) * (human_ghost_count + 1); i++)
HR = i / (human_ghost_count + 1);
GR = i % (human_ghost_count + 1);
HL = human_ghost_count - HR;
GL = human_ghost_count - GR;
if((HL & 0) && (HL & GL))
if((HR & 0) && (HR & GR))
printf(&H%dG%d:H%dG%d L\n&, HL, GL, HR, GR);
printf(&H%dG%d:H%dG%d R\n&, HL, GL, HR, GR);
state[state_count].H = HL;
state[state_count].G = GL;
state[state_count].B = LBOAT;
state_count++;
state[state_count].H = HL;
state[state_count].G = GL;
state[state_count].B = RBOAT;
state_count++;
for(j = 0; j & state_ j++)
printf(&H%dG%d[%c] &, state[j].H, state[j].G, state[j].B);
printf(&\n&);
for(i = 0; i & state_ i++)
printf(&H%dG%d[%c] |&, state[i].H, state[i].G, state[i].B);
for(j = 0; j & state_ j++)
transfer_ref(i, j) = 1;
if(state[i].B == LBOAT)
if(state[j].B == LBOAT) transfer_ref(i, j) = 0;
if(state[i].H & state[j].H) transfer_ref(i, j) = 0;
if(state[i].G & state[j].G) transfer_ref(i, j) = 0;
tmp = (state[i].H + state[i].G) - (state[j].H + state[j].G);
if(tmp &= 0 || tmp & boat_capacity) transfer_ref(i, j) = 0;
if(state[j].B == RBOAT) transfer_ref(i, j) = 0;
if(state[i].H & state[j].H) transfer_ref(i, j) = 0;
if(state[i].G & state[j].G) transfer_ref(i, j) = 0;
tmp = (state[j].H + state[j].G) - (state[i].H + state[i].G);
if(tmp &= 0 || tmp & boat_capacity) transfer_ref(i, j) = 0;
if(transfer_ref(i, j))
printf(& H%dG%d%c |&, state[j].H, state[j].G, state[j].B);
printf(&\n&);
stack_init();
search(state[0], human_ghost_count);
} while(0);
if(stack) free(stack);
if(state) free(state);
if(transfer) free(transfer);
int main(int argc, char *argv[])
int human_ghost_count = 0;
int boat_capacity = 0;
human_ghost(3, 2);
程序的输出结果：
human_ghost:3 boat_capacity:2
H3G3:H0G0 L
H3G3:H0G0 R
H3G2:H0G1 L
H3G2:H0G1 R
H3G1:H0G2 L
H3G1:H0G2 R
H3G0:H0G3 L
H3G0:H0G3 R
H2G2:H1G1 L
H2G2:H1G1 R
H1G1:H2G2 L
H1G1:H2G2 R
H0G3:H3G0 L
H0G3:H3G0 R
H0G2:H3G1 L
H0G2:H3G1 R
H0G1:H3G2 L
H0G1:H3G2 R
H0G0:H3G3 L
H0G0:H3G3 R
H3G3[*] H3G3[ ] H3G2[*] H3G2[ ] H3G1[*] H3G1[ ] H3G0[*] H3G0[ ] H2G2[*] H2G2[ ] H1G1[*] H1G1[ ] H0G3[*] H0G3[ ] H0G2[*] H0G2[ ] H0G1[*] H0G1[ ] H0G0[*] H0G0[ ]
H3G2[ ] | H3G3* |
H3G1[ ] | H3G3* |
H2G2[ ] | H3G3* |
=======================================================================================================
H3G3[*] H3G1[ ] H3G2[*] H3G0[ ] H3G1[*] H1G1[ ] H2G2[*] H0G2[ ] H0G3[*] H0G1[ ] H1G1[*] H0G0[ ]
-------------------------------------------------------------------------------------------------------
=======================================================================================================
=======================================================================================================
H3G3[*] H3G1[ ] H3G2[*] H3G0[ ] H3G1[*] H1G1[ ] H2G2[*] H0G2[ ] H0G3[*] H0G1[ ] H0G2[*] H0G0[ ]
-------------------------------------------------------------------------------------------------------
=======================================================================================================
=======================================================================================================
H3G3[*] H2G2[ ] H3G2[*] H3G0[ ] H3G1[*] H1G1[ ] H2G2[*] H0G2[ ] H0G3[*] H0G1[ ] H1G1[*] H0G0[ ]
-------------------------------------------------------------------------------------------------------
=======================================================================================================
=======================================================================================================
H3G3[*] H2G2[ ] H3G2[*] H3G0[ ] H3G1[*] H1G1[ ] H2G2[*] H0G2[ ] H0G3[*] H0G1[ ] H0G2[*] H0G0[ ]
-------------------------------------------------------------------------------------------------------
=======================================================================================================
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：33672次
排名：千里之外
原创：19篇
评论：11条
(3)(3)(1)(1)(1)(2)(6)(1)(2)