给你一个装有n枚硬币的袋子。n枚硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这枚伪造的硬币.分治算法c++

以下是使用分治算法在C++中找出伪造硬币的示例代码：

#include <iostream>
#include <vector>

using namespace std;

// 分治算法找出伪造的硬币
int findFakeCoin(vector<int>& coins, int left, int right) {
    // 当只有一个硬币时，直接返回该硬币的索引
    if (left == right) {
        return left;
    }

    // 计算中间位置
    int mid = (left + right) / 2;

    // 比较左右两组硬币的总重量
    int leftSum = 0, rightSum = 0;
    for (int i = left; i <= mid; i++) {
        leftSum += coins[i];
    }
    for (int i = mid + 1; i <= right; i++) {
        rightSum += coins[i];
    }

    // 如果左边总重量小于右边总重量，则伪造硬币在左边
    if (leftSum < rightSum) {
        return findFakeCoin(coins, left, mid);
    }
    // 如果左边总重量大于右边总重量，则伪造硬币在右边
    else if (leftSum > rightSum) {
        return findFakeCoin(coins, mid + 1, right);
    }
    // 如果左边总重量等于右边总重量，则伪造硬币在剩余的硬币中
    else {
        return findFakeCoin(coins, mid + 1, right);
    }
}

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

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

    int fakeCoinIndex = findFakeCoin(coins, 0, n - 1); // 找出伪造硬币的索引
    cout << "伪造硬币的索引是：" << fakeCoinIndex << endl;

    return 0;
}