被低估的“笨办法”:枚举与模拟才是算法思维的起点
看到一道算法题,你的第一反应是什么?翻书找公式?回忆某个“经典套路”?还是……直接硬着头皮试一遍?
如果你选最后一种,恭喜你,你其实已经在用编程里最古老也最可靠的两种思维方式了——枚举和模拟。它们不像动态规划那样高深,也不如二分查找那样精巧,但恰恰是这两个看似“笨”的办法,构成了算法思维的真正地基。不会枚举和模拟,你连“笨办法”都不会写,更别谈什么优化了。
枚举不是“暴力”,是“穷尽”
很多人管枚举叫暴力解法,我不太喜欢这个说法。暴力意味着不计后果地乱来,而枚举的核心是有策略地穷尽。你从000试到999试密码箱,这不是暴力,这是确定性——你最多试1000次,一定能打开。
水仙花数问题就是最典型的枚举: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)
你发现没有,这段代码的三步其实对应着枚举的三种核心能力:确定搜索空间(100到999)、解析当前状态(拆数字)、判断目标条件(立方和相等)。所有枚举题都逃不出这三步。
但很多新手挂在第一步和第二步的交接处。比如拆数字的时候,(num // 10) % 10 写成 num // 10 % 10,虽然结果一样,但自己心里糊涂;再比如百位直接写 num // 100,搞不清为什么不是 num % 1000 // 100。本质上,你是在做一次“状态翻译”,把整数翻译成它每一个数位上的字符。翻译错了,后面的判断全白搭。
百钱百鸡那道题,考察的其实是搜索空间的裁剪。公鸡5文,母鸡3文,小鸡1文3只,100文买100只。如果你老老实实枚举100×100×100的组合,当然也能出结果,但那是1百万次循环。而经典解法是把空间缩小到公鸡020、母鸡033,然后小鸡数量直接用 100 - x - y 算出来。这里体现了一个枚举中的重要思想:能用约束消掉的维度,就不要去枚举它。
for x in range(0, 21): # 公鸡最多20只
for y in range(0, 34): # 母鸡最多33只
z = 100 - x - y
if 5*x + 3*y + z/3 == 100:
print(x, y, z)
你看,代码量没多多少,但复杂度从O(n³)降到了O(n²)。枚举不是无脑循环,它是在“有可能的范围”里找“有可能的答案”,只不过你把这个范围划得越精准,效率越高。
模拟不是“翻译”,是“建模”
如果说枚举是侦探,那么模拟就是演员。演员拿到剧本,不是逐字背诵台词,而是理解角色的处境,然后按照性格逻辑去行动。写模拟题也是一样:你读题目,先要在脑内建立起一个“过程模型”,然后用代码把这个模型跑起来。
猴子吃桃问题,很多人的第一反应是设未知数列方程。但方程是数学思维,程序员的思维应该是:既然题目给了最后一天的状态,那我直接倒着把过程“演”回去。
left = 1 # 第10天早上
for day in range(9, 0, -1):
left = (left + 1) * 2
第9天有 (1+1)*2 = 4 个,第8天有 (4+1)*2 = 10 个……9次循环之后,得到的1534就是答案。
这道题的“建模”关键在哪儿?在于把“吃了一半又多一个”这个动作反过来翻译成“加1再乘2”。如果你顺着题目的方向写代码,那就是 left = left/2 - 1,永远不会得到正确答案。模拟的第一步永远是把题目的规则翻译成反向的、可计算的操作,这一关过不了,后面循环写得再漂亮也没用。
约瑟夫环那道题,则把模拟的另一个难点暴露得很赤裸:状态更新。n=5,k=3,第一轮报数到3的人出列,索引是2,元素是3。这没啥争议,但如果你写代码的时候没意识到列表索引从0开始,或者忘了每次移除元素后列表长度变了、索引要重新计算,后面的结果就全乱了。
index = (index + k - 1) % len(queue)
result.append(queue.pop(index))
这两行代码,其实就是整个约瑟夫环模拟的核心。第一次运行:index = (0+3-1) % 5 = 2,弹出元素3。第二次运行:index = (2+3-1) % 4 = 0,弹出元素1。你以为是在“报数”,实际上是在“在一个不断变短的环里算偏移量”。这就是模拟题的本质——你要精确地追踪每一个变量的变化,一步都不能错。
枚举与模拟,其实是一体两面
很多人把枚举和模拟当成两种独立的题型,但在我看来,它们是一体两面的。枚举是在“时间上”遍历所有可能的状态,模拟是在“状态上”推进时间的演化。前者关心“有哪些可能”,后者关心“下一步发生了什么”。
一旦你看穿了这一点,你的编程思维会打开一扇门:很多看似复杂的搜索问题,本质上都是枚举+模拟的组合。迷宫寻路,是枚举方向;球的反弹轨迹,是模拟物理过程;甚至贪心算法、动态规划的朴素版本,在写成递归暴力之前,也是枚举所有决策路径,模拟所有可能结果之后才被总结出来的“优化方案”。
所以,别总觉得枚举和模拟是入门级的低级操作。恰恰相反,它们是所有算法的公共基础。你只有把“范围内的所有可能”想得够透,把“状态的每一步推进”算得够准,才有资格去谈剪枝、记忆化、状态压缩这些进阶技巧。地基不稳,楼层再花哨也只是纸糊的。
进阶的建议很简单:在学任何新算法之前,先问你两个问题——如果我不知道这个算法,我能不能用枚举解决?如果我要追踪这个过程,我需要多少变量才能精确描述它的状态?想清楚这两点,等你在未来遇到剪枝、分治、动态规划的时候,你会发现自己对“为什么这样优化”的理解,比别人深得多。