查找假币--天平秤重法（C++，完善版）

一、题目

编写一个实验程序查找假币，有n（n>3）个硬币，其中有一个假币，且假币较轻，采用天平秤重方式找到这个假币，并给出操作步骤。

本篇文章是基于博主（逆风的蔷薇）的思路进行进一步完善的，感谢大神的思路！！

附原文链接：

http:// https://blog.csdn.net/fly_yr/article/details/48350551?utm_source=app&app_version=5.0.1&code=app_1562916241&uLinkId=usr1mkqgl919blen

#include<iostream>
using namespace std;
#define MAX 30
int found(int weight[],int left,int right)
{if (left == right)//如果只有一枚硬币，则返回0return 0;else if (left == right - 1)//如果有两枚硬币，则返回较轻的硬币{if (weight[left] == weight[right])	//两枚硬币一样重，返回-1return -1;else if (weight[left] > weight[right])	//左边比右边重，则返回右边的硬币return right + 1;else   //否则返回左边的额硬币return left + 1;}int left_weight=0;//记录左边的重量int right_weight=0;//记录右边的重量//如果是偶数个硬币if ((right - left + 1) % 2 == 0){for (int i = left; i < (left + (right - left + 1) / 2); i++)//记录左边的重量left_weight += weight[i];for (int j = left + (right - left + 1) / 2; j < right; j++)//记录右边的重量right_weight += weight[j];if (left_weight == right_weight)//如果左右一样重，则返回-1return -1;else{if (left_weight < right_weight)//右边重于左边，则对左边进行再次二分法天平秤重found(weight, left, left + (right - left) / 2);else						//否则对右边进行再次二分法天平秤重found(weight, left + (right - left + 1) / 2, right);}}//如果是奇数枚硬币else if ((right - left + 1) % 2 != 0){for (int i = 0; i <= left + (right - left + 1) / 2 -1; i++)//记录左边的重量left_weight += weight[i];for (int j = left + (right - left + 1) / 2 + 1; j <= right; j++)//记录右边的重量right_weight += weight[j];//如果两边一样重，且左边的某个硬币重量和中间的硬币重量一样重，则返回-1if (left_weight == right_weight && weight[left] == weight[left + (right - left+ 1) / 2])return -1;//否则返回中间值else if (left_weight == right_weight && weight[left] > weight[left + (right - left + 1) / 2])return left + (right - left + 1) / 2+1;//如果两边不一样重，再次进行类似判断else{if (left_weight < right_weight)found(weight, left, left + (right - left + 1) / 2-1);elsefound(weight, left + (right - left + 1) / 2 + 1, right);}}
}int main()
{int coin_weight[MAX];int NUM;while (1){cout << "请输入硬币个数：";cin >> NUM;cout << "请输入每枚硬币的重量" << endl;for (int i = 0; i < NUM; i++)cin >> coin_weight[i];int judge = found(coin_weight, 0, NUM - 1);if (judge == -1)cout << "无假币！" << endl;else if (judge == 0)cout << "无法判断是否是假币！" << endl;elsecout << "第" << judge << "个是假币" << endl;cout << "======================" << endl;cout << endl;}
}

运行结果：

欢迎各位大佬指出错误~