假币问题三分法c语言

三分法是一种数值计算方法，用于求解一元函数的极值或者方程的根。对于假币问题，可以使用三分法来判断一个硬币是否为真币。

以下是一个基于三分法的假币检测的 C 语言程序示例：

#include <stdio.h>

// 模拟硬币重量函数
double Weight(int n)
{
    if (n <= 0) return 0;
    if (n == 1) return 1.0;
    if (n % 2 == 0) return Weight(n / 2) + Weight(n / 2);
    else return Weight(n / 2) + Weight(n / 2 + 1);
}

// 三分法求解假币问题
int FindFakeCoin(int left, int right)
{
    int mid1, mid2;
    double w1, w2, w3;

    while (left < right)
    {
        mid1 = left + (right - left) / 3;
        mid2 = right - (right - left) / 3;

        w1 = Weight(left);
        w2 = Weight(mid1);
        w3 = Weight(mid2);
        if (w1 == w2 && w2 == w3) return -1; // 三个硬币重量相等，无法判断
        else if (w1 < w2 && w2 < w3) left = mid1 + 1; // 假币在 mid2 的右边
        else if (w1 > w2 && w2 > w3) right = mid2 - 1; // 假币在 mid1 的左边
        else { left = mid1 + 1; right = mid2 - 1; } // 假币在 mid1 和 mid2 之间
    }

    return left;
}

int main()
{
    int n;

    printf("请输入硬币数量：");
    scanf("%d", &n);

    int fake = FindFakeCoin(1, n);
    if (fake == -1) printf("无法判断硬币真假！\n");
    else printf("第 %d 枚硬币为假币！\n", fake);

    return 0;
}

在程序中，我们定义了一个模拟硬币重量的函数 `Weight(int n)`，用于计算第 n 枚硬币的重量。对于假币问题，我们可以假设真币和假币的重量相差 1，然后使用递归的方式模拟硬币的重量。

在 `FindFakeCoin(int left, int right)` 函数中，我们使用三分法对硬币进行判断。首先，我们将硬币分成三个部分，分别为 `left` 到 `mid1`、`mid1` 到 `mid2`、`mid2` 到 `right`。然后，我们分别计算这三个部分的重量，并进行比较。如果三个部分的重量相等，说明无法判断，返回 -1；如果重量递增，说明假币在 `mid2` 的右边；如果重量递减，说明假币在 `mid1` 的左边；否则，假币在 `mid1` 和 `mid2` 之间。最后，我们将 `left` 和 `right` 更新到新的位置，并继续进行判断，直到 `left` 和 `right` 相等。

在 `main()` 函数中，我们输入硬币的数量，然后调用 `FindFakeCoin()` 函数进行判断。如果返回值为 -1，说明无法判断；否则，返回的值就是假币的位置。