解題思路：在本題中，已經(jīng)明確說明塞利保證在三次稱量后能夠確定假幣，也就是說，輸入的三組稱量數(shù)據(jù)有唯一的答案。硬幣有三種狀態(tài)：較重的假幣、較輕的假幣、真幣。由于只有1枚假幣，且總共只有12枚銀幣，因此可以對所有的情況進行枚舉。假幣可能是任意一枚，故有12種情況；且假幣可能比真幣重，也可能比真幣輕，故有兩種情況。在這全部的24種情況當(dāng)中，只有一種情況能夠符合三組稱量數(shù)據(jù)，這就是所要尋找的答案。

? ? ? ? 假設(shè)用0、-1和1表示真幣、較輕假幣和較重假幣的重量。分別計算天平左側(cè)與右側(cè)的重量，若下面三個條件中有一個不滿足，則說明假設(shè)不成立，當(dāng)前的情況與稱量數(shù)據(jù)矛盾。

? ? ? ?（1）如果天平左側(cè)較重，且稱量結(jié)果為up。

? ? ? ?（2）如果天平右側(cè)較重，且稱量結(jié)果為down。

? ? ? ?（3）如果天平左右兩側(cè)重量相同，且稱量結(jié)果為even。

具體實現(xiàn)時，需要注意以下兩點。

（1）可以使用字符串存儲稱量數(shù)據(jù)。題目中并沒有說明一定要使用4枚銀幣進行稱量，由于總共有12枚銀幣，天平的一側(cè)最多可以有6枚銀幣。

（2）在枚舉的過程中，一旦發(fā)現(xiàn)不滿足條件的情況，可以立即跳出循環(huán)，繼而枚舉下一枚銀幣；同樣地，一旦發(fā)現(xiàn)符合所有稱量數(shù)據(jù)的情況，可以立即輸出結(jié)果。

#include<stdio.h>int status[12]; char left[3][7],right[3][7],result[3][7];//判斷當(dāng)前的情況是否滿足條件 bool Balanced() {int i,k,leftw,rightw;for(i = 0; i < 3; i++){leftw = rightw = 0;for(k = 0; k <6 && left[i][k] !=0; k++){leftw += status[left[i][k]-'A'];rightw += status[right[i][k]-'A'];}if(leftw > rightw && result[i][0]!='u') //條件1 return false;if(leftw < rightw && result[i][0]!='d') //條件2 return false;if(leftw == rightw && result[i][0]!='e') //條件3 return false; }return true; } int main() {int i,num;scanf("%d",&num);while(num--){for(i = 0; i < 3; i++)scanf("%s%s%s",left[i],right[i],result[i]);for(i = 0; i < 12; i++)status[i] = 0;for(i = 0; i < 12; i++){status[i] = 1; //第i枚硬幣是較重假幣 if(Balanced()) break;status[i] = -1; //第i枚硬幣是較輕假幣 if(Balanced())break;status[i] = 0; //第i枚硬幣是真幣 }printf("%c is the counterfeit coin and it is %s.\n",i+'A',status[i] > 0?"heavy":"light");}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的假币问题POJ2692的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。