模拟(泊松分酒).doc

泊松分酒
法国数学家泊松（Poisson）曾提出以下分酒趣题：某人有一瓶12品脱（容量单位）的酒，同时有容积为5品脱与8品脱的空杯各一个。借助这两个空杯，如何将这瓶12品脱的酒平分？
我们要解决一般的平分问题：借助容量分别为bv与cv（单位为整数）的两个空杯，用最少的分倒次数把容量为偶数a的酒平分。这里正整数bv，cv与偶数a均从键盘输入。
1. 模拟算法设计
求解一般的“泊松分酒”问题：借助容积分别为整数bv，cv的两个空杯，用最少的分倒次数把总量为偶数a 的酒（并未要求满瓶）平分，采用直接模拟平分过程的分倒操作。
为了把键盘输入的偶数a通过分倒次数操作平分为两个i：i=a/2（i为全局变量），设在分倒过程中：
瓶A中的酒量为a，（0≤a≤2*i）；
杯B（容积为bv）中的酒量为b，（0≤b≤bv）；
杯C（容积为cv）中的酒量为c，（0≤c≤cv ）；
我们模拟下面两种循环分倒操作：
⑴ 按AàBàC顺序操作
① 当B杯空（b=0）时，从A瓶倒满B杯。
② 从B杯分一次或多次倒满C杯。
b>cv-c，倒满C杯，操作③
b≤cv-c，倒空B杯，操作①
③ 当C杯满（c=cv）时，从C杯倒回A瓶。
分倒操作中，用变量n统计分倒次数，每分倒一次，n增1。
若b=0且a<bv时，步骤①无法实现(即A瓶的酒倒不满B杯)而中断，记n=-1为中断标志。
分倒操作中若有a=i或b=i或c=i时，显然已达到平分目的，分倒循环结束，用试验函数Probe（a,bv,cv）返回分倒次数n的值。否则，继续循环操作。
模拟操作描述：
while (!(a==i||b=i||c=i))
{ if (!b){ a-=bv;b=bv;} 从A瓶倒满B杯
else if (c=cv) { a+=cv;c=0;} 从C杯倒回A瓶
else if (b>cv-c) {b-=(cv-c);c=cv;} 从B倒满C杯
else { c+=b;b=0;} 从B倒C，倒空B杯
printf(“%6d%6d%6d\n”,a,b,c);
}
⑵ 按AàCàB顺序操作
这一循环操作与⑴实质上是C与B杯互换，相当于返回函数值Probe(a,cv,bv)。
试验函数Probe()的引入是巧妙的，可综合摸拟以上两种分倒操作避免了关于cv与bv大小关系的讨论。
同时设计实施函数Practice(a,bv,cv)，与试验函数相比较，把n增1操作改变为输出中间过程量a、b、c，以标明具体分倒操作进程。
在主函数main()中，分别输入a、bv、cv的值后，为寻求较少的分倒次数，调用试验函数并比较m1=Probe(a,bv,cv)与m2=Probe(a,cv,bv)；
若m1<0或m2<0，表明无法平分（均为中断标志）。
若m2<0，只能按上述（1）操作；若0<m1<m2，按上述（1）操作分倒次数较少（即m1）。此时调用实施函数Practivce(a,bv,cv)。
若m1<0，只能按上述（2）操作；若0<m2<m1，按上述（2）操作分倒次数较少（即m2）。此时调用实施函数Practice(a,cv,bv)。
实施函数打印整个模拟分倒操作进程中的a、b、c。最后打印出最少的分倒次数。
2. 泊松分酒的C程序实现
/*泊松分酒模拟操作*/
int i,n;
#include<stdio.h>
void main()
{ int a,bv,cv,m1,m2;
printf(“\n请输入酒总量（偶数）；”);
scanf(“%d”,&a);
printf(“两空杯容量bv,cv分别为：”);
scanf(“%d,%d”,&bv,&cv);
i=a/2;m1=probo(a,bv,cv);m2=probo(a,cv,bv);
if (m1<0 && m2<0 )
printf(“无法平分！”);
if ( m1>0 && (m2<0 || m1<m2))
{ n=m1;practice(a,bv,cv);}
if (m2>0 && (m1<0 || m2<m1))
{ n=m2,practice(a,cv,bv);}
}
#include <stdio.h>
practice(a,bv.cv) /*模拟实施函数*/
int a,bv,cv;
{ int b=0,c=0;
printf(“平分酒的分法：\n”);
printf(“酒瓶%d空杯%d空杯%d\n”,a,bv,cv);
printf(“%6d%6d%6d\n”,a,b,c);
while (!(a==i||b==i||c==i))
{ if (!b) { a-=bv;b=bv;}
else if ( c==cv) { a+=cv;c=0;}
else if (b>cv-c) { b-=(cv-c);c=cv;}
else { c+=b;b=0;}
printf(“%6d%6d%6d\n”,a,b,c);
}
printf(“平分酒共分倒%d次.\n”,n);
}
int probo(a,bv,cv) /*试验函数*/
int a,bv,cv;
{ int n=0,b=0,c=0;
while (!(a==i||b==i||c==i))
{ if (!b)
if (a<bv) { n=-1;break;}
else { a-=bv;b=bv;}
else if (c==cv) { a+=cv;c=0;}
else if (b>cv-c){ b-=(cv-c);c=cv;}
else {c+=b;b=0;}
n++;
}
return(n);
}
3. 程序运行示例
请输入酒总量（偶数）：12
两空杯容量bv,cv分别为：5，8
平分酒的分法：
酒瓶12 空杯8 空杯5
12 0 0
4 8 0
4 3 5
9 3 0
9 0 3
1 8 3
1 6 5
平分酒共分倒6次。
请输入酒总量（偶数）：20
两空杯容量bv,cv分别为：12，7
平分酒的分法：
酒瓶20空杯12空杯7
20 0 0
8 12 0
8 5 7
15 5 0
15 0 5
3 12 5
3 10 7
平分酒共分倒6次。