Lesson 22: 猜数游戏 CNB

练习任务

实现一个经典的 猜数游戏（Bulls and Cows / Mastermind 变体）：计算机随机生成一个 4 位不重复数字，玩家每次输入 4 位数字进行猜测，程序返回 ?A?B 格式的反馈，直到猜中为止。

提示：这个问题可以拆解为三个独立模块——生成不重复随机数、比较两个数组得到 ?A?B、以及用循环串联起来的游戏主控。先从最简单的模块入手，逐个击破。

核心知识点

伪随机数 — rand() 的底层原理：线性同余生成器 (LCG)，种子与可复现性
srand() / 播种 — 用 time(NULL) 让每次运行产生不同序列
do-while 循环 — 先执行后判断，与 while 的区别及适用场景
used[] 数组标记 — 用数组标记已使用元素，实现"不重复"约束
双重循环 — 外层遍历猜测，内层遍历答案，实现 ?A?B 的 B 计数逻辑
指针参数 — 通过 int *a, int *b 从函数"返回"多个值
fgets() 输入 — 读取字符串、处理换行符、与 scanf 的对比
字符串解析 — char 到 int 的转换 (s[i] - '0')，输入验证
游戏主循环 — while (1) + break 构成的交互式循环结构
二分查找策略 — 用二分思想优化猜测过程，从 10000 种可能中快速收敛
信息论视角 — 每次猜测能获得多少信息？最少需要几次猜测？

代码框架

guess.c

#include <stdio.h>
#include <string.h>

/* 平台无关的伪随机数生成器 (Linear Congruential Generator) */
static unsigned int _seed = 42;
int my_rand(void) { _seed = _seed * 1103515245 + 12345; return (_seed >> 16) & 0x7fff; }

// 生成 4 位不重复随机数，存入 secret[4]
static void generate_secret(int secret[4])
{
    // 在这里用 used[10] 数组 + do-while 生成不重复数字
}

// 比较 guess 和 secret，通过指针返回 ?A?B
static void check(const int secret[4], const int guess[4], int *a, int *b)
{
    // 在这里实现双重循环比较逻辑
}

// 将字符串 s 解析为 4 位数字数组 guess[4]
static int parse_guess(const char *s, int guess[4])
{
    // 在这里实现字符串解析和输入验证
}

int main(void)
{
    // 在这里实现完整的游戏循环
    return 0;
}

请先尝试根据代码框架中的注释自己填充各个函数，尤其注意 do-while 的适用场景和双重循环中 B 的计算逻辑。完成后可以对照下文的深度讲解和参考解答来验证你的实现。

先不要往下翻看参考解答

自己动手实现后，再看深度讲解中的分析和参考解答代码，学习效果最好。建议先完成 22a（生成）、22b（比较）、22c（完整循环）三个子练习。

深度讲解

1. 伪随机数：从 `rand()` 到底层原理

在编写猜数游戏之前，首先要解决的问题是：如何让程序"随机"生成一个 4 位数？

1.1 计算机能产生真正的随机数吗？

计算机是一台确定性机器——给定相同的输入，必然产生相同的输出。因此，计算机无法产生真正的随机数。我们所用的 rand() 实际上是伪随机数生成器（Pseudo-Random Number Generator, PRNG）：它通过一个确定性的数学公式，从一个初始值（称为种子，seed）出发，生成一个看起来"随机"的数字序列。

这就像一本巨大的随机数表：如果你每次都从同一页开始读，你每次读到的数字序列都一模一样。srand() 的作用就是指定从哪一页开始读——即设置种子。

1.2 线性同余生成器 (LCG)

C 标准库中的 rand() 通常使用线性同余生成器（Linear Congruential Generator），其核心公式为：

X_{n+1} = (a × X_n + c) mod m

其中 a、c、m 是精心选择的常数。每次调用 rand() 时，内部状态按此公式更新，然后从更新后的状态中截取一部分位作为返回值。

在本课的练习中，我们使用了一个平台无关的 LCG 实现：

my_rand.c

static unsigned int _seed = 42;

int my_rand(void)
{
    _seed = _seed * 1103515245 + 12345;
    return (_seed >> 16) & 0x7fff;
}

让我们逐行理解这段代码：

行	作用
`_seed = 42`	初始种子。固定种子意味着每次运行产生相同的随机数序列——这对练习验证至关重要
`_seed * 1103515245 + 12345`	LCG 的核心递推公式：`a = 1103515245`, `c = 12345`, `m = 2^31`（隐式，因为 `unsigned int` 溢出会自动取模）
`_seed >> 16`	取中间 16 位。为什么不直接返回 `_seed`？因为低位的随机性较差（周期性短），高位更好
`& 0x7fff`	确保返回值在 `[0, 32767]` 范围内，且为非负数

NOTE

_seed >> 16 取高位是一个经典技巧。LCG 的低位比特周期性很差——最低位只在 0 和 1 之间交替。取高位可以获得更好的随机性。这也是为什么 glibc 的 rand() 只返回低 31 位中的一部分。

1.3 `srand()` 与 `time(NULL)`

在实际应用中，我们希望每次运行程序产生不同的随机序列，所以需要用随时间变化的量来播种：

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

srand(time(NULL));  // 用当前时间（秒级）作为种子
int x = rand();      // 现在每次运行结果不同

time(NULL) 返回自 1970-01-01 00:00:00 UTC 以来的秒数。因为每次运行程序的时间不同，种子不同，随机序列也就不同。

WARNING

不要在循环内部反复调用 srand()！种子只需要设置一次。如果在循环中每次调用 srand(time(NULL))，由于 time(NULL) 在秒级不变化，你会反复获得相同的"随机数"。

srand_bad.c

// 错误示范：在循环内反复播种
for (int i = 0; i < 10; i++) {
    srand(time(NULL));
    printf("%d\n", rand());
}
// 输出：10 个相同的数字！

1.4 `rand() % N` 的模运算

