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;

}