C程序設計例解(07)

2019-11-17 05:40:49

字體：大中小

來源：轉載

供稿：網(wǎng)友

06.設有大小不等的X，Y，Z三個無刻度的油桶，分別能夠盛滿油X，Y，Z(例如，X=80，Y=50，Z=30)，并約定X>Y>Z。初始時，僅X油桶盛滿油，Y和Z油桶為空。要求程序?qū)ふ乙环N最少的分油步聚，在某個油桶中分出T升油(例如T=40)。
解：
    令三個油桶的盛油情況為倒油過程的狀態(tài)，則倒油過程就是狀態(tài)變化的過程。為了記錄倒油過程，程序引入倒油狀態(tài)隊列，將倒油過程中產(chǎn)生的狀態(tài)存儲在隊列中。隊列的每個元素記錄每次分油后各個油桶的分油后各個油桶的盛油量和倒油軌跡等有關信息。程序反復從隊列中取出第一個還未檢查過的狀態(tài)，對該狀態(tài)下的每個油桶判定其是否可以倒出油，及是否可以倒進油。由于油桶沒有刻度，分油時只能將某個油桶倒?jié)M或倒空。程序分別按倒空或倒?jié)M兩種可能的倒油動作執(zhí)行不同的處理，產(chǎn)生新的倒油狀態(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(當前桶不是倒出桶且桶還有空)
                {
                    確定本次倒油量；
                    在隊列中檢查倒油后的結果狀態(tài)是否在隊列中出現(xiàn)；
                    if(結果狀態(tài)不在隊列中出現(xiàn))
                    {
                        將結果狀態(tài)和軌跡信息存入隊列；
                        if(有桶中的油達到目標容量)
                            設置找到解標志；
                    }
                }
        if(還未找到解)
        {
            修正隊列第一個還未檢查過的元素指針；
            if(隊列中的元素都已檢查過)
                設置無解標志；
        }
    }while(還未找到解且還未確定無解)；
    if(找到解)
    {
        根據(jù)倒油步聚的軌跡信息，形成倒油步聚序列；
        輸出倒油步聚序列；
    }
}
倒油隊列中的元素應包含下列信息：各桶的盛油量，該狀態(tài)是從哪一個桶(源桶)倒向哪一個桶(目標桶)而形成的，形成該狀態(tài)的元素在隊列中的位置。根據(jù)以上算法編寫如下程序。

程序代碼如下：
#include<stdio.h>
#define N 100
#define BUCKETS 3
struct ele{
    int state[BUCKETS];        /*各桶盛油量*/
    int sbucket;               /*源桶*/
    int obucket;               /*目標桶*/
    int last;                  /*軌跡元素在隊列中的下標*/
}q[N];            /*隊列*/
int full[BUCKETS];
int i,j,k,found,unable,wi,wj,v,targ;
int head,tail;
void main()
{
    /*輸入各桶容量和目標容量*/
        for(i=0;i<BUCKETS;i++)
        scanf("%d",&full[i]);
    /*如要檢查full[0]>full[1]>full[2],相應代碼在此*/
    printf("Enter volume of targ./n");
    scanf("%d",&targ);    /*檢查targ<=full[0]的代碼在此*/
    /*設置將初始狀態(tài)存入倒油狀態(tài)隊列等初值*/
    q[0].state[0]=full[0];
    for(i=1;i<BUCKETS;i++)
        q[0].state[i]=0;
    q[0].sbucket=0;
    q[0].obucket=0;
    q[0].last=0;
    found=unable=0;
    head=tail=0;
    do
    {
        /*對狀態(tài)隊列中第一個還未檢查過的元素在還未檢查完每個倒出的桶
          且還未找到解且還未確定無解情況下循環(huán)*/
        for(i=0;i<BUCKETS&&!found&&!unable;i++)
            if(q[head].state[i]>0)        /*倒出桶有油*/
        /*在還未檢查完每個油桶且還未找到解且還未確定無解情況下循環(huán)*/
        for(j=0;j<BUCKETS&&!found&&!unable;j++)
            if(j!=i&&q[head].state[j]<full[j])
            {   /*當前桶不是倒出桶且桶還有空*/
                /*確定本次倒油量*/
                if(q[head].state[i]>full[j]-q[head].state[j])
                    v=full[j]-q[head].state[j];
                else v=q[head].state[i];
                wi=q[head].state[i]-v;
                wj=q[head].state[j]+v;
                /*在隊列中檢查倒油后的結果狀態(tài)是否在隊列中出現(xiàn)*/
                for(k=0;k<=tail;k++)
                    if(q[k].state[i]==wi&&q[k].state[j]==wj) break;
                if(k>tail)