要获得 0 到 9 之间的随机数，我们使用：

int d = rand() % 10;  // [0, 9]

% 是取模运算符，rand() % 10 返回 rand() 除以 10 的余数，范围是 0 到 9。

WARNING

rand() % N 存在微小的偏差问题。当 N 不能整除 RAND_MAX 时，较小的余数出现的概率略微偏高。对于游戏场景这种偏差可以忽略，但在密码学或科学模拟中应使用更严格的随机数生成方法。

2. `do-while` 与 `used[]` 去重：生成不重复的 4 位数字

2.1 问题分析

猜数游戏要求生成的 4 位数字互不相同——不允许出现 "1123" 这样的重复数字。这意味着：

生成第 1 位：从 0-9 中任选，无限制
生成第 2 位：从 0-9 中选，但不能等于第 1 位
生成第 3 位：不能等于前两位
生成第 4 位：不能等于前三位

核心问题是：如何高效地"记住"哪些数字已经用过了？

2.2 `used[]` 数组标记法

用一个大小为 10 的数组 used[10]，初始全为 0。当数字 d 被选中后，设置 used[d] = 1：

used_concept.c

int used[10] = {0};   // 全部初始化为 0，表示都未使用

used[3] = 1;           // 数字 3 已被使用
used[7] = 1;           // 数字 7 已被使用

// 检查数字 3 是否可用：
if (used[3] == 0) {
    // 数字 3 还没被用过，可以使用
}

数组下标直接对应数字本身——这是一种非常高效的 O(1) 查找方案。

2.3 `do-while`：先执行后判断

do-while 循环的语义是：先执行循环体，再判断条件。这恰好适合"不断生成随机数直到遇到一个未使用的数字"这种场景：

do {
    d = rand() % 10;     // 先随机生成一个数字
} while (used[d]);       // 如果这个数字已被用过，就再来一次

为什么用 do-while 而不是 while？因为我们至少需要生成一次——不能在不生成任何数字的情况下就去判断 used[d]（此时 d 尚未初始化）。

对比两种写法：

while_vs_dowhile.c

// do-while：简洁自然
int d;
do {
    d = rand() % 10;
} while (used[d]);

// 等价的 while 写法：需要先初始化 d 为已使用状态
int d = 0;
while (used[d]) {
    d = rand() % 10;
}
// 问题：如果 used[0] == 0，循环体一次都不执行，d 保持为 0

TIP

do-while 适用于"至少执行一次"的场景。典型应用包括：输入验证（至少读一次）、随机数去重（至少生成一次）、菜单循环（至少显示一次）。

2.4 完整实现

generate_secret.c

static void generate_secret(int secret[4])
{
    int used[10] = {0};
    for (int i = 0; i < 4; i++) {
        int d;
        do {
            d = my_rand() % 10;
        } while (used[d]);
        secret[i] = d;
        used[d] = 1;
    }
}

执行流程追踪（假设种子 42）：

步骤	i	生成 d	used[d]?	操作	used 状态
1	0	1	0	`secret[0]=1, used[1]=1`	`[0,1,0,0,0,0,0,0,0,0]`
2	1	3	0	`secret[1]=3, used[3]=1`	`[0,1,0,1,0,0,0,0,0,0]`
3	2	9	0	`secret[2]=9, used[9]=1`	`[0,1,0,1,0,0,0,0,0,1]`
4	3	1	1 → 重试	重新生成	—
4'	3	6	0	`secret[3]=6, used[6]=1`	`[0,1,0,1,0,0,1,0,0,1]`

最终 secret = {1, 3, 9, 6}，4 个数字互不相同。

3. 双重循环与 ?A?B 逻辑

3.1 游戏规则

Bulls and Cows（公牛和母牛）是一种经典的猜数字游戏：

A（位置和数字都对）：猜的数字在正确的位置上
B（数字对但位置不对）：猜的数字存在于答案中，但位置错误

例如，secret = {1, 3, 9, 6}，guess = {1, 3, 2, 5}：

位置	secret	guess	结果
0	1	1	A — 位置和数字都对
1	3	3	A — 位置和数字都对
2	9	2	无 — 2 不在答案中
3	6	5	无 — 5 不在答案中

结果：2A0B

再看 guess = {3, 1, 9, 8}：

位置	secret	guess	结果
0	1	3	B — 3 在位置 1，但猜在位置 0
1	3	1	B — 1 在位置 0，但猜在位置 1
2	9	9	A — 位置和数字都对
3	6	8	无 — 8 不在答案中

结果：1A2B

3.2 A 的计算：单层循环

A 的计算很简单——逐个位置比较：

*a = 0;
for (int i = 0; i < 4; i++) {
    if (guess[i] == secret[i]) {
        (*a)++;
    }
}

3.3 B 的计算：双重循环 + 排除 A

B 的计算更复杂：对于每个位置不对的 guess 数字，在 secret 中寻找相同数字：

*b = 0;
for (int i = 0; i < 4; i++) {
    if (guess[i] == secret[i]) {
        (*a)++;   // 位置对 → 算 A，不算 B
    } else {
        for (int j = 0; j < 4; j++) {
            if (guess[i] == secret[j]) {
                (*b)++;
                break;  // 找到一个就够了
            }
        }
    }
}

IMPORTANT

关键细节：只有当 guess[i] != secret[i] 时才进入 B 的判断。如果 guess[i] == secret[i]，它已经被计入 A，不应再计入 B。这是 if-else 分支的核心意义。

3.4 为什么用指针参数？

check() 需要返回两个值（A 和 B），但 C 语言的 return 只能返回一个值。解决方案是通过指针参数：

void check(const int secret[4], const int guess[4], int *a, int *b)
{
    *a = *b = 0;
    // ...
    (*a)++;  // 通过解引用修改调用者传入的变量
}

调用时传入地址：

int a, b;
check(secret, guess, &a, &b);
printf("%dA%dB\n", a, b);  // a 和 b 已被 check 修改

