题目是信息学竞赛和考研机试里的一道经典递归入门题东华OJ把它放在进阶题第7题的位置确实有道理。这道题表面是让你“输出一串花里胡哨的公式”实际考的是对递归结构的分拆能力以及C里字符串拼接的基本功。网上不少题解直接甩一段代码但没讲清楚An和Sn到底是怎么嵌套出来的导致很多人抄完代码还是一头雾水。今天这篇文章就把这道题的拆解思路、代码实现、常见坑一次性讲透。1. 东华OJ“Sine之舞”到底在考什么1.1 题目本身的直观感受先看一眼题目描述输入一个整数n输出对应的Sn表达式。n的取值范围一般不超过10但题目给的样例输出长这样n 3时 Sn ((sin(1)3)sin(1-sin(2))2)sin(1-sin(2sin(3)))1我第一次看到这个样例的输出说实话也有点懵。感觉像是某个公式被拆成了奇奇怪怪的嵌套结构括号一会儿有一会儿没有加号一会儿跟在这个括号后面一会儿又出现在别的地方。如果你直接动手写大概率会卡在“不知道从哪里开始输出”这个问题上。其实这道题的核心就两个函数A(n)生成sin(1-sin(2sin(3-...)))这种嵌套的An表达式。S(n)生成(...n-1)sin(...)n-2...这种嵌套的Sn表达式。理解了这个结构之后剩下的就是C基础语法的问题了。1.2 为什么说它是“进阶题”这道题被归为进阶不是因为算法本身有多难而是考察三个层面的能力第一层是观察能力。能不能从输出样例中看出A和S是两套独立的嵌套结构而不是一大坨需要硬编码的东西。很多新手看到样例输出第一反应是“我按字符串拼就行”但题目输入是动态的手动拼只能拿到一个测试点。第二层是递归思维。A(n)和S(n)都是一个递归定义的结构An sin(n)或An sin(n - A(n-1))Sn n - S(n-1)的变形。你需要在代码中用递归或递推方式去表达这种自相似结构。第三层是C字符串处理能力。这道题在C里做天然要用到string类的拼接、插入操作。很多人在纸上画规律画得很好一写代码就卡在字符串拼接的顺序上。所以东华OJ把它放在进阶题阶段刚好卡在“入门语法已经会了但还没有形成算法思维”这个过渡期。能独立写出来的人递归和字符串这块的地基就打得差不多了。2. 拆解Sine之舞的两个核心公式结构2.1 A(n)的表达规律与递归定义先只看An部分。n1时sin(1)n2时sin(1-sin(2))n3时sin(1-sin(2sin(3)))n4时sin(1-sin(2sin(3-sin(4))))仔细观察A(n)并不是简单地在A(n-1)右边拼一段。它的规律是A(n) sin( 1 符号 A(n-1的子结构) )更准确地说当n1时直接返回sin(1)当n1时应返回sin(1 运算符 A(2) 运算符 A(3) ... 的嵌套形式)这里有一个相对容易理解的角度如果我们从最里层往外写第n项永远是sin(n)第n-1项是sin(n-1 ± sin(n))第n-2项是sin(n-2 ± sin(n-1 ± sin(n)))。可见它是一个从内往外逐层扩展的过程。每往外套一层里面的数字要加1符号由奇偶决定——第2层用减号第3层用加号第4层用减号交错出现。符号规律第i层从外往内数最外层i1当i为1时没有前面的符号从第二层开始奇数位置的运算符是减号偶数位置的运算符是加号。换一种写法在sin(i 运算符 ...)这个结构中如果i是奇数运算符是减号如果i是偶数运算符是加号。唯独最外层的数字1前面没有运算符。我们可以用递归函数这样写string makeA(int n, int current) { if (current n) { return sin( to_string(current) ); } char op (current % 2 1) ? - : ; return sin( to_string(current) op makeA(n, current 1) ); }这个函数理解起来比较容易输入总层数n和当前层号current。当current等于n时直接返回sin(n)否则在当前层拼上sin(current 符号...)符号由current的奇偶决定然后递归调用下一层。举例验证调用makeA(3, 1)时current1不是3符号是-返回sin(1- makeA(3,2) )current2符号是返回sin(2 makeA(3,3) )其中makeA(3,3)返回sin(3)拼接起来就是sin(1-sin(2sin(3)))和题目要求完全一致。2.2 S(n)的嵌套规律与边界条件再看Sn部分。样例中说Sn (...A(n)n-1)A(n-1)n-2...这里的结构比An更复杂一些因为它把An整体当作一个项来拼。S(1) sin(1)1S(2) (sin(1)2)sin(1-sin(2))1S(3) ((sin(1)3)sin(1-sin(2))2)sin(1-sin(2sin(3)))1S(4) (((sin(1)4)sin(1-sin(2))3)sin(1-sin(2sin(3)))2)sin(1-sin(2sin(3-sin(4))))1S(n)的递归规律比An稍微复杂一点但仔细观察会发现S(n)从右往左看就是若干个...An 数字的结构叠加。从最里层最右边开始每一项是An然后跟着一个加号和数字。数字从1开始递增直到n-1最外层左边会有n-1个左括号。我们可以把S(n)看成从右往左构建的过程初始化时res A(1) 1当i从2到n每次都把当前res套上一层括号然后在括号右边拼接A(i) i例如i1res sin(1)1i2res (sin(1)2)sin(1-sin(2))1i3res ((sin(1)3)sin(1-sin(2))2)sin(1-sin(2sin(3)))1这和目标样例的输出完全对应。所以Sn的递归表述可以是string makeS(int n) { string res makeA(1, 1) 1; // 最里层基础 for (int i 2; i n; i) { res ( res ) makeA(i, 1) to_string(i); // 注意不是res ( res )还要在前面拼上A(i) } return res; }等等这里的循环写法敲代码时要特别小心上面这个伪代码里( res )和makeA(i,1)的顺序需要推敲。S(3)的推导过程是初始res sin(1)1i2时S(2) (sin(1)1的什么东西 )吗实际上S(2) (sin(1)2)sin(1-sin(2))1这里是(sin(1)2)A(2)1。所以规律其实是每次迭代时把已生成的res最外层套上括号然后前面拼A(1)加数字不对再理一遍。用最直观的方法S(n)的从外到内结构是S(n) ( ( ... ( A(1) n ) A(2) (n-1) ) A(3) (n-2) ... ) A(n) 1注意里面数字是递减的从n到1。这个结构里最外层左边有n-1个左括号最右边是A(n)1倒数第二层是A(3)2等等。所以如果从最外层开始递归S(n) 如果 n 1返回 A(1)1 否则返回 ( S(n-1) ) A(n) n等一下验证一下n2的情况按照上面公式S(2) ( S(1) ) A(2) 2S(1) sin(1)1A(2) sin(1-sin(2))所以S(2) (sin(1)1)sin(1-sin(2))2但题目中S(2)的预期输出是(sin(1)2)sin(1-sin(2))1数字的顺序和加号位置有出入。说明方向反了。换个思路题目输出里S(2)是(sin(1)2)sin(1-sin(2))1数字是2在sin(1)后面1在最后。S(3)是((sin(1)3)sin(1-sin(2))2)sin(1-sin(2sin(3)))1。数字分布是用3、2、1递减从左到右嵌入不同层级的。所以正确的递归规律应该是S(n) 左括号 A(1) n 右括号 A(2) (n-1) 右括号... A(n) 1也就是说中间那部分A(1)n是最外层不是最内层。如果把它转成递推构建我们可以从内到外换个方向先构建最右边的A(n)1然后向左扩展A(n-1)(n-1)但每次都套一层括号。用代码描述string res makeA(n, 1) 1; // 最右边的部分 for (int i n - 1; i 1; i--) { // 每次在前面包一层括号然后把新的部分放在括号内左侧 res ( makeA(i, 1) to_string(i) ) res; }验证n3初始res A(3)1 sin(1-sin(2sin(3)))1i2res ( A(2) 2) res (sin(1-sin(2))2)sin(1-sin(2sin(3)))1i1res ( A(1) 3) res (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(1)3)sin(1-sin(2))2)sin(...)1括号位置差在第二层A(2)的那个部分。这说明我上面这个递推公式里括号和A(2)的拼接逻辑有出入正确答案应该是A(2)不是包在自己的括号里而是和前面的A(1)3同一层。重新观察样例((sin(1)3)sin(1-sin(2))2)sin(1-sin(2sin(3)))1。去掉最后一层看前边部分其实是((sin(1)3)sin(1-sin(2))2)再往内一层是(sin(1)3)sin(1-sin(2))再往内一层是sin(1)3。所以它的展开逻辑变成S(1) A(1) 1 sin(1)1作为基准但这只是底层结构不是实际输出S(2) ( A(1) 2 ) A(2) 1S(3) ( S(2)的前面加一个括号不对。我们拆S(3)的结构S(3) ((sin(1)3)sin(1-sin(2))2)sin(1-sin(2sin(3)))1从最外层看S(3) X A(3) 1其中X ((sin(1)3)sin(1-sin(2))2)。 X Y A(2) 2其中Y (sin(1)3)。 Y ( A(1) 3 )。也就是说真正的规律是S(n) f(n) A(n) 1 f(n) f(n-1) A(n-1) n-1 ...?但是注意Y (sin(1)3)和S(2)里的(sin(1)2)形式很相似只是S(2)后面直接接A(2)而Y后面接的是A(2)然后整个外包括号。所以可以定义辅助函数T(m)表示(sin(1)m)sin(1-sin(2))...即从A(1)m开始到A(m)的部分T(m) (A(1)m)当m1时对于m1T(m) ( T(m-1) ) A(m) m不对T(2)应该是(sin(1)2)sin(1-sin(2))1但这是S(2)整体也就是T(2)S(2)T(1)sin(1)1。T(3)应该是S(3)去掉最后的A(3)1之后的((sin(1)3)sin(1-sin(2))2)。这里T(3) ( T(1)替换版本(sin(1)3) A(2) 2 (sin(1)3)sin(1-sin(2))2这已经是去掉最后A(3)1的部分了。所以T(3) ( A(1) 3) A(2) 2 (sin(1)3)sin(1-sin(2))2。注意T(3)前面并没有两个左括号因为(sin(1)3)本身已经带了左括号。T(4)就会是((sin(1)4)sin(...)3)sin(...)2也就是T(4) ( (A(1)4) A(2)3?...)。总结出最终规律我们可以用循环从外到内构建字符串 ans 表示S(n)的最终结果 前置预备先处理最外层的A(1)n?其实最简洁的构建方式是从 i n 到 1 如果这是第一次in先拼上 A(1) n 否则 在已有结果左边拼上 ( A(1?) i?这种表述绕来绕去容易出错。更稳的方式是使用递归函数buildS(n)string buildS(int n, int k) { // 返回从第k层开始构建的部分k从1到n }不过对于大多数参赛者来说最简单可靠的做法是先构造An数组再构造Sn。An部分用一个递归或递推函数生成并存储A[1..n]Sn部分从里向外扩展。这里给一个最不容易出错的递推构建方法我们已知S(1) A[1] 1 S(2) ( A[1] 2 ) A[2] 1 S(3) ( ( A[1] 3 ) A[2] 2 ) A[3] 1观察括号的分布每次迭代时把当前res整体包一层括号然后在res的里面、最左侧插入A[1]当前数字不对实际是在res前面加(然后往里面塞入A[1]数字的更新版。用递推式表达可能反而复杂。我们可以用另一个思路直接模拟从左到右的拼接过程。S(n)最左端是n-1个左括号然后是A(1)n然后是)A(2)(n-1))A(3)(n-2)...直到A(n)1。所以可以用一个循环string res; // 先输出 n-1 个左括号 for (int i 1; i n; i) res (; // 然后依次输出 A[1] n, ), A[2] (n-1), )... for (int i 1; i n; i) { res A[i]; res to_string(n - i 1); if (i ! n) res ); }验证n3先加两个左括号((i1A[1]sin(1)加号3((sin(1)3i不是n加右括号((sin(1)3)i2A[2]sin(1-sin(2))2((sin(1)3)sin(1-sin(2))2加右括号((sin(1)3)sin(1-sin(2))2)i3A[3]sin(1-sin(2sin(3)))1((sin(1)3)sin(1-sin(2))2)sin(1-sin(2sin(3)))1完美符合题目输出样例。这个循环构建方式不涉及递归逻辑也直白强烈推荐。2.3 符号交替规律的严谨推导前面提到A(n)里的符号是交替的。什么时候是加号什么时候是减号看样例A(2) sin(1-sin(2))1和sin(2)之间是减号A(3) sin(1-sin(2sin(3)))2和sin(3)之间是加号A(4) sin(1-sin(2sin(3-sin(4))))3和sin(4)之间是减号所以规律是第k层内部如果k是奇数则用减号如果k是偶数则用加号。最特别的是第1层数字1前面没有运算符因为它直接跟在sin(后面。如果写成递归式就是A(1) sin(1) A(k) sin( k (k%21 ? - : ) A(k1) ) 当 kn 时注意上面这个表述里k是当前层数字不是总层数。从外层到内层k从1递增到n。第k层的符号由k的奇偶决定。自己推导的时候可以画一张表n4时A(4) sin(1-sin(2sin(3-sin(4))))读你的时候会发现1后面是减号2后面是加号3后面是减号对应奇数为减、偶数为加清晰明了。3. C代码实现与逐段讲解3.1 生成An数组的基础函数理解了规律后代码就水到渠成了。先生成A[1]到A[n]#include iostream #include string using namespace std; string makeA(int n) { string ans sin( to_string(n) ); for (int i n - 1; i 1; i--) { char op (i % 2 1) ? - : ; ans sin( to_string(i) op ans ); } return ans; }这里用了一个从内向外递推的思路。以n3为例初始ans sin(3)i2sin(2sin(3))sin(2sin(3))i1sin(1-sin(2sin(3)))sin(1-sin(2sin(3)))符号判断当i2时i%20使用i1时i%21使用-。与规律一致。注意这里to_string函数是C11引入的东华OJ的编译器一般支持C11如果遇到特别老的编译器比如某些OJ只支持C98to_string可能不可用需要自己写一个int转string的函数。建议提前确认一下评测机的标准不行就手动转换string intToStr(int x) { if (x 0) return 0; string s; while (x 0) { char c 0 (x % 10); s c s; x / 10; } return s; }3.2 生成Sn的递推主函数拿到A数组之后生成S(n)就简单了。直接用前面验证过的“先输出左括号再逐层拼接”的方式string makeS(int n) { // 提前生成所有 A[1]..A[n] string A[11]; for (int i 1; i n; i) { A[i] makeA(i); } string res; // 先拼接 n-1 个左括号 for (int i 1; i n; i) { res (; } // 逐层拼接 A[i] 数字 ) for (int i 1; i n; i) { res A[i]; res ; res to_string(n - i 1); if (i ! n) { res ); } } return res; }主函数int main() { int n; cin n; cout makeS(n) endl; return 0; }这个写法简洁、不容易错而且没有递归爆栈的风险。完整的参考代码如下#include iostream #include string using namespace std; string makeA(int n) { string ans sin( to_string(n) ); for (int i n - 1; i 1; i--) { char op (i % 2 1) ? - : ; ans sin( to_string(i) op ans ); } return ans; } string makeS(int n) { string A[11]; for (int i 1; i n; i) { A[i] makeA(i); } string res; for (int i 1; i n; i) { res (; } for (int i 1; i n; i) { res A[i]; res ; res to_string(n - i 1); if (i ! n) { res ); } } return res; } int main() { int n; cin n; cout makeS(n) endl; return 0; }这个代码在n3时输出((sin(1)3)sin(1-sin(2))2)sin(1-sin(2sin(3)))1与题目样例完全一致。3.3 一个容易混淆的等价写法网上还能看到另一种写法把Sn也用递归生成string makeS(int n) { if (n 1) { return makeA(1) 1; } return ( makeS(n - 1) ??? }这种写法需要注意makeS(n)如果直接定义为S(n)整体那么( makeS(n-1) )会多出一些与题目不符的括号。因为前面分析过S(n)并不是简单在S(n-1)外层套括号。所以递归版需要定义一个辅助函数处理“某一层”的拼接稍微麻烦一点。比较下来循环构建Sn的方案更符合直觉推荐优先使用。4. 实战调试常见错误与避坑指南4.1 加号和减号的位置写反这是最常见的错误。有人会以为An的符号规律是“第一层用减号第二层用加号”于是把判断写成了if (i 1) op -; else op ;输出sin(1sin(2-sin(3)))之类的错误结果。正确做法是按当前层数字的奇偶判断奇数层减号偶数层加号。也就是(i % 2 1) ? - : 。我刚开始也在这上面栽过跟头对着样例自查了很久才反应过来。4.2 括号数量不对Sn最外层左边应该有n-1个左括号。n5时最前面一定是四个(。如果你最后输出的字符串里左括号数量少于n-1或者右括号多出来了多半是循环边界出了问题。推荐一个自查方法手动写出n2、n3的输出逐字符对比。n2的答案很短一眼就能看出括号对不对n3的完整字符序列可以拿来对照。4.3 数字拼接时用错了to_string位置在Sn的拼接中加号后面的数字是从n递减到1的。也就是说最左边配的是n最右边是1。我当时第一反应是写成了to_string(i)输出就变成((sin(1)1)...这种顺序错乱的结果。这类错误用眼睛很难发现最好的办法是打印中间变量分别输出A[1]、A[2]、A[3]和最终的res确认A数组本身没有错再检查Sn的逻辑。4.4 忘记处理n1的边界情况当n1时S(1) sin(1)1。这个用例必须单独验证。代码里Sn部分左边循环for (int i 1; i n; i)当n1时不会执行res为空。主循环执行一次输出A[1] 1刚好是sin(1)1。所以上面这套代码天然支持n1不需要特判。但如果你用递归写法n1的边界条件就要仔细处理。4.5 OJ提交时的输入输出格式东华OJ这一类题目对输入输出格式要求比较严格。输入只有一个整数n输出是Sn的字符串最后要换行。我提交过几次发现容易踩的坑是输出多余的换行或空格。用cin n读入后直接cout makeS(n) endl;即可不要在前后加额外输出。4.6 一个容易忽略的坑字符串长度与内存n最大是多少题目通常没有明确说但根据东华OJ的原题n不超过10。即便n20字符串长度也在可接受范围内。不用过度担心性能。但要注意OJ的栈空间如果用了递归生成大n的A(n)递归深度也就是n完全没问题。5. 从Sine之舞延伸这类题的通用套路5.1 递归题的核心观察法Sine之舞这类题的通用解法是先不要急着写代码先手算3-4个长度的结果把规律写在纸上。等你能用自然语言把“从第几层开始、符号怎么变、括号怎么嵌套”说清楚了再动手写代码效率高得多。矩阵覆盖、汉诺塔、斐波那契这类递归题也都可以先画递归树或者写展开式找最小重复单元。5.2 字符串拼接题的调试技巧跟字符串相关的OJ题调试时最痛苦的就是看不出细微差别。我常用的三个办法打印长度对比预期输出和实际输出的长度。如果长度不一样括号或数字肯定有缺漏。分段比对把预期字符串按An或数字位置拆成几段逐一比对。用diff查看在本地把两个字符串写到文件里用diff命令或编辑器的对比功能高亮差异一步定位问题。5.3 变式练习反推或组合如果把Sine之舞稍微改一下比如符号规律变成“第几层是否有数字2出现则使用减号”或者要求输出带缩进的树状表达式本质上还是同一个思维。建议做完之后试着自己改一下An的生成规则看Sn怎么跟着变能加深理解。另一个常见变式是不使用string拼接改用字符数组。在老一点OJ不支持C11的情况下用char数组手动拼接也是一种基本功建议了解。6. 我的个人体会与总结建议这道题做下来我自己最大的收获不是背会了一种字符串拼接方法而是学会了“如何把嵌套结构拆成最小单元再一步步组合”。很多人卡住是因为一开始盯着完整S(3)那串长输出发呆但实际上拆开之后就是一个An生成函数和一个Sn拼接循环。如果你正在刷OJ进阶题我的建议是先花10分钟在纸上推A(1)到A(5)、S(1)到S(3)形成直觉。代码尽量写成“生成An数组”和“拼接Sn”两个独立部分方便调试。提交之前把n1、n2、n3都测一遍尤其是样例给的那组数据必须一字不差。最后再分享一个小技巧我在本地测试的时候会把makeA(i)的结果单独打印出来检查而不是直接盯最终输出。这样一旦Sn出问题能立刻判断是An的锅还是拼接的锅。这个方法适用于所有类似的多步骤字符串构造题省了非常多排查时间。