编辑代码

#include <iostream>
#include <ctime>
#include <cstdlib> // 包含产生随机数的库函数
#define MAX 1000
using namespace std;

int data[MAX];

int sum(int low, int high) { // 求data[low..high]的重量
	int sum = 0;
	for(int i = low; i <= high; i++) sum += data[i];
	return sum;
}

int solve(int low, int high) {
	if(low == high) return low; // 只有一个硬币 
	if(low == high - 1) { // 只有两个硬币 
		if(data[low] < data[high]) return low;
		else return high;
	}
	int mid = (low + high) / 2;
	int sum1, sum2;
	if((high - low + 1) % 2 == 0) { // 区间内硬币个数为偶数
		sum1 = sum(low, mid);
		sum2 = sum(mid + 1, high);
		printf("硬币%d-%d和硬币%d-%d称重一次：", low, mid, mid + 1, high);
	} else { // 区间内硬币个数为奇数
		sum1 = sum(low, mid - 1);
		sum1 = sum(mid + 1, high);
		printf("硬币%d-%d和硬币%d-%d称重一次：", low, mid - 1, mid + 1, high);
	}
	if(sum1 == sum2) {
		printf("两者重量相同。\n");
		return mid;
	} else if(sum1 < sum2) { // 假币在左区间 
		printf("前者重量轻。\n");
		if((high - low + 1) % 2 == 0) return solve(low, mid); // 区间内硬币个数为偶数 
		else return solve(low, mid - 1); // 区间内硬币个数为奇数 
	} else { // 假币在右区间 
		printf("后者重量轻。\n");
		return solve(mid + 1, high);
	}
}

int main (void) {
	int n = 12; // 假设有12个硬币
	for(int i = 0; i < n; i++) data[i] = 2;
	srand((unsigned)time(NULL)); // 随机数种子 
	data[rand() % n] = 1;  // 随机生成一个假币 
	printf("求解过程：\n");
	printf("硬币%d是假币。\n", solve(0, n - 1));
	return 0;
}