回顾 Lesson 06 中学到的：指针参数是实现"输出参数"的标准手段。const int secret[4] 中的 const 表明该数组不会被修改——这是只读输入参数。

3.5 内层 `break` 的必要性

内层循环中的 break 至关重要。考虑以下场景：

secret = {1, 3, 9, 6}
guess  = {3, 1, 1, 8}

当 i = 2（guess[2] = 1）时，内层循环在 secret 中搜索数字 1：

j = 0：secret[0] = 1，匹配！(*b)++，break

如果没有 break，内层循环会继续：

j = 1：secret[1] = 3，不匹配
j = 2：secret[2] = 9，不匹配
j = 3：secret[3] = 6，不匹配

在这个例子中没有问题，但如果有重复的 guess 数字，没有 break 可能导致 B 被重复计数。

4. 字符串解析与输入处理

4.1 为什么用 `fgets()` 而不是 `scanf()`？

本课使用 fgets() 读取用户输入，而非此前常用的 scanf()。原因：

特性	`fgets()`	`scanf("%d")`
读取内容	整行字符串（含空格）	格式化数据
缓冲区溢出保护	有（需指定大小）	无
错误处理	需要手动解析	自动转换
灵活性	高，可以自定义解析逻辑	低，格式固定
处理非预期输入	可控	容易陷入无限循环

对于"4 位数字"这种输入，我们需要验证长度和每个字符的范围，fgets() + 手动解析是更好的选择。

4.2 `fgets()` 的基本用法

char input[16];
fgets(input, sizeof(input), stdin);

fgets() 读取一行（包括换行符 \n），存入 input。如果输入超过缓冲区大小，多余部分留在输入流中。

4.3 字符串转数字数组

parse_guess.c

static int parse_guess(const char *s, int guess[4])
{
    // 1. 检查长度：至少需要 4 个数字字符
    int len = strlen(s);
    if (len < 4) return 0;

    // 2. 逐字符转换
    for (int i = 0; i < 4; i++) {
        if (s[i] < '0' || s[i] > '9') return 0;  // 非数字字符
        guess[i] = s[i] - '0';
    }
    return 1;  // 解析成功
}

关键技巧：s[i] - '0' 将字符 '0'-'9' 转换为整数 0-9。这是因为 ASCII 编码中，'0' 到 '9' 是连续排列的（码点 48-57），相减恰好得到数值。

char_to_int.c

char c = '7';
int n = c - '0';  // n = 7

// ASCII 码表：
// '0' = 48, '1' = 49, ..., '9' = 57
// '7' - '0' = 55 - 48 = 7

NOTE

C 标准保证 '0' 到 '9' 的字符码点是连续的，因此 c - '0' 是可移植的标准做法。

4.4 更完善的输入验证

实际游戏中，用户可能输入各种奇怪的内容——空格、字母、超长字符串。一个健壮的 parse_guess 需要考虑：

parse_guess_robust.c

static int parse_guess(const char *s, int guess[4])
{
    int len = strlen(s);

    // 去除末尾换行符
    if (len > 0 && s[len - 1] == '\n') len--;

    // 恰好 4 个字符
    if (len != 4) {
        printf("Please enter exactly 4 digits.\n");
        return 0;
    }

    for (int i = 0; i < 4; i++) {
        if (s[i] < '0' || s[i] > '9') {
            printf("Invalid character '%c'.\n", s[i]);
            return 0;
        }
        guess[i] = s[i] - '0';
    }
    return 1;
}

5. 游戏主循环：`while (1)` + `break`

5.1 交互式循环结构

猜数游戏需要一个交互式循环：反复读取输入、计算反馈、判断是否猜中。这本质上是 Lesson 05 中学到的循环结构的应用，但增加了用户输入这一交互维度：

game_loop.c

int main(void)
{
    int secret[4];
    int guess[4];
    int a, b;
    int attempts = 0;
    char input[16];

    generate_secret(secret);

    while (1) {                              // 无限循环
        printf("Enter your guess: ");
        fgets(input, sizeof(input), stdin);

        if (!parse_guess(input, guess))      // 输入无效则跳过
            continue;

        attempts++;
        check(secret, guess, &a, &b);
        printf("%dA%dB\n", a, b);

        if (a == 4) {                        // 4A0B = 完全猜对
            printf("Congratulations! "
                   "You got it in %d attempts!\n", attempts);
            break;                           // 退出循环
        }
    }

    printf("The secret was: %d%d%d%d\n",
           secret[0], secret[1], secret[2], secret[3]);
    return 0;
}

IMPORTANT

while (1) 创建了一个无限循环。退出循环的唯一方式是 break。这种模式在交互式程序（游戏、命令行工具、服务器）中非常常见，因为"结束条件"由用户行为决定，而非固定的循环次数。

5.2 `continue` 的妙用

当 parse_guess 返回 0（输入无效）时，使用 continue 跳过本次循环的剩余部分，回到 while 开头重新读取输入。这样无效输入不会增加 attempts 计数。

5.3 流程图

      ┌──────────────┐
      │ 生成 secret   │
      └──────┬───────┘
             │
      ┌──────▼───────┐
      │ 读取输入      │◄─────────────────┐
      └──────┬───────┘                    │
             │                            │
      ┌──────▼───────┐    无效            │
      │ 解析输入      ├───────────────────┘
      └──────┬───────┘
             │ 有效
      ┌──────▼───────┐
      │ attempts++   │
      │ check()      │
      │ 打印 ?A?B    │
      └──────┬───────┘
             │
      ┌──────▼───────┐
      │ a == 4 ?     │
      └──┬───────┬───┘
    否   │       │ 是
         │  ┌────▼────┐
         └──► 打印祝贺 │
            │ break   │
            └────┬────┘
                 │
          ┌──────▼───────┐
          │ 打印 secret   │
          └──────────────┘

5.4 完整数据流追踪

