泊松分酒问题

1、泊松分酒问题1. 问题描述 有一个酒瓶装八斤酒，没有量器，只有分别装五斤和三斤的空酒瓶。设计程序将八斤酒分为两个四斤，求出最少步骤。输入：问题无需输入。输出：输出最少步数或者最少步数下的倒酒过程。2. 问题的解决方法： 这个题目有许多方法，这里主要介绍两个方法，第一个方法是用纯数学知识解 决问题，第二个方法是采用广搜算法，去试各种情况。纯数学解决该问题方法原理：解决问题的一套规则：1. 大瓶子只能倒入中瓶子2. 中瓶子只能倒入小瓶子3. 小瓶子只能倒入大瓶子4. 小瓶子只有在已经装满的情况下才能倒入大瓶子5. 若小瓶子被倒空，则无论中瓶子是否满，应马上从中瓶子倒入小瓶子 之所以要规定倒酒的顺序

2、是为了防止状态重复。 而根据这 5 条规则，大瓶子每次 倒入中瓶子的酒总是 5 斤，小瓶子每次倒入大瓶子的酒总是 3 斤。（理解这句话， 理解这点很重要，下面会给出理论高度上的描述）上述解题方法的原理：设大，中，小三个瓶子容量分别是 C1, C2, C3,需要倒出的容量是R 则实际上要是我们能将容量为 R的酒倒到中瓶子和小瓶子中就可以了。设大瓶子 倒满中瓶子 X 次，从小瓶子中倒入大瓶子 Y 次。那么显然由大瓶子累次倒入中瓶 子和小瓶子总共C2*X的酒。而由小瓶子倒入大瓶子一共有 C3*丫的酒。那么最终， 小瓶子和中瓶子剩余的酒显然就是 C2*X - C3*Y因此，分酒问题实质上转化为下面的不

3、定方程是否有正整数解的问题：C2*X - C3*Y = R对于我们的问题，C1=8， C2=5， C3=3， R=4第一种倒酒规则实质上相当于解下面这个不定方程：5X - 3丫 = 4 （ 限定 X 0 ， 丫 0 ）最小整数解是 X=2， 丫= 2表示倒满 5斤的瓶子 2次， 3斤的瓶子倒空 2次那么 5 斤的瓶子和 3 斤的瓶子剩酒总量必然是 4 斤了，现在你明白为什么要规定 倒酒的顺序了吧。 小瓶子和中瓶子是一个系统， 而大瓶子又是另外一个系统， 大 瓶子的酒只能倒入中瓶子和小瓶子组成的系统， 小瓶子的酒只能倒出到大瓶子的 系统。我们关注的是由中瓶子和小瓶子组成的系统，这个系统每次增加都

4、是 5 斤（中瓶子容量），每次减少都是 3 斤（小瓶子容量）。另外，如果存在X和丫，使得下面的方程有解：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至U B 倒酒函数 void B_To_C();void C_To_A();int a = A;/初始状态int b = 0;int c = 0;int main()while(a !=

5、 A/2)/当没有分出A瓶容积一半时循环if(b=0)A_To_B();if(c=C)C_To_A();else if(b!=0)B_To_C();return 0;void A_To_B()b = aB?B：a;a -= b;printf(na-b:t a=%dtb=%dtc=%dt,a,b,c);void B_To_C()int n = c;c = b+cC?C:b+c;b -= c-n;printf(nb-c:t a=%dtb=%dtc=%dt,a,b,c);void C_To_A()a += c;c = 0;printf(nc-a:t a=%dtb=%dtc=%dt,a,b,c);算法

6、二：广搜算法实现：广搜算法最重要是解决好状态判重问题，而这个问题比较简单在于状态判重比 较简单，通过对二维数组的标记就可以实现判重。 其它部分则是按照广搜的一般 模式去写就行。#include#include struct Nodeint state3;/ 数组存下三个容器当前的酒的容量 ;Node curState; int num;int a96;Node open10000; int head,tail;int pour(int i,int j)/ 判断状态转移(即能否倒酒从一个容器到另一个) if(i = j) return 0;if(curState.statei=0)return

7、0;int empty = 0;if(i = 0)if(j = 1)empty = 5 - curState.statej; if(curState.statei empty) return curState.statei;else return empty;else if(j = 2)empty = 3 - curState.statej; if(curState.statei empty) return curState.statei; elsereturn empty;else if(i = 1)if(j = 0)empty = 8 - curState.statej; if(curSt

8、ate.statei empty) return curState.statei;elsereturn empty;else if(j = 2)empty = 3 - curState.statej; if(curState.statei empty) return curState.statei;else return empty;elseif(j = 0)empty = 8 - curState.statej; if(curState.statei empty) return curState.statei;elsereturn empty;else if(j = 1)empty = 5

9、- curState.statej; if(curState.statei empty) return curState.statei;elsereturn empty;void move(int i,int j,int n)curState.statei -=n;curState.statej +=n;int isAim(Node n)/ 判断是否为目标 if(n.state0=4)&(n.state1=4)&(n.state2=0) return 1;elsereturn 0;int hasExit()/ 判重函数，通过标记二维数组实现if(acurState.state0curState

10、.state1=1)return 1;else acurState.state0curState.state1=1; return 0;int emptyopen()if(head=tail)return 1;elsereturn 0;Node pop()Node u;if(head=tail) printf(errorn);u=openhead+;head=head%10000;return u;void push( Node u)opentail+=u; tail=tail%10000;void init()Node initState,node;initState.state0=8;in

11、itState.state1=0;initState.state2=0;head=0;tail=1;node.state0=-1;/ 加入队列负数进行计数标记，为了输出最少步数 node.state1=-1;node.state2=-1;open0=initState;open1=node;tail+;int main()int i,j,n;init();Node temp,node;：0 ujn；8j 9|!MMjO pua/ esp jo pua/ (+!匸0=!)0打0 pua/(+比0二Doj jo pua/)! P pua/n o)L|s nd 伽!xo !(|/8S8pou-,11up%11)uijd(21S