C++经典算法题-八枚银币

cwl_java

发布于 2022-11-30 08:35:17

2190

发布于 2022-11-30 08:35:17

文章被收录于专栏：cwl_Java

9.Algorithm Gossip: 八枚银币

说明

现有八枚银币a b c d e f g h，已知其中一枚是假币，其重量不同于真币，但不知是较轻或较重，如何使用天平以最少的比较次数，决定出哪枚是假币，并得知假币比真币较轻或较重。

解法

单就求假币的问题是不难，但问题限制使用最少的比较次数，所以我们不能以单纯的回圈比较来求解，我们可以使用决策树（decision tree），使用分析与树状图来协助求解。一个简单的状况是这样的，我们比较a+b+c与d+e+f ，如果相等，则假币必是g或h，我们先比较g或h哪个较重，如果g较重，再与a比较（a是真币），如果g等于a，则g为真币，则h为假币，由于h比g轻而 g是真币，则h假币的重量比真币轻。

#include<stdio.h> 
#include<stdlib.h> 
#include<time.h>

    void compare(int[], int, int, int);

    void eightcoins(int[]);

    int main(void) {
        int coins[ 8] ={
            0
        } ;
        int i;

        srand(time(NULL));


        for (i = 0; i < 8; i++) coins[i] = 10;

        printf("\n输入假币重量(比10大或小)：");
        scanf("%d", & i);
        coins[rand() % 8] = i;
        eightcoins(coins);
        printf("\n\n列出所有钱币重量：");
        for (i = 0; i < 8; i++)
            printf("%d ", coins[i]);
        printf("\n");
        return 0;
    }

    void compare(int coins[], int i, int j, int k) {
        if (coins[i] > coins[k])
            printf("\n假币 %d 较重", i + 1);

        else

    }


    printf("\n假币 %d 较轻",j+1);


    void eightcoins(int coins[]) {
        if (coins[0] + coins[1] + coins[2] ==
                coins[3] + coins[4] + coins[5]) {
            if (coins[6] > coins[7])
                compare(coins, 6, 7, 0);

            else

        }


        compare(coins, 7, 6, 0);

            else if (coins[0] + coins[1] + coins[2] > coins[3] + coins[4] + coins[5]) {
            if (coins[0] + coins[3] == coins[1] + coins[4]) compare(coins, 2, 5, 0);
            else if (coins[0] + coins[3] > coins[1] + coins[4]) compare(coins, 0, 4, 1);
            if (coins[0] + coins[3] < coins[1] + coins[4])

                compare(coins, 1, 3, 0);
        } else if (coins[0] + coins[1] + coins[2] < coins[3] + coins[4] + coins[5]) {
            if (coins[0] + coins[3] == coins[1] + coins[4]) compare(coins, 5, 2, 0);
            else if (coins[0] + coins[3] > coins[1] + coins[4]) compare(coins, 3, 1, 0);
            if (coins[0] + coins[3] < coins[1] + coins[4]) compare(coins, 4, 0, 1);
        }
    }

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-01-17，如有侵权请联系 cloudcommunity@tencent.com 删除

algorithm