以一次完整的游戏过程为例，追踪数据在各函数之间的流动。假设 secret = {1, 3, 9, 6}，玩家输入 "1325"：

main()                         generate_secret()
  │                                  │
  │  generate_secret(secret) ───────►│
  │                                  │  secret = {1,3,9,6}
  │◄─────────────────────────────────┘
  │
  │  while (1) {
  │    fgets → input = "1325\n"
  │    parse_guess("1325\n", guess)
  │      │
  │      │  len = strlen("1325\n") = 5
  │      │  len-- (去掉 \n) → len = 4
  │      │  guess[0] = '1' - '0' = 1
  │      │  guess[1] = '3' - '0' = 3
  │      │  guess[2] = '2' - '0' = 2
  │      │  guess[3] = '5' - '0' = 5
  │      │  return 1 (解析成功)
  │      │
  │    attempts = 1
  │    check(secret, guess, &a, &b)
  │      │
  │      │  i=0: guess[0]=1, secret[0]=1 → A=1
  │      │  i=1: guess[1]=3, secret[1]=3 → A=2
  │      │  i=2: guess[2]=2, secret≠2
  │      │        j=0..3: 都不匹配 → B不变
  │      │  i=3: guess[3]=5, secret≠5
  │      │        j=0..3: 都不匹配 → B不变
  │      │  结果: a=2, b=0
  │      │
  │    printf("2A0B\n")
  │    a != 4 → 继续循环
  │  }

这种逐步骤追踪的方法（称为 desk check 或手工执行）是调试程序的必备技能。当你对某段代码的行为有疑问时，拿出一张纸，逐行模拟计算机执行，往往能快速定位问题。

6. 二分查找策略：用算法优化猜测

6.1 信息论视角

每次猜测获得的反馈（?A?B）包含信息。从信息论的角度看：

4 位不重复数字共有 10 × 9 × 8 × 7 = 5040 种可能（不是 10000！因为数字不重复）
每次反馈（如 "1A2B"）将可能空间划分为多个子集
理想情况下，每次猜测将剩余可能性减半，约需 log2(5040) ≈ 12.3 次

6.2 简单二分策略

如果我们将可能的 4 位数按大小排序，可以用二分查找的思想逐步逼近：

binary_guess_strategy.c

// 策略：维护一个可能答案的范围 [low, high]
// 每次取中间值猜测，根据反馈调整范围

int low = 0;
int high = 9999;

while (1) {
    int mid = (low + high) / 2;
    // 将 mid 转为 4 位数字数组并猜测
    // 如果反馈是 4A0B → 猜对
    // 根据 A+B 的数量调整 low 或 high
}

NOTE

二分法在猜数游戏中并非最优策略，因为 ?A?B 的反馈比简单的"大了/小了"包含更多信息。真正的最优策略需要维护所有可能答案的集合，每次选择能最大化期望信息增益的猜测。这属于更高级的算法范畴，感兴趣的读者可以课后研究 Knuth 的 Mastermind 算法。

6.3 最坏情况分析

即使采用最简单的随机猜测策略：

最坏情况：5040 次猜测（每次排除一个错误答案）
平均情况：约 2520 次猜测
采用启发式策略后：通常在 5-8 次内猜中

这说明好的策略可以带来数量级的效率提升——算法思维的价值所在。

6.4 常见错误：检查中的边界条件

在实现 ?A?B 算法时，有几个容易出错的细节：

错误 1：内层循环未 break

check_no_break_bug.c

// 错误：没有 break
for (int j = 0; j < 4; j++) {
    if (guess[i] == secret[j]) {
        (*b)++;    // 可能对同一个 guess[i] 多次匹配
    }
}

如果 secret = {1, 2, 1, 3}，guess = {1, 4, 5, 6}（虽然允许重复时才会出现），guess[0] = 1 会匹配 secret[0] 和 secret[2]，导致 B 被错误地计数 2 次。

错误 2：A 和 B 的判断顺序颠倒

check_order_bug.c

// 错误：先检查 B，再检查 A
if (guess[i] == secret[j]) (*b)++;  // 可能把 A 算成 B
if (guess[i] == secret[i]) (*a)++;

当 guess[i] == secret[i] 时，内层循环的 j=i 也会匹配，导致该位置既算 A 又算 B。

正确做法：先检查 guess[i] == secret[i]（A），只有不相等时才进入 B 的内层搜索。

错误 3：*a 和 *b 未初始化

check_uninit_bug.c

void check(..., int *a, int *b) {
    // 忘记写 *a = *b = 0;
    for (...) { (*a)++; ... }  // *a 的初始值是垃圾值！
}

忘记初始化会导致 A 和 B 从一个随机的"垃圾值"开始累加，输出不可预测的结果。

CAUTION

局部变量不会自动初始化为 0！C 标准规定：具有自动存储期的变量（局部非 static 变量）若未显式初始化，其值是未定义的（indeterminate）。这就是为什么 *a = *b = 0 这一行必不可少。

7. 内存视角：数组与栈帧

7.1 函数调用中的数组传递

当我们将数组传递给函数时，传递的实际上是数组首元素的地址：

array_pass.c

void generate_secret(int secret[4])  // 等价于 int *secret
{
    secret[0] = 1;  // 修改的是调用者的数组
}

int secret[4] 作为函数参数时，实际上被编译器解释为 int *secret——这和 Lesson 06 中学到的数组退化是一致的。

7.2 栈帧布局

在 main() 调用 check() 时，栈帧布局大致如下：

高地址
┌────────────────────┐
│ main 的栈帧         │
│   secret[4]        │  ← 4 个 int = 16 字节
│   guess[4]         │  ← 4 个 int = 16 字节
│   a, b             │  ← 2 个 int = 8 字节
│   input[16]        │  ← 16 个 char = 16 字节
│   attempts         │  ← 1 个 int = 4 字节
├────────────────────┤
│ check 的栈帧        │
│   参数: secret*    │  ← 8 字节（64 位指针）
│   参数: guess*     │  ← 8 字节
│   参数: a*         │  ← 8 字节（指向 main 中 a 的指针）
│   参数: b*         │  ← 8 字节（指向 main 中 b 的指针）
│   局部变量: i, j   │
└────────────────────┘
低地址

