『ACM C++』PTA浙大 | 基础题 - 打印沙漏
2019-02-25 16:09:30来源:博客园 阅读 ()
《数据结构》开课前的一些小作业练习,可能因为一个寒假都没有打C++手生了,整个寒假都在帮拍电影做后期特效,导致这道题居然用了两个钟去AC,深感惭愧,作个标记吧,下面上题。
一首好曲推荐:同时我也设置成了我的博客背景音乐
《开启新征程》 —— 流浪地球电影的片尾曲
收藏链接:https://music.163.com/#/song?id=1343461538
------------------------------------------------题目----------------------------------------------------------
本题要求你写个程序把给定的符号打印成沙漏的形状。例如给定17个“*”,要求按下列格式打印
*****
***
*
***
*****
所谓“沙漏形状”,是指每行输出奇数个符号;各行符号中心对齐;相邻两行符号数差2;符号数先从大到小顺序递减到1,再从小到大顺序递增;首尾符号数相等。
给定任意N个符号,不一定能正好组成一个沙漏。要求打印出的沙漏能用掉尽可能多的符号。
输入格式:
输入在一行给出1个正整数N(≤1000)和一个符号,中间以空格分隔。
输出格式:
首先打印出由给定符号组成的最大的沙漏形状,最后在一行中输出剩下没用掉的符号数。
输入样例:
19 *
输出样例:
*****
***
*
***
*****
2
------------------------------------------------题目----------------------------------------------------------
(一) 题目分析:
首先经过题目分析,可知特殊符号数跟行数有着某种特殊关系,除去中间的一颗星星*,可以发现上半部分的是个递增的等差数列:3,5,7,9,.......,可得通项公式2n+1(其中n = 上半部分行数 = 下半部分行数)
那么求和即为Sn = n2+2n,这是上半部分的。那么上下两部分即可得到:
总**用量:2( n2+2n) = 2n2+4n
到这里我们就可以算出输入的数能生成几行了。
(二)代码分块:
首先,先计算得出能上下部分各能生成几行:
for(i = 1;;i++) { temp = 2*i*i+4*i; if(temp > cNumber-1) break; Max = temp; }
temp临时存放下一行所需的总量,如果这个总量超过了输入的量数,那么就break打破永真循环,不把temp值赋值给Max行数,否则就把temp的行数赋值给Max变量。
第二步,绘制上半部分:
for(temp = i-1;temp>0;temp--) { for(int count = 0;count != (i-1)-temp;count++) printf(" "); for(int count = 0;count<(2*temp+1);count++) printf("%c",symbol); printf("\n"); }
这时候的temp就是行数了,i-1是因为永真循环的时候被i++多了一次,所以需要减掉,以样例为例,输入19后,此时temp应该为2,也就是给上半部分绘制两行。
因为题目要求中心对齐,我们同时也发现空格和行数之间的关系,例如第一行是没有空格的,第二行有一个空格,第三行有两个空格,所以通过空格数和行的关系去输出即可,然后每一行最后都换行,代码就形成了。
第三步,绘制下半部分:
for(temp = 0;temp<=i-1;temp++) { for(int count = 0;count != (i-1)-temp;count++) printf(" "); for(int count = 0;count<(2*temp+1);count++) printf("%c",symbol); printf("\n"); }
此时需要注意,最外层的for,在绘制上半部分的时候,是temp>0,是不取边界的,如果取了边界会使上部分多画一行单个*。我这里选择的是下半部分取绘制这单个*,因此需要temp<=i-1,取到边界。
(三)AC代码:
#include<iostream> #include<stdio.h> using namespace std; int cNumber,Max,i,temp; char symbol; int main() { scanf("%d %c",&cNumber,&symbol); for(i = 1;;i++) { temp = 2*i*i+4*i; if(temp > cNumber-1) break; Max = temp; } for(temp = i-1;temp>0;temp--) { for(int count = 0;count != (i-1)-temp;count++) printf(" "); for(int count = 0;count<(2*temp+1);count++) printf("%c",symbol); if(temp != 0) printf("\n"); } for(temp = 0;temp<=i-1;temp++) { for(int count = 0;count != (i-1)-temp;count++) printf(" "); for(int count = 0;count<(2*temp+1);count++) printf("%c",symbol); printf("\n"); } printf("%d",cNumber-Max-1); return 0; }
(四)AC截图:
(五)解后分析
题目难度不大,刚开始可能手生,在写for的时候总是渲染多一行或者找错最大行数。
推荐知识:
1、将声明变量放在main主函数外,可以申明稍微大型一点的变量,因为main的函数栈容量有限。同时还有一个好处,在函数外申明数组的时候会自动默认全为0清零。
2、推荐使用scanf("%d %c",&cNumber,&symbol); printf("%c",symbol); 这种C语言输入输出方式,在ACM中将能大大减少输入输出所占用的算法时间。
(六)优质解法更新:
这是在写博客的时候突然想到可以从上到下一次性绘图,写完博客就去试了一下,还真的可以,空间复杂度大大降低了,同样也AC,现在贴上代码:
#include<iostream> #include<cmath> #include<stdio.h> using namespace std; int cNumber,Max,i,temp; char symbol; int main() { scanf("%d %c",&cNumber,&symbol); for(i = 1;;i++) { temp = 2*i*i+4*i; if(temp > cNumber-1) break; Max = temp; } for(temp = 2*(i-1);temp>=0;temp--) { for(int count = i-1;count != abs((i-1)-temp);count--) printf(" "); for(int count = 0;count<2*abs(temp-i+1) + 1;count++) printf("%c",symbol); printf("\n"); } printf("%d",cNumber-Max-1); return 0; }
可以发现内存使用量大大减少,将两块的上下绘制合并到一块之后代码空间复杂度下降很多。
注:如果有更好的解法,真心希望您能够评论留言贴上您的代码呢~
原文链接:https://www.cnblogs.com/winniy/p/10419440.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C++ 转换函数搭配友元函数 2020-06-10
- C++ 自动转换和强制类型转换(用户自定义类类型) 2020-06-10
- C++ rand函数 2020-06-10
- C++ 友元函数 2020-06-10
- C++ 运算符重载 2020-06-10
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash