c语言程序设计：分酒问题某人有12品脱的酒一瓶，想从中倒出6品脱.....

Question

某人有12品脱的酒一瓶，想从中倒出6品脱，但他没有6品脱的容器，仅有一个8品脱和5品脱的容器，设计一个程序输出每一步的分法将啤酒分为两个6品脱。
最好把你的算法先简略说一下。

最好把你的算法先用语言简略描述一下。

Answer 1

给，
详细的算法分析，以及源代码和注释：

问题分析与算法设计
将12品脱酒 8品脱和5品脱的空瓶平分，可以抽象为解不定方程：
8x-5y=6
其意义是：从12品脱的瓶中向8品脱的瓶中倒x次，并且将5品脱瓶中的酒向12品脱的瓶中倒y次，最后在12品脱的瓶

中剩余6品脱的酒。
用a,b,c代表12品脱、8品脱和5品脱的瓶子，求出不定方程的整数解，按照不定方程的意义则倒法为：
a -> b -> c ->a
x y
倒酒的规则如下：
1) 按a -> b -> c ->a的顺序；
2) b倒空后才能从a中取
3) c装满后才能向a中倒
按以上规则可以编写出程序如下：
*程序与程序注释
#include<stdio.h>
void getti(int a,int y,int z);
int i; /*最后需要分出的重量*/
void main()
{
int a,y,z;
printf("input Full a,Empty b,c,Get i:"); /*a 满瓶的容量 y:第一个空瓶的容量 z:第二个空瓶的容量*/
scanf("%d,%d,%d,%d",&a,&y,&z,&i);
getti(a,y,z); /*按a -> y -> z -> a的操作步骤*/
getti(a,z,y); /*按a -> z -> y -> a的步骤*/
}
void getti(int a,int y,int z) /*a:满瓶的容量 y:第一个空瓶的容量 z:第二个空瓶的容量*/
{
int b=0,c=0; /* b:第一瓶实际的重量 c:第二瓶实际的重量*/
printf(" a%d b%d c%d\n %4d%4d%4d\n",a,y,z,a,b,c);
while(a!=i||b!=i&&c!=i) /*当满瓶!=i或另两瓶都!=i*/
{
if(!b)
{ a-=y; b=y;} /*如果第一瓶为空，则将满瓶倒入第一瓶中*/
else if(c==z)
{ a+=z; c=0;} /*如果第二瓶满，则将第二瓶倒入满瓶中*/
else if(b>z-c) /*如果第一瓶的重量>第二瓶的剩余空间*/
{ b-=(z-c);c=z;} /*则将装满第二瓶，第一瓶中保留剩余部分*/
else{ c+=b; b=0;} /*否则，将第一瓶全部倒入第二瓶中*/
printf(" %4d %4d %4d\n",a,b,c);
}
}

Answer 2

用状态空间描述：
假设一个状态 (x, y, z)，代表当前三个容器(酒瓶、8品脱容器和5品脱容器)
那么明显有 x + y + z = 12
目标状态是 x = 6 或 y = 6
而出时状态为 (12, 0, 0)
每次，都可以考虑从 x 倒向 y，从 y 倒向 x，等，共六种转移操作。
然后在这个状态空间中进行广度优先搜索即可得到解。。
加到 150 分帮你写完所有代码。。

Answer 3

#include <iostream>
using namespace std;

int V[3]={12,8,5};
int src[6] ={0,0,1,1,2,2};
int dest[6]={1,2,0,2,0,1};
int record[100][3];
int rec_index=0;

void Pour(int state[],int a,int b)
{
int r=V[b]-state[b];
if(state[a]<r) {state[b]+=state[a];state[a]=0;}
else {state[b]=V[b];state[a]-=r;}
}

void Output()
{
printf(" A B C\n");
for(int i=0;i<rec_index;++i)
printf("%4d %4d %4d\n",record[i][0],record[i][1],record[i][2]);
printf("\n\n");
}

void Record(int state[])
{
record[rec_index][0]=state[0];
record[rec_index][1]=state[1];
record[rec_index][2]=state[2];
++rec_index;
}

bool Exist(int state[])
{
for(int i=0;i<rec_index;++i)
if (state[0]==record[i][0]
&& state[1]==record[i][1]
&& state[2]==record[i][2])
return true;
return false;
}

void Solve(int state[])
{

int a=state[0],b=state[1],c=state[2];
Record(state);
if(a==6 && b==6 && c==0) {Output();return;}
for(int i=0;i<6;++i)
{
if(state[src[i]]==0) continue;
Pour(state,src[i],dest[i]);
if(!Exist(state))
{
Solve(state);
--rec_index;
}
state[0]=a;state[1]=b;state[2]=c;
}
}

int main()
{
int init[3]={12,0,0};
Solve(init);
return 0;
}

参考资料：本人原创

本回答被提问者采纳