用枚举和模拟解经典题：百钱百鸡与开关灯

枚举法和模拟法是编程里最基础也最实用的两种方法。枚举就像“挨个儿试”，把所有可能性都列出来检查一遍；模拟就像“按步骤做”，一步步重现过程。这两个方法能解决很多有趣的问题，今天我们就通过两个经典题目来实际练习一下。

例题1：百钱百鸡——枚举法找所有方案

中国古代数学家张丘建在《算经》里提出了一道题：公鸡5文钱一只，母鸡3文钱一只，小鸡三只一文钱（也就是1文钱能买3只小鸡）。现在有100文钱，要买100只鸡，问公鸡、母鸡、小鸡各多少只？

这个问题就是典型的“枚举法”——我们不知道每种鸡各几只，但知道总数量和总钱数，所以可以挨个试公鸡和母鸡的数量，小鸡的数量自然就确定了（因为一共100只鸡），然后检查总钱数是不是正好100文。

思路分析

• 公鸡最多能买多少只？如果全买公鸡，100文能买20只（5×20=100），所以公鸡数量范围0~20。
• 母鸡最多能买多少只？如果全买母鸡，100文能买33只（3×33=99，剩1文不够买一只母鸡），所以母鸡数量范围0~33。
• 小鸡的数量 = 100 - 公鸡 - 母鸡，因为总共100只鸡。
• 检查总钱数：5×公鸡 + 3×母鸡 + 小鸡/3 是否等于100。注意小鸡数量必须是3的倍数，不然钱数会有小数，但我们在判断时用浮点数比较，或者直接让条件为 5*gong + 3*mu + xiao//3 == 100 and xiao%3==0 更严谨。

生活小类比：就像你去超市买零食，手里有100元，要买正好100件零食，有A零食5元、B零食3元、C零食1元3个。你不想多花一分钱，也不想多拿一个，那就只能一个个试A和B的数量，C的数量自然就出来了。

代码实现（保留原有代码，添加更严谨的判断和输出格式）

# 百钱百鸡 - 枚举法
print("可能的购买方案：")
for gong in range(21):              # 公鸡0~20只
    for mu in range(34):            # 母鸡0~33只
        xiao = 100 - gong - mu      # 小鸡数量
        if xiao < 0:
            continue                # 数量不能为负
        # 检查钱数：小鸡数量必须是3的倍数，否则钱数不对
        if xiao % 3 == 0 and 5 * gong + 3 * mu + xiao // 3 == 100:
            print(f"公鸡{gong}只，母鸡{mu}只，小鸡{xiao}只")

运行结果会输出四组方案：

公鸡0只，母鸡25只，小鸡75只
公鸡4只，母鸡18只，小鸡78只
公鸡8只，母鸡11只，小鸡81只
公鸡12只，母鸡4只，小鸡84只

新手容易犯的错误：

• 忘记考虑小鸡数量必须是3的倍数，直接用 xiao / 3 做浮点数比较可能会出现精度问题（比如 100.0 == 100 没问题，但如果是其他值可能出错）。最好用整数除法并检查余数。
• 循环范围没算准，比如把母鸡上限写成33，但range(34)包含0~33共34个数，没问题。如果写range(33)则少了33这个值（33只母鸡刚好99文，剩下1文买3只小鸡，也是可能方案）。
• 忽略小鸡数量可能为负的情况，虽然xiao<0时continue了，但如果不判断，xiao//3会得到负数，造成错误。

另一种写法：有时候为了展示“枚举所有可能性”，也可以用三层循环分别枚举公鸡、母鸡、小鸡，但那样循环次数多（21×34×101≈7万多次），不如两层循环高效。代码里用两层循环就已经穷举了所有可能。

例题2：开关灯——模拟法重现过程

有n盏灯，编号1~n，初始全部关闭。第一个人把所有灯打开；第二个人把编号是2的倍数的灯关闭；第三个人把编号是3的倍数的灯状态翻转（开变关，关变开）……第k个人把编号是k的倍数的灯翻转。问经过m个人操作后，哪些灯是亮的？

这个问题需要“模拟”整个过程——我们按照规则一步步操作灯的状态。用计算机模拟比手工快得多。

思路分析

• 用一个列表表示灯的状态：1表示开，0表示关（或者用布尔值True/False）。为了下标方便，我们可以建一个长度为n+1的列表，忽略下标0，直接用下标1~n对应灯编号。
• 第1个人：将所有灯打开（即把灯的状态设为1）。
• 第2个人：编号是2的倍数（2,4,6,…）的灯，状态翻转。
• 第3个人：编号是3的倍数的灯，状态翻转。
• …直到第m个人。
• 最后遍历所有灯，输出状态为1的灯编号。

