/* 功 能：安全过河，初始状态可变，寻找一种方案 */
#define N 30
int x[N],y[N],u[6],v[6],k
/* x,y：状态值，分别表示此岸商人、随从数；u,v：决策值，分别表示船上商人、随从数；*/
/* k：决策步数；k的奇偶性标志着船在河的此岸或彼岸 */next(int k,int i)
/* 计算下一状态x,y */
{ if(k%2) /* k+1 为偶数，船从此岸到彼岸 */
{ x[k+1]=x[k]-u[i]
y[k+1]=y[k]-v[i]
}
else /* k+1 为奇数，船从彼岸到此岸 */
{ x[k+1]=x[k]+u[i]
y[k+1]=y[k]+v[i]
}
return
}allow(int p,int q)
/* 判定状态是否允许,是否重复 */
{ int ok,j /* ok:标记状态是否允许,是否重复；j:循环变量 */
if(p<0 || p>x[1] || p!=0 &&q>p ||(x[1]-p)!=0 &&(y[1]-q)>(x[1]-p) || q<0 || q>y[1])
ok=0 /* 此时状态不属于允许集 */
else
{ for(j=k-1j>0j-=2) /* 是否重复与船在河的哪一岸有关 */
if(p==x[j] &&q==y[j] )
{ ok=0 /* 此时状态出现重复 */
break
}
if(j<=0)
ok=1 /* 此时状态属于允许集，且不重复 */
}
return ok
}main()
{ int i,j,m[N],flag=1
/* m:采用的决策序号，flag:回溯标记 */
u[1]=2v[1]=0 /* 给决策编号并赋值 */
u[2]=0v[2]=2
u[3]=1v[3]=0
u[4]=0v[4]=1
u[5]=1v[5]=1
k=1 /* 从初始状态出发 */
printf("qing shu ru chu shi zhuang tai:\n shangren ren shu=")
scanf("%d",&x[k])
printf(" sui cong ren shu=")
scanf("%d",&y[k])
while(flag)
{ for(i=1i<6i++) /* 遍历各种决策 */
{ next(k,i) /* 计算下一状态 */
if(allow(x[k+1],y[k+1]))/* 若新状态允许且不重复 */
{ m[k]=i /* 记录采用的决策序号 */
if(x[k+1]==0 &&y[k+1]==0) /* 若到达目标状态 */
{ printf("chu shi zhi:shang ren %d sui cong%d\n",x[1],y[1])/* 输出结果 */
for(j=1j<=kj++)
printf(" di %2d ci %d %d\n",j,x[j+1],y[j+1])
flag=0
break
}
else /* 若未到达目标状态 */
{ k++ /* 生成下一步的步数值 */
break /* 遍历终止，进入下一步 */
}
}
else /* 若新状态不允许或重复 */
{ while(i==5) /* 本步决策已经遍历时 */
{ if(k==1)
{ printf("ben ti wu jie! \n")
flag=0
break
}
else /* 未到达初始状态 */
{ k--/* 回溯——退回1步，寻找新路径 */
i=m[k]
}
}
if(flag)
continue /* 本步决策尚未遍历时 */
else
break /* 本步决策遍历时 */
}
}
}
}
你好，我来为你解答：解法如下：
2.农夫带狼过去，带羊回来
3.农夫带白菜过去，自己回来
4.农夫带羊过去
全部安全过岸.
程序暂时没有时间做
