1. 从一道竞赛题说起Sine之舞是什么第一次看到“Sine之舞”这道题是在蓝桥杯的练习系统里。题目要求输出一个嵌套的字符串序列形如An sin(1 - sin(2 sin(3 - ...))) Sn A1 n - A2 (n-1) - ... An 1说实话第一眼看到这个公式描述时我有点懵。但当你真正理解了它的递归本质会发现这其实是一道非常经典的“递归 字符串拼接”入门题既考察对递归调用的理解也考察对数学规律的归纳能力。这篇文章我想把自己的完整推导过程、代码实现和踩过的坑都整理出来。这道题适合三类人阅读正在备战蓝桥杯或其他算法竞赛的选手、刚学递归但总感觉“似懂非懂”的初学者、以及想找一道典型题目来练习“从问题到代码”完整思路的开发者。我会尽量把每一步的思考过程都写清楚而不是只丢一个最终代码。2. 读懂题目背后的数学规律2.1 A(n) 的嵌套结构拆解先看 A(n) 的定义。题目里给出的公式是A1 sin(1) A2 sin(1 - sin(2)) A3 sin(1 - sin(2 sin(3))) A4 sin(1 - sin(2 sin(3 - sin(4))))注意观察规律A(n) 最外层是sin(最里层是sin(n)中间的数字从 1 递增到 n。符号在减号和加号之间交替第 1 个是减号第 2 个是加号第 3 个是减号……也就是第 i 个符号当 i 为奇数时是-当 i 为偶数时是。用人话说A(n) 的结构就是从数字 1 开始不断在数字后面拼接一个符号和下一层的 sin直到数字 n。比如 A(4)sin(1 - sin(2 sin(3 - sin(4))))拆开来看就是先写sin(1然后遇到-接着是sin(2遇到再是sin(3遇到-最后是sin(4然后再补上对应数量的右括号。这里容易踩的第一个坑是符号的判断到底和什么有关我见过有人用全局变量记录当前拼接次数也有人用传入参数。实际上从定义看第 i 个符号只和 i 的奇偶性有关这在递归实现时很关键。2.2 S(n) 的组合规则再看 S(n) 的定义S1 A1 1 S2 A1 2 - A2 1 S3 A1 3 - A2 2 - A3 1对照着写出来S1 sin(1) 1 S2 sin(1 - sin(2)) 2 - sin(1) 1 S3 sin(1 - sin(2 sin(3))) 3 - sin(1 - sin(2)) 2 - sin(1) 1S(n) 的模式是从 A1 开始依次和数字n, n-1, ..., 1交替拼接连接符号也是交替的先是加号然后是减号循环往复。注意第一个连接符号是加号这和 A(n) 里第一个符号是减号恰好相反。我当年第一次做这题时把 S 的符号规律也按“奇数加、偶数减”去套结果前两项对后面全错。S 的符号规律更像是“加、减、加、减”交替即第 j 个连接符号j 为奇数时是j 为偶数时是-。仔细对照定义就能发现S(n) 里 A1 和数字 n 之间是加号A2 和数字 n-1 之间是减号。3. 递归实现的核心思路3.1 为什么用递归而不是循环这道题当然可以用循环做但用递归更贴合问题的数学本质。A(n) 的定义本身就是一个递归结构A(n) 等于sin(1 - sin(2 ... sin(n)))要构造 A(n)你需要先知道 A(n-1) 的一部分结构。更重要的是蓝桥杯这类竞赛题考察的往往是“你对问题的抽象能力”而不是单纯能不能算出来。用递归能把代码写得极其简洁也方便在考试中快速验证思路。A(n) 的递归函数可以这样定义def generate_A(i, n): if i n: return fsin({i} else: symbol - if i % 2 1 else return fsin({i}{symbol}{generate_A(i 1, n)})注意这里的symbol用的是-和而非题目描述的“减号和加号”原因是下一个数字前面的符号就是当前层拼接时决定的。比如 A(3) 的展开过程i1, 拼接 -结果为 sin(1 - generate_A(2, 3)) i2, 拼接 结果为 sin(1 - sin(2 generate_A(3, 3))) i3, 到达递归终点返回 sin(3 最后补上3个右括号sin(1 - sin(2 sin(3)))仔细看这个流程实际返回的字符串并没有在递归终点补右括号而是靠外层递归在返回时统一补上)。这是递归处理括号的一种常用套路左括号在进入时加上右括号在返回时补上一层层地闭合。3.2 生成 A(n) 时右括号的补全策略上面的代码有个细节需要特别注意当i n时我们返回的是sin(i而没有右括号。这个右括号由谁补答案是上一层的递归调用。因为每一层在拼接sin(i后必须有一个对应的)来闭合这个sin而这个闭合动作发生在当前层的 return 语句中。所以 A(n) 的完整结构就是每层进入时写sin(数字然后接着写符号和子问题最后统一加上)。这样写最大的好处是不需要单独计算右括号的数量递归本身天然完成了括号的配对。不过这里有个非常容易犯的错误递归终点如果返回fsin({i})会导致最内层的括号提前闭合最终多出一层括号。我第一次写的时候就在终点加了右括号结果输出变成了sin(1 - sin(2 - sin(3)))少了一层嵌套但字符串长度却对了非常隐蔽。所以记住递归终点只返回左半部分右括号统一由进入时的每一层负责添加。3.3 S(n) 的递归构造逻辑S(n) 的递归就相对简单了但要注意它的终止条件和拼接顺序def generate_S(n, i): if i n: return f{generate_A(1, i)}1 # 这里 i 等于 n但生成 A 时从 1 开始 symbol if i % 2 1 else - # 注意这里 A 的起点是从 1 开始但终点是 i return f{generate_A(1, i)}{symbol}{n - i 1}-{generate_S(n, i 1)}这段代码有个容易混淆的地方generate_S(n, i)中 i 表示当前要生成 A(i)但 A(i) 的递归起点是 1终点是 i。同时 S(n) 里拼接的数字是从 n 开始递减到 1 的所以第 i 项拼接的数字是n - i 1。举 S(3) 的例子i1: A1 3 - generate_S(3, 2) i2: A2 2 - generate_S(3, 3) i3: A3 1合并就是A1 3 - A2 2 - A3 1和题目要求完全一致。但注意这种方法里generate_S的基线条件是i n此时返回A(i) 1而中间过程的符号是-还是取决于 i 的奇偶性。这样看 S 的符号规律其实和 A 一样奇数位置是加偶数位置是减只不过因为 S 里第一项是 i1所以第一项是加号。4. 完整代码实现与运行验证4.1 Python 递归版本把上面两个函数组合起来就是完整的解题代码def generate_A(i, n): if i n: return fsin({i} symbol - if i % 2 1 else return fsin({i}{symbol}{generate_A(i 1, n)}) def generate_S(n, i1): if i n: return f{generate_A(1, i)}1 symbol if i % 2 1 else - return f{generate_A(1, i)}{symbol}{n - i 1}-{generate_S(n, i 1)} n int(input().strip()) print(generate_S(n))直接运行输入3输出为sin(1 - sin(2 sin(3))) 3 - sin(1 - sin(2)) 2 - sin(1) 1等等这里有个问题。题目要求的 S(n) 里A1 和 A2 之间的符号是加号还是减号从定义看S3 A1 3 - A2 2 - A3 1也就是 A1 和数字 3 之间是加号A2 和数字 2 之间是减号。但实际的嵌套关系中A2 是sin(1 - sin(2))它的外层右括号闭合后紧接着的数字是 2并且前面是减号。因此 A2 和数字 2 之间是-这符合公式描述。但我上面的代码里generate_S的拼接顺序是A1 3 - A2 2 - A3 1这没问题。但为什么我的代码中递归调用前面有个-仔细看return f{generate_A(1, i)}{symbol}{n - i 1}-{generate_S(n, i 1)}这个-是写死的因为 S(n) 从第二项开始A 和数字之间全是减号不例子中 A2 和 2 之间是减号A3 和 1 之间是加号不对啊。让我再仔细拆解。4.2 重新核对 S(n) 的符号规律再看原题的定义S3 A1 3 - A2 2 - A3 1。也就是说A1 和 3 之间3 和 A2 之间-A2 和 2 之间2 和 A3 之间-A3 和 1 之间所以实际上是在 S(n) 中A 的下标为 i 时它和数字 n-i1 之间的符号是加号i 为奇数或减号i 为偶数但数字和下一个 A(i1) 之间的符号总是交替的减号和加号不对看上面的结构里“3”和“A2”之间是-“2”和“A3”之间是-没有S3 里“3 - A2 2 - A3 1”所以 3 和 A2 之间是减号2 和 A3 之间是减号而 A2 和 2 之间是加号A3 和 1 之间是加号。换句话说这个表达式可以看成序列A1 3 - A2 2 - A3 1从整体看每一项是 “A_i 加号或减号 数字”其中 A_i 和数字之间的符号取决于 A_i 的下标 i而数字和下一个 A_{i1} 之间的符号固定是减号。但这样理解在编程实现时会变得很麻烦。更简单的方式是把 S(n) 当作一个字符串拼接过程。我们从 i1 开始拼接每次拼接内容为A(i) 符号 数字其中数字为 n-i1符号为如果 i 是奇数-如果 i 是偶数。比如 i1数字是 3符号是得到A13i2数字是 2符号是-得到A2-2i3数字是 1符号是得到A31但原式是A13-A22-A31对比一下会发现符号位置错了我们的方案得到的是A13-A22-A31吗i2 时符号是减号所以是A13-A2。这和原式开头完全一致。i3 时符号是加号所以整体是A13-A22-A31。这也一致。好那就是说我上面的代码思路是对的但我必须检查代码里的symbol和递归顺序。代码是return f{generate_A(1, i)}{symbol}{n - i 1}-{generate_S(n, i 1)}这里的问题是我在每一项的前面加了一个-而实际上符号已经由symbol决定了。这个多出来的-会导致什么比如 n3i1: A1 3 - generate_S(3, 2) i2: A2 2 - generate_S(3, 3) i3: A3 1所以结果是A13-A22-A31。但如果代码写成...{n - i 1}-{generate_S(...)}那 i1 时是A13-A22-A31实际上 i1 时有一个symbol然后拼接3再拼接写死的-然后是递归的 S(2)。S(2) 里又是A22-A31。合在一起是A13-A22-A31。这正好是原式因为原式中数字 3 和 A2 之间是减号而我们恰好用写死的-来连接。这说明一个巧合S(n) 中数字和下一个 A 之间确实是固定减号直到最后一项。但当 n2 时S2 A1 2 - A2 1。代码流程i1 返回A12-A21。原式也是A12-A21符合。当 n4 时S4 A1 4 - A2 3 - A3 2 - A4 1。代码流程i1 返回A14-A23-A32-A41。完全符合。所以这种拼接方式是可行的。但这里真的很绕我建议用更直观的方式干脆写一个循环来拼接 S(n)每次独立的生成 A(i)然后用符号连接。4.3 更直观的循环实现版本对于竞赛来说高频使用的往往是直接了当的循环方式因为递归虽优雅但容易在拼字符串时把符号搞混。用循环的方式S(n) 的逻辑就一目了然def generate_A(n): res for i in range(1, n 1): res fsin({i} if i ! n: res - if i % 2 1 else res ) * n return res def generate_S(n): res for i in range(1, n 1): res generate_A(i) res if i % 2 1 else - res str(n - i 1) return res n int(input().strip()) print(generate_S(n))这个版本生成 A(3) 时i1 会写sin(1-i2 写sin(2i3 写sin(3最后补 3 个右括号。中间用-还是取决于i % 2i 为奇数时是-。注意这里和递归版本的区别递归版本里符号是当前 i 对应的符号而循环版本里符号也是当前 i 对应的符号。S(n) 的循环版本同样清晰每项生成 A(i)然后拼接符号和数字n-i1。我实际测试下来循环版输出如下n4sin(1) 4 - sin(1 - sin(2)) 3 - sin(1 - sin(2 sin(3))) 2 - sin(1 - sin(2 sin(3 - sin(4)))) 1而递归版输出也相同。两个版本可以互为验证。5. 输入输出格式与细节规范5.1 蓝桥杯的输入输出要求这道题在蓝桥杯中的输入格式很简单一个正整数 n范围通常在 1 到 200 之间。输出要求是字符串形式且要求_严格符合公式中的空格_。注意题目描述里给出的示例是带空格的sin(1 - sin(2 sin(3))) 3 - sin(1 - sin(2)) 2 - sin(1) 1细节在于符号和数字之间有空格数字和后面的右括号之间没有空格但右括号后面如果是符号则有空格。我最初直接用fsin({i}{- if ...})这种拼接方式输出了不带空格的紧凑格式结果被判错。所以构造字符串时必须注意空格的位置sin(数字之间没有空格数字和符号之间有一个空格比如1 -、2 符号和下一个sin之间有一个空格比如- sin(2右括号和后面的符号之间有一个空格比如sin(1)) 3数字和右括号之间没有空格比如sin(3)中数字 3 和右括号)之间没有空格看了题目里的提示其实它已经给出了具体的空格规范。但如果你只写了逻辑没注意这些细节第一次提交大概率会吃一个“格式错误”的评判结果。5.2 空字符串与 n1 等边界情况当 n1 时S1 A1 1 sin(1)1。注意这里按照空格规范应当是sin(1) 1。循环版代码可以正确处理因为 i1 时生成 A1 后拼接1但我们在符号前后添加了空格。递归版同样适用。不过要特别小心循环版本中res ) * n当 n1 时它会补 1 个右括号正确。边界情况的另一个风险是如果 n 稍大比如 n200递归版会因为递归深度过大而出错其实 A 的递归深度最高到 200S 的递归深度也是 200对于 Python 默认的 1000 层递归限制来说绰绰有余。但如果 n 能到 10^5 级别就必须改为迭代。6. 竞赛应用与进阶思考6.1 这类题在竞赛中的定位Sine之舞在蓝桥杯中属于“基础题”中的偏中档题不算难但非常考验参赛者的递归思维和字符串处理能力。我见过不少人在考场上卡在符号规律上一是因为 S(n) 里的数字是倒序的二是因为 A(n) 和 S(n) 的符号交替规律容易混淆。其实这道题在考察的底层能力是“对递归式展开的理解”。如果你能真正手写出 A1 到 A4 的展开式那么代码基本就是翻译的过程。反过来如果你直接试图硬模拟公式可能会花很多时间调试。6.2 从这题延伸出去字符串拼接类题目的通用解法这类题的通用解法可以总结为三步先手动写出小规模输入的前几项结果找出递增规律将规律抽象为递归或循环结构注意边界条件检查输出格式空格、括号、符号再提交。我自己刷题时养成的习惯是每道字符串构造题都会在小黑板上手动写出 n1,2,3,4 的结果然后再写代码。这个小习惯帮我省掉了大量无意义的试错时间。Sine之舞也正是这样一道“手写几项就通了”的题目。7. 调试过程与常见错误实录7.1 我踩过的三个典型坑第一个坑是前面提到的递归终点多加了右括号。那时候我写的 A 函数返回fsin({i})看起来顺理成章但输出里总多一对括号。排查了很久才发现问题出在“终点返回的右括号和每层进入时添加的右括号叠加了”。理解递归的“进入和返回”对称性后问题迎刃而解。第二个坑是 S(n) 里的数字倒序。一开始我用了i直接拼接输出了A11-A2...和题目完全对不上。后来把 S(n) 定义展开写出来比对才意识到第 i 项的数字应该是n - i 1。这就是_没有先手写展开式_的代价。第三个坑是空格问题。我最初在生成 A(n) 时用fsin({i}后面直接跟符号导致出现了sin(1-sin(2))这种没有空格的错误输出。因为蓝桥杯的评测系统是字符串精确匹配所以必须严格按题目的空格规则来。我最终给符号两侧手动加上空格并在数字到右括号之间不加空格才通过。7.2 快速自测的方法写完代码后建议第一时间用 n1、2、3 手动验证。理论上如果这三个值都对了更大的 n 一般也不会有问题。如果你在校验时发现 n3 的输出多了个括号或缺了个空格优先检查递归终点和符号拼接部分。另外一个排查技巧是把 A(n) 和 S(n) 分开测试。先单独输出 A(3)确认它等于sin(1 - sin(2 sin(3)))再测试 S(3) 的组合。这样可以快速定位错误是在子函数还是主函数。8. 性能分析与优化空间8.1 时间复杂度和空间复杂度递归版和循环版的代码时间复杂度都是 O(n^2)。原因是每次生成 A(i) 需要 O(i) 的字符串拼接而 S(n) 中要对 i1 到 n 调用生成 A(i)所以总操作次数为 12...n n(n1)/2即 O(n^2)。对于 n ≤ 200 的题目规模这个复杂度完全没有压力运行时间基本在毫秒级。字符串拼接在 Python 中虽然理论上较慢但因为总长度不超过 n(n1)/2 量级实际不会成为瓶颈。8.2 是否可以优化到 O(n)可以。如果预先用循环生成所有 A(n) 的字符串并存起来后续直接查表拼接 S(n)就能把时间复杂度降到 O(n)。比如A [] * (n 1) A[0] for i in range(1, n 1): # 利用前一项生成当前项 # 但注意 A(n) 并不是简单的在 A(n-1) 上插入所以真的想 O(n) 得用别的方式严格来说A(n) 并不是 A(n-1) 的简单扩展因为 A(n-1) 的终点是 sin(n-1)而 A(n) 需要在 sin(n-1) 后面插入符号和 sin(n)。所以 A(n) 可以从 A(n-1) 的末尾右括号处插入但实现起来并不直观。竞赛场景下 n 很小O(n^2) 已经完全够用没必要为了优化而增加代码复杂度。9. 从 Sine之舞到更广的解题思维9.1 数学归纳法的实际应用Sine之舞这类问题本质上就是在考察“你是否能把一个递归定义的数学公式用程序语言翻译出来”。而递归定义在我看来就是编程里的数学归纳法你只需要证明“如果第 n-1 项是对的那么第 n 项就一定对”然后再证明第一项是对的整个方案就成立了。我在学习递归时最大的收获就是学会“假设子问题已经解决了”。在写 generate_A 时我根本不关心 generate_A(i1, n) 内部怎么实现我只知道它会返回一个合法的嵌套字符串我只需要把当前层的内容拼接好。这种思维模式在做很多复杂递归题时都能用上。9.2 应对竞赛中的“文字游戏”题蓝桥杯的题目往往不会直接告诉你“用递归”而是通过一个生动形象的名字比如 Sine之舞把数学规律藏起来。破解的关键永远是把题目描述转化为数学表达式再把数学表达式转化为递归或循环结构。整个过程有三个核心能力模式识别、抽象建模、代码落地。Sine之舞就是这三个能力的一个极佳训练样本。10. 我的个人实现技巧与建议最后分享几个我刷这道题时总结出来的小技巧希望对你有帮助。第一个技巧写代码前先用纸笔推导 A1、A2、A3、S1、S2、S3 的完整字符串并且用不同颜色的笔标出符号和数字。把规律看清楚了再动手绝对是事半功倍。第二个技巧严格控制输出格式。蓝桥杯对字符串题目的评测是严格的任何多余或缺失的空格都会导致错误。建议在构造字符串时单独把空格当成一个“字符”来看待而不是最后统一处理。第三个技巧如果递归版调试困难先写循环版验证正确性再尝试递归版。循环版虽然代码看起来繁琐但它更符合人类的直觉逻辑出错率更低。第四个技巧理解“递归终点只写一半”的括号配对方式。当你发现输出的括号数量不对时优先检查递归终点是否多写了右括号这是这类题目最高频的 Bug 来源。就我个人经验来说每次重新做这道题都会对递归和字符串拼接有更深的理解。建议你第一次做不出来没关系关键是把展开式写清楚然后照着展开式翻译代码一遍不行就两遍很快你就能完全掌握。