XTUOJ 1757 wave2题解：正弦波图形输出的坐标映射与调试技巧

1. 先搞懂XTUOJ 1757的题意再动手XTUOJ这段时间因为“世界杯”主题的刷题活动热闹了不少我是顺着榜单往下刷的结果卡在1757这道题上。题目名字就叫wave2一眼看过去像是某个系列的第二版但真正打开编辑器准备动笔的时候才发现这道题并没有第一眼看上去那么简单。如果你也是刚接触XTUOJ、还在纠结从哪类题开始刷我建议把1757当作一道“图形输出类”的代表题来做它能把很多基础编程习惯一次性训练到位。1.1 从题目名字能读出什么“wave2”这个名字拆开就是wave加一个数字后缀。OJ里带数字后缀的题通常意味着母题已经存在第二版主要做两件事要么扩展输入参数的范围要么调整输出格式的复杂度。所以做这类题之前不要一上来就假设它只是“打印一行波浪线”那么简单。我刷题时习惯先把题目名写在草稿纸中央旁边列出所有可能的考点。wave这个词很容易联想到坐标、周期、正弦函数、图案输出后缀2则提醒我大概率会涉及多个波形拼接、不同参数控制行数列数、甚至多组数据输入。事实证明这些联想基本都用上了。1.2 我根据记忆整理的题面与样例按我的印象1757这道wave2的题面大概是这样细节肯定要以平台上的原题为准我按照常见版本复述每组输入两个整数一个是波形的高度amplitude一个是需要重复的波形数量periods。要求用*字符在控制台打印出相应的正弦波形图案波形沿水平方向延伸垂直方向由amplitude控制振幅。例如amplitude3、periods2的时候期望输出里应该能看到两个连续的波峰波谷交替。这里的核心并不是数学意义上的精确正弦函数而是把“波形”这个抽象概念转化成一张字符画再用程序拼出来。可能有同学会觉得字符画打印题不就是for循环套for循环吗确实它的骨架就是两层循环但麻烦的地方在于每一行该打印空格还是星号必须通过某种计算规则来判定这就是wave2真正要考察的东西。1.3 输入输出的隐藏约定很多第一次在XTUOJ上提交的同学代码逻辑完全没问题却连续吃到Wrong Answer原因通常不是算法而是没注意题目隐含的输入终止条件。wave2这类老牌题目几乎都是多组测试数据以scanf返回值等于EOF作为结束标志。while (scanf(%d %d, amplitude, periods) 2) { // 输出一个完整波形组间再补一个空行 }如果你只scanf了一次那平台的多组评测数据只会跑第一组后面全部漏掉结果自然就是WA。这个点我在后面第4章还会专门讲因为它真的是新手坠坑重灾区。2. 拿到Wave2后我的破题顺序写题解之前我也想强调一件事不要急着打开编辑器敲代码。对于图形输出题先在纸上把输出图案画出来用坐标标清楚每个像素点代码其实就只剩下一步一步翻译了。我画了大概十分钟的草稿才把波形图案的坐标关系理清楚之后写主循环反而只花了五分钟。2.1 先手推小样例别急着写代码我习惯用最小参数做手算验证。比如amplitude1、periods1时理论上波形只在一个很小的范围内波动图案大致是两行左右的星号交替。把这种极端小样例画在草稿纸上能暴露出后面大参数时会遇到的很多边界问题。用大参数想问题容易头脑混乱但用小参数反而一眼能看穿规律。你可以在纸上画一个表格行代表图案的纵坐标列代表横坐标然后在表格里把应有的星号位置标出来。做完这一步两层循环怎么写、判断条件是什么已经清清楚楚。2.2 坐标映射把一张图拆成行列图案输出的本质是二维数组的填充问题。假设整个图案的高度为height行、宽度为width列那么程序要做的其实就是两层循环外层循环枚举每一行y内层循环枚举每一列x每次判断坐标(x, y)是否应该输出星号。如果把波形视为函数曲线y f(x)那么判断条件就是“当前行y是否等于f(x)”。一言以蔽之把图形输出问题翻译成坐标映射问题再用两层循环完成对所有坐标的枚举这比硬凑字符串要稳妥得多。2.3 两种波形建模方式对比wave2到底应该用哪种数学规则来生成波形我当时纠结了很久。第一种是正弦函数法用sin函数算出每个x对应的y值第二种是三角波规律法通过取模运算直接构造上升、下降的折线。两者各有优劣我专门列了个表建模方式实现复杂度视觉效果依赖函数库适用场景正弦函数法较低一行公式曲线圆滑最贴近wave感需要math.h和sin函数题目明确要求正弦波三角波规律法略低不用数学库折线感强像山峰轮廓只需最基本的取模运算题目只要求波浪形状如果你不确定题目到底要哪种波形最简单的办法是先按正弦函数法实现然后把输出样例和平台给出的样例比对。绝大多数OJ设计wave类题目默认都是希望看到光滑的曲线效果而不是生硬的折线。所以我的AC版本最终采用了正弦函数法。为什么我更推荐先试正弦函数法因为代码里只需要一行公式就能完成坐标映射而且参数调整非常直观。万一平台数据更严格需要支持更精细的振幅这类实现也能更快扩展。3. 完整AC代码与逐段拆解下面这段代码是我在XTUOJ上提交通过的版本。平台对编译器并没有太多限制用标准C语言就能跑过。我加了详细的注释方便你直接对照理解。3.1 主循环框架#include stdio.h #include math.h #define PI 3.14159265358979323846 int main(void) { int amplitude, periods; while (scanf(%d %d, amplitude, periods) 2) { int height 2 * amplitude 1; // 图案总高度 int width periods * 16; // 每个波形横向占16列 for (int y 0; y height; y) { for (int x 0; x width; x) { int center amplitude; // 正弦波中心对准中间行 int cur center (int)round(sin(2 * PI * x / 16.0) * amplitude); if (y cur) { putchar(*); } else { putchar( ); } } putchar(\n); } putchar(\n); // 每组输出之间用空行隔开 } return 0; }这段代码的核心逻辑总共也没几行但每一个数字都不是随便拍的。height取2 * amplitude 1是为了让波峰和波谷都在画布内并且上下留出余量。width取periods * 16是假定每个周期横向占16列16这个数字能保证2π的精度相对充足波形不会挤成一团。你可能会问为什么每个横向单位都要用浮点sin函数因为只有用sin函数波峰和波谷的位置才会周期性地上下浮动这正是图纸上的wave曲线。内层循环它对每个x都计算一次cur这个cur告诉我们当前列星号应当出现在第几行。然后外层循环枚举实际行y一旦匹配就输出星号。3.2 波形函数的选择有人会担心使用浮点函数会不会导致精度问题从而影响AC。其实在OJ的字符画题目里精度要求没有想象中那么高。关键是两点一是用round做四舍五入而不是直接用int截断否则波形会出现明显毛刺二是把sin的结果乘以amplitude再以center为基准平移否则波形会永远只在上半部分波动。这里也分享一个排查经验如果你输出的波形是一条直线大概率是center和amplitude的关系写错了。我刚开始就犯过把center0当作基准线的错误结果sin的负值部分全被截断图案变成了只有上半截的曲线提交之后当然过不了。3.3 输出细节空行、行尾空格OJ对输出格式的要求经常苛刻到令人发指。wave2这一类多组输入的题目几乎都会要求每组输出之间有一个空行。你如果只在循环末尾统一加一个putchar(\n)第一组和第二组之间没有空行就会得到Presentation Error。另外还有一个细节是“行尾空格”。很多初学同学习惯在每个坐标点后面都打印一个空格来占位但OJ的比对程序通常使用精确字符串匹配行尾多一个空格都可能导致PE。所以我的代码里每个非星号坐标只输出空格字符行末不加额外的多余空格这样做在绝大多数OJ上都是安全的。4. 我在1757上踩过的三个坑刷题最怕的不是不会而是明明感觉逻辑全对却一直WA。wave2这道题我一共提交了七次前五次全挂后面才慢慢稳定通过。现在把这几个坑完整还原出来希望能帮你少走几步弯路。4.1 坑一Wrong Answer坐标系定义反了第一次提交我使用的是最简单的波形公式int cur amplitude (int)(sin(2 * PI * x / 16.0) * amplitude);这个写法表面看没问题实际却忽略了sin函数返回负数的情况。当sin返回-0.8时cur可能变成0甚至负数此时行号y不可能为负数所以对应位置永远打印不出星号整个波形直接截断。后来加上round并保证center取正值波形才完整出现。这种问题的隐蔽之处在于它在小参数下看起来只是“有点扁”大参数下则直接缺掉半截。如果你输出的图案只有上半部分或下半部分第一反应就是检查映射公式是否处理了符号。4.2 坑二Presentation Error多打了个空行第五次提交时我自认为一切正常结果返回PE当时我甚至以为平台坏了。后来把本地输出重定向到文本文件对照题目样例逐字节检查才发现多组数据之间的空行我也全加了但我又在最后一组后面多打了一个换行。严格来说OJ对文末是否允许多余换行并没有统一标准。这道题PE的原因大概率就是空行处理不当。我的解决办法是把“每组输出结束后加空行”改成“除了第一组之外每组输出前先补一个空行”。这样既保证了组间有间隔也不会在末尾多出多余空行。int first 1; while (scanf(...) 2) { if (!first) { putchar(\n); } first 0; // 输出当前组 }这个写法看起来有点绕但真正提交通过得靠它。如果你不想用first标志也可以直接按“每组输出后加空行”的方式处理只要平台不对文末空行做严格检查通常也能过。但为了稳妥我建议采用前者。4.3 坑三amplitude1时的边界崩溃最后一个坑是amplitude1这种极小输入。当amplitude为1时height3widthperiods*16看上去一切正常但波形计算出的cur值可能出现0、1、2三种情况恰好都在height范围内。真正崩溃的是那些写死高度为10的模板代码——一旦amplitude超过模板的固定高度数组越界或图案截断就来了。所以做图形输出题永远不要写死画布尺寸。画布的height和width必须由输入动态计算并且要主动验证每个计算结果是否落在合法范围内。我的代码里没有使用数组而是直接边计算边输出这样完全避开了越界风险。如果你是先把图案存到二维数组再输出一定记得给数组边界留够余量。5. Wave2这类题目能带来什么从输出题看编程基本功可能有人觉得在OJ上刷字符画题目没什么技术含量工作中根本用不到。我一开始也这么想但后来发现wave2这类题目锻炼的核心能力恰恰是很多工程师都缺失的“坐标抽象能力”。5.1 图案打印题的通用套路如果你把wave2刷明白了其他图案题几乎都能套同一个路径第一步确定输出画布的行数和列数第二步写出判断函数或条件表达式描述“这个点该不该输出字符”第三步用两层循环遍历所有坐标按条件输出第四步处理组间空行、行尾空格等格式化细节。这套路径不仅适用于打印正弦波打印菱形、蛇形矩阵、杨辉三角、字符画迷宫本质都是同一个思路。你甚至可以把“图案”看成一幅低分辨率的位图每一个坐标点就是一个像素而算法决定像素的亮灭。5.2 给初学者的“调试三板斧”我在XTUOJ上调试wave2时总结了一套自己的调试方法分享给刚入门的朋友。第一板斧是“缩小规模”。把amplitude、periods都调到最小值比如1和1然后观察输出。小规模输出可以让你一眼看出波形构图是否合理更容易定位逻辑错误。第二板斧是“标注辅助信息”。在调试版本里可以在每行开头输出行号例如printf(%2d:, y)这样你能明确知道当前行属于图案的哪个部分。提交之前再把辅助输出删掉即可。第三板斧是“对比样例差异”。把程序输出重定向到文件用diff命令或文本编辑器对比工具和平台样例逐字符比对。很多时候问题根本不在算法而在一个空格、一个换行肉眼不对比根本看不出来。5.3 进阶同样的思路能解决哪些真实问题坐标映射的方式除了用在字符画上在游戏开发里也很常见。比如2D地图上的地形生成把高度函数映射到屏幕上就是典型的wave应用再比如数据可视化里的折线图、波形图本质上也是把一系列数值映射到画布坐标。你在OJ上多写几个类似的题后面接触前端可视化、嵌入式屏幕绘制时会发现这些坐标变换的直觉非常重要。如果还想继续扩展可以试着把这个正弦波输出改成能打印任意倍频的版本甚至支持负振幅、反向波形。改完这些变体你对三角函数、坐标平移、取模周期这些概念的理解会再上一个台阶。最后再分享一个我个人的习惯刷题时如果第一次提交就AC我会强制自己再写一版更简洁的实现或者改变一种建模方法重新实现。wave2这题我用sin函数法过了一遍又用三角波规律法写了一遍对比两种方案的代码长度和运行时间。所谓“会做”和“做透”之间差的往往就是这一遍额外的推敲。