CC++ & Algorithm

Python枚举与模拟经典例题

困难3
语言版本:C++Python
概述:通过两道经典例题,学会如何用枚举和模拟解决实际问题。

枚举与模拟:像侦探一样找答案,像演员一样按剧本走

枚举和模拟是编程里两个非常实用的“套路”。枚举就像侦探在破案时把所有可能的线索都试一遍,看看哪个正确;模拟就像演员按照导演的剧本一步步表演,把过程重现出来。很多编程题要么让你“试遍所有可能性”(枚举),要么让你“按规则一步步执行”(模拟)。下面我们用两个经典例子,让你彻底搞懂它们。

枚举:把所有可能都试一次

枚举的思路很简单:把所有可能的情况列出来,检查每个情况是否满足条件。就像你想知道自己的密码箱密码,你从000试到999,试对为止。生活中的例子:妈妈让你用10元、5元、1元凑出18元,你可以枚举所有组合;体育课上老师让同学们站成一排,你想知道有多少种站法,也可以枚举。

在编程里,枚举通常用循环(比如for)来遍历一个范围,然后用if判断条件。下面我们通过一个经典的数学问题来学习。

例题1:寻找三位数的水仙花数(枚举)

题目:水仙花数是指一个三位数,其各位数字的立方和等于该数本身。例如153 = 1³ + 5³ + 3³。请找出所有三位数的水仙花数。

思路:枚举所有100到999之间的三位数,对每个数拆出百位、十位、个位,计算立方和,判断是否等于原数。