NOTE

check() 中的 (*a)++ 通过指针直接修改了 main() 栈帧中的 a 变量。这就是指针作为"输出参数"的内存原理。

参考解答

22a：生成不重复 4 位随机数

22a 参考解答

22a_generate.c

#include <stdio.h>

/* 平台无关的伪随机数生成器 (Linear Congruential Generator) */
static unsigned int _seed = 42;
int my_rand(void) { _seed = _seed * 1103515245 + 12345; return (_seed >> 16) & 0x7fff; }

void generate_secret(int secret[4])
{
    int used[10] = {0};
    for (int i = 0; i < 4; i++) {
        int d;
        do {
            d = my_rand() % 10;
        } while (used[d]);
        secret[i] = d;
        used[d] = 1;
    }
}

int main(void)
{
    int secret[4];
    int i;

    generate_secret(secret);

    for (i = 0; i < 4; i++)
        printf("%d", secret[i]);
    printf("\n");

    return 0;
}

解析：核心在于 used[10] 数组的标记策略。每次用 do-while 生成一个随机数后，检查 used[d]——如果已被占用就重新生成。生成成功后，将 used[d] 设为 1，确保该数字不会再次被选中。{0} 初始化将数组全部清零，省去了手动赋值的麻烦。

22b：计算 ?A?B

22b 参考解答

22b_check.c

#include <stdio.h>

void check(const int secret[4], const int guess[4], int *a, int *b)
{
    *a = *b = 0;
    for (int i = 0; i < 4; i++) {
        if (guess[i] == secret[i]) {
            (*a)++;
        } else {
            for (int j = 0; j < 4; j++) {
                if (guess[i] == secret[j]) {
                    (*b)++;
                    break;
                }
            }
        }
    }
}

int main(void)
{
    int secret[4] = {1, 2, 3, 4};
    int guess[4];
    int a, b;
    int i;
    char input[16];

    fgets(input, sizeof(input), stdin);
    for (i = 0; i < 4; i++)
        guess[i] = input[i] - '0';

    check(secret, guess, &a, &b);
    printf("%dA%dB\n", a, b);

    return 0;
}

解析：外层循环 i 遍历 guess 的每一位。如果 guess[i] == secret[i]，说明位置和数字都对，计入 A。否则进入 else 分支，用内层循环 j 在 secret 中查找 guess[i]。找到后 (*b)++ 并 break，避免重复计数。*a = *b = 0 利用了赋值运算符的右结合性，将两个变量同时初始化为 0。

22c：完整猜数游戏

22c 参考解答

guess.c

#include <stdio.h>
#include <string.h>

/* 平台无关的伪随机数生成器 (Linear Congruential Generator) */
static unsigned int _seed = 42;
int my_rand(void) { _seed = _seed * 1103515245 + 12345; return (_seed >> 16) & 0x7fff; }

static void generate_secret(int secret[4])
{
    int used[10] = {0};
    for (int i = 0; i < 4; i++) {
        int d;
        do { d = my_rand() % 10; } while (used[d]);
        secret[i] = d;
        used[d] = 1;
    }
}

static void check(const int secret[4], const int guess[4], int *a, int *b)
{
    *a = *b = 0;
    for (int i = 0; i < 4; i++) {
        if (guess[i] == secret[i]) {
            (*a)++;
        } else {
            for (int j = 0; j < 4; j++) {
                if (guess[i] == secret[j]) {
                    (*b)++;
                    break;
                }
            }
        }
    }
}

static int parse_guess(const char *s, int guess[4])
{
    int len = strlen(s);
    if (len > 0 && s[len - 1] == '\n') len--;
    if (len != 4) return 0;
    for (int i = 0; i < 4; i++) {
        if (s[i] < '0' || s[i] > '9') return 0;
        guess[i] = s[i] - '0';
    }
    return 1;
}

int main(void)
{
    int secret[4];
    int guess[4];
    int a, b;
    int attempts = 0;
    char input[16];

    generate_secret(secret);

    while (1) {
        printf("Enter your guess: ");
        if (fgets(input, sizeof(input), stdin) == NULL)
            break;

        if (!parse_guess(input, guess))
            continue;

        attempts++;
        check(secret, guess, &a, &b);
        printf("%dA%dB\n", a, b);

        if (a == 4) {
            printf("Congratulations! You got it in %d attempts!\n", attempts);
            break;
        }
    }

    printf("The secret was: %d%d%d%d\n",
           secret[0], secret[1], secret[2], secret[3]);
    return 0;
}

解析：完整的猜数游戏整合了三个模块——generate_secret（生成）、check（比较）、parse_guess（解析），以及用 while (1) + break 构成的游戏主循环。attempts 变量追踪猜测次数。parse_guess 中添加了换行符处理（\n）和长度检查（len != 4）。fgets 返回 NULL 表示 EOF 或读取错误，此时退出循环。最后无论是否猜中，都打印出 secret 的值。

课堂讨论

如果去掉 do-while 中的 used[d] 检查，程序的行为会有什么变化？为什么随机数可能重复？
check() 函数中，为什么 B 的计算要放在 else 分支里？如果和 A 并列（不用 else）会发生什么？
如果将 used[10] 替换为逐个检查 secret[0] 到 secret[i-1] 来去重，两种方法的效率差异有多大？分别分析时间复杂度。
在 parse_guess() 中，为什么使用 fgets() 而不是 scanf("%d") 读取 4 位数字？两种方法各有什么优缺点？
从信息论的角度看，每次 ?A?B 反馈能提供多少比特的信息？最少需要几次猜测才能保证猜对任意 4 位不重复数字？
如果要支持 N 位不重复数字（N 可以是 3、5、6 等），代码需要做哪些修改？如何让程序更具通用性？

