枚举算法

枚举算法（穷举法）：按照问题本身的性质，一一列举该问题所有可能解，并在逐一列举的过程中，检验每个可能解是否是问题的真正解。

  • 是，采纳这个解。
  • 不是，抛弃这个解。

在列举的过程中不能遗漏也不能重复，遗漏会造成算法求解结果的不正确，重复会显著降低算法执行效率。

枚举算法的以下三个突出特点：

  1. 解的高准确性和全面性：
    1. 检验问题的每一种可能情况；
    2. （时间足够）枚举算法的答案肯定是正确的；
    3. 能方便求解出问题的所有解。
  2. 实现简单：通过循环for来逐一列举和验证。
  3. 效率提升空间大。

“枚举三步”：

  1. 确定枚举对象；
  2. 逐一列举可能解；
  3. 逐一验证可能解。

模糊数字

百位缺失

问题分析

1⃣确定枚举对象

在该五位数编码中，只有百位数模糊不清，百位数字只能是 0∼90 \sim 9 中的某一个数字。

⇒\Rightarrow 选择百位数作为枚举对象。

2⃣逐一列举可能解

将百位数字 h∈{0,1,2,3,4,5,6,7,8,9}h \in\{0,1,2,3,4,5,6,7,8,9\} 和问题中的其他已知 44 位数字组成完整的 55 位数编码 vv 作为可能解。

3⃣逐一验证可能解

验证五位数 vv 能否同时被 5757 和 6767 整除。

算法设计与实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <cstdio>

int main()
{
    int iValue, d5, d4, d2, d1, h;
    int iResult[10];
    scanf("%d %d %d %d", &d5, &d4, &d2, &d1);
    while (d5 != -1)
    {
        int iCount = 0;
        for (int h = 0; h < 10; h++)
        {
            iValue = 10000 * d5 + 1000 * d4 + 100 * h + 10 * d2 + d1;
            if ((iValue % 57 == 0) && (iValue % 67 == 0))
                iResult[iCount++] = iValue;
        }
        printf("%d", iCount);
        for (int i = 0; i < iCount; i++)
            printf(" %d", iResult[i]);
        printf("\r\n");
        scanf("%d %d %d %d", &d5, &d4, &d2, &d1);
    }
    return 0;
}

万位和百位缺失

1⃣确定枚举对象

在该五位数编码中，万位数字和百位数字都模糊不清，这两位数字只能是 0∼90 \sim 9 中的某一个数字。

⇒\Rightarrow 选择万位数字和百位数字作为枚举对象。

2⃣逐一列举可能解

  • 万位数字 h1∈{0,1,2,3,4,5,6,7,8,9}h_1 \in\{0,1,2,3,4,5,6,7,8,9\}
  • 百位数字 h2∈{0,1,2,3,4,5,6,7,8,9}h_2 \in\{0,1,2,3,4,5,6,7,8,9\}
  • 问题中的其他已知33位数字

和问题中的其他已知 44 位数字组成完整的 55 位数编码 vv 作为可能解。

3⃣逐一验证可能解

验证五位数 vv 能否同时被 5757 和 6767 整除。

算法设计与实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <cstdio>

int main()
{
    int iValue, d5, d4, d2, d1, h;
    int iResult[10];
    scanf("%d %d %d %d", &d5, &d4, &d2, &d1);
    while (d5 != -1)
    {
        int iCount = 0;
        for (int h1 = 0; h1 < 10; h1++)
        {
            for (int h2 = 0; h2 < 10; h2++)
                iValue = 10000 * h1 + 1000 * d4 + 100 * h2 + 10 * d2 + d1;
            if ((iValue % 57 == 0) && (iValue % 67 == 0))
                iResult[iCount++] = iValue;
        }
        printf("%d", iCount);
        for (int i = 0; i < iCount; i++)
            printf(" %d", iResult[i]);
        printf("\r\n");
        scanf("%d %d %d %d", &d5, &d4, &d2, &d1);
    }
    return 0;
}

m 钱买 n 鸡

问题分析

1⃣确定枚举对象

任何一个购买方案都会包含鸡翁、鸡母、鸡雏的数目 n1、n2、n3n1、n2、n3，且任意一种类型的鸡数目不能超过 nn。

⇒\Rightarrow 枚举对象用三元组 (n1,n2,n3)(n_1,n_2,n_3)，且 0⩽n1,n2,n3⩽n0 \leqslant n_{1}, n_{2}, n_{3} \leqslant n 表示

2⃣逐一列举可能解

0⩽n1,n2,n3⩽n0 \leqslant n_{1}, n_{2}, n_{3} \leqslant n

3⃣逐一验证可能解

n1+n2+n3=nn_1+n_2+n_3=n 且 5n1+3n2+n33=m5 n_{1}+3 n_{2}+\frac{n_3}{3}=m

算法设计与实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <cstdio>

int main()
{
    int N, M, n1, n2, n3;
    scanf("%d %d", &N, &M);
    while (N != -1)
    {
        int iCount = 0;
        for (n1 = 0; n1 <= N; n1++)
            for (n2 = 0; n2 <= N; n2++)
                for (n3 = 0; n3 <= N; n3++)
                    if ((n1 + n2 + n3 == N) && (5 * n1 + 3 * n2 + n3 / 3.0 == M))
                        iCount++;
        printf("%d", iCount);
        printf("\r\n");
        scanf("%d %d", &N, &M);
    }
    return 0;
}

