泊松分酒算法設(shè)計(jì)論文

塔里木大學(xué)信息工程學(xué)院課程論文第3頁共6頁一．案例提出 2二．模擬設(shè)計(jì) 2三．編程實(shí)現(xiàn) 3四．結(jié)果分析 5六．心得體會(huì) 5七．參考文獻(xiàn) 6正文一．案例提出法國(guó)數(shù)學(xué)家泊松曾提出以下分酒趣題：某人有一瓶12品脫（容量單位）的酒，同時(shí)有容積為5品脫的空杯各一個(gè)。借助這兩個(gè)空杯，如何將這瓶12品脫的酒平分？我們要解決一般的平分酒案例：借助容量分別為bv與cv的兩個(gè)空杯，用最少的分倒次數(shù)把總?cè)萘繛榕紨?shù)a的酒平分。這里正整數(shù)bv,cv與偶數(shù)a均從鍵盤輸入。二．模擬設(shè)計(jì)求解一般的“泊松分酒”問題：借助容積分別為整數(shù)bv,cv的兩個(gè)空杯，用最少的分倒次數(shù)把總?cè)萘繛榕紨?shù)a的酒（并未要求滿瓶）平分，采用直接模擬平分過程的分倒操作。為了把鍵盤輸入的偶數(shù)a通過分倒操作平分為兩個(gè)i:i=a/2(i為全局變量)，設(shè)在分倒過程中：瓶A中的酒量為a，（0<=a<=2*i）;杯B(容積為bv)中的酒量為b，（0<=b<=bv）;杯C(容積為cv)中的酒量為c,(0<=c<=cv);我們模擬下面兩個(gè)方向的分倒操作：按A->B->C順序分倒操作當(dāng)B杯空（b=0）時(shí)，從A瓶倒?jié)MB杯。從B杯分一次或多次倒?jié)MC杯。若b>cv-c,倒?jié)MC杯，操作3>若b<=cv-c,倒空B杯，操作1>當(dāng)C杯滿（c=cv）時(shí)，從C杯倒回A瓶。分倒操作中，用變量n統(tǒng)計(jì)分倒次數(shù)，每分倒一次，n增1.若b=0且a<bv時(shí)，步驟1>無法實(shí)現(xiàn)（即A瓶的酒不滿B杯）而中斷，記n=-1為中斷標(biāo)志。分倒操作中若有a=i或b=i或c=i時(shí)，顯然已達(dá)到平分目的，分倒循還結(jié)束，用實(shí)驗(yàn)函數(shù)Probe(a,bv,cv)返回分倒次數(shù)n的值。否則，繼續(xù)循環(huán)操作。模擬操作描述： while(!(a==i||b==i||c==i)) { if(!b){a-=bv;b=bv;} elseif(c==cv){a+=cv;c=0;} elseif(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順序分倒操作這一循環(huán)操作與（1）實(shí)質(zhì)上是C與B杯互換，相當(dāng)于返回函數(shù)值Probe(a,cv,bv)。試驗(yàn)函數(shù)Probe()的引入是巧妙的，可綜合模擬以上兩種分倒操作避免了關(guān)于cv與bv大小關(guān)系的討論。同時(shí)設(shè)計(jì)實(shí)施函數(shù)Practice(a,bv,cv),與試驗(yàn)函數(shù)相比較，把n增1操作改變?yōu)檩敵鲋虚g過程量a,b,c，以標(biāo)明具體操作進(jìn)程。在主函數(shù)main()中，分別輸入a,bv,cv的值后，為尋求較少的分倒次數(shù)，調(diào)用試驗(yàn)函數(shù)并比較m1=Probe(a,bv,cv)與(m2=Probe(a,cv,bv)。若m1<0且m2<0，表明無法平分（均為中斷標(biāo)志）。若m2<0,只能按上述（1）操作；若0<m1<m2,按上述（1）操作分倒次數(shù)較少（即m1）。此時(shí)調(diào)用實(shí)施函數(shù)Practice(a,bv,cv)。若m1<0,只能按上述（2）操作；若0<m2<m1,按上述（2）操作分倒次數(shù)較少（即m2）。此時(shí)調(diào)用實(shí)施函數(shù)Practice(a,cv,bv)。實(shí)施函數(shù)打印整個(gè)模擬分倒操作進(jìn)程中的a,b,c的值。最后打印出最少的分倒次數(shù)。三．編程實(shí)現(xiàn)#include<stdio.h>voidpractice(int,int,int);inti,n,probo(int,int,int);voidmain(){ inta,bv,cv,m1,m2; printf("\n請(qǐng)輸入酒總量(偶數(shù)):"); 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);}}voidpractice(inta,intbv,intcv){ intb=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;} elseif(c==cv){a+=cv;c=0;} elseif(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);}intprobo(inta,intbv,intcv){ intn=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;} elseif(c==cv){a+=cv;c=0;} elseif(b>cv-c){b-=(cv-c);c=cv;} else{c+=b;b=0;} n++; } return(n);}四．結(jié)果分析當(dāng)輸入酒總量：12，兩空杯容量為5,8時(shí)，程序運(yùn)行結(jié)果如上圖所示。五．程序改進(jìn)以上程序中，對(duì)m1和m2的全路徑判斷雖然可以獲得分倒次數(shù)較少的方法，但這是建立在程序有解的前提之下，而程序有沒有解并不能通過對(duì)m1,m2的全路徑判斷已完全確定。例如，當(dāng)輸入a=10,nv=4,cv=6時(shí)，顯然沒有解，這時(shí)程序進(jìn)入死循環(huán)。那輸入的數(shù)據(jù)在滿足什么條件下才有解呢?令d=gcd(bv,cv)表示bv與cv的最大公約數(shù)，且滿足基本條件：bv+cv>=(a/2)時(shí)，可以證明，當(dāng)mod(a/2,d)=0時(shí)，所輸入的數(shù)據(jù)一定有解。特別當(dāng)bv與cv互質(zhì)時(shí)，a為任何偶數(shù)都有解。六．心得體會(huì)泊松分酒是個(gè)很有趣的案例，而計(jì)算機(jī)可以無限推演，因此，可以設(shè)計(jì)一個(gè)算法將泊松分酒實(shí)現(xiàn)。而將泊松分