讨论答案

Q1: 去掉 used[d] 检查会怎样？

去掉 used[d] 检查后，do-while 变成普通的 do { d = my_rand() % 10; } while (0)（因为 used[d] 始终为 0），等价于直接执行一次 d = my_rand() % 10。此时每次生成都是独立的随机事件，可能出现重复数字——例如生成 "1123" 这种结果。

my_rand() % 10 每次调用有 1/10 的概率产生任何一个数字，且各次调用之间是独立的（伪随机序列的性质）。4 次独立抽取中出现至少一对重复的概率为：

P(重复) = 1 - P(全部不同) = 1 - (10/10 × 9/10 × 8/10 × 7/10)
        = 1 - 5040/10000 = 49.6%

也就是说，去掉去重检查后，将近一半的概率会出现重复数字，破坏了游戏规则。

Q2: 为什么 B 的计算要放在 else 分支里？

如果将 B 的计算和 A 并列（不用 else），会导致一个数字被重复计入：

check_wrong.c

for (int i = 0; i < 4; i++) {
    if (guess[i] == secret[i])
        (*a)++;                    // 计入 A
    // 缺少 else！下面总是执行
    for (int j = 0; j < 4; j++)
        if (guess[i] == secret[j]) {
            (*b)++;                // 又计入 B！
            break;
        }
}

考虑 secret = {1,2,3,4}, guess = {1,2,3,4}（完全猜对）：

i=0: guess[0]==secret[0] → A++ → 内层循环找到 secret[0]=1 → B++（错误！）
最终结果：4A4B，但正确答案应该是 4A0B

else 确保了互斥性：一个 guess 数字要么是 A，要么参与 B 的判断，不能两者兼得。

Q3: used[] vs 逐个检查的效率对比

方法一：used[10] 数组标记

int used[10] = {0};
// ...
do { d = my_rand() % 10; } while (used[d]);  // O(1)
used[d] = 1;

每次检查是 O(1) 的数组访问。生成 4 个不重复数字的总时间为 O(4 × 平均重试次数)。平均重试次数很小（因为冲突概率随已用数字增多而增大，但平均而言每次只需约 1.1 次尝试）。

方法二：逐个检查已有数字

for (int i = 0; i < 4; i++) {
    int d;
    int duplicate;
    do {
        duplicate = 0;
        d = my_rand() % 10;
        for (int j = 0; j < i; j++)  // O(i)
            if (secret[j] == d) { duplicate = 1; break; }
    } while (duplicate);
    secret[i] = d;
}

每次去重检查需要遍历已生成的 i 个数字，总时间复杂度约为 O(4² × 重试) = O(16) 级别。对于 N 位数字，方法一是 O(N)，方法二是 O(N²)。

虽然对于 4 位数字两者差异微乎其微，但 used[] 的 O(1) 查找体现了空间换时间的经典思想——用 10 个 int 的额外空间换取常数时间的查找效率。

Q4: fgets() vs scanf("%d") 对比

维度	`fgets()` + 手动解析	`scanf("%d")`
输入格式	字符串，完全控制	自动解析为整数
验证能力	可精确验证每个字符	自动跳过空白，难以发现"12345"超长输入
缓冲区安全	`fgets(buf, size, stdin)` 有大小限制	`scanf` 无内置保护
错误恢复	可检测并提示具体错误	`scanf` 失败后输入流状态混乱
对"4 位数字"的处理	可以检测输入是 3 位还是 5 位	`scanf("%d")` 不区分 12 和 0012
前缀 0 问题	"0139" 正确解析为 `{0,1,3,9}`	`scanf("%d")` 读取为整数 139，丢失前导 0

对于猜数游戏，4 位数字可能以 '0' 开头（如 "0139"），scanf("%d") 会将其读为整数 139，丢失前导 0 的信息。而 fgets() + 逐字符解析能正确处理这种情况。

scanf 的真正问题在于错误恢复。如果用户输入了非数字字符（如 "abc"），scanf 不会消耗输入，字符留在缓冲区中，导致程序陷入无限循环。而 fgets 每次读取一整行，天然避免了这个问题。

Q5: 信息论分析

4 位不重复数字共有 P(10,4) = 10 × 9 × 8 × 7 = 5040 种可能。

每次 ?A?B 反馈可能的结果数：A 可以取 0-4（5 种），B 可以取 0-4（但受 A 的约束），总共约 14 种不同的反馈组合（如 0A0B、1A0B、0A1B、1A1B、2A0B 等）。

一次猜测最多能区分 14 种情况，提供 log2(14) ≈ 3.8 比特的信息。要区分 5040 种可能，理论上最少需要：

log2(5040) / log2(14) ≈ 12.3 / 3.8 ≈ 3.2 次

但实际上，最优策略也远达不到这个理论下界，因为：

反馈组合的分布不均匀（有些组合出现的概率远大于其他）
每次猜测后剩余的可能性并不总能被均等划分

Donald Knuth 在 1976 年的论文中证明了 Mastermind（4 个位置，6 种颜色，允许重复）的最坏情况最少需要 5 次猜测。对于我们的 10 数字不重复版本，最优策略通常需要 5-7 次。

Q6: 如何支持 N 位不重复数字？

需要做以下修改：

使用宏或常量定义 N：

generalized.c

#define N 4    // 改为 3、5、6 等即可

调整数组大小：

int secret[N];
int guess[N];
int used[10];  // used 大小不变（数字仍然是 0-9）

修改循环上界：

for (int i = 0; i < N; i++) { ... }

修改 parse_guess 的期望长度：

if (len != N) return 0;

修改胜利条件：

if (a == N) { ... }  // NA0B = 完全猜对

输出也需相应调整。可以用循环打印，而非硬编码 %d%d%d%d。

关键约束：N 不能超过 10，因为只有 10 个不同的数字（0-9）。如果 N > 10，必然出现重复，违反了"不重复"的规则。

