/* 功 能:安全过河,初始状态可变,寻找一种方案 */
#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 /* 本步决策遍历时 */
}
}
}
}
按照你的要求,不使用数组。
我的思路,起点货物狼、羊、白菜,人一直在开船,通过递归函数,每次靠岸尝试装卸货方案,直到找满足条件的方案。将可行方案存放在结构链表中形成 *** 作流水打印。
人狼羊菜存储方式模拟4位2进制,用1111表示,每位表示一个单位,1存在,0不存在。
#include<stdio.h>#include<malloc.h>
typedef enum{false,true}bool
typedef struct opRecord//用结构链表记录 *** 作流水
{
int p1_take//p1载货值
int p1_goAd//p1卸货值
int p2_take//p2载货值
int p2_goAd//p2卸货值
int cen//递归层号
struct opRecord *next
}OPR
OPR *oprHead
OPR *oprTail
char *getName(int b)//获取对应名称
int beEaten(int p1,int p2)//检查是否发生被吃事件,发生返回1,未发生返回0
int toShip(int *p1,int *p2,int *ship,bool f)//递归函数:上船人及任意一组合,返回状态,1:方案可行;0:方案不可行
int getFist(int pn)//获取物品组合中第一个
void addLog(int p1_take,int p1_goAd,int p2_take,int p2_goAd,int cen)//将有效 *** 作添加进日志,cen相同,将视为修改覆盖
void printfLog()//打印 *** 作流水
OPR *findLogBycen(int cen)//通过cen查找流水。 有返回节点指针。无返回NULL
int count=1
int flag=0//标识变量=1成立; =0不成立
int cen=0
int main()
{
int p1=111,ship=1000,p2=0000//p1,p2分别表示两岸,4位数每一位分别表示人狼羊菜,位数值1表示存在,0表示不存在
oprHead=(OPR *)malloc(sizeof(OPR))
oprHead->next=NULL
oprTail=NULL
printf("河岸有人、狼、羊、白菜要过河,船每次载人及一物,为避免人上船后狼吃羊或羊吃菜\n开始生成方案:\n\n")
if(toShip(&p1,&p2,&ship,0))
{
printf("\n开始生成结果报告:\n")
printfLog()
}
else
printf("无可行方案!!\n")
return 0
}
void addLog(int p1_take,int p1_goAd,int p2_take,int p2_goAd,int cen)//将有效 *** 作添加进日志,cen相同,将视为修改覆盖,
{
OPR *oprNew=findLogBycen(cen)
if(oprNew==NULL)//通过查找。确认无记录,新增记录
{
oprNew=(OPR *)malloc(sizeof(OPR))
oprNew->p1_take=p1_take
oprNew->p1_goAd=p1_goAd
oprNew->p2_take=p2_take
oprNew->p2_goAd=p2_goAd
oprNew->cen=cen
oprNew->next=NULL
if(oprHead->next==NULL)
oprHead->next=oprNew
else
oprTail->next=oprNew
oprTail=oprNew
}
else//查找发现已有记录,修改
{
oprNew->p1_take=p1_take
oprNew->p1_goAd=p1_goAd
oprNew->p2_take=p2_take
oprNew->p2_goAd=p2_goAd
}
}
OPR *findLogBycen(int cen)//通过cen查找流水。 有返回节点指针。无返回NULL
{
OPR *headSave=oprHead
while(headSave->next!=NULL)
{
if(headSave->next->cen==cen)
return headSave->next
headSave=headSave->next
}
return NULL
}
void printfLog()//打印 *** 作流水
{
OPR *headSave=oprHead
int p1_take,p1_goAd,p2_take,p2_goAd,cen,p1TOp2,p2TOp1
while(headSave->next!=NULL)
{
p1_take=headSave->next->p1_take
p1_goAd=headSave->next->p1_goAd
p2_take=headSave->next->p2_take
p2_goAd=headSave->next->p2_goAd
cen=headSave->next->cen
if(p1_take>0 || p1_goAd>0)
p1TOp2=1
else
p1TOp2=0
if(p2_take>0 || p2_goAd>0)
p2TOp1=1
else
p2TOp1=0
printf(" *** 作流水%2d:",cen)
printf("%s%s",p1TOp2>0?"从p1":"",p2TOp1>0?"从p2":"")
printf("%s%s",p1_goAd>0?getName(p1_goAd):"",p1_goAd>0?"下船":"")
printf("%s%s",p1_take>0?getName(p1_take):"",p1_take>0?"上船":"")
printf("%s%s",p2_goAd>0?getName(p2_goAd):"",p2_goAd>0?"下船":"")
printf("%s%s",p2_take>0?getName(p2_take):"",p2_take>0?"上船":"")
if(headSave->next->next!=NULL)
printf("。之后行驶方向:%s%s\n",p1TOp2>0?"p1->p2":"",p2TOp1>0?"p1<-p2":"")
else
printf("\n")
headSave=headSave->next
}
}
char *getName(int b)//获取对应名称
{
if(b==1000)
return "人"
else if(b==100)
return "狼"
else if(b==10)
return "羊"
else if(b==1)
return "菜"
return ""
}
int toShip(int *p1,int *p2,int *ship,bool f)//递归函数:上船人及任意一组合;lastTake:上一次承载物体,首次调用传0;f=0:p1->p2方向1:反向。返回状态,1:方案可行;0:方案不可行
{
int take=-1,goAd,gdflag=1,cenSave//take:上船物体。 goAd:下船物体。gdflag:标识变量,p2判断能否直接下船,1能0不能
cenSave=++cen
while(1)
{
goAd=*ship-1000
if(f==0)//准备p1往p2
{
if(take==-1)
take=getFist(*p1)
*p1-=take
*p1+=goAd
gdflag=1//标识置1,等到p2首先尝试直接卸货
}
else//准备p2往p1
{
if(take==-1 && gdflag==0)
{
take=getFist(*p2)
printf("开始尝试替换货物:\n")
}
if(gdflag==1)//如果p2可以直接卸货
*p2+=goAd
else//如果不能直接卸货,尝试带走一个同时卸货
{
*p2-=take
*p2+=goAd
}
}
printf("递归层级%d:假设%s从%s上船。%s下船,%s方向行驶。\n",cenSave,take>0?getName(take):"无货物",f==0?"p1":"p2",goAd!=0?getName(goAd):"无货物",f==0?"p1往p2":"p2往p1")
if(beEaten(*p1,*p2))//如果发生被吃,假设失败,还原数据,选择下一假设
{
if(f==0)
{
*p1+=take
*p1-=goAd
}
else
{
if(gdflag==1)//p2点确定不能直接卸货,还原数据,标识置0
{
printf("----不能直接卸货,货物%s回到船上。",getName(goAd))
*p2-=goAd
gdflag=0
continue
}
else//不能直接卸货并尝试替换货物失败,选择下一个货物替换
{
*p2+=take
*p2-=goAd
}
}
if(take==1)
{
printf("本次靠岸无可行的装卸方案,返回层级%d!\n",cenSave-1)
return 0
}
take=take/10//尝试选择下一个货物
continue
}
else
{
if(f==1 && gdflag==1)//p2直接卸货假设成立船清空
*ship=1000
else
*ship=1000+take//换货假设成立货物装船
if(*p1==0)//如果已经完全转移
{
printf("所有货物过河成功!!\n")
return 1
}
if(f==0)
addLog(take,goAd,0,0,cenSave)//生成流水日志
else
addLog(0,0,take,goAd,cenSave)//生成流水日志
if(toShip(p1,p2,ship,f==0?1:0))
{
return 1
}
else//由于下级失败,本回合重新选择
{
gdflag=0
continue
}
}
}
}
int getFist(int pn)//获取物品组合中第一个
{
int i,count=0
while(1)//上船物体从岸上第一个物体开始选择
{
if(pn<=1)
break
pn=pn/10
count++
}
for(i=0i<counti++)
pn=pn*10
return pn
}
int beEaten(int p1,int p2)//检查是否发生被吃事件,发生返回1,未发生返回0
{
int ren=0
if(p1==110 && ++ren==1)
printf("----河岸p1狼把羊吃了!重新选择\n")
if(p2==110 && ++ren==1)
printf("----河岸p2狼把羊吃了!重新选择\n")
if(p1==11 && ++ren==1)
printf("----河岸p1羊把菜吃了!重新选择\n")
if(p2==11 && ++ren==1)
printf("----河岸p2羊把菜吃了!重新选择\n")
return ren
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)