在n(n>=3)枚硬币中有一枚重量不合格的硬币(过轻或过重)，如果只有一架天平可以用来称重且称重的硬币数没有限制，设计一个算法，找出这枚不合格的硬币，使得称重的次数最少(优于O(n))。
(提示：分成n/3或n/4份，至少两份数量相等)
借鉴二分法的思想，不过是分成3堆，其中两堆个数一致，另外一堆可以不一致。不管是奇数还是偶数个硬币，（被3整除最好）都可分成大致相同的3堆，比较两堆一致的，若不相等，说明坏硬币在这两堆中。若相等，说明在第3堆中。重复操作，直到只剩2个硬币。
//Q6 在n(n>=3)枚硬币中有一枚重量不合格的硬币(过轻或过重)，如果只有一架天平可以用来称重且称重的硬币数没有限制， // 设计一个算法，找出这枚不合格的硬币，使得称重的次数最少(优于O(n))。 // 思路： 采用分治策略。如果n<3，那么将拿走的硬币与剩下的硬币比较，不等的是坏币；将n枚硬币分为大致相等的3份， //如果n(mod 3)≠0，那么令两份少的硬币相等。取两份相等的硬币放到天平上，如果不等，那么这两份硬币中含有坏币， //否则坏币在第3份中。递归处理，直到n<3为止。 //关键词：硬币 坏 分治coins //硬币结构体 struct Coin { int weight; int label; Coin(int weight, int label)// 构造函数 { this->weight = weight; this->label = label; } }; int gettotalweight(vector<Coin> coins) { int totalweight = 0; for (vector<Coin>::iterator iter = coins.begin(); iter != coins.end(); ++iter) { totalweight = totalweight+iter->weight; } return totalweight; } #include "algorithm" int turewight = 0; int findBadCoin(vector<Coin> coins) { int n = coins.size(); int k = n / 3; // 将硬币分为3堆 个数分别为k,k,n-2k vector<Coin> A,B,C; int result = 0; A.insert(A.begin(),coins.begin() , coins.begin() + k); B.insert(B.begin(),coins.begin() + k, coins.begin() + 2*k ); C.insert(C.begin(),coins.begin() + 2*k, coins.end()); if (n == 2) { coins[0].weight == turewight ? result = coins[1].label : result = coins[0].label; return result; } if(n>3){ if (gettotalweight(A)!= gettotalweight(B)) { //A与B的重量不相等 coins.clear(); coins.insert(coins.begin(), A.begin(), A.end()); // 重新整合A和B的元素到coins中 coins.insert(coins.end(), B.begin(), B.end()); turewight = C[0].weight;//记录真实重量方便最后的比较 } else // 坏币在第3堆中 { coins.clear(); coins.insert(coins.begin(), C.begin(), C.end()); } return findBadCoin(coins); } } //Ques20201004 int main() { //Q1 //cin >> k;//输入要找的数字c语言把cin换为scanf即可 //cout << BinarySearch(0, 9);//从数组a[0]到a[9]c语言把cout换为printf即可 //Q2 /*int n = 9; int arr[] = { -1,3,5,2,7,8,-9,1,-4 }; f(arr,n);*/ // Q3 /* char A = 'A'; char B = 'B'; char C = 'C'; Hanoi(3, A, B, C);*/ //Q4 /* int arr[] = { 1,3,5,8,9,7,6,1,2 }; cout<<siglePeak(arr,0,8);*/ // Q5 //int arr[] = { 1,1,2,3,5,7,8,9 }; //printL_U(arr,1,7,8);// L=1，U=7 数组长度为8 // Q6 vector<Coin> coins; for (int i = 0; i < 19;i++) { if (i == 12) {// 坏硬币的重量为2 coins.push_back(Coin(2, 12)); } else { // 生成20个硬币 coins.push_back(Coin(1, i)); } } cout<<findBadCoin(coins); return 0; }