课后练习

练习 1：猜测次数限制

为游戏添加猜测次数限制：玩家最多只能猜测 10 次。超过 10 次仍未猜中，则游戏失败，打印 "Game Over!" 和 secret 的值。

知识点提示：在 while 循环条件中增加 attempts < 10 的判断，或者循环内 if (attempts >= 10) break。

参考解答

guess_limit.c

#define MAX_ATTEMPTS 10

int main(void)
{
    int secret[4], guess[4], a, b, attempts = 0;
    char input[16];

    generate_secret(secret);

    while (attempts < MAX_ATTEMPTS) {
        printf("Enter your guess (%d/%d): ",
               attempts + 1, MAX_ATTEMPTS);
        if (fgets(input, sizeof(input), stdin) == NULL)
            break;
        if (!parse_guess(input, guess))
            continue;

        attempts++;
        check(secret, guess, &a, &b);
        printf("%dA%dB\n", a, b);

        if (a == 4) {
            printf("Congratulations! "
                   "You got it in %d attempts!\n", attempts);
            break;
        }
    }

    if (a != 4)
        printf("Game Over! ");
    printf("The secret was: %d%d%d%d\n",
           secret[0], secret[1], secret[2], secret[3]);
    return 0;
}

练习 2：添加"还差一步"提示

当反馈为 3A0B 时（即 3 个数字位置全对，1 个数字完全不对），打印提示："还差一步！"

知识点提示：在 printf("%dA%dB\n", a, b) 之后增加条件判断：if (a == 3 && b == 0) 时输出额外提示。

参考解答

hint_3a0b.c

// 在 check 和 printf 之后添加：
printf("%dA%dB\n", a, b);

if (a == 3 && b == 0)
    printf("Hint: You are just one step away!\n");

还可以进一步扩展：3A1B 表示 3 个数字位置正确，第 4 个数字对但位置错——此时也离胜利很近。可以根据不同的 ?A?B 组合给出不同级别的提示。

练习 3：记录猜测历史

修改程序，将每次猜测和对应的反馈记录在一个二维数组中，猜中后打印完整的猜测历史。

知识点提示：使用一个 int history[20][6] 数组（最多 20 次猜测，每行存储 4 位 guess + A + B），每次猜测后将 guess[0..3]、a、b 存入。

参考解答

guess_history.c

#define MAX_HISTORY 100

int main(void)
{
    int secret[4], guess[4], a, b, attempts = 0;
    int history[MAX_HISTORY][6];  // [guess0, guess1, guess2, guess3, a, b]
    char input[16];

    generate_secret(secret);

    while (1) {
        printf("Enter your guess: ");
        if (fgets(input, sizeof(input), stdin) == NULL)
            break;
        if (!parse_guess(input, guess))
            continue;

        check(secret, guess, &a, &b);

        // 记录历史
        for (int i = 0; i < 4; i++)
            history[attempts][i] = guess[i];
        history[attempts][4] = a;
        history[attempts][5] = b;
        attempts++;

        printf("%dA%dB\n", a, b);

        if (a == 4) {
            printf("Congratulations! "
                   "You got it in %d attempts!\n", attempts);
            break;
        }
    }

    // 打印猜测历史
    printf("\n--- Guess History ---\n");
    for (int i = 0; i < attempts; i++) {
        printf("%2d: ", i + 1);
        for (int j = 0; j < 4; j++)
            printf("%d", history[i][j]);
        printf(" → %dA%dB\n", history[i][4], history[i][5]);
    }

    printf("The secret was: %d%d%d%d\n",
           secret[0], secret[1], secret[2], secret[3]);
    return 0;
}

练习 4：实现 Mastermind 颜色变体

将 10 个数字替换为 6 种"颜色"（用字母 R/G/B/Y/O/P 表示），允许重复。修改 check() 函数以正确处理重复颜色的情况——这是经典 Mastermind 游戏的核心挑战。

知识点提示：当允许重复时，B 的计数不能简单地"找到一个就 break"。需要追踪哪些 secret 位置已被匹配，避免重复计数。可以用一个额外的 secret_used[4] 数组来标记。

参考解答

mastermind.c

#include <stdio.h>

// 颜色：R=0, G=1, B=2, Y=3, O=4, P=5

void check_mastermind(const int secret[4], const int guess[4],
                      int *a, int *b)
{
    int secret_used[4] = {0};  // 标记已被匹配的 secret 位置

    *a = *b = 0;

    // 第一遍：找 A（位置和颜色都对）
    for (int i = 0; i < 4; i++) {
        if (guess[i] == secret[i]) {
            (*a)++;
            secret_used[i] = 1;  // 这个位置已被占用
        }
    }

    // 第二遍：找 B（颜色对但位置不对）
    for (int i = 0; i < 4; i++) {
        if (guess[i] == secret[i])
            continue;  // 已经是 A，跳过
        for (int j = 0; j < 4; j++) {
            if (!secret_used[j] && guess[i] == secret[j]) {
                (*b)++;
                secret_used[j] = 1;  // 标记为已使用
                break;
            }
        }
    }
}

关键区别：允许重复颜色时，必须分两遍扫描。第一遍先锁定所有 A（位置和颜色都对），第二遍再找 B。secret_used[] 数组确保每个 secret 位置最多被匹配一次，避免了重复计数问题。这是 Mastermind 标准算法，与"不重复数字"版本的逻辑有本质区别。

练习 5：AI 自动猜数玩家

实现一个简单的 AI，能自动猜出计算机生成的数字。使用"维护所有可能答案集合"的策略：初始集合包含所有 5040 种不重复 4 位数字组合，每次猜测后根据反馈过滤集合，从剩余可能性中随机选择一个作为下一次猜测。

知识点提示：生成所有可能答案可以用 4 层嵌套循环。过滤时，对集合中每个候选答案调用 check(secret, candidate, &a, &b)，只保留反馈与实际反馈一致的候选。

