1. 外观数列的数学魅力与编程实现
第一次接触外观数列是在大学算法课上,教授用"1, 11, 21, 1211, 111221..."这个神奇序列向我们展示了简单规则如何产生复杂模式。十年编程生涯中,我多次在面试题和算法竞赛中遇到这个经典问题,今天就来深入剖析它的数学本质和实现技巧。
外观数列(Look-and-say sequence)由数学家约翰·康威命名,其生成规则简单却蕴含深意:每一项都是对前一项的数字描述。比如从"1"开始,读作"1个1"即"11",接着是"2个1"即"21",然后是"1个2,1个1"即"1211"。这种自我描述的属性使其在数据压缩、密码学等领域都有应用场景。
需要模型API调用? 免费领10W Token,多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 核心算法解析与实现方案
2.1 基础递归实现方案
最直观的实现方式是递归,完美对应数列的定义:
python复制def look_and_say(n):
if n == 1:
return "1"
prev = look_and_say(n-1)
result = []
i = 0
while i < len(prev):
count = 1
while i + 1 < len(prev) and prev[i] == prev[i+1]:
i += 1
count += 1
result.append(f"{count}{prev[i]}")
i += 1
return ''.join(result)
这个实现有几个关键点需要注意:
- 递归基线是n=1时返回"1"
- 使用双指针技巧统计连续相同数字的个数
- 字符串拼接采用列表append再join的方式提升性能
实际测试发现,当n>30时递归版本会出现栈溢出问题,这是所有递归算法都需要注意的边界条件。
2.2 迭代优化版本
针对递归的缺陷,我们可以改用迭代实现:
python复制def look_and_say_iterative(n):
current = "1"
for _ in range(1, n):
next_str = []
