查找假币
- 题目描述：
一个袋子里有n (n>3) 个银币，其中一枚是假币，并且假币和真币一模一样， 肉眼很难分辨， 目前只知道假币比真币的重量轻一点。 所以采用的是天平进行称重找出假币。 请给出这样的操作。
本题采用的是分治法进行求解问题
初始将硬币分成两份， 将两份分别分在天平两边，寻找到分量少的一份。 则假币一定在分量少的一份。之后一直调用该算法，则可一直找到最后那个假币。
代码实现
#include <iostream> #include <cstdlib> using namespace std; const int MAXNUM = 100; int falseCoin(int weight[], int lhs, int rhs) { if (lhs == rhs) return lhs + 1; //如果只剩下两个银币，则较轻的那个便是假币 else if (lhs == (rhs - 1)) { return weight[lhs] < weight[rhs] ? lhs + 1 : rhs + 1; } int lsum = 0, rsum = 0; //如果偶数个银币，则比较两等份 if ((rhs - lhs + 1) % 2 == 0) { for (int i = lhs; i < (lhs + (rhs - lhs + 1) / 2); i++) { lsum += weight[i]; } for (int j = lhs + (rhs - lhs + 1) / 2; j <= rhs; j++) { rsum += weight[j]; } //左右两份等重，则无假币 if (lsum == rsum) return -1; else return (lsum < rsum) ? falseCoin(weight, lhs, lhs + (rhs - lhs) / 2) : falseCoin(weight, lhs + (rhs - lhs) / 2 + 1, rhs); } //如果奇数个银币，则比较除中间银币外的两等份 else if ((rhs - lhs + 1) % 2 != 0) { for (int i = lhs; i < (lhs + (rhs - lhs) / 2); i++) { lsum += weight[i]; } for (int j = (lhs + (rhs - lhs) / 2 + 1); j <= rhs; j++) { rsum += weight[j]; } //左右两份等重，则无假币 if (lsum == rsum && weight[lhs] == weight[lhs + (rhs - lhs) / 2]) return -1; //如果两份等重，中间银币较轻，则中间银币为假币 else if (lsum == rsum && weight[lhs] > weight[lhs + (rhs - lhs) / 2]) return lhs + (rhs - lhs) / 2 + 1; //否则，返回较轻那份中的假币 else return (lsum < rsum) ? falseCoin(weight, lhs, lhs + (rhs - lhs) / 2 - 1) : falseCoin(weight, lhs + (rhs - lhs) / 2 + 1, rhs); } } int main() { int weight[MAXNUM]; int n; cout << "请输入您的硬币数量:" <<endl; while (cin >> n) { cout << "请输入您每个硬币重量： "<<endl; for (int i = 0; i < n; i++) cin >> weight[i]; int falsePos = falseCoin(weight, 0, n - 1); if (falsePos != -1) cout << "第" << falsePos << "个银币为假币！" << endl; else cout << "无假币!" << endl; }//while system("pause"); return 0; }
注意
- 输入的假币是要比真币的重要少的
- 这堆硬币可能是偶数和奇数我们要分情况实现