生活小类比：想象教室里有100个座位，每个座位上有一盏小灯。班长（第1个人）把所有灯都打开；学习委员（第2个人）把偶数座位号的灯关掉；卫生委员（第3个人）把座位号是3的倍数的灯切换状态（原来开的关掉，原来关的打开）……这样每个人只动自己负责的倍数座位。最后看看哪些灯还亮着。

代码实现（保留原有代码，增加注释和输出优化）

# 开关灯 - 模拟法
n = 100          # 灯的数量
m = 100          # 人数
lights = [0] * (n + 1)   # 灯编号1~n，初始全部关闭（0）

# 第1个人：全部打开
for i in range(1, n + 1):
    lights[i] = 1

# 第2个人到第m个人：翻转倍数灯
for person in range(2, m + 1):      # 注意从2开始，因为第1个人已经处理过了
    for lamp in range(person, n + 1, person):   # 编号是person倍数的灯
        lights[lamp] = 1 - lights[lamp]        # 翻转：1变0，0变1

# 输出亮着的灯编号
print("亮着的灯编号：", end="")
first = True
for i in range(1, n + 1):
    if lights[i] == 1:
        if not first:
            print(", ", end="")
        print(i, end="")
        first = False
print()

优化点：第1个人的操作可以直接用一个循环，也可以跟后面的统一处理，但为了清晰我们单独写。更简洁的做法是从person=1开始统一处理，不过要注意第1个人把所有灯打开，而翻转初始状态（关→开）就是打开。所以我们也可以把第1个人纳入循环，初始lights全0，第1个人对1的倍数的灯翻转（就是所有灯），第2个人对2的倍数翻转……这样代码更短：

n = 100
m = 100
lights = [0] * (n + 1)

for person in range(1, m + 1):          # 第1到m个人
    for lamp in range(person, n + 1, person):
        lights[lamp] = 1 - lights[lamp]

# 输出同前

运行结果会发现，亮着的灯编号正好是完全平方数：1, 4, 9, 16, 25, 36, 49, 64, 81, 100。原因很有趣：每个灯被翻转的次数等于它编号的约数个数，只有完全平方数的约数个数是奇数，所以最终状态是亮。

新手容易犯的错误：

• 忘记初始化列表长度时，下标从0开始容易混淆。常见错误是lights = [0] * n，然后操作中下标从1开始就越界了。所以最好建n+1长度，忽略下标0。
• 翻转操作写成 lights[lamp] = not lights[lamp] 但列表元素是整数0/1，not会变成布尔值，再比较时可能不匹配。所以用 1 - lights[lamp] 或 lights[lamp] ^= 1 更好。
• 忘记第1个人的操作，或者把第1个人也当作翻转（初始关闭，翻转一次正好打开，没问题，但要注意起始标号）。
• 循环范围：range(person, n+1, person)，注意n+1才能包括n本身。

完整可运行示例

把两个题目合在一起，写一个完整的Python程序，你可以直接复制运行：

# 枚举与模拟经典题 - 完整示例

print("=" * 40)
print("百钱百鸡问题")
print("=" * 40)
print("可能的购买方案：")
for gong in range(21):              # 公鸡0~20
    for mu in range(34):            # 母鸡0~33
        xiao = 100 - gong - mu      # 小鸡
        if xiao < 0:
            continue
        if xiao % 3 == 0 and 5 * gong + 3 * mu + xiao // 3 == 100:
            print(f"公鸡{gong}只，母鸡{mu}只，小鸡{xiao}只")

print()
print("=" * 40)
print("开关灯问题 (n=100, m=100)")
print("=" * 40)
n = 100
m = 100
lights = [0] * (n + 1)           # 0:关, 1:开

for person in range(1, m + 1):
    for lamp in range(person, n + 1, person):
        lights[lamp] = 1 - lights[lamp]    # 翻转

print("亮着的灯编号：", end="")
result = [str(i) for i in range(1, n+1) if lights[i] == 1]
print(", ".join(result))

运行后你会看到百钱百鸡的四个解，以及开关灯后亮着的灯是1,4,9,16,...,100。

相关指引

学完这两个例子，你可以继续挑战类似的枚举与模拟题目：

• 枚举法：找水仙花数、鸡兔同笼、质数判定、排列组合问题等。
• 模拟法：约瑟夫环、报数游戏、机器人走路、棋盘上的移动等。

如果你对循环和列表操作还不熟悉，建议先复习一下Python的for循环和range函数，以及列表的索引和修改。另外，“开关灯”问题中推导出的“完全平方数”规律可以看作数学与编程结合的妙处，有兴趣可以了解“约数个数”的性质。

继续加油，用枚举和模拟去解决更多生活中的问题吧！