PKU1013 Counterfeit Dollar

PKU1013 Counterfeit Dollar

描述：12枚金币中有一枚是假币，除重量與真币不同外其它特征均相同，用一個天平每次稱相同個數的金币，稱三次既能确定假币。金币分别用A~L代表。

輸入：第一行輸入n，表示有n組測試執行個體，每組測試執行個體包括三行，每行三個字元串，分别指左邊的金币，右邊的金币，天平右側是下降、上升、平衡。

輸出：代表假金币的字母和假币比真币偏重還是偏輕。

思路：這道題開始的思路是模拟，用一個數組存金币的真假情況，模拟了老半天，寫了一大堆for，但情況巨多，考慮不周，結果被殺了回來，然後在Discuss中淘得用枚舉不錯，竊喜，又開工，四五十分鐘搗騰，代碼由一大堆for搖身變成一大堆if else，狂暈，情況依然巨多，又不周，再殺回，無奈。。。。請教隊友，隊友提供幾組資料，發現少考慮了如果假設的假币在兩次稱量中輕重沖突的情況，終于a了，又得知藍皮書上有原題，看其代碼，思路清晰明了，居然連switch都用上了，實在經典，遂記下。順便和自己比較一番差距還是蠻大的。

我的代碼：

//枚舉假币的所有情況，包括輕重

#include<stdio.h>

#include<string.h>

char right[3][10],left[3][10],result[3][10];

bool isHeavy(char i)//判斷是否假币為重

{

int j;

for(j=0;j<3;j++)//判斷是否與三次稱量結果沖突

{

switch(result[j][0])//switch的妙用

{

case 'u': if(strchr(right[j],i)==NULL) return false;

break;

case 'e': if(strchr(left[j],i)!=NULL||strchr(right[j],i)!=NULL) return false;

break;

case 'd': if(strchr(left[j],i)==NULL) return false;

break;

}

}

return true;

}

bool isLight(char i)//判斷是否假币為輕

{

int j;

for(j=0;j<3;j++)//判斷是否與三次稱量結果沖突

{

switch(result[j][0])

{

case 'd': if(strchr(right[j],i)==NULL) return false;

break;

case 'e': if(strchr(left[j],i)!=NULL||strchr(right[j],i)!=NULL) return false;

break;

case 'u': if(strchr(left[j],i)==NULL) return false;

break;

}

}

return true;

}

int main()

{

int n;

char i;

scanf("%d",&n);

while(n--)

{

for(i=0;i<3;i++)

scanf("%s%s%s",right[i],left[i],result[i]);

for(i='A';i<='L';i++)

{

if(isLight(i))

{

printf("%c is the counterfeit coin and it is light./n",i);

break;

}

if(isHeavy(i))

{

printf("%c is the counterfeit coin and it is heavy./n",i);

break;

}

}

}

return 0;

}

标程：

 #include<stdio.h>

#include<string.h>

int main()

{

int n,i,j,b;

bool a;//判斷是否已經找到符合目前的假币，符合a=1，一旦發現假設不成立就把a還原成0

char str[3][3][20];

char str1[2][10]={"heavy","light"};//将輕重存起來，由b決定輸出

scanf("%d",&n);

while(n--)

{

for(i=0;i<3;i++)

for(j=0;j<3;j++)

scanf("%s",str[i][j]);

for(i='A';i<='L';i++)//枚舉假币（沒有假設輕重，而是在程式中判斷

{

a=0,b=0;

for(j=0;j<3;j++)

{

if((strchr(str[j][0],i)!=NULL||strchr(str[j][1],i)!=NULL)&&!strcmp(str[j][2],"even")) { a=0; break; }//在平衡中找到，一定不是假币

else if(!strcmp(str[j][2],"up"))//上升的左端是重，右端是輕

{

if(strchr(str[j][0],i)!=NULL)

{

if(a==0) b=0;.//如果是第一次符合假設，輕b=1，重b=0 else if(b!=0){ a=0; break; }//如果b值沖突，假設失敗

a=1;

}

else if(strchr(str[j][1],i)!=NULL) {

if(a==0) b=1;

else if(b!=1) { a=0; break; }

a=1;

}

else if(a==1){a=0; break;}

}

else if(!strcmp(str[j][2],"down"))//下降的左端是輕，右端是重

{

if(strchr(str[j][0],i)!=NULL)

{

if(a==0) b=1;

else if(b!=1){ a=0; break; }

a=1;

}

else if(strchr(str[j][1],i)!=NULL)

{

if(a==0) b=0;

else if(b!=0){ a=0; break; }

a=1;

}

else if(a==1){a=0; break;}

}

}

if(a==1) break;//當假設成立時，break，輸出

}

printf("%c is the counterfeit coin and it is %s./n",i,str1[b]);

}

return 0;

}