泊松分酒问题.docx

泊松分酒问题

有一个酒瓶装八斤酒,没有量器,只有分别装五斤和三斤的空酒瓶。设计程序
将八斤酒分为两个四斤,求出最少步骤。
输入:
问题无需输入。
输出:
输出最少步数或者最少步数下的倒酒过程。
:
这个题目有许多方法,这里主要介绍两个方法,第一个方法是用纯数学知识解
决问题,第二个方法是采用广搜算法,去试各种情况。
纯数学解决该问题方法原理:
解决问题的一套规则:
1. 大瓶子只能倒入中瓶子
2. 中瓶子只能倒入小瓶子
3. 小瓶子只能倒入大瓶子
4. 小瓶子只有在已经装满的情况下才能倒入大瓶子
5. 若小瓶子被倒空,则无论中瓶子是否满,应马上从中瓶子倒入小瓶子
(
之所以要规定倒酒的顺序是为了防止状态重复。 而根据这 5 条规则, 大瓶子每次
倒入中瓶子的酒总是 5 斤,小瓶子每次倒入大瓶子的酒总是 3 斤。 理解这句话,
理解这点很重要,下面会给出理论高度上的描述)
上述解题方法的原理:
设大,中,小三个瓶子容量分别是 C1,C2, C3,需要倒出的容量是 R
则实际上要是我们能将容量为 R 的酒倒到中瓶子和小瓶子中就可以了。 设大瓶子
倒满中瓶子 X 次,从小瓶子中倒入大瓶子 Y 次。那么显然由大瓶子累次倒入中瓶
子和小瓶子总共 C2*X的酒。而由小瓶子倒入大瓶子一共有 C3*Y的酒。那么最终,
小瓶子和中瓶子剩余的酒显然就是 C2*X - C3*Y
因此,分酒问题实质上转化为下面的不定方程是否有正整数解的问题:
C2*X - C3*Y = R
对于我们的问题,
C1=8,C2=5,C3=3,R=4
第一种倒酒规则实质上相当于解下面这个不定方程:
5X - 3Y = 4 ( 限定 X > 0 ,Y > 0 )
最小整数解是 X=2,Y= 2
表示倒满 5 斤的瓶子 2 次, 3 斤的瓶子倒空 2 次
那么 5 斤的瓶子和 3 斤的瓶子剩酒总量必然是 4 斤了,现在你明白为什么要规定
倒酒的顺序了吧。 小瓶子和中瓶子是一个系统, 而大瓶子又是另外一个系统, 大
瓶子的酒只能倒入中瓶子和小瓶子组成的系统, 小瓶子的酒只能倒出到大瓶子的
系统。我们关注的是由中瓶子和小瓶子组成的系统,这个系统每次增加都是 5
斤(中瓶子容量),每次减少都是 3 斤(小瓶子容量)。
另外,如果存在 X 和 Y,使得下面的方程有解:
C2*X - C3*Y = 1
实质上就是说能够倒出 1 斤的酒,那么任意斤的酒都能倒出了。
因为 : (C2*X - C3*Y)*N = N
根据不定方程写出分酒问题代码如下:
#include<>
#include<>
#define A 8
#define B 5
#define C 3
void A_To_B();//A 到 B 倒酒函数
void B_To_C();
void C_To_A();
int a = A;// 初始状态
int b = 0;
int c = 0;
int main()
{
while(a != A/2)// 当没有分出 A 瓶容积一半时循环
{
if(b==0)
A_To_B();
if(c==C)
C_To_A();