回复 22楼 beyondyf
你的代码我还是没看懂，不过我看一个多月的书。再回头看这道题，自己写了一个。利用递归函数做的。有时间指点一下阿。WaterNext()函数如果用数组加循环应该可以替代6种方案挨个写出来。但是效率好像是一样的。
我觉的用栈应该也能替代递归函数，其实到最后就是建立一个树，树的叶子结点都是（6，6，0）。但是我不知道我这么做是不是效率不高？
#include <stdio.h>
#include <stdlib.h>
typedef struct
{
int a,b,c;
}water; /* 定义结构体，a,b,c分别表示三瓶水的存水量 */
water visited[400]; /* 储存到水方法 */
int count=0; /* 储存到水次数 */
int sum=0; /* 储存方法数 */
int minicount=100; /* 最优方法到水次数 */
water mini[100]; /* 最优方法到水方案 */
void WaterNext(w);
void pfv() /* 打印到水方法，并且选出最优方案 */
{
int i;
sum++;
printf("方法%d: ",sum);
for(i=0;i<count;i++)
printf("(%d,%d,%d) ",visited[i].a,visited[i].b,visited[i].c);
printf("\n*************\n");
if (count<minicount) /* 比较选出最优方案 */
{
for(i=0;i<count;i++)
{
mini[i]=visited[i];
}
minicount=count;
}
}
void water_check(int *a,int *b,int *c,water w) /* 到水方式的判断 */
{
int i,flog=1;
if (*a==6 && *b==6) /* a，b存数量为6，此方案成功 */
{
visited[count].a=*a;
visited[count].b=*b;
visited[count].c=*c;
count++;
pfv();
count--;
}
else
{
for(i=0;i<count;i++)
if (*a==visited[i].a && *b==visited[i].b ) /* 检查次到水方式是否已经被使用 */
{
flog=0;
break;
}
if (flog!=0) /* 没有使用，记录此方式，进入下一层到水程序 */
{
visited[count++]=w;
WaterNext(*a,*b,*c);
}
else
{
flog=1;
}
}
*a=w.a; /* 恢复3个瓶子水量，尝试同一层其他到水方式 */
*b=w.b;
*c=w.c;
}
void WaterNext(water w)
{
int a,b,c;
a=w.a;
b=w.b;
c=w.c;
if(a!=0) /* 每次分别检查3个瓶子可能的6种到水方式 */
{
if(b!=8)
{
if(a>(8-b))
{
a=a-(8-b);
b=8;
}
else
{
b=a+b;
a=0;
}
water_check(&a,&b,&c,w); /* 判断此种到水方式如何处理 */
}
if(c!=5)
{
if(a>(5-c))
{
a=a-(5-c);
c=5;
}
else
{
c=a+c;
a=0;
}
water_check(&a,&b,&c,w);
}
}
if(b!=0)
{
if(a!=12)
{
if(b>(12-a))
{
b=b-(12-a);
a=12;
}
else
{
a=a+b;
b=0;
}
water_check(&a,&b,&c,w);
}
if (c!=5)
{
if(b>(5-c))
{
b=b-(5-c);
c=5;
}
else
{
c=b+c;
b=0;
}
water_check(&a,&b,&c,w);
}
}
if(c!=0)
{
if (b!=8)
{
if(c>(8-b))
{
c=c-(8-b);
b=8;
}
else
{
b=c+b;
c=0;
}
water_check(&a,&b,&c,w);
}
if (a!=12)
{
if(c>(12-a))
{
c=c-(12-a);
a=12;
}
else
{
a=a+c;
c=0;
}
water_check(&a,&b,&c,w);
}
}
count--;
return;
}
void main()
{
int i;
water w1;
w1.a=12;
w1.b=0;
w1.c=0;
printf("开始！\n");
WaterNext(w1);
printf("\n共%d种方法，最短的是%d步：\n",sum,minicount);
for(i=0;i<minicount;i++)
printf("(%d,%d,%d) ",mini[i].a,mini[i].b,mini[i].c);
printf("\n");
}
