Sine之舞这道题刷过蓝桥杯基础练习的人多少都见过。题目本身不给任何高级算法就一串sin来回套却能把不少新手卡在原地一整天。当初我练的时候也栽过跟头后来把An和Sn的生成规律彻底捋了一遍发现其实就是“递归规律”和“字符串拼接”两件事。这篇文章就把推导过程、完整代码和我在赛场上踩过的坑一次性写清楚适合正在备赛蓝桥杯的选手也适合刚学完递归想找实战练手的初学者。1. 题目还原Sine之舞的输入输出到底长什么样1.1 An的题目定义与样例展开蓝桥杯原题里定义了一组字符串用字母A表示前几项是这样的A1 sin(1)A2 sin(1-sin(2))A3 sin(1-sin(2sin(3)))A4 sin(1-sin(2sin(3-sin(4))))初看会觉得它就是在sin的参数里不断往里嵌新的sin。每增加一项就在最内层继续套一个sin(k)而且数字之间的符号是交替变化的A2里1和sin(2)之间是减号A3里2和sin(3)之间变成加号A4里3和sin(4)之间又变成减号。换句话说数字1后面跟负号数字2后面跟正号数字3后面跟负号如此交替。题目要求输入一个整数n输出对应的Sn。Sn不是直接等于An而是把An当作零件和数字n、n-1、...、1拼起来。1.2 Sn的组装规则初印象Sn的样例也给了几项S1 A11 sin(1)1S2 (A12)A21 (sin(1)2)sin(1-sin(2))1S3 ((A13)A22)A31稍微展开一点S2左边多了一个左括号A1后面跟的是“2”然后一个右括号接着是A2最后“1”。S3左边是两个左括号A1后面跟“3”右括号A2后面跟“2”又一个右括号A3后面跟“1”。这个结构和An很像区别在于An是往sin的参数里嵌套Sn是往表达式外层不断加括号。Sn需要你把An先求出来再按规则拼装。很多人在这一步就开始乱套因为Sn的左括号、加号、右括号、A串的位置太接近了手写都能抄错更别说写成代码。我看到这道题的第一反应是必须先找到形式化的规律再动手写代码。如果对着样例硬拼字符串n稍微大一点就会彻底乱掉。2. 拆解An一个隐藏着符号交替的递归串2.1 从A1到A4看结构变化把A1到A4并排看A1 sin(1) A2 sin(1-sin(2)) A3 sin(1-sin(2sin(3))) A4 sin(1-sin(2sin(3-sin(4))))可以把它理解成一个“洋葱”结构最外面是sin(1)1里面包着第二层第二层是sin(2)2里面包着第三层一直包到sin(n)为止。每一层往里包的时候需要带一个符号这个符号就写在这一层数字的后面。比如A3里1后面是减号表示要减去下一层2后面是加号表示要加上再下一层。于是An就能写成这种通式An sin(1 - sin(2 sin(3 - sin(4 ... sin(n))...)))从1开始数字i后面如果还有下一层就根据i的奇偶性决定符号i为奇数用减号i为偶数用加号。这个规则其实非常固定比背样例可靠得多。2.2 用递归函数生成An代码与逐层推演既然An是典型的自相似结构用递归是最自然的写法。定义一个函数g(i, n)它负责生成“从数字i开始一直到数字n”的那一层sin字符串。也就是说g(n, n) sin(n)当 i n 时g(i, n) sin( i 符号 g(i1, n) )其中符号由i的奇偶决定i是奇数时取减号i是偶数时取加号。对应的C代码string g(int i, int n) { if (i n) { return sin( to_string(i) ); } string op (i % 2 1) ? - : ; return sin( to_string(i) op g(i 1, n) ); } string A(int n) { return g(1, n); }拿n3走一遍g(1,3)发现1不等于31是奇数走减号返回sin(1- g(2,3) )g(2,3)发现2是偶数走加号返回sin(2 g(3,3) )g(3,3)等于n返回sin(3)。最后拼出来就是sin(1-sin(2sin(3)))和题目样例完全一致。这个写法的好处是把符号规律收敛到一行判断里。只要记住了“奇数减、偶数加”整个An生成就永远不会错。2.3 一个容易写错的非递归写法我也见过有人尝试用循环直接拼An写法大概是string badA(int n) { string s sin(1; for (int k 2; k n; k) { s (k % 2 0 ? - : ) string(sin() to_string(k) ); } s ); return s; }这个写法对n3会得到sin(1-sin(2)sin(3))根本不是题目要的sin(1-sin(2sin(3)))。问题出在哪它把加号和sin(3)拼在了sin(2)的外面实际上是“1减去sin(2)再加上sin(3)”而题目要求的是“1减去sin(2sin(3))”。差别就是一层括号的位置。所以An绝对不能靠简单循环从左往右平铺必须用递归让每一层sin的参数都“包住”右边的剩余部分。这个坑我印象很深因为很多初学递归的人第一次意识到“字符串也是可以递归构造的”。3. 拆解Sn括号、数字和An的排列顺序3.1 Sn的外层框架规律An解决了Sn本质上就是把An当作一个字符块插入到另一个规律字符串里。再看一遍题目给的样子S1 A11S2 (A12)A21S3 ((A13)A22)A31S4 (((A14)A23)A32)A41这里有一个非常清晰的规律Sn最前面连续出现n-1个左括号然后依次是A1、A2、...、An每个Ai后面跟着一个数字n-i1除了最后一个An后面不跟右括号其余每个Ai后面都要写一个右括号。写成形式化描述就是Sn (重复n-1次 A1 n ) A2 (n-1) ) ... An 1比如n4时S4 ((( A1 4 ) A2 3 ) A3 2 ) A4 1和题目样例完全吻合。3.2 循环拼接Sn的完整思路这个规律用循环实现非常直接string S(int n) { string s; for (int i 1; i n; i) { s (; } for (int i 1; i n; i) { s A(i); s to_string(n - i 1); if (i n) { s ); } } return s; }注意A(i)在这里不是An而是一个“从i层开始生成到n”的调用因为Sn里的每个Ai用的都是同一个总长度nA1 g(1,n)A2 g(2,n)...An g(n,n)。拿n3试一下先加两个左括号变成((然后A(1)即g(1,3)sin(1-sin(2sin(3)))加上3再加右括号接着A(2)即g(2,3)sin(2sin(3))加上2再加右括号最后A(3)即g(3,3)sin(3)加上1。合成结果就是((sin(1-sin(2sin(3)))3)sin(2sin(3))2)sin(3)1展开后和题目S3样例一致。3.3 为什么嵌套括号的数量是n-1很多人容易忽略一个细节为什么Sn前面要有n-1个左括号而不是n个或者别的数量从S1到S3观察括号数正好等于n-1。这个括号的作用是把前面的“A数字”整体包住让后面的运算保持嵌套。比如S3里两个左括号先连续打开两层然后A13之后闭合一层A22之后闭合第二层。如果括号数量改成n个整个表达式的括号配对就会失衡输出格式直接错误。做题的时候不需要纠结这个括号在数学上的运算优先级但写代码时必须严格按n-1来。我见过有人拿n去凑括号数结果S1就输出多一个左括号被评测系统判格式错误。4. 完整参考实现与边界用例验证4.1 完整C代码把递归生成An和循环拼接Sn合在一起就是一个完整的解法#include iostream #include string using namespace std; string g(int i, int n) { if (i n) { return sin( to_string(i) ); } string op (i % 2 1) ? - : ; return sin( to_string(i) op g(i 1, n) ); } int main() { int n; cin n; string ans; for (int i 1; i n; i) { ans (; } for (int i 1; i n; i) { ans g(i, n); ans to_string(n - i 1); if (i n) { ans ); } } cout ans endl; return 0; }这个代码包含了全部逻辑没有额外的头文件依赖蓝桥杯的评测环境可以直接运行。4.2 对n1和n4两个用例的验证n1时第一个for循环不添加任何左括号第二个for循环只执行i1ans g(1,1) sin(1)加上1i不小于n不加右括号。最终输出sin(1)1正是S1。n4时按照我们前面的形式化公式逐步拼接第一步添加3个左括号 (((。 第二步g(1,4)sin(1-sin(2sin(3-sin(4))))加4加右括号。 第三步g(2,4)sin(2sin(3-sin(4)))加3加右括号。 第四步g(3,4)sin(3-sin(4))加2加右括号。 第五步g(4,4)sin(4)加1。最终结果S4 (((sin(1-sin(2sin(3-sin(4))))4)sin(2sin(3-sin(4)))3)sin(3-sin(4))2)sin(4)1把题目给的结构代进去完全对应。4.3 复杂度分析与能否优化从时间复杂度看生成g(i,n)时每一层都要进行字符串拼接字符串长度是O(n)级别递归深度O(n)所以单个g(i,n)的复杂度是O(n^2)。main循环里最多调用n次g(i,n)整体复杂度是O(n^3)。n在蓝桥杯这类题里通常不超过两位数或三位数这个复杂度完全够用。如果追求效率可以用string的reserve提前分配容量减少拼接时的反复扩容。比如在main里先算个大概长度调用ans.reserve(n * n * 2)对性能有一点帮助但在这道题里不是必需。也可以把An的生成改成自底向上递推先算g(n,n)再往外拼但那样反而要维护一个数组代码没有递归版直观。竞赛里“能AC且好读”比“极致性能”更重要所以我个人推荐递归写法。5. 蓝桥杯赛场上的实操心得与避坑建议5.1 字符串拼接的效率陷阱C里直接用加号拼字符串确实方便但频繁拼接会反复产生临时对象时间复杂度翻倍。蓝桥杯这类题数据量小通常看不出问题但如果你把同样的思路带到n1000甚至更大的场景就可能超时。我的建议是main里初始化ans时顺手写一行ans.reserve(10000)量级大致按n*n估算。不用精算多点没坏处。这个习惯能让你从“蓝桥杯基础题”顺利过渡到“算法提高题”不会在字符串处理上吃暗亏。5.2 小心递归爆栈与函数签名设计g(i,n)的递归深度是nn不大的时候毫无压力。但如果题目某天把n加大到几万递归肯定爆栈。届时候要么改成递推要么把函数设计成尾递归形式。不过就Sine之舞这道题而言完全不需要担心。比较关键的是函数签名。我第一次写的时候把n写成全局变量函数只传i看起来简洁但遇到多组测试数据时容易忘记更新n。蓝桥杯的题往往单组输入全局变量问题不大可一旦你养成这种习惯在其他OJ题里就容易翻车。建议函数参数把i和n都显式传进去自包含、可读性强、也好调试。5.3 如何快速验证输出正确性赛场时间紧张不可能每次都用肉眼对比长字符串。我的调试套路是先测试n1、n2、n3这三个值的输出短能直接和题目样例逐字符比对。比对通过后再测n4重点看右括号数量和左括号数量是否匹配。一个小技巧在代码里临时加一个统计左右括号数的helper如果左右括号数不相等说明拼接逻辑有问题。写完AC代码后记得删掉调试代码。这个习惯帮我在不少字符串类题目里省了大量时间。另外输出时别忘了换行。很多新手把逻辑写对了最后因为没输出endl被判定presentation error这种丢分最冤。Sine之舞这道题说难不难说简单也不简单。它真正训练的是“观察样例、形式化规律、用递归表达自相似结构”这套通用能力。我后来做很多字符串递归题都会先想起这道题的洋葱结构。如果你练的时候卡住了不要盯着代码发呆先在纸上把A4和S4写出来规律往往比你想的更简单。
