有n(n>3)个硬币，其中有一个假币，且假币较轻，用天平称重得到其重量为w[i],请设计一 个程序，用分治法实现，并分析其时间复杂度。用c语言编写代码，要求用c99标准

实现。

分治法思路：

1. 将硬币分成三堆，分别称重，假设分别称为left、right、mid。

2. 如果left和right重量相等，说明假币在mid堆中，递归地对mid堆进行称重。

3. 如果left和right重量不相等，说明假币在left或right堆中，递归地对left或right堆进行称重。

4. 当硬币数为3时，直接比较三枚硬币的重量来确定假币位置。

时间复杂度分析：

每次称重将硬币分成三堆，最坏情况下需要进行log3(n-1)次称重才能确定假币位置，每次称重需要比较n/3个硬币的重量，因此时间复杂度为O(nlog3(n-1))。

代码实现：

#include <stdio.h>

#define MAXN 100000

int n, w[MAXN + 1];

int find_fake_coin(int l, int r) {
    if (l == r) return l;  // 只剩一枚硬币，即为假币
    int len = (r - l + 1) / 3;
    int left = l, right = r;
    // 将硬币分成三堆，分别称重
    int w1 = w[left], w2 = w[left + len], w3 = w[left + len + len];
    if (w1 == w2) {  // 假币在第三堆中
        return find_fake_coin(left + len * 2, right);
    } else if (w1 == w3) {  // 假币在第二堆中
        return find_fake_coin(left + len, left + len * 2 - 1);
    } else {  // 假币在第一堆中
        return find_fake_coin(left, left + len - 1);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &w[i]);
    }
    int fake = find_fake_coin(1, n);
    printf("The fake coin is No.%d\n", fake);
    return 0;
}