# 枚举所有三位数
for num in range(100, 1000):
    # 取出各位数字
    a = num // 100          # 百位
    b = (num // 10) % 10    # 十位
    c = num % 10            # 个位
    # 判断是否为水仙花数
    if a**3 + b**3 + c**3 == num:
        print(num, "是水仙花数")

运行结果
153 是水仙花数
370 是水仙花数
371 是水仙花数
407 是水仙花数

这个题完美体现了枚举思想:用循环遍历所有可能,检查条件,输出结果。

新手容易犯的错误

  • 范围写错:比如写成range(0,1000),这样会把0到99也枚举进来,但0也是水仙花数(0³=0),但题目要求三位数,所以应该从100开始。如果使用range(100,1000),就不包括1000本身,因为999是最后一个。
  • 拆数字时顺序搞混://是整数除法,%是取余数。比如256:256//100=2(百位),(256//10)%10 = 25%10 = 5(十位),256%10=6(个位)。如果写成num%10//100就错了。
  • 立方的写法:Python里a**3表示a的三次方,不要写成a^3,那是按位异或运算。
  • 忘记转换:数字已经整型,直接运算没问题,但要注意如果从输入读字符串时要先转整型。

模拟:像导演一样一步步演

模拟就是按照题目描述的规则,一步一步地执行,把整个过程在程序中重现。比如老师让你模拟“小红的零花钱每天增加2元,第1天有5元,问第10天有多少元”,你可以写一个循环,每天加2元。模拟的关键是准确理解规则,然后用变量保存状态用循环控制步骤

生活中的例子:模拟超市收银流程(顾客拿商品→扫码→计算总价→找零);模拟体育课的报数游戏(1,2,3,1,2,3...);模拟小红和小明轮流吃零食(每人每次吃几个,最后谁吃得多)。

下面我们看一个稍微复杂一点的模拟题。

例题2:模拟猴子吃桃子(模拟)

题目:猴子第一天摘下若干个桃子,当即吃了一半,还不瘾,又多吃了一个。第二天早上又将剩下的桃子吃掉一半,又多吃了一个。以后每天早上都吃了前一天剩下的一半多一个。到第10天早上想再吃时,见只剩下一个桃子了。求第一天共摘了多少个桃子?

思路:模拟从第10天倒推到第1天。规则是:第10天剩下1个;前一天的桃子数量 = (当天剩下的 + 1)* 2。例如第9天:第10天有1个,则第9天有 (1+1)*2 = 4个。

# 最后一天剩下的桃子数
left = 1  # 第10天剩下1个桃子
# 倒推前9天
for day in range(9, 0, -1):  # day从9,8,...1
    # 前一天桃子数 = (当天剩下 + 1) * 2
    left = (left + 1) * 2
    print("第", day, "天早上有", left, "个桃子")

print("第一天共摘了", left, "个桃子")

运行结果
第 9 天早上有 4 个桃子
第 8 天早上有 10 个桃子
第 7 天早上有 22 个桃子
第 6 天早上有 46 个桃子
第 5 天早上有 94 个桃子
第 4 天早上有 190 个桃子
第 3 天早上有 382 个桃子
第 2 天早上有 766 个桃子
第 1 天早上有 1534 个桃子
第一天共摘了 1534 个桃子

这个题的模拟思路是倒着模拟:从已知的最后状态开始,按照规则逆运算推回初始状态。如果是正着模拟,就是从第一天开始,但不知道第一天的数量,所以倒推更方便。

新手容易犯的错误

  • 模拟的方向搞反:有的同学可能会正着设未知数,用方程计算。但既然题目给了最后状态,倒推更简单。
  • 规则理解错:题目说“吃了前一天剩下的一半多一个”,意思是吃掉的量是“前一天剩下的一半再加一个”,所以剩下的就是“总数 - (总数/2 + 1) = 总数/2 - 1”。倒过来就是:前一天的数量 = (当天剩下的 + 1) * 2。注意不要写反。
  • 循环次数:一共有10天,第10天已知,需要倒推9次,所以循环从9到1。如果写range(9,0),不会执行,因为range默认步长为正,9>0所以直接结束。应该加步长-1:range(9,0,-1)
  • 变量更新:每次循环后left的值会被更新,最后得到的left就是第一天的数量。

完整示例:一个程序同时包含枚举和模拟

为了让你看到完整的代码是怎么组织的,下面写一个脚本,既有水仙花数枚举,又有猴子吃桃模拟。你可以直接复制到Python里运行。

# 枚举部分:找水仙花数
print("===== 水仙花数枚举 =====")
for num in range(100, 1000):
    a = num // 100          # 百位
    b = (num // 10) % 10    # 十位
    c = num % 10            # 个位
    if a**3 + b**3 + c**3 == num:
        print(num, "是水仙花数")

print()  # 空行

# 模拟部分:猴子吃桃倒推
print("===== 猴子吃桃模拟 =====")
left = 1  # 第10天剩下1个
for day in range(9, 0, -1):  # day从9,8,...1
    left = (left + 1) * 2
    print("第", day, "天早上有", left, "个桃子")
print("第一天共摘了", left, "个桃子")

运行这个程序,你会得到两个结果区域。

常见错误总结(枚举与模拟通用)

错误类型具体表现解决办法
范围错误枚举时多一个或少一个数,比如 range(1,10) 不包括10记住 range(a,b) 包含a,不包含b;range(100,1000) 包含100~999
循环方向模拟时忘记倒着循环,或步长写反想清楚:循环变量是增加还是减少,用 range(start, stop, step) 控制
变量更新模拟时未正确更新状态,导致死循环或结果错误在循环体里修改关键变量,确保每次循环状态推进
运算优先级拆数字时括号写错,比如 num//10%10 应改成 (num//10)%10不确定时加括号,或一步步拆:shi = num // 10; bai = shi // 10; ge = shi % 10 等等
跳出条件模拟时不知道什么时候停止如果规则是“直到某个条件”,用 while;如果已知步数,用 for 循环

相关知识点指引

如果你想更深入地学习枚举和模拟,可以先掌握这些基础知识:

  • 循环for循环(遍历固定范围)和 while循环(条件循环)是模拟的基础。
    ? 可以看“Python循环结构”相关内容。
  • 条件判断if语句用来筛选枚举中的有效结果。
    ? 可以看“Python条件语句”相关内容。
  • 整数运算//整除和%取余是拆数字的常用工具。
    ? 可以看“Python算术运算符”相关内容。
  • 列表:如果你需要存储所有枚举结果,可以用列表。
    ? 可以看“Python列表基础”相关内容。

继续练习,你会发现枚举和模拟能解决很多有趣的数学问题、游戏问题,甚至物理模拟(比如小球反弹)。多试试自己编题目,比如“枚举所有1~100之间的质数”、“模拟小红每天存1元,小明每天存2元,问几天后两人钱相等”。动手编码,进步更快!

例题精讲

1单选题

百钱百鸡问题:公鸡5文钱一只,母鸡3文钱一只,小鸡三只1文钱,用100文钱买100只鸡,请问有多少种买法?以下哪段代码能正确枚举所有可能?

Afor x in range(0, 21): for y in range(0, 34): z = 100 - x - y; if 5*x+3*y+z/3==100: print(x,y,z)
Bfor x in range(0, 20): for y in range(0, 33): z = 100 - x - y; if 5*x+3*y+z/3==100: print(x,y,z)
Cfor x in range(0, 21): for y in range(0, 34): z = 100 - x - y; if 5*x+3*y+z//3==100: print(x,y,z)
Dfor x in range(0, 21): for y in range(0, 34): z = 100 - x - y; if 5*x+3*y+int(z/3)==100: print(x,y,z)
2单选题

约瑟夫环问题模拟:n个人围成一圈,从第一个人开始报数,数到k的人出列,然后从下一个人重新报数,直到所有人都出列。以下是用模拟法(列表)实现的代码片段: queue = list(range(1, n+1)) index = 0 result = [] while queue: index = (index + k - 1) % len(queue) result.append(queue.pop(index)) 假设n=5, k=3,执行后result的第一个元素是?

A1
B2
C3
D4
3判断题

枚举法通常适用于问题规模较小的情况,因为需要遍历所有可能的候选解,时间复杂度往往较高。

4填空题
模拟时钟的分钟累加:给定初始时间(小时h,分钟m),经过t分钟后,请输出新的时间(小时和分钟,24小时制)。请补全代码:
def add_minutes(h, m, t):
    total_minutes = h * 60 + m + t
    new_h = (total_minutes // 60) % ___
    new_m = total_minutes % 60
    return new_h, new_m
5填空题
以下代码模拟一个简单的猜数字游戏,游戏会随机生成1~100之间的整数,玩家输入猜测,程序提示“大了”或“小了”直到猜中。请补全代码中缺失的部分:
import random
target = random.randint(1, 100)
guess = None
while guess != target:
    guess = int(input("请输入你的猜测: "))
    if guess > target:
        print("大了")
    ___ guess < target:
        print("小了")
print("恭喜你猜对了!")