刚写好 经过VC6测试通过 以下是代码片段:
int M=7;//A容量
int N=4;//B容量
int K=1;//要求量
int watera=0;
int emptya=M;
int flaga=0;//0空 1满 -1有水
int waterb=0;
int emptyb=N;
int flagb=0;//0空 1满 -1有水
int i=0;
char op[500];
void oprec(int oflag)//操作记录-------------------
{
switch(oflag)
{
case 0:op[i]='0';i++;break;
case 1:op[i]='1';i++;break;
case 2:op[i]='2';i++;break;
case 3:op[i]='3';i++;break;
case 4:op[i]='4';i++;break;
case 5:op[i]='5';i++;break;
}
}
void aputin()//0
A装满水----------------------
{
if (flaga==0&&flagb!=1)
{
watera=M;
emptya=0;
flaga=1;
oprec(0);
return;
}
else return;
}
void aputoff()//1 A水清空----------------------
{
if (flaga==1&&flagb!=0)
{
watera=0;
emptya=M;
flaga=0;
oprec(1);
return;
}
else return;
}
void atob()//2 A水倒进B-----------------------
{
if(flaga==0||flagb==1||watera==emptyb)
return;
else if(watera<emptyb)
{
waterb=waterb+watera;
watera=0;
emptya=M;
flaga=0;
emptyb=N-waterb;
flagb=-1;
oprec(2);
return;
}
else if(watera==emptyb)
{
watera=0;
emptya=M;
flaga=0;
waterb=N;
emptyb=0;
flagb=1;
oprec(2);
return;
}
else {
watera=watera-emptyb;
waterb=N;
emptyb=0;
flagb=1;
emptya=M-watera;
flaga=-1;
oprec(2);
return;
}
}
void bputin()//3
B装满水---------------------
{
if (flagb==0&&flaga!=1)
{
waterb=N;
emptyb=0;
flagb=1;
oprec(3);
return;
}
else return;
}
void bputoff()//4 B水清空-----------------------
{
if (flagb==1&&flaga!=0)
{
waterb=0;
emptyb=N;
flagb=0;
oprec(4);
return;
}
else return;
}
void btoa()//5 B水倒进A-----------------------
{
if(flagb==0||flaga==1||waterb==emptya)
return;
else if(waterb<emptya)
{
watera=watera+waterb;
waterb=0;
emptyb=N;
flagb=0;
emptya=M-watera;
flaga=-1;
oprec(5);
return;
}
else if(waterb==emptya)
{
waterb=0;
emptyb=N;
flagb=0;
watera=M;
emptya=0;
flaga=1;
oprec(5);
return;
}
else {
waterb=waterb-emptya;
watera=M;
emptya=0;
flaga=1;
emptyb=N-waterb;
flagb=-1;
oprec(5);
return;
}
}
int _tmain(int argc, TCHAR* argv[], TCHAR* envp[])
{
................
if (!AfxWinInit(::GetModuleHandle(NULL), NULL, ::GetCommandLine(), 0))
{
...............
}
else
{
..............
int ofg;
srand(time(0));
do{
ofg=rand()%6;
switch(ofg)
{
case 0:aputin();break;
case 1:aputoff();break;
case 2:atob();break;
case 3:bputin();break;
case 4:bputoff();break;
case 5:btoa();break;
}
if (watera==K||waterb==K)
{
printf("成功步骤:");
for (int l=0;l<500;l++)
printf("%c",op[l]);
return nRetCode;
}
} while(i<500);
printf("无解");
}
return nRetCode;
}
基本思路是:
将A B两桶行为分别分解成3种:装满水 倒光水 倒进另一个桶
两个桶就是6个行为
程序模拟人的思路
随机作出有效行动
知道在500步内解答
500以外的认为是无解
解答有很多种 就是解有很多 暂时该程序无法得出最优解 除非自己手动运行N次 找出最少步骤解
比如7 4
1
可行步骤有3535
02420252525242420152520242 (0标示A装满水,具体看程序说明)
甚至353435
353434343435
就是重复步骤问题没有解决
[
本帖最后由 vandychan 于 2010-8-30 10:59 编辑 ]