分油問題C語言

1、.設有大小不等的 X，Y，Z 三個無刻度的油桶，分別能夠盛滿油 X， Y，Z(例如， X=8 ，Y=5 ， Z=3)，并約定 X YZ 。初始時，僅 X 油桶盛滿油， Y 和 Z 油桶為空。要求程序尋找一種最少的分油步聚，在某個油桶中分出 T 升油 (例如 T=4) 。解：令三個油桶的盛油情況為倒油過程的狀態(tài)， 則倒油過程就是狀態(tài)變化的過程。 為了記錄倒油過程，程序引入倒油狀態(tài)隊列 ,將倒油過程中產生的狀態(tài)存儲在隊列中。 隊列的每個元素記錄每次分油后各個油桶的分油后各個油桶的盛油量和倒油軌跡等有關信息。程序反復從隊列中取出第一個還未檢查過的狀態(tài)， 對該狀態(tài)下的每個油桶判斷其是否可以倒出油，及是

2、否可以倒進油。由于油桶沒有刻度，分油時只能將某個油桶倒?jié)M或倒空。 程序分別按倒空或倒?jié)M兩種可能的倒油動作執(zhí)行不同的處理，產生新的倒油狀態(tài)，為避免某個倒油狀態(tài)在隊列中重復出現(xiàn)， 程序只將未曾出現(xiàn)過的新狀態(tài)及其倒油軌跡信息存入隊列中，假定程序檢查了相當多的狀態(tài)后，或能找到解，或能確定問題無解。倒油程序算法如下：算法 -無刻度油桶分油輸入各桶容量和目標容量；將初始狀態(tài)存入倒油狀態(tài)隊列；設置其它初始值；do對狀態(tài)隊列中第一個還未檢查的元素在還未檢查完每個倒出的桶且還未找到解且還未確定無解情況下循環(huán)if(倒出桶有油 )在還未檢查完每個桶且還未找到解且還未確定無解情況下循環(huán)if(當前桶不是倒出桶且桶還有空

3、 )確定本次倒油量；在隊列中檢查倒油后的結果狀態(tài)是否在隊列中出現(xiàn)；if(結果狀態(tài)不在隊列中出現(xiàn))將結果狀態(tài)和軌跡信息存入隊列；if(有桶中的油達到目標容量).設置找到解標志；if(還未找到解 )修正隊列第一個還未檢查過的元素指針；if(隊列中的元素都已檢查過)設置無解標志；while( 還未找到解且還未確定無解)；if(找到解 )根據倒油步聚的軌跡信息，形成倒油步聚序列；輸出倒油步聚序列；倒油隊列中的元素應包含下列信息：各桶的盛油量，該狀態(tài)是從哪一個桶(源桶 )倒向哪一個桶 (目標桶 )而形成的，形成該狀態(tài)的元素在隊列中的位置。根據以上算法編寫如下程序。程序代碼如下：#include#defi

4、ne N 100#define BUCKETS 3struct eleint stateBUCKETS; /* 各桶盛油量 */int sbucket; /* 源桶 */int obucket; /* 目標桶 */int last; /* 軌跡元素在隊列中的下標*/qN; /* 隊列 */int fullBUCKETS;int i,j,k,found,unable,wi,wj,v,targ;int head,tail;void main()/*輸入各桶容量和目標容量*/printf(Enter volume of buckets. );.for(i=0;ifull1full2, 相應代碼在此

5、*/printf(Enter volume of targ. );scanf(%d,&targ); /* 檢查 targ=full0 的代碼在此 */*設置將初始狀態(tài)存入倒油狀態(tài)隊列等初值*/q0.state0=full0;for(i=1;iBUCKETS;i+)q0.statei=0;q0.sbucket=0;q0.obucket=0;q0.last=0;found=unable=0;head=tail=0;do/*對狀態(tài)隊列中第一個還未檢查過的元素在還未檢查完每個倒出的桶且還未找到解且還未確定無解情況下循環(huán)*/for(i=0;i0) /* 倒出桶有油 */*在還未檢查完每個油桶且還未找到解

6、且還未確定無解情況下循環(huán)*/for(j=0;jBUCKETS&!found&!unable;j+)if(j!=i&qhead.statejfullj-qhead.statej) v=fullj-qhead.statej;else v=qhead.statei; wi=qhead.statei-v;wj=qhead.statej+v;/*在隊列中檢查倒油后的結果狀態(tài)是否在隊列中出現(xiàn)*/for(k=0;ktail) /* 結果狀態(tài)不在隊列中出現(xiàn)*/*將結果狀態(tài)和軌跡信息存入隊列*/.tail+;qtail.statei=wi;qtail.statej=wj;qtail.state3-i-j=qhe

7、ad.state3-i-j;qtail.sbucket=i+1;qtail.obucket=j+1;qtail.last=head;/*如有桶達到目標盛油量，則設置找到解標志*/if(wi=targ|wj=targ)found=1;if(!found) /* 還未找到解 */head+; /* 修正隊列第一個還未檢查過元素指針 */ if(headtail) /* 隊列中的元素都已檢查過 */ unable=1; /* 設置無解標志 */while(!found&!unable); /*還未找到解且還未確定無解*/if(found) /* 找到解 */*根據倒油步聚的軌跡信息，形成倒油步聚序列

8、 */ i=tail;j=-1;do /* 原倒油步聚逆向鏈接，現(xiàn)改為正向鏈接*/k=qi.last;qi.last=j;j=i;i=k;while(j);/*輸出倒油步聚序列 */for(k=qk.last;k=0;k=qk.last)printf(%5d to %2d:,qk.sbucket,qk.obucket);for(i=0;ib-c-a并且必須符合如下規(guī)則：1.b(5 斤桶 )倒空后才能從a(8 斤桶 )中取油。2c(3 斤桶 )盛滿后才能向a(8 斤捅 )中倒油。我們設從 a 中往 b 倒油 x 次，從 c 往 a 倒油 y 次，那么最后 a 中剩下的油應該為 8-5x+3y 斤

9、，按照題意，我們得到如下方程，8-5x+3y=4 ：我們?yōu)榱说玫竭@個方程的解，應按照上述的倒油規(guī)則不斷的倒下去，直到 a 中或 b 中油的重量為 4 斤為止，另外也可以改變倒油的規(guī)則， 看能否找到最好的倒油步聚。代碼：#includeint i;main()int a,y,z;printf(Input Full a ,Empty b,c,Get i:); /*讀入 3 個容器的容量和最后需要的數(shù)量 */scanf(%d%d%d,&a,&y,&z,&i);getti(a,y,z);getti(int a,int y,int z)int b=0,c=0;/*b,c 為二個容器的實際重量 */printf(a%d b%d c%d %4d%4d%4d ,a,y,z,a,b,c);while(a!=i|b!=i)/*如果滿足要求退出循環(huán) */if(!b)/*如果 b 為空，從 a 往 b 倒油 */ a-=y;b=y;.else if(c=z)a+=z;c=0/*如果 c 已滿，從 c 往 a 倒油 */else if(bz-c)b-=(z-c);c=z;/*如果 b 的重量大于 c 的剩余重量，