2692:假幣問題

#include <bits/stdc++.h> using namespace std; char Left[3][7]; char Right[3][7]; char result[3][5]; bool isFake(char c,bool light){//假設c是假幣，是否更輕for(int i=0;i<3;i++){char *fleft;char *fright;if(light==true){fleft=Left[i];fright=Right[i];}else if(light==false){fleft=Right[i];//if假幣更重，那么驗出哪邊輕，假幣就在另一邊， // 早早調換好順序，因為fleft就是用來指向假幣所在字符串來找假幣的 fright=Left[i];}char res=result[i][0];switch(res){case 'u'://右邊的翹起，說明右邊更輕，假幣在右邊 if(strchr(fright,c)==NULL){//在右邊沒有找到更輕的那枚幣 return false;// break;一定要break呀，如果找到了說明這次稱量證明假設成立 } break; case 'e'://兩側平衡，說明稱的硬幣里沒有假的 if(strchr(fright,c)||strchr(fleft,c)){//如果找到了假幣 return false;}break;case 'd'://右邊的沉下，說明右邊更重，假幣在左邊 if(strchr(fleft,c)==NULL){//在左邊沒有找到更輕的那枚幣 return false;}break;} }return true;//三次稱量結果都與假設結果符合時，才證明假設成立 } int main(int argc, char** argv) {int t;cin>>t;while(t--){for(int i=0;i<3;i++){cin>>Left[i]>>Right[i]>>result[i];}for(char c='A';c<='L';c++){//假設第i枚硬幣是假幣if(isFake(c,true)){//假設第i枚硬幣是假幣且輕于真幣 printf("%c is the counterfeit coin and it is light. \n",c); }else if(isFake(c,false)){//假設第i枚硬幣是假幣且重于真幣 printf("%c is the counterfeit coin and it is heavy. \n",c); }}}return 0;}//兩種思路： //方法一、對12枚硬幣進行枚舉，分別假設第i枚硬幣是假幣且分別為輕、重 //的情況 ，在已知的更輕/重的那一邊尋找這枚假幣，找到了假幣說明成立 //方法二、對硬幣編號1~12，設正常重量為0，輕為-1，重為1，依然是 分別假設第i枚硬幣 //是假幣且分別為輕、重的情況，不是尋找，而是累加重量來比較輕重，如何通過字母 //確定硬幣，字母-'A'即可代表硬幣編號 #include <bits/stdc++.h> using namespace std; char Left[3][7]; char Right[3][7]; char result[3][5]; int w[12]; bool isBalance(){//for(int i=0;i<3;i++){int leftw=0;//給出的三次稱量中，左邊的重量 int rightw=0;for(int j=0;j<6&&Left[i][j]!='\0';j++){//左右兩邊硬幣數量相等 leftw+=w[Left[i][j]-'A'];rightw+=w[Right[i][j]-'A'];}if(result[i][0]=='u'&&leftw>rightw)continue;else if(result[i][0]=='d'&&leftw<rightw)continue;else if(result[i][0]=='e'&&leftw==rightw)continue;else return false;}return true; } int main(int argc, char** argv) {int t;cin>>t;while(t--){for(int i=0;i<3;i++){cin>>Left[i]>>Right[i]>>result[i];}memset(w,0,sizeof(w));int i=0;for( i=0;i<12;i++){w[i]=-1;//假設第i枚硬幣為假的，且更輕if(isBalance()){break;} w[i]=1;//假設第i枚硬幣為假的，且更重 if(isBalance()){break;} w[i]=0;//第i枚是假幣不成立，那i枚硬幣就是真的 }printf("%c is the counterfeit coin and it is %s. \n",i+'A',w[i]<0?"light":"heavy"); }return 0;}//兩種思路： //方法一、對12枚硬幣進行枚舉，分別假設第i枚硬幣是假幣且分別為輕、重 //的情況 ，在已知的更輕/重的那一邊尋找這枚假幣，找到了假幣說明成立 //方法二、對硬幣編號1~12，設正常重量為0，輕為-1，重為1，依然是 分別假設第i枚硬幣 //是假幣且分別為輕、重的情況，不是尋找，而是累加重量來比較輕重，如何通過字母 //確定硬幣，字母-'A'即可代表硬幣編號

分治法尋找假幣法

總結

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

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