枚举算法实例应用

第一题：Counterfeit Dollar

Description

Sally Jones has a dozen Voyageur silver dollars. However, only eleven of the coins are true silver dollars; one coin is counterfeit even though its color and size make it indistinguishable from the real silver dollars. The counterfeit coin has a different weight from the other coins but Sally does not know if it is heavier or lighter than the real coins.
Happily, Sally has a friend who loans her a very accurate balance scale. The friend will permit Sally three weighings to find the counterfeit coin. For instance, if Sally weighs two coins against each other and the scales balance then she knows these two coins are true. Now if Sally weighs
one of the true coins against a third coin and the scales do not balance then Sally knows the third coin is counterfeit and she can tell whether it is light or heavy depending on whether the balance on which it is placed goes up or down, respectively.
By choosing her weighings carefully, Sally is able to ensure that she will find the counterfeit coin with exactly three weighings.

Input

The first line of input is an integer n (n > 0) specifying the number of cases to follow. Each case consists of three lines of input, one for each weighing. Sally has identified each of the coins with the letters A--L. Information on a weighing will be given by two strings of letters and then one of the words ''up'', ''down'', or ''even''. The first string of letters will represent the coins on the left balance; the second string, the coins on the right balance. (Sally will always place the same number of coins on the right balance as on the left balance.) The word in the third position will tell whether the right side of the balance goes up, down, or remains even.

Output

For each case, the output will identify the counterfeit coin by its letter and tell whether it is heavy or light. The solution will always be uniquely determined.

Sample Input

1 
ABCD EFGH even 
ABCI EFJK up 
ABIJ EFGH even 

Sample Output

K is the counterfeit coin and it is light. 

简言之：有12枚硬币，其中有11枚真币和1枚假币。假币、真币重量不同，但不知假币比真币轻还是重。现用天平称了三次(两边币数相同)，已知称重三次的结果，求出假币并确定假币比真币轻还是重 (数据保证一定能找出来)。

首先，大体思路为：

利用反证法

1. 先假设A是假币，并且A是轻的，把A是轻的带入天平的三次比对中，判断是否与结论矛盾，若有一个或多个矛盾，则条件不成立，即A不是轻的假币；若均成立，则证明题设成立，即A为轻的假币。
2. 若1条件不成立，则假设A是重的假币，再将该条件带入天平的三次比对中，判断是否与结论矛盾，若有一个或多个矛盾时，则条件不成立，即A不是重的假币；若均成立，则证明题设成立，即A为轻的假币。
3. 若1、2条件同时不成立，则A为真币。再返回步骤1继续判断‘A’++，即下一个字符‘B’。直到最后一个字符‘L’。

• 可以采用三个数组来存储天平的左边、右边、和平衡结果。

//12个硬币最多 一边6个，故列选为6
char Left[3][6] = {"ABCD", "ABCI", "ABIJ"};    //天平左边的硬币
char Right[3][6] = {"EFGH", "EFJK", "EFGH"};   //天平右边的硬币
char Result[3][4] = {"even", "up", "even"};    //结果数组

通过CounterfeitDollar函数实现步骤1~3。

void CounterfeitDollar() {
    for (char c = 'A'; c <= 'L'; c++) {//十一个硬币即A~K
        if (IsFake(c, true)) {//假设c为假币，且是轻的，判断是否满足为假的条件
            printf("%c is the counterfeit coin and it is light.\n", c);
            break;
        } else if (IsFake(c, false)) {//若不满足，则假设c是重的假币，判断是否满足c为假的条件
            printf("%c is the counterfeit coin and it is heavy.\n", c);
            break;
        }
    }
}

其中IsFake(char c,bool light)为假设与三次输入的天平结果比较的结果。只要与其中任何一个结果不匹配则表示假设不成立，均匹配时则表示假设成立，即得出对应解。

其中，为了保证假币无论是轻还是重，都能使三次天平结果的判断代码统一，在3~10行中，通过指针及轻重情况指针指示的对调实现代码统一。

代码详细解释见代码段中注释。

bool IsFake(char c, bool light) {   //light=TRUE表示假币为轻，否则表示为重。
    for (int i = 0; i < 3; ++i) {
        char *pLeft, *pRight;       //天平两边字符串的指针。
        if (light) {                //若硬币为轻的假币。
            pLeft = Left[i];        //第i次称量时，天平左边的字符串。
            pRight = Right[i];      //第i次称量时，天平右边的字符串。
        } else {                    //若硬币为重的假币
            pLeft = Right[i];       //对调左右称量结果
            pRight = Left[i];       //使得Switch中算法恒成立
        }
        //在Switch中我们假设c是轻的假币，因为上述的结果对调使得在Switch中算法不受轻重影响，恒成立。
        switch (Result[i][0]) {     //天平右边三种情况的分支，
            case 'u':               //即up,若右边上升，即表示右边轻，那么假币c一定出现在天平的右边
                if (strchr(pRight, c) == NULL)//strchr返回pRight中首次出现c的位置
                    return false;
                //若不在pRight数组中，则表示当前假设为错误的，即c为(light)(轻/重)为错！
                break;
            case 'e':               //即even，若两边相等，即表示右边轻，那么假币c一定没有出现在两边数组中
                if (strchr(pLeft, c) || strchr(pRight, c))
                    return false;
                //若c存在于pLight或pRight数组中，则表示当前假设为错误的，即c为(light)(轻/重)为错！
                break;
            case 'd':               //即down,若右边下降，即表示右边重，那么假币c一定出现在天平的左边
                if (strchr(pLeft, c) == NULL)
                    return false;
                //若不在pLeft数组中，则表示当前假设为错误的，即c为(light)(轻/重)为错！
                break;
        }
    }
    return true;
}