参考解答

ai_player.c

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

// 生成所有 5040 种不重复 4 位数字组合
static int generate_all_candidates(int candidates[5040][4])
{
    int count = 0;
    for (int a = 0; a < 10; a++)
        for (int b = 0; b < 10; b++) {
            if (b == a) continue;
            for (int c = 0; c < 10; c++) {
                if (c == a || c == b) continue;
                for (int d = 0; d < 10; d++) {
                    if (d == a || d == b || d == c) continue;
                    candidates[count][0] = a;
                    candidates[count][1] = b;
                    candidates[count][2] = c;
                    candidates[count][3] = d;
                    count++;
                }
            }
        }
    return count;  // 应返回 5040
}

// 过滤候选集：只保留与 guess 反馈一致的候选
static int filter(int candidates[5040][4], int count,
                  const int guess[4], int a_fb, int b_fb)
{
    int new_count = 0;
    for (int i = 0; i < count; i++) {
        int a, b;
        check(candidates[i], guess, &a, &b);
        if (a == a_fb && b == b_fb) {
            // 保留此候选（原地复制）
            for (int j = 0; j < 4; j++)
                candidates[new_count][j] = candidates[i][j];
            new_count++;
        }
    }
    return new_count;
}

这个 AI 的完整实现需要约 100 行代码。核心思路是"排除法"——每次猜测后，所有与反馈不符的候选都被剔除。在大多数情况下，5-7 次猜测即可确定答案。

参考资料

C Reference: rand() — C 标准库 rand() 和 srand() 的官方文档
Linear Congruential Generator — 维基百科：线性同余生成器的数学原理
Bulls and Cows — 维基百科：猜数游戏的历史和变体
Knuth's Mastermind Algorithm — Knuth 1976 年论文：Mastermind 的最优策略
Information Theory and Guessing Games — 信息论视角下的猜测策略分析

"The computer was born to solve problems that did not exist before." — Bill Gates

Lesson 22: 猜数游戏 ​CNB

练习任务 ​

核心知识点 ​

代码框架 ​

深度讲解 ​

1. 伪随机数：从 rand() 到底层原理 ​

1.1 计算机能产生真正的随机数吗？ ​

1.2 线性同余生成器 (LCG) ​

1.3 srand() 与 time(NULL) ​

1.4 rand() % N 的模运算 ​

2. do-while 与 used[] 去重：生成不重复的 4 位数字 ​

2.1 问题分析 ​

2.2 used[] 数组标记法 ​

2.3 do-while：先执行后判断 ​

2.4 完整实现 ​

3. 双重循环与 ?A?B 逻辑 ​

3.1 游戏规则 ​

3.2 A 的计算：单层循环 ​

3.3 B 的计算：双重循环 + 排除 A ​

3.4 为什么用指针参数？ ​

3.5 内层 break 的必要性 ​

4. 字符串解析与输入处理 ​

4.1 为什么用 fgets() 而不是 scanf()？ ​

4.2 fgets() 的基本用法 ​

4.3 字符串转数字数组 ​

4.4 更完善的输入验证 ​

5. 游戏主循环：while (1) + break ​

5.1 交互式循环结构 ​

5.2 continue 的妙用 ​

5.3 流程图 ​

5.4 完整数据流追踪 ​

6. 二分查找策略：用算法优化猜测 ​

6.1 信息论视角 ​

6.2 简单二分策略 ​

6.3 最坏情况分析 ​

6.4 常见错误：检查中的边界条件 ​

7. 内存视角：数组与栈帧 ​

7.1 函数调用中的数组传递 ​

7.2 栈帧布局 ​

参考解答 ​

22a：生成不重复 4 位随机数 ​

22b：计算 ?A?B ​

22c：完整猜数游戏 ​

课堂讨论 ​

讨论答案 ​

课后练习 ​

练习 1：猜测次数限制 ​

练习 2：添加"还差一步"提示 ​

练习 3：记录猜测历史 ​

练习 4：实现 Mastermind 颜色变体 ​

练习 5：AI 自动猜数玩家 ​

参考资料 ​

Lesson 22: 猜数游戏 CNB

练习任务

核心知识点

代码框架

深度讲解

1. 伪随机数：从 `rand()` 到底层原理

1.1 计算机能产生真正的随机数吗？

1.2 线性同余生成器 (LCG)

1.3 `srand()` 与 `time(NULL)`

1.4 `rand() % N` 的模运算

2. `do-while` 与 `used[]` 去重：生成不重复的 4 位数字

2.1 问题分析

2.2 `used[]` 数组标记法

2.3 `do-while`：先执行后判断

2.4 完整实现

3. 双重循环与 ?A?B 逻辑

3.1 游戏规则

3.2 A 的计算：单层循环

3.3 B 的计算：双重循环 + 排除 A

3.4 为什么用指针参数？

3.5 内层 `break` 的必要性

4. 字符串解析与输入处理

4.1 为什么用 `fgets()` 而不是 `scanf()`？

4.2 `fgets()` 的基本用法

4.3 字符串转数字数组

4.4 更完善的输入验证

5. 游戏主循环：`while (1)` + `break`

5.1 交互式循环结构

5.2 `continue` 的妙用

5.3 流程图

5.4 完整数据流追踪

6. 二分查找策略：用算法优化猜测

6.1 信息论视角

6.2 简单二分策略

6.3 最坏情况分析

6.4 常见错误：检查中的边界条件

7. 内存视角：数组与栈帧

7.1 函数调用中的数组传递

7.2 栈帧布局

参考解答

22a：生成不重复 4 位随机数

22b：计算 ?A?B

22c：完整猜数游戏

课堂讨论

讨论答案

课后练习

练习 1：猜测次数限制

练习 2：添加"还差一步"提示

练习 3：记录猜测历史

练习 4：实现 Mastermind 颜色变体

练习 5：AI 自动猜数玩家

参考资料