C++解决假币问题

题目

一个袋子里有30个银币，其中一枚是假币，并且假币和真币一模一样，肉眼很难分辨，目前只知道假币比真币重量轻一点。请问，如何区分出假币？

分析

首先为每个银币编号，然后将所有的银币等分为两份，放在天平的两边。这样就将区分30个银币的问题变为区别两堆银币的问题。

因为假币分量较轻，因此天平较轻的一侧中一定包含假币。再将较轻的一侧中银币等分为两份，重复上述做法。直到剩下两枚银币，便可用天平直接找出假银币。类似于二分法

代码

由于这个是自己做的一个练习题，没有使用OJ判题，所以自己利用随机数生成银币的重量和假币相关信息

#include <iostream>
#include <algorithm>
#include <ctime>
using namespace std; 

void generate_seq(int coin[])
{
    srand(time(0));
    int coin_weight = rand() % 100;
    int fake_weight = rand() % coin_weight;
    int fake_add = rand() % 30;
    for (int i = 1; i <= 30; i++)
    {
        if (i == fake_add)
            coin[i] = fake_weight;
        else
            coin[i] = coin_weight;
    }
    cout << "fake_add=" << fake_add << endl; 
    cout << "fake_weight=" << fake_weight << endl; 
}

void show_seq(int coin[])
{
    for (int i = 1; i <= 30; i++)
    {
        cout << coin[i] << " ";
    }
    cout << endl; 
}

int find_fake(int coin[], int begin, int end)
{ 
    if (begin == end)
        return begin;
    
    double mid = (begin + end) / 2; 
    int weight_a = 0, weight_b = 0;

    if ((end - begin + 1) % 2 == 0) //可等分
    {
        for (int i = begin; i <= (int)mid; i++)
            weight_a += coin[i];
        for (int i = (int)mid + 1; i <= end; i++)
            weight_b += coin[i];
        cout << begin << " " << end << " " << mid << endl;
        cout << weight_a << " " << weight_b << endl;

        if (weight_a < weight_b)
            find_fake(coin, begin, (int)mid); 
        else 
            find_fake(coin, (int)mid+1, end); 
    }else //不可等分，中间留一个mid
    {
        for (int i = begin; i < mid; i++)
            weight_a += coin[i];
        for (int i = mid + 1; i <= end; i++)
            weight_b += coin[i];
        cout << begin << " " << end << " " << mid << endl;
        cout << weight_a << " " << weight_b << endl;

        if (weight_a < weight_b)
            find_fake(coin, begin, (int)mid - 1);
        else if (weight_a > weight_b)
            find_fake(coin, (int)mid + 1, end);
        else    
            return mid; 
    }
    
}

int main()
{
    //产生随机数列
    int coin[31];
    generate_seq(coin); 

    //打印数列
    show_seq(coin); 

    //找
    int fake_add = find_fake(coin, 1, 30); 
    cout << "fake_add=" << fake_add << endl; 
    cout << "fake_weight=" << coin[fake_add] << endl;  
    return 0; 
}