第二题：完美立方式判断

Description

形如a^3=b^3+c^3+d^3的等式被称为完美立方等式。例如12^3=6^3+8^3+10^3。编写一个程序，对任给的正整数N(N≤100)，寻找所有的四元组(a，b，c，d)，使得a^3=b^3+c^3+d^3，其中1 < a,b,c,d ≤ N，且b ≤ c ≤ d。

Input

一个正整数N (N ≤ 100)。

Output

每行输出一个完美立方。输出格式为：Cube = a，Triple =(b,c,d)其中a，b，c，d所在位置分别用实际求出四元组值代入。

请按照a的值，从小到大依次输出。当两个完美立方等式中a的值相同，则b值小的优先输出、仍相同则c值小的优先输出、再相同则d值小的先输出。

Sample Input

24

Sample Output

Cube=6, Triple=(3,4,5)
Cube=12, Triple=(6,8,10)
Cube=18, Triple=(2,12,16)
Cube=18, Triple=(9,12,15)
Cube=19, Triple=(3,10,18)
Cube=20, Triple=(7,14,17)
Cube=24, Triple=(12,16,20)

该题较为简单，通过枚举所有情况即可求解。

采用四重循环枚举a，b，c，d，其中a在最外层，d在最里层，每一层都是从小到大枚举

为了减少不可能是正确解的枚举次数，应使

a的枚举范围为 [2,N];

b的枚举范围为 [2,a-1];

c的枚举范围为 [b,a-1];

d的枚举范围为 [c,a-1];

代码如下：

void PerfectCube(int N) {
    for (int a = 2; a <= N; ++a) {
        for (int b = 2; b < a; ++b) {
            for (int c = b; c < a; ++c) {
                for (int d = c; d < a; ++d) {
                    if (pow(a, 3) == pow(b, 3) + pow(c, 3) + pow(d, 3)) {
                        printf("Cube=%d, Triple=(%d,%d,%d)\n", a, b, c, d);
                    }
                }
            }
        }
    }
}

第三题：生理周期

Description

人有体力、情商、智商的高峰日子，它们分别每隔23天、28天和33天出现一次。对于每个人，我们想知道何时三个高峰落在同一天。给定三个高峰出现的日子physical，emotion和intelligence (不一定是第一次高峰出现的日子) 再给定另一个指定的日子day，你的任务是输出日子day之后，下一次三个高峰落在同一天的日子 (用距离day的天数表示)。例如: 给定日子为10，下次出现三个高峰同一天的日子是12，则输出2。

Input

输入四个整数：physical，emotion，intelligence和day。physical，emotion，intelligence分别表示体力、情感和智力高峰出现的日子。day是给定的日子，可能小于physical，emotion或intelligence。所有给定日子是非负的并且小于或等于365，所求的日子小于或等于21252。

Output

从给定日子day起，距离下一次体力、情感和智力高峰同一天的天数。

Sample Input

(0, 0, 0, 0)
(0, 0, 0, 100)
(5, 20, 34, 325)
(4, 5, 6, 7)
(283, 102, 23, 320)
(203, 301, 203, 40)

Sample Output

the next triple peak occurs in 21252 days.
the next triple peak occurs in 21152 days.
the next triple peak occurs in 19575 days.
the next triple peak occurs in 16994 days.
the next triple peak occurs in 8910 days.
the next triple peak occurs in 10789 days.

_

该题可以从day+1天开始，枚举至第21252天，对其中每一个日期count判断是否满足题中要求，即是否满足：

((count - physical) % 23 == 0 && (count - emotion) % 23 == 0 && (count - intelligence) % 23 == 0) 

但count的中由许多明显不满足题目条件的情况，

如：

• 体力高峰到达一次后下次到达是在23天之后，所以要求满足体力高峰的情况下到达情感高峰的天数时count的递增步数应为23。
• 同理当满足体力高峰、情感高峰日子的同时，求再满足智商高峰日子时，count的递增步数应为23、28的最小公倍数23*28。
• 综上，按此方法跳着尝试判断count是否满足条件时，可以剪去很多明确的错解的分枝。

所以代码描述如下：

void CircadianCycle(int physical, int emotion, int intelligence, int day) {
    int count;
    for (count = day + 1; (count - physical) % 23; count++); //找到第一个体力高峰。
    for (; (count - emotion) % 28; count += 23);            //找到下一个体力、情感双高峰。
    for (; (count - intelligence) % 33; count += 23 * 28);     //在双高峰的基础上找到智力高峰，即为所求。
    printf("(%3d,%3d,%3d,%3d) -> the next triple peak occurs in %d days.\n", physical, emotion, intelligence, day,
           count - day);
}

• 二三题的枚举方法在题目中体现的较为直观，第一题体现的并不直观，应详细分析后再枚举。

                                    by Ss1Two 2023/01/04