泊松分酒算法设计论文.doc

塔里木大学信息工程学院课程论文
一．案例提出 2

二．模拟设计 2

三．编程实现 3

四．结果分析 5

六．心得体会 5

七．参考文献 6

正文
一．案例提出
法国数学家泊松曾提出以下分酒趣题：某人有一瓶12品脱（容量单位）的酒，同时有容积为5品脱的空杯各一个。借助这两个空杯，如何将这瓶12品脱的酒平分？
我们要解决一般的平分酒案例：借助容量分别为bv与cv的两个空杯，用最少的分倒次数把总容量为偶数a的酒平分。这里正整数bv,cv与偶数a均从键盘输入。

二．模拟设计
求解一般的“泊松分酒”问题：借助容积分别为整数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);
我们模拟下面两个方向的分倒操作：
（1） 按A->B->C顺序分倒操作
1> 当B杯空（b=0）时，从A瓶倒满B杯。
2> 从B杯分一次或多次倒满C杯。
若b>cv-c,倒满C杯，操作3>
若b<=cv-c,倒空B杯，操作1>
3> 当C杯满（c=cv）时，从C杯倒回A瓶。
分倒操作中，用变量n 统计分倒次数，每分倒一次，n 增1.
若b=0且a<bv时，步骤1>无法实现（即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;}
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);
}
(2) 按A->C->B顺序分倒操作
这一循环操作与（1）实质上是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）。此时调用实施函数Practice(a,bv,cv)。
若m1<0,只能按上述（2）操作；若0<m2<m1,按上述（2）操作分倒次数较少（即m2）。此时调用实施函数Practice(a,cv,bv)。
实施函数打印整个模拟分倒操作进程中的a,b,c的值。最后打印出最少的分倒次数。
三．编程实现

#include<stdio.h>
void practice(int,int,int);
int i,n,probo(int,int,int);
void main()
{
int a,bv,cv,m1,m2;
printf("\n请输入酒总量(偶数):");
scanf("%d",&a);
printf("两空杯容量bv,cv分别为:");
scanf("%d,%d",&bv,&cv);
i=a/2;
if(bv+cv<i)
{ printf("空杯容量太小，无法平分！\n");
return;
}
m1=probo(a,bv,cv);
m2=probo(a,cv,bv);
if(m1<0 && m2<0)
{ printf("无法平分！\n");
return;
}
if(m1>0 && (m2<0 || m1<=m2))
{ n=m1;practice(a,bv,cv);}
else
{ n=m2;practice(a,cv,bv);}
}
void practice(int a,int bv,int 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(int a,int bv,int 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);
}
四．结果分析

当输入酒总量：12，两空杯容量为5,8时，程序运行结果如上图所示。
五．程序改进
以上程序中，对m1和m2的全路径判断虽然可以获得分倒次数较少的方法，但这是建立在程序有解的前提之下，而程序有没有解并不能通过对m1,m2的全路径判断已完全确定。例如，当输入a=10,nv=4,cv=6时，显然没有解，这时程序进入死循环。那输入的数据在满足什么条件下才有解呢?
令d=gcd(bv,cv)表示bv与cv的最大公约数，且满足基本条件：bv+cv>=(a/2)时，可以证明，当mod(a/2,d)=0时，所输入的数据一定有解。特别当bv与cv互质时，a为任何偶数都有解。
六．心得体会
泊松分酒是个很有趣的案例，而计算机可以无限推演，因此，可以设计一个算法将泊松分酒实现。而将泊松分酒案例实现，就需要运用模拟的思想。每当程序出现某个问题时，进行细心的调试让我获益良多。泊松分酒的实现让我对模拟思想有了更深的认识，更让我从另一个方面感受到了解决泊松分酒的乐趣。
七．参考文献
《c primer plus》
《c 算法》
《高质量c编程指南》
《c语言核心技术》
《C语言深度剖析》
第 6 页 共 6 页