枚舉算法——稱硬幣

枚舉算法：核心思想就是枚舉所有的可能，本質是從所有的候選答案中去搜索正確的解，使用該算法要滿足兩個條件：
（1）可預先確定候選答案的數量；
（2）候選答案的范圍在求解之前必須要有一個確定的集合。

優點：算法簡單，在局部地方使用枚舉法，效果十分的好；
缺點：運算量過大，當問題規模變大的時候，循環的階數越大，執行速度越慢。

問題描述：

賽利有12枚銀幣。其中有11枚真幣和1枚假幣。假幣看起來和真幣沒有區別，但是重量不同。但賽利不知道假幣比真幣輕還是重。于是他向朋友借了一架天平。朋友希望賽利稱三次就能找出假幣并且確定假幣是輕是重。例如:如果賽利用天平稱兩枚硬幣，發現天平平衡，說明兩枚都是真的。如果賽利用一枚真幣與另一枚銀幣比較，發現它比真幣輕或重，說明它是假幣。經過精心安排每次的稱量，賽利保證在稱三次后確定假幣。

輸入

第一行有一個數字n，表示有n組測試用例。
對于每組測試用例：
輸入有三行，每行表示一次稱量的結果。賽利事先將銀幣標號為A-L。每次稱量的結果用三個以空格隔開的字符串表示：天平左邊放置的硬幣 天平右邊放置的硬幣 平衡狀態。其中平衡狀態用up'',down’’, 或 ``even’'表示, 分別為右端高、右端低和平衡。天平左右的硬幣數總是相等的。

輸出

輸出哪一個標號的銀幣是假幣，并說明它比真幣輕還是重(heavy or light)。

Sample input

1
ABCD EFGH even
ABCI EFJK up
ABIJ EFGH even

Sample Output

K is the counterfeit coin and it is light

思路：

A-L中每個都有兩種可能，是假幣或不是假幣，一共就有12x2=24種

#include<stdio.h> #include<string.h> char left[3][7],right[3][7]; char result[3][5]; int heavy(char c){int i;for(i=0;i<3;i++){switch(result[i][0]){case 'e':if(strchr(left[i],c)!=NULL||strchr(right[i],c)!=NULL) return 0;break;case 'u':if(strchr(left[i],c)==NULL) return 0;break;case 'd':if(strchr(right[i],c)==NULL) return 0;break;}}return 1;} int light(char c) {int i;for(i=0;i<3;i++){switch(result[i][0]){case 'e':if(strchr(left[i],c)!=NULL||strchr(right[i],c)!=NULL) return 0;break;case 'u':if(strchr(right[i],c)==NULL) return 0;break;case 'd':if(strchr(left[i],c)==NULL) return 0;break;}}return 1; } int main() {int i,k,n;char c; scanf("%d",&n);for(k=0;k<n;k++){for(i=0;i<3;i++)scanf("%s %s %s",&left[i],&right[i],&result[i]); for(c='A';c<='L';c++){ if(heavy(c)){printf("%c is the counterfeit coin and it is heavy.\n",c);break;}if(light(c)){printf("%c is the counterfeit coin and it is light.\n",c);break;}}}return 0; }

總結

以上是生活随笔為你收集整理的称硬币的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。