上面代码时间复杂度 O(n3)O\left(n^{3}\right)，当输入的规模增大，时间也会增大，进一步缩小范围：

  • 购买鸡翁的数目不可能超过 m/5m / 5，0⩽n1⩽m/50 \leqslant n_{1} \leqslant m / 5
  • 购买鸡母的数目不可能超过 m/3m/3，0⩽n2⩽m/30 \leqslant n_{2} \leqslant m / 3
  • 当鸡翁和鸡母的数目确定之后，鸡雏的数目也唯一确定，n3=n−n1−n2n_3=n-n_1-n_2

算法时间复杂度减少为O(n2)O\left(n^{2}\right)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <cstdio>

int main()
{
    int N, M, n1, n2, n3;
    scanf("%d %d", &N, &M);
    while (N != -1)
    {
        int iCount = 0;
        for (n1 = 0; n1 <= M / 5; n1++)
            for (n2 = 0; n2 <= M / 3; n2++)
            {
                n3 = N - n1 - n2;
                if (5 * n1 + 3 * n2 + n3 / 3.0 == M)
                    iCount++;
            }
        printf("%d", iCount);
        printf("\r\n");
        scanf("%d %d", &N, &M);
    }
    return 0;
}

真假银钱

问题分析

1⃣确定枚举对象

从三组数据中得到唯一答案，答案的两个要素：

  1. 假币标号 ss ：s∈{A,B,⋯ ,L}s \in\{\text {A,} \text {B}, \cdots, \text {L}\}
  2. 假币比真币轻还是重 bb：b∈{light,heavy,true}b \in\{\text {light}, \text {heavy}, \text {true}\}
  • light\text {light}：假币比真币轻；
  • heavy\text {heavy}：假币比真币重；
  • true\text {true}：银币为真。

⇒\Rightarrow 枚举对象用二元组 (s,b)(s,b) 表示

2⃣逐一列举可能解

3⃣逐一验证可能解

与输入的 33 组称重数据进行比对，存在一组或一组以上的矛盾，不是问题的解。

如果都不矛盾，是问题的真正解，更具体的：

  1. even\text {even} 情况下，两边的天平都没有出现 ss；
  2. 如果 b=lightb=\text {light}：
    1. 称量结果为 up\text {up} 的天平右边出现 ss
    2. 称量结果为 down\text {down} 的天平左边出现 ss
  3. 如果 b=heavyb=\text {heavy}：
    1. 称量结果为 up\text {up} 的天平左边出现 ss
    2. 称量结果为 down\text {down} 的天平右边出现 ss

算法设计与实现

选择合适的算法

  • ss 比真币轻的猜测是否成立？猜测成立则进行输出；
  • ss 比真币重的猜测是否成立？猜测成立则进行输出；
  • 如果上述两种猜测都不成立，则表明 ss 是真币，继续验证下一个银币。

选择合适的数据结构

  • 用字符串数组存储每次称量的结果
  • 天平左右每次最多有 66 枚银币 ⇒ 字符串长度最多为 77（6+1=76+1=7）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
#include <cstring>

char left[3][7], right[3][7], result[3][5];

bool isLight(char);
bool isHeavy(char);

// 判断当前字符对应银币是否为假币，且比真币轻
bool isLight(char curChar)
{

    for (int i = 0; i < 3; i++)
    {
        switch (result[i][0])
        {
        case 'u': // 右端高 右端没有curChar
            if (strchr(right[i], curChar) == NULL)
                return false;
            break;
        case 'e': // 平衡 左端有或者右端有curChar
            if ((strchr(right[i], curChar) != NULL) || (strchr(left[i], curChar) != NULL))
                return false;
            break;
        case 'd': // 右端低 左端没有curChar
            if (strchr(left[i], curChar) == NULL)
                return false;
            break;
        }
    }
    return true;
}

// 判断当前字符对应银币是否为假币，且比真币重
bool isHeavy(char curChar)
{
    for (int i = 0; i < 3; i++)
    {
        switch (result[i][0])
        {
        case 'u': // 右端高 左端没有curChar
            if (strchr(left[i], curChar) == NULL)
                return false;
            break;
        case 'e': // 平衡 左端有或者右端有curChar
            if ((strchr(right[i], curChar) != NULL) || (strchr(left[i], curChar) != NULL))
                return false;
            break;
        case 'd': // 右端低 右端没有curChar
            if (strchr(right[i], curChar) == NULL)
                return false;
            break;
        }
    }
    return true;
}

int main()
{
    int n;
    scanf("%d", &n);
    while (n--)
    {
        for (int i = 0; i < 3; i++) // 读入该次测量中的三组测试数据 包括左右两边银币编号以及结果
            scanf("%s %s %s", left[i], right[i], result[i]);
        for (char curChar = 'A'; curChar <= 'L'; curChar++)
        { // 枚举每一个银币的标号A~L
            if (isLight(curChar))
            {
                printf("%c %s", curChar, "light");
                printf("\r\n");
                break;
            }
            if (isHeavy(curChar))
            {
                printf("%c %s", curChar, "heavy");
                printf("\r\n");
                break;
            }
        }
    }
    return 0;
}