分治法找假硬币c++

分治法是一种常见的算法思想，可以用来解决许多问题，包括找假硬币。在找假硬币问题中，我们需要将硬币分成若干组，每组中的硬币重量相等，然后对每组进行称重比较，如果某组中的硬币重量不同于其他组，则该组中必有假硬币。接下来，我们可以将该组继续分成更小的组，重复上述步骤，直到找到假硬币。

以下是用C++实现分治法找假硬币的代码示例：

#include <iostream>
using namespace std;

int find_fake_coin(int coins[], int left, int right) {
    int n = right - left + 1;
    if (n == 1) {
        return left;
    } else if (n == 2) {
        return coins[left] < coins[right] ? left : right;
    } else {
        int mid = (left + right) / 2;
        int left_sum = 0, right_sum = 0;
        for (int i = left; i <= mid; i++) {
            left_sum += coins[i];
        }
        for (int i = mid + 1; i <= right; i++) {
            right_sum += coins[i];
        }
        if (left_sum < right_sum) {
            return find_fake_coin(coins, left, mid);
        } else if (left_sum > right_sum) {
            return find_fake_coin(coins, mid + 1, right);
        } else {
            return -1; // 没有假硬币
        }
    }
}

int main() {
    int n;
    cout << "请输入硬币数量：";
    cin >> n;

    int coins[n];
    cout << "请输入硬币重量：";
    for (int i = 0; i < n; i++) {
        cin >> coins[i];
    }

    int fake_coin_index = find_fake_coin(coins, 0, n - 1);
    if (fake_coin_index == -1) {
        cout << "没有假硬币" << endl;
    } else {
        cout << "假硬币的索引为：" << fake_coin_index << endl;
    }

    return 0;
}