1. 开胃Sine之舞到底是个什么题Sine之舞是蓝桥杯练习系统里非常经典的一道基础题看起来像数学题实际上是一道不折不扣的“字符串构造 递归/递推”题。题面不长输入只有一个自然数 n输出是一个特别长的、由 sin、数字、加号、括号组成的字符串。很多第一次碰到它的人第一反应是去算三角函数值或者被输出样例里那一大串括号绕晕。其实它根本不要求你算任何数值只要求你按照规律把字符串原样拼出来。这个“规律”有两个层次一个是 A_n 内部正弦嵌套的规律另一个是 S_n 外部拼接的规律。把这两层拆开看这道题就是送分题。我强烈建议准备蓝桥杯、正在学递归、或者想练习“根据规则生成字符串”的同学认认真真把这道题独立做一遍。它的价值不在于算法有多高级而在于它能训练你两件事一是从几项样例里反推模式二是把递归形式转化成代码时不出括号错误。这两个能力在后面的很多动态规划、表达式解析题里都用得上。题目给的定义大概是A_n sin(1 - sin(2 sin(3 - sin(4 ... sin(n))...)))S_n (A_1 n) - (A_2 n-1) - ... - (A_n 1)输入 n输出 S_n 对应的那个字符串。官方样例 n3 的输出长这样((sin(1)3)sin(1-sin(2))2)sin(1-sin(2sin(3)))1记住这个样例后面所有的推导都会围绕它展开。2. 剖开 A_n先解决正弦那层皮2.1 先把前几项写出来规律自己就蹦出来了遇到这类题第一步永远是“手写前几项”别急着敲代码。A_n 的前几项是A1 sin(1) A2 sin(1-sin(2)) A3 sin(1-sin(2sin(3))) A4 sin(1-sin(2sin(3-sin(4)))) A5 sin(1-sin(2sin(3-sin(4sin(5)))))从这五项的对比里能看出三件事不管 n 多大开头固定是sin(1。每增加一项就会在原来的内部再包一层sin(i)。连接 sin(1) 和 sin(2) 的运算符是减号连接 sin(2) 和 sin(3) 的运算符是加号sin(3) 和 sin(4) 之间又是减号sin(4) 和 sin(5) 之间又是加号。也就是说运算符在减号和加号之间交替而且第一个一定是减号。用一句话归纳在 A_n 中sin(i) 和 sin(i1) 之间的运算符当 i 是奇数时取减号当 i 是偶数时取加号。这个规律是整个 A_n 生成的核心。2.2 用递归定义把规律变成公式理解了规律后我们要把它写成可计算的递归形式。可以定义一个函数A(k, n)它表示“从 sin(k) 开始一直嵌套到 sin(n) 为止的字符串”A(n, n) sin(n) A(k, n) sin(k 运算符 A(k1, n) ) 其中 k n运算符怎么选就看 k 是奇数还是偶数。k 为奇数取减号k 为偶数取加号。举个例子。当 k1、n3 时A(1,3) sin(1 - A(2,3)) A(2,3) sin(2 A(3,3)) A(3,3) sin(3)一层层代入得到A(1,3) sin(1 - sin(2 sin(3)))和题面里的 A3 一模一样。为什么要以 k 的奇偶性来判断而不是以 n 或别的变量判断因为运算符出现在“当前这一层”和“下一层”之间它在字符串里紧跟在第 k 个 sin 后面。递归每次往下一层时k 加 1奇偶性翻转运算符自然交替。2.3 两种代码实现递归版和迭代版按照上面的递归定义Python 可以写成def gen_a_recursive(k, n): if k n: return fsin({k}) op - if k % 2 1 else return fsin({k}{op}{gen_a_recursive(k 1, n)})调用时传gen_a_recursive(1, n)就是 A_n。不过实际做题时我身边不少同学更习惯迭代写法因为少一层思考递归出口的负担。迭代的思路是先用sin(1开头然后从 2 开始逐个往后追加-sin(i)或sin(i)最后统一补 n 个右括号def gen_a_iterative(n): s sin(1 for i in range(2, n 1): if i % 2 0: s -sin( str(i) else: s sin( str(i) s ) * n return s注意这里判断i为偶数时追加的是减号和递归里判断k为奇数用减号并不矛盾。因为迭代里当前要追加的是“紧跟在 sin(i-1) 后面的运算符”而声明里的减号是“紧跟在 sin(k) 后面的运算符”角度不同判断方式就镜像了。自己写的时候建议固定一种思路千万不要两种混着看很容易绕晕。2.4 括号数量怎么自查A_n 这个字符串的括号必须是完全配对的而且左右括号数量都等于 n。原因很简单每出现一次sin(就会有一个左括号代码最后补了 n 个右括号正好一一对应。如果你手工推演或者程序调试时发现括号对不上先检查两处一是追加运算符时有没有漏写或-二是最后补右括号的数量是不是 n。还有一个常见低级错误就是把str(i)写成了str(i - 1)导致输出sin(0)这种错误在最内层的地方很难一眼看出来建议先用 n1 到 n5 的小样例逐个打印验证。3. 再战 S_n外层拼接才是重头戏3.1 题面公式和输出样例之间的矛盾A_n 只是第一步真正让很多人卡住的是 S_n。题面里的定义是S_n (A_1 n) - (A_2 n-1) - ... - (A_n 1)如果照这个公式直接拼接n3 会得到类似((sin(1)3)-(sin(1-sin(2))2))-(sin(1-sin(2sin(3)))1)但官方样例输出却是((sin(1)3)sin(1-sin(2))2)sin(1-sin(2sin(3)))1减号全部消失了。第一次看到这个差异的时候我一度以为是样例印错了。后来反复对照题目描述里“输出 S_n 这个表达式所对应的字符串”这句话才知道输出格式里把“- (”这两部分都省掉了只保留每个括号组的右括号和加号。换句话说题目要的不是带完整运算符的数学式而是经过整理的紧凑字符串。3.2 从样例反推真正的输出规则与其纠结题面怎么描述不如直接记住这个输出流程先输出 n-1 个左括号。对于 i 从 1 到 n输出A_i输出输出数字n - i 1如果 i 还没到 n再输出一个右括号。把这个流程写成模板就是( * (n-1) A1 n ) A2 (n-1) ) ... An 1用 n3 套一遍先输出 不对是 n-12 个左括号 ( ( i1A1 是 sin(1)输出 3因为是第 1 项后面加 ): ((sin(1)3) i2A2 是 sin(1-sin(2))输出 2后面加 ): ((sin(1)3)sin(1-sin(2))2) i3A3 是 sin(1-sin(2sin(3)))输出 1最后一项不加右括号 ((sin(1)3)sin(1-sin(2))2)sin(1-sin(2sin(3)))1结果和官方样例完全一致。所以写代码时千万别画蛇添足地去补减号。题面里的减号是数学含义输出规则里的紧凑字符串才是评测机真正比对的东西。3.3 为什么前导左括号是 n-1 个这一步很多题解都直接给结论但我想解释一下原因因为理解了才不会背错。观察样例n1 时输出是sin(1)1前面没有括号。n2 时输出是(sin(1)2)sin(1-sin(2))1前面有 1 个括号。n3 时输出是((sin(1)3)...前面有 2 个括号。规律就是 n-1 个前导左括号。这些括号本质上是在给每个“非最后一项”的分组做左边界因为每一组 i除了最后一组末尾都会输出一个右括号这个右括号需要一个对应的左括号。第 1 项的右括号其实对应的就是最外层前导括号第 2 项、第 3 项依次往后推。因此前导括号数恰好等于“后面要输出右括号的组数”也就是 n-1。多打印一个左括号最终的字符串括号数就不平衡少打印一个又会少一层包裹。调试的时候如果你发现字符串的左右括号总数不等优先检查这里。3.4 配合 A_n 生成 S_n 的代码现在把 gen_a 和 S_n 拼接逻辑合在一起。Python 完整版可以这样写def gen_a(n): s sin(1 for i in range(2, n 1): if i % 2 0: s -sin( str(i) else: s sin( str(i) s ) * n return s def gen_s(n): res [] res.append(( * (n - 1)) for i in range(1, n 1): res.append(gen_a(i)) res.append() res.append(str(n - i 1)) if i n: res.append()) return .join(res) n int(input()) print(gen_s(n))这里有一个实现细节不要用res ...反复拼接字符串尤其当 n 稍大时Python 字符串是不可变对象每做一次都会生成一个新的字符串复杂度容易被放大。更稳妥的做法是用列表把所有片段装起来最后.join(res)一次拼完。C 里string的一般有优化但用ostringstream或者先放进 vector 再拼接也是好习惯。3.5 S_n 的另一种理解方式递归版本如果你想练习递归S_n 也可以写成递归形式def gen_s_recursive(i, n): if i n: return gen_a(n) 1 return ( gen_s_recursive(i 1, n) ) # 需要小心不过注意这种“从右往左”递归写起来很容易乱因为它还要处理前导括号和右括号的位置。我个人建议如果只是为了拿分用上面那段迭代拼接的代码就够了清晰、不容易错递归版本留作理解 A_n 用即可。S_n 的拼接本质上是线性过程强行套递归反而增加出错概率。4. 完整 AC 代码与复杂度分析4.1 C 参考实现蓝桥杯的练习系统里 C 提交量最大很多学校教学也用 C。参考实现如下#include iostream #include string using namespace std; string genA(int n) { string s sin(1; for (int i 2; i n; i) { if (i % 2 0) s -sin( to_string(i); else s sin( to_string(i); } for (int i 0; i n; i) s ); return s; } string genS(int n) { string s; for (int i 0; i n - 1; i) s (; for (int i 1; i n; i) { s genA(i); s ; s to_string(n - i 1); if (i n) s ); } return s; } int main() { int n; cin n; cout genS(n) endl; return 0; }4.2 Java 参考实现import java.util.*; public class Main { static String genA(int n) { StringBuilder sb new StringBuilder(sin(1); for (int i 2; i n; i) { if (i % 2 0) sb.append(-sin().append(i); else sb.append(sin().append(i); } for (int i 0; i n; i) sb.append()); return sb.toString(); } static String genS(int n) { StringBuilder sb new StringBuilder(); for (int i 0; i n - 1; i) sb.append((); for (int i 1; i n; i) { sb.append(genA(i)); sb.append().append(n - i 1); if (i n) sb.append()); } return sb.toString(); } public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); System.out.println(genS(n)); } }Java 这里我用StringBuilder而不是 String 拼接主要就是为了避免创建大量中间字符串。虽然这道题 n200 时用 String 也能过但养成良好的拼接习惯没有坏处。4.3 复杂度分析n200 到底会不会超时很多第一次做题的人会担心输出太长。我们来实际估算一下。A_i的长度大概是O(i)量级。比如 i200 时字符串里有 200 个sin(片段、200 个数字、200 个运算符和 200 个右括号再加上数字本身的位数总长度大概在 1000 多字符。S_n 要把A_1到A_n全部拼接起来总长度大约是n * 所有 A_i 的平均长度也就是O(n^2)级别。n200 时总字符数大概也就几十万级别。这个规模无论 Python 还是 C 都能轻松应付。真正值得注意的是输出时间。几十万字符一次性输出没问题但如果你在循环里用cout 或System.out.print逐字符输出IO 开销会变大。稳妥做法是先拼成完整字符串再一次输出。代码里就是这么做的。5. 实战中的坑与排查5.1 高频错误速查表错误现象常见原因解决方法输出里出现sin(0)数字从 0 开始计数确认循环从 1 开始字符串最后多一个右括号最后一项也加)只在i n时加右括号前导括号数量不对写了 n 个而不是 n-1 个先手工推 n2 样例验证运算符全是减号或全是加号奇偶判断写反手写 A2、A3 对比输出比样例多出一堆减号照着题面数学式硬拼记住输出规则省略减号A_i 本身括号不平衡右括号补了 n-1 个而不是 n 个数一遍 A3 的括号数量这六条错误基本覆盖了大部分人在这个题上踩过的坑。尤其是“画蛇添足补减号”那条几乎每个第一次接触这道题的人都会犯。我的建议是拿到任何输出题先拿样例输入把预期输出抄在纸上然后让自己的程序输出和纸上完全对齐不要凭感觉。5.2 调试技巧先单独验证 A_n我调试这道题时的习惯是分两步走。第一步只写gen_a然后分别打印 n1、2、3、4、5 的结果和手写的前几项对比A1 sin(1) A2 sin(1-sin(2)) A3 sin(1-sin(2sin(3)))只要这一步对了说明运算符规律没问题。第二步再写 S_n 的拼接逻辑打印 n1、2、3 的结果对比官方样例。n3 是你最好的测试用例因为它的前导括号、右括号、A2、A3全都覆盖到了。如果 n3 能对上这道题基本就稳了。5.3 递归版本常见问题栈溢出这道题 n 最大只有 200递归深度最多也就是 200 层完全不会栈溢出放心用。有些同学可能因为被“200”这个数字吓到担心递归太深。实际上 200 层递归在默认栈空间下绰绰有余几个毫秒就能跑完。真正需要担心的是如果 n 范围扩大到几万递归就未必合适了到时候再用迭代写法也不迟。5.4 一个容易被忽略的细节n1n1 是个很特殊的边界。按输出规则n-10 个前导括号S_n 就是A_1 1也就是sin(1)1。有些同学写 S_n 时因为循环里的“非最后一项加右括号”判断写得不对导致 n1 时输出变成sin(1)1)或者(sin(1)1这就错了。所以提交前一定要单独测一次 n1。还有一点输入数据保证 n 是正整数不需要处理 n0 的情况但如果你自己扩展练习可以把 n0 的防御也写上。6. 这类“字符串构造题”的通用心得做完 Sine之舞我觉得最值得沉淀的不是这道题本身而是它背后的一套通用解题方法。以后遇到类似的“按规则生成字符串”的题你都可以照着这个套路走第一步手写前几项把规律可视化。不要直接上代码。S_n 的规律如果不写前几项你很难意识到减号被省略了。第二步把复杂结构拆成两层。A_n 是一层S_n 是另一层。每一层单独验证不要等两层拼完再整体对拍。两道锅叠一起出了问题你连是哪层错了都分不清。第三步用样例输出反推格式而不是用题面公式直接翻译。竞赛题的输出格式常常和数学定义有细微差异样例是唯一权威。我自己第一次做这道题时就是照着题面的(A_1n)-(A_2n-1)硬写结果输出里全是减号样例怎么都对不上。后来把样例拆开发现减号根本不存在才反应过来题目输出的是一个“压缩后的表达式字符串”。从那以后我对所有输出类题目都会对样例做一次逐字符比对不再想当然。如果你正在备赛建议把这道题和斐波那契数列的递归版本放在一起整理进笔记。它们都体现了同一个核心思想把大问题拆成小问题把小问题的输出作为大问题的一部分。区别只是 Fibonacci 返回数字Sine之舞返回字符串。会处理字符串递归之后很多类似题都能一通百通。
