分治法求假币，假币比真币轻，在n个硬币中找出假币，c语言代码

分治法解决找假币问题通常涉及二分查找的思想，假设我们有天平作为工具。以下是C语言的基本思路：

首先，我们需要一个函数，如`findFakeCoin(n, coins, weight)`，其中`n`是硬币总数，`coins`是一个整数数组表示每枚硬币的重量，`weight`是天平两边平衡的标准重量。

1. 如果只有一个硬币，直接比较其重量是否等于标准重量，如果不同，则它是假币；否则，它就是真币。
2. 若有超过一个硬币，将硬币分成两组，每组各半，分别称重：
a. 把一组放在一边，另一组放在另一边。
b. 如果天平平衡，假币一定在未称的那一组里，递归地在那一组继续查找；
c. 如果天平不平衡，假币在较轻的那一边，再次把这一边的一半分成两部分，重复步骤b直到找到假币或者只剩下一个硬币。

#include <stdio.h>

int findFakeCoin(int n, int coins[], int targetWeight) {
    if (n == 1) {
        return coins[0] != targetWeight ? 0 : n;
    }

    int half = n / 2;
    int leftSum = 0;
    for (int i = 0; i < half; ++i) {
        leftSum += coins[i];
    }
    
    int rightSum = 0;
    for (int i = half; i < n; ++i) {
        rightSum += coins[i];
    }

    // 如果左右重量相等，假币在剩余的一半
    if (leftSum == rightSum) {
        return findFakeCoin(half, &coins[half], targetWeight);
    } else { // 如果左边重，假币在左边或已知较轻的那一堆
        if (leftSum > rightSum) {
            return findFakeCoin(half, coins, targetWeight);
        } else {
            return findFakeCoin(half, &coins[half + 1], targetWeight - rightSum);
        }
    }
}

int main() {
    int n = 5; // 假设有5个硬币
    int coins[] = {1, 1, 1, 1, 2}; // 真实重量可能为1，假币重量为2
    int targetWeight = 1; // 标准重量为1

    int fakeIndex = findFakeCoin(n, coins, targetWeight);
    printf("假币在第 %d 位\n", fakeIndex);

    return 0;
}