编程竞赛宝典 C++语言和算法入门

版权信息

书名：编程竞赛宝典：C++语言和算法入门

ISBN：978-7-115-55461-1

本书由人民邮电出版社发行数字版。版权所有，侵权必究。

您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。

我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。

如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。

版　权

编　　著　张新华

责任编辑　赵祥妮

人民邮电出版社出版发行　　北京市丰台区成寿寺路11号

邮编　100164 　电子邮件　315@ptpress.com.cn

网址　http://www.ptpress.com.cn

读者服务热线：(010)81055410

反盗版热线：(010)81055315

内容提要

编程类竞赛活动受各级各类学校重视，受青少年学生欢迎。本书以Dev-C++为C++语言的开发环境，首先带领读者入门C++语言，然后循序渐进、由浅入深地讲解C++语言的基本结构、数组、函数、指针、结构体、位运算等知识，并编排了竞赛模拟、阶段检测等内容，使读者能及时评估自己的学习效果。

本书在介绍C++语言的同时，更加侧重于计算思维的培养，通过“一题多解”及“数学求解”等方法，拓展读者对题目的本质和内涵的思考与理解。本书还配备了参考程序、习题解答、测试数据、讲解视频等资源供读者参考学习。

本书由具有丰富经验的编程竞赛教练编写，适合作为全国青少年编程竞赛及大学生程序设计竞赛的培训用书，也可作为计算机专业学生、算法爱好者的参考和学习用书。

本书编委会

主任：　　严开明　　　　胡向荣

成员：　　张义丰　　　　李守志

　　　　　陈　科　　　　王　震

　　　　　谢春玫　　　　梁靖韵

　　　　　葛　阳　　　　徐景全

　　　　　刘路定　　　　黎旭明

　　　　　张就序　　　　郭继飞

　　　　　伍婉秋　　　　热则古丽

前      言

编程竞赛介绍

随着计算机逐步深入人类生活的各个方面，利用计算机及其程序设计来分析、解决问题的算法在计算机科学领域乃至整个科学界的作用日益明显。相应地，各类以算法为主的编程竞赛也层出不穷：在国内，有全国青少年信息学奥林匹克联赛（National Olympiad in Informatics in Provinces，NOIP），该联赛与全国中学生生物学联赛、全国中学生物理竞赛、全国高中数学联赛、全国高中学生化学竞赛并称为国内影响力最大的“五大奥赛”；在国际上，有面向中学生的国际信息学奥林匹克竞赛（International Olympiad in Informatics， IOI）、面向亚太地区在校中学生的信息学科竞赛即亚洲与太平洋地区信息学奥林匹克（Asia-Pacific Informatics Olympiad，APIO）以及由国际计算机 学会主办的面向大学生的国际大学生程序设计竞赛（International Collegiate Programming Contest，ICPC）等。

各类编程竞赛要求参赛选手不仅具有深厚的计算机算法功底、快速并准确编程的能力以及创造性的思维，而且有团队合作精神和抗压能力，因此编程竞赛在高校、IT公司和其他社会各界中获得越来越多的认同和重视。编程竞赛的优胜者更是微软、谷歌、百度、Facebook等全球知名IT公司争相高薪招募的对象。因此，除了各类参加编程竞赛的选手外，很多不参加此类竞赛的研究工作者和从事IT行业的人士，也都希望能获得这方面的专业训练并从中得到一定的收获。

为什么要学习算法

经常有人说：“我不学算法也照样可以编程开发软件。”那么，为什么还要学习算法呢？

首先，算法（Algorithm）一词源于算术（Algorism），具体地说，算法是一个由已知推求未知的运算过程。后来，人们把它推广到一般过程，即把进行某一工作的方法和步骤称为算法。一个程序要完成一个任务，其背后大多会涉及算法的实现，算法的优劣直接决定了程序的优劣。因此，算法是程序的“灵魂”。学好了算法，就能够设计出更加优异的软件，以非常有效的方式实现复杂的功能。例如，设计完成一个具有较强人工智能的人机对弈棋类游戏，程序员没有深厚的算法功底是根本不可能实现的。

其次，算法是对事物本质的数学抽象，是初等数学、高等数学、线性代数、计算几何、离散数学、概率论、数理统计和计算方法等知识的具体运用。真正懂计算机的人（不是“编程匠”）都在数学上有相当高的造诣，既能用科学家的严谨思维来求证，也能用工程师的务实手段来解决问题——这种思维和手段的最佳演绎之一就是“算法”。学习算法，能锻炼我们的思维，使思维变得更清晰、更有逻辑、更有深度和广度。学习算法更是培养逻辑推理能力的非常好的方法之一。因此，学会算法思想，其意义不仅在于算法本身，更重要的是，对以后的学习生活和思维方式也会产生深远的影响。

最后，学习算法本身很有意思、很有趣味。所谓“技术做到极致就是艺术”，当一个人真正沉浸到算法研究中时，他会感受到精妙绝伦的算法的艺术之美，也会为它的惊人的运行速度和构思而深深震撼，并从中体会到一种不可言喻的美感和愉悦。当然，算法的那份“优雅”与“精巧”虽然吸引人，却也令很多人望而生畏。事实证明，对很多人来说，学习算法是一件非常有难度的事情。

本书的特色

本书尽可能详尽而全面地介绍编程竞赛中用到的大多数知识，读者如果能按照书中的安排，认真做好每一道题，必然能在各类编程竞赛中一展身手。

本书中部分题目采用了“多向思考”“一题多解” “一题多变”的解决方法，其目的主要有3点：一是充分调动读者思维的积极性，提高读者综合运用已学知识解答问题的技能；二是锻炼读者思维的灵活性，促进读者知识和智慧的增长；三是增加读者思维的深度和广度，引导读者灵活地掌握知识的纵横联系，培养和发挥读者的创造性。因此，绝不能简单地将这种训练看作编程技巧的花哨卖弄，相反，它能培养读者思维的敏捷性，促进读者智力和思维的发展，提高读者的变通能力与综合运用所学知识的能力。读者若能坚持这种思维训练方法，必能获得意想不到的良好学习效果。

如何使用本书

本书采用的是循序渐进、由浅入深的教学方法。一开始讲解引入新知识点的题目时，书中会提供该题目的完整参考代码以供读者参考，但随着读者对此知识点的理解逐步加深，后续的同类型题目将逐步向仅提供算法思路、提供伪代码和无任何提示的方式转变。此外，对于一些思维跨度较大的题目，本书会酌情给予读者一定的提示。

本书在“第02章 基本结构”后直接安排了“第03章 竞赛模拟”，是为了使读者尽快熟悉竞赛环境，做到在平时的训练中以竞赛的标准要求自己，例如，制作全面而完善的测试数据验证程序的正确性、确保提交的程序一次通过而不是反复提交才通过等。但这种思维习惯的养成，非一朝一夕之功，所以读者无须循规蹈矩，只需大致了解第03章的内容后就可以继续后面章节的学习，因为第03章的内容是贯穿于整本书的学习过程，并在不断做题实践中加深理解的。

第08章是关于指针的内容，通常初学者在竞赛中应用极少，读者可以根据自身情况确定是否学习。

题目后括号内的英文为提交的源代码名。

资源与支持

为了让读者有更好的使用体验，本书提供了多种资源与支持的方式。

（1）增值讲解视频

• 扫描书上二维码即可在线观看视频。

• “内容市场”微信小程序或App中搜索本书书名，即可在线观看视频。

• 异步社区网站搜索本书书名，单击在线课程，即可在线观看视频。

（2）测试数据

登录本书作者开发维护的在线评测网站www.magicoj.com，单击【课程分类】-【语言和算法入门】，选择对应题目即可查看，还可解锁海量题库并在线提交代码获得反馈。

（3）例题完整参考代码

在异步社区网站搜索本书书名，单击下载资源，即可下载例题完整参考代码。

适合阅读本书的读者

本书可作为NOIP的复赛教程和ICPC的参考和学习用书，还可作为计算机专业学生、算法爱好者的参考和学习用书。

致谢

感谢安徽省安庆市石化第一中学胡向荣老师，感谢浙江省宁波市北仑区霞浦学校张义丰老师，感谢浙江省慈溪市周巷镇潭北小学陈科老师，感谢贵州省贵阳市第一中学李守志老师，感谢全国各省市中学、大学的信息学奥赛指导老师，他们给本书提了许多真诚而有益的建议，并对笔者在写书过程中遇到的一些困惑和问题给予了热心的解答。

本书在完成过程中，使用了NOIP的部分原题、在线评测网站的部分题目，并参考和收集了其他创作者发表在互联网、杂志等媒体上的相关资料，无法一一列举，在此一并表示衷心感谢。

感谢卷积文化传媒（北京）有限公司CEO高博先生和他的同事，他们成功地将现代AI技术与传统的图书完美地结合起来，降低了读者学习编程的门槛。

最后要说的话

由于笔者水平所限，书中难免存在不妥之处，欢迎同仁或读者赐正。读者如果在阅读中发现任何问题，请发送电子邮件到hiapollo@sohu.com，更希望读者对本书提出建设性意见，以便修订再版时改进。

本书对应的题库网站正在不断完善中，网址为www.magicoj.com。

希望本书的出版，能够给学有余力的中学生、计算机专业的大学生、程序算法爱好者以及IT行业从业者提供学习计算机科学的帮助。

张新华

2021年5月

第01章　C++语言入门

计算机编程语言能够实现人与计算机之间的沟通与交流，使计算机能够根据人编写的代码一步一步地工作，完成某些特定的任务。C++语言是使用最广泛的编程语言之一，也是许多编程竞赛指定的编程语言之一。

1.1　我的第一个程序

扫码看视频

我们使用Dev-C++这个适合初学者使用的C/C++集成开发环境来学习C++语言，读者可上网搜索“Dev C++ 下载”等关键词从网上下载该软件，或者使用浏览器访问www.magicoj.com（或者www.razxhoi.com），下载它的改进版本——Dev-CPP智能开发平台，如图1.1所示。

图1.1

安装界面如图1.2（a）所示。单击其中的“下一步”按钮，出现选择目标位置的界面，建议继续单击“下一步”按钮默认安装，如图1.2（b）所示。

图1.2

安装完成后运行软件，将出现初始设置界面。

如果没有出现初始设置界面或者弹出错误对话框（因为未正确卸载旧版Dev-C++）等，可在软件的“工具”菜单里选择“环境选项”，在“文件和路径”选项卡中单击“删除设置并退出”按钮，再重新运行软件即可恢复正常，如图1.3所示。

图1.3

设置好的软件界面（Dev-CPP智能开发平台支持换肤功能）如图1.4所示。

图1.4

存放代码的文件称为源代码文件，编写代码之前要新建一个源代码文件，图1.5所示为新建源代码文件的两种方法。

图1.5

如图1.6所示，由模板自动生成的代码（若使用的非Dev-CPP智能开发平台则用户需手动输入）显示在代码编辑区。

图1.6

如果不想要自动生成代码，想自己手动输入全部代码，只要在“工具”→“环境选项”中将新建文件时选中的“自动加载模板”选项取消即可。

＃include <bits/stdc++.h> 表示编写的代码要包含子目录bits下的一个名为“stdc++.h”的头文件。之所以叫作头文件，是因为这类文件一般放在代码的开头。C++有许多头文件，它们可以实现一些特定的功能。stdc++.h头文件又称“万能”头文件，因为代码中只要包含该头文件就基本无须再包含其他头文件了。

using namespace std;表示使用的命名空间为“std”（std是英文单词“standard”即“标准”的缩写），这主要是为了解决名字冲突的问题，初学者暂不必深究。

“int”是英文单词“integer”即“整数”的缩写，和第7行的return 0相呼应。“return”的中文含义是“返回”，而0是整数，意思是给系统（调用者）返回整数0。0表示一切运行正常，即“没有消息就是好消息”，显然代码能运行到return 0，说明代码是正常结束而不是运行半途出错、异常退出的。

“main”的中文含义是“主要的”，C++程序里，必须有且只能有一个名为“main”的函数（主函数）。函数是指能完成一定功能的程序块，函数后面有圆括号，随后函数体用花括号标注，即第5～第8行。

C++程序的运行总是由main()函数的函数体里的第一条语句开始，到main()函数的函数体的最后一条语句结束。

现在编写代码，使程序运行后显示一行字符“Hello,world”，这需要在代码编辑区第6行空白处加入cout<<"Hello,world\n"；，如图1.7所示。

图1.7

cout用于输出紧随操作符“<<”后的双引号中的字符串，输出的字符串必须包含在双引号之中，其中“\n”表示换行。

C++语言对字母大小写敏感，例如字母“a”和“A”不同。

除输出内容有中文，需要用中文输入法在双引号中输入中文字符外，其他字符都必须用英文输入法输入，否则代码可能无法运行。

C++语言中，每条语句末尾应以分号（;）表示结束，但预处理、函数头及花括号之后一般不加分号。

写好的代码要及时保存，保存的文件的扩展名为.cpp，如图1.8所示。

图1.8

以.cpp为扩展名保存的文件叫作源文件，源文件不能直接运行，要编译成可执行的EXE文件后方可运行。如图1.9所示，打开“运行”菜单后单击“编译”，无论编译成功还是失败，都会在软件界面下方功能区的信息栏输出相应的信息。

图1.9

编译成功后，打开“运行”菜单单击“运行”，将出现如图1.10所示的命令提示符窗口，显示输出的文字，第一个C++程序编写成功了！

图1.10

如图1.11所示，程序编译生成的EXE文件可独立运行而无须编译器的环境支持。

图1.11

使用cout可以输出各类字符，例如，输出多行中文字符串的代码如下。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6   cout<<"你好，C++语言\n\n"; 
 7   cout<<"我是初学者\n";      
 8   cout<<"我喜欢编程\n";      
 9   return 0;
10 }

每一行输出字符串的末尾均有“\n”表示换行，输出结果如图1.12所示。

图1.12

1.1.1　并排的树（tree）

【题目描述】

请尝试编程输出如下的两棵“并排的树”。

   *         *

  ***       ***

 *****     *****　

*******   *******　

   *        *

   *        *

1.2　数据类型及运算

扫码看视频

编程需要用到各种类型的数据，例如整数、浮点数（包含小数）、字符串等。Dev-C++是Windows平台下的编译器，常用数据类型的字节长度和取值范围如表1.1所示。

表1.1

浮点数是表示小数的一种方法，简单理解就是小数点可以任意浮动的数字，例如3.14可以写成3.14×10⁰、31.4×10^-1、314×10^-2等多种表现形式。而3.4×10³⁸这种表示法也可以用科学记数法表示为3.4E+38，例如2E-2即2×10^-2。

现代数码产品使用二进制数（0和1）来存储各类数据。例如，有一张存储视频的CD，图1.13（a）所示的螺旋形轨道表示存储的视频数据，图1.13（b）所示是在显微镜下显示出来的CD表面一个个的“坑”。我们将有坑的地方表示为1，没有坑的地方表示为0，这就是CD用二进制数存储数据的原理。

图1.13

位（bit）是计算机存储信息的最小单位，代表1个二进制位，其值为0或1，可以表示2种状态/2个数值；2个二进制位可以表示4个数值，即00、01、10、11；n个二进制位可以表示2ⁿ个数值。例如，短整型的字节长度为16位，可以表示2¹⁶即65 536个数值，考虑到正数、负数及0的表示，所以取值范围为-32 768～32 767。

8个二进制位为1字节(Byte)；1 024字节为1KB；1 024KB为1MB；1 024MB为1GB；1 024
GB为1TB ……

不同的编译器支持的各数据类型的字节长度可能不同，sizeof()可用于获取各数据类型的字节长度，例如输出各数据类型的字节长度的代码如下所示。

cout<<"int的字节长度为"<<sizeof(int)<<"\n";
cout<<"short的字节长度为"<<sizeof(short)<<"\n";
cout<<"long long的字节长度为"<<sizeof(long long)<<"\n";

C++程序用到的算术运算符如表1.2所示。

表1.2

C++语言以圆括号代替数学中的方括号和花括号，程序运行时将按由内到外的顺序计算圆括号里的值。例如数学表达式2×{4-[3-(2-9)]}，转换成C++语言中的表达式为2*(4-(3-(2-9)))。

诸如x²＋y²这样的表达式，转换成C++语言中的表达式为x*x+y*y。

数学中常用x、y等字符代表未知数或未定数，例如代数方程x＋y等。类似地，C++语言也用字符代表某个数值，其在程序运行中没有固定值、可以改变的数值称为变量。

代表变量的字符只能由字母、数字、美元符号和下划线等字符组成，且第一个字符必须为字母、下划线或美元符号。例如，可以定义变量名为_sum、abc、Day1、school_name、lotus_1_2、$sum，而Mr.Wang、234NUM、#34、a＞＝b、¥1234这些变量名是错误的。

为增加程序的可读性，应注意做到“见名知意”，即选择有含义的英文单词（或其缩写）作为变量名，例如count、total、price等，尽量少用简单的符号，例如a、b、c、u1、v1等。

1.2.1　求两个整数的积和平均值（calc）

【题目描述】

试编写一个程序，使得程序运行时，用键盘输入两个整数（两个整数之间以一个或多个空格间隔）后按Enter键，计算机显示器上输出这两个整数的积和平均值。

【输入格式】

输入两个整数。

【输出格式】

第一行输出两个整数相乘的完整表达式。

第二行输出平均值（仅输出整数部分），注意最后应以换行结束。

【输入样例】

5 6

【输出样例】

5*6=30

5

参考程序如下所示。

 1 /*
 2   这个程序的名字叫作求两个整数的积和平均值，它真的太强大了！好吧，
 3   这么说有点无聊，但反正是注释语句，不影响程序运行 
 4 */
 5 #include <bits/stdc++.h>
 6 using namespace std;
 7 
 8 int main()                      //这也是注释语句，不影响程序运行
 9 {
 10   int a,b,c;                    //定义变量 a、b、c，此时a、b、c的值未知
 11   cin>>a>>b;                    //输入a和b的值
 12   c=a*b;                        //计算a和b的乘积，把结果赋值给c
 13   cout<<a<<"*"<<b<<"="<<c<<endl;//输出的变量和字符串要用"<<"隔开 
 14   cout<<(a+b)/2<<endl;          //整数除整数会舍去小数部分，自动取整 
 15   return 0;
 16 }

第1～第4行中的“/*…… */”用作C++代码的多行注释，表示从“/*” 开始，到“*/”结束的这一段语句均为注释部分。

“//”用作C++代码的单行注释，表示从“//”开始，一直到本行结束的语句均为注释部分。

注释语句只是方便阅读代码的人更好地理解代码，编译程序时，编译器会自动忽略注释语句，它不会对程序的运行产生任何影响。

int a,b,c;定义了a、b、c这3个整型变量，C++语言规定变量必须要先定义才能使用。定义变量相当于向计算机内存申请“房子”，变量只有住进“房子”里才允许使用，数据类型规定的存储空间有多大，分配的“房子”就有多大。例如定义了两个变量，如图1.14所示。因为a是整型变量，所以内存给它分配了4字节的空间；因为x是超长整型变量，所以内存给它分配了8字节的空间。

图1.14

可以在定义变量数据类型的同时给它赋值（初始化），例如：

int a=5;       //定义a为整型变量，初始值为5
float f=3.45;   //定义f为单精度浮点型变量，初始值为3.45

诸如int a=5；这样的语句，相当于下面两条语句：

int a;
a=5;

也可以对定义的变量的其中一部分变量赋值，例如：

int a，b，c=5;    //定义了整型变量a、b、c，其中c的初始值为5，a和b的初始值未知

注意，在程序中a、b、c之间要用逗号分隔。

如果对几个变量均赋值为5，应该写成int a=5,b=5,c=5;，而不能写成int a=b=c=5;。

变量数据类型的定义应视题目的要求而定，选取的数据类型的字节长度数值过大会降低运算速度、浪费内存空间，过小可能会导致数据溢出。

第11行是输入语句，cin表示程序运行时，用键盘输入“>>”右边的变量的值。 cin>>a>>b；表示用键盘输入两个整数。

第12行中的“=”和数学运算中用到的等号不同，它是赋值运算符，表示将右边的值赋给左边的变量，所以如果将代码写成a+b=c，程序将无法编译。

第13行中的endl代表换行，类似于换行符“\n”。

用键盘输入数据时，要严格按输入语句要求的格式输入。例如上例中，如果a=1，b=2，那么cin>>a>>b语句的正确输入方式应该是用英文输入法输入半角字符1 2后按Enter键，其中1和2之间以一个或多个空格分隔，但不能是其他符号。如果用键盘输入a=1,b=2，或者1，2之类的均是错误的。

输入/输出语句应严格按照格式编写，例如不能写成cin>>a,b,c或者cout<<a+b=c等。输入/输出的各变量之间应使用“>>”或“<<”分隔。

1.2.2　3个浮点数相加（add2）

【题目描述】

输入3个双精度类型的浮点数，计算3个浮点数相加的和。

【输入格式】

输入3个浮点数（整数部分不超过2位，小数部分不超过3位）。

【输出格式】

输出3个浮点数相加的和，注意最后应以换行结束。

【输入样例】

1.2 3.2 1

【输出样例】

5.4

浮点数在内存中是用有限的存储单元存储的，所以能提供的有效数字总是有限的，在有效位以外的数字将会被舍去，由此可能会产生一些误差。

下面的程序演示了浮点数的舍入误差。

 1 //浮点数的舍入误差演示
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4
 5 int main()
 6 {
 7   float a=2345678900.001;        　//定义一个很大的浮点数
 8   float b=3;                    　 //定义一个很小的浮点数
 9   cout<<fixed<<a<<endl;          　//fixed表示可禁止以科学记数法形式输出
 10   float c=a+b;
 11   cout<<c<<endl;
 12   return 0;
 13 }

输出结果如图1.15所示。

图1.15

可以看到，两个浮点数相加后的结果没有变化，这是由于单精度浮点型的精度为6～7位有效数字，后面的数字被忽略，并不能准确地表示该数。例如定义float f=3456.12345;，当运行cout<<f语句输出f时，结果为3456.12。

所以在使用浮点数时要避免因浮点数运算产生的误差而导致结果错误。例如，应避免将一个很大的浮点数和一个很小的数直接运算，否则会“丢失”小的数。

1.2.3　捡石头（stone）

【题目描述】

小光捡了3块石头，这3块石头的质量的输入在代码中用cin语句实现，他想再捡一块石头，让这4块石头的质量正好为30千克，请编程用cout语句输出第4块石头的质量。

【输入格式】

输入3个数，数与数之间以空格间隔，表示3块石头的质量。

【输出格式】

输出一个数，表示第4块石头的质量，注意最后应以换行结束。

【输入样例】

1 1 1

【输出样例】

27

1.2.4　简单解方程（equation）

【题目描述】

设S=(a+b) / 2，给定a与S的值，求b的值。

【输入格式】

输入两个整数a和S（，）。

【输出格式】

输出一个整数b。

【输入样例】

4 3

【输出样例】

2

1.2.5　计算多项式的值（cal）

【题目描述】

试计算多项式y=ax³+bx²+cx+d的值，其中a、b、c、d、x的值由键盘输入。

【输入格式】

输入5个整数，分别代表a、b、c、d、x的值。

【输出格式】

输出一个整数，即多项式的值，注意输出最后应以换行结束。

【输入样例】

3 4 5 6 5

【输出样例】

506

初学者容易将表达式ax³+bx²+cx+d写成ax^3+bx^2+cx+d这样的错误形式，其正确形式应该为a*x*x*x+b*x*x+c*x+d。

程序写好后，试输入1999 1999 1999 1999 1999，观察输出结果有什么异常。

每种类型的数据都有各自的取值范围，请务必确保所定义的数据不超过该类型数据的取值范围，否则会造成数据的溢出而导致结果错误。数据的溢出在编译和运行程序时并不报错，完全要靠编程者的细心和经验来保证结果的正确性。

下面的程序显示了整型数据溢出的错误。

 1 //整型数据的溢出
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int a=2147483647;
 8   a=a+1;
 9   cout<<"a="<<a<<endl;                    //输出a=-2147483648
10   return 0;
11 }

1.2.6　混合运算（cal2）

【题目描述】

试编程用键盘输入a、b、c、d、e的值后计算图1.16所示的算式的值。

图1.16

【输入格式】

输入5个双精度浮点数，分别为a、b、c、d、e的值。

【输出格式】

输出混合运算的结果。

【输入样例】

2.1 2.2 2.3 2.4 2.5

【输出样例】

-0.454327

如表1.3所示，如果程序中定义的某个数据类型的值永远不可能出现负数时，可以使用unsigned将其定义为无符号的数据类型，这样就使正整数的取值范围大约比原先扩大了一倍。

表1.3

1.2.7　两个整数相乘（mul）

【题目描述】

使用cin语句输入两个整数a和b，计算两个整数的乘积并输出。

【输入格式】

输入两个整数a和b（，）。

【输出格式】

输出两个整数的乘积。

【输入样例】

100 10

【输出样例】

1000

1.2.8　巨型人造天体（aster）

【题目描述】

制造巨型人造天体需要A部件和B部件，其质量分别为2 012 345 678克、1 912 345 678克。

（1）试计算这两种部件的质量之和的最后4位数。

（2）试计算12 345 678个A部件的总质量的最后4位数。

【输入格式】

无输入。

【输出格式】

输出两行，第一行为两种部件的质量之和的最后4位数，第二行为12 345 678个A部件的总质量的最后4位数。

使用“内容市场”
App扫描看视频

【输入样例】

略。

【输出样例】

略。

【算法分析】

提示：(a+b)%c=(a%c+b%c)%c，(a*b)%c=(a%c*b%c)%c。

与变量相对应，在程序运行中，值不能被改变的数值称为常量，常量使用关键字const标识，例如：

const int num=34; 　 //定义num为整型常量，值为34

const float pi=3.1415;//定义pi为单精度浮点型常量，值为3.1415

程序运行时，常量的值不能被更改。下面是一个试图改变常量a的错误程序，程序编译会出现“assignment of read-only variable ' a ' ”的错误，即只读变量'a'的赋值错误。

 1 //试图改变常量a的错误程序
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   const int a=34;                 //定义了一个整型常量a，a的值为34
 8   a=a*5;                          //试图将a乘以5后再将其值赋给a
 9   cout<<a<<endl; 
10   return 0;
11 }

也可以用预处理指令#define定义常量的值，例如下面的程序中用#define定义PRICE代表数值34，此后凡是在该程序中出现的PRICE都代表34。常量名一般用大写字母表示，可以和变量一样运算。

 1 //预处理指令定义常量
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 #define PRICE 34     //定义PRICE为一个常量，值为34，注意末尾无分号
 5 
 6 int main()
 7 {
 8   int num=10;
 9   int total=num*PRICE;                     //PRICE会替换为34来运算
10   cout<<"total="<<total<<endl;             //输出结果为total=340
11   return 0;
12 }

定义常量的好处是含义清晰，而且在需要改变常量值时能做到“一改全改”。例如，将#define PRICE 34改为#define PRICE 100，则程序中所有用到PRICE的地方就全部由34变成100而无须一个一个修改。

1.3　字符和字符串

扫码看视频

字符变量用于存放单个字符，用单引号标注，例如 'a'、'x'、 '?'、 '$'等。

字符串变量用于存放任意多个字符，用双引号标注，例如"Hello,world!"、"a" 、"$34567"等。

每一个字符串的结尾有一个“字符串结束标志”，以便系统判断字符串是否结束。C++语言规定以字符'\0'作为字符串结束的标志，'\0'占1字节。例如，如图1.17所示，字符串"Hello"的实际存储空间不是5字节，而是6字节，最后一个字节为'\0'。但'\0'是隐含的，输出时不会输出'\0'，赋值时也不必手动加'\0'，这些系统会自动进行后台处理。

图1.17

字符变量的使用很简单，参考例程如下所示。

 1 //字符变量的使用 
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   char a='A',b='B',c,d;   //定义字符变量a、b、c、d，a和b已赋值为'A'和'B'
 8   cin>>c>>d;                            //从键盘输入c和d的值 
 9   cout<<a<<' '<<b<<' '<<c<<' '<<d<<'\n';//输出,字符间以一个空格间隔 
10   return 0;
11 }

不要将字符变量和字符串变量混淆，例如，char c="a"这种把字符串"a"赋给只能容纳一个字符的字符变量c的语句是错误的，因为字符串"a"实际包含两个字符'a'和'\0'。

1.3.1　字符金字塔（Pyramid）

【题目描述】

试编程输入一个字符，用该字符构造一个高度为3的字符金字塔。例如，输入字符为“*”，则输出的字符金字塔如下。

*

* * *

* * * * *

【输入格式】

用键盘输入一个字符。

【输出格式】

输出用该字符构造的一个高度为3的字符金字塔，第1行行首有4个空格，第2行行首有2个空格，第3行行首无空格，非空格的字符间以一个空格间隔，行末无多余空格。

【输入样例】

*

【输出样例】

*

* * *

* * * * *

英文字母、数字以及一些常用的符号（例如*、#、@等）在计算机中是使用二进制数来表示的。具体用哪些二进制数表示哪个符号，每个人都可以约定自己的一套编码规则，但如果想互相通信而不造成混乱，就必须使用相同的编码规则。美国国家标准协会（American National Standards Institute,ANSI）出台了美国信息交换标准代码（American Standard Code for Information Interchange, ASCII），统一规定了上述常用符号用哪些二进制数来表示。

ASCII对照表请参见本书的附录部分。表1.4中列出了几个常用的码表值。

表1.4

字符在内存中以该字符相对应的ASCII值存储，它的存储形式与整数的存储形式类似，这样使得字符型数据和整型数据可以通用。一个字符既可以以字符形式输出，也可以以整数形式输出，还可以对它们进行算术运算。

下面的程序演示了字符变量与整数之间的通用性。

 1 //字符变量与整数的通用性演示
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   char c1,c2;
 8   c1=65;                      //此处用数字而不是字符赋值 
 9   c2=66;                      //此处用数字而不是字符赋值 
10   cout<<c1<<"  "<<c2<<endl;   //因为c1、c2为字符类型，所以默认输出字符 
11   cout<<int(c1)<<"  "<<int(c2)<<'\n';          //int()表示强制转换为整数
12   return 0;
13 }

输出结果如图1.18所示。

图1.18

程序中的第11行使用int(c1)将字符c1强制转换为整数。C++可以利用强制类型转换运算符将表达式转换成所需的类型，例如：

cout<<int(3.84); //将浮点数3.84强制转换为整数，故舍去小数部分，输出整数3
cout<<fixed<<double(10);//将整数10强制转换为浮点数10.0000输出

C++有两种转换，一种是系统自动进行的类型转换，例如3+3.4的结果是浮点数；另一种是强制类型转换。当系统自动进行的类型转换不能实现目的时，可以用强制类型转换。例如，取模运算符"％"要求其两侧均为整数，若x为浮点数，则x%3不合法，必须用int(x)%3进行转换。由于强制类型转换运算符优先级高于"％"运算符，因此先强制转换浮点数x为整数，再进行取模运算。

1.3.2　ASCII值转字符（ASCII1）

【题目描述】

输入一个整数，然后输出对应的字符。

【输入格式】

输入一个整数（保证整数存在对应的可见字符）。

【输出格式】

输出对应的字符。

【输入样例】

65

【输出样例】

A

1.3.3　小写字母转大写字母

【题目描述】

下面的程序实现了小写字母转对应的大写字母。

 1 //小写字母转大写字母
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   char c1,c2;
 8   c1='a';                  //c1赋值为小写字母'a'
 9   c2='b';                  //c2赋值为小写字母'b'
10   c1=c1-32;                //小写字母比对应的大写字母的ASCII值大32
11   c2=c2-32;
12   cout<<c1<<"  "<<c2<<'\n';//输出大写字母：A  B
13   return 0;
14 }

从附录的ASCII对照表可以看出，每一个小写字母比它对应的大写字母的ASCII值大32。C++语言允许字符数据与整数直接进行算术运算，这种处理方法增大了程序的自由度，对字符做各种转换比较方便。

1.3.4　大写字母转小写字母（ASCII2）

【题目描述】

试编程使用cin语句输入3个大写字母，并将之转换为对应的小写字母输出。

【输入格式】

输入3个大写字母，字母间以一个空格间隔。

【输出格式】

输出3个对应的小写字母，字母间以一个空格间隔，行末无空格，有换行。

【输入样例】

A B C

【输出样例】

a b c

1.3.5　恺撒加密术

【题目描述】

“恺撒加密术”是一种替代密码的加密技术。如图1.19所示，对于信件中的每个字母，会用它后面的第t个字母代替。例如当t=4时，“China”加密的规则是用原来字母后面的第4个字母代替原来的字母，即字母“A”后面的第4个字母是“E”，用“E”代替“A”。因此，“China”应加密为“Glmre”。请编写程序将任意5个字符加密（暂不考虑替代的字母跳过“界”的问题）。

图1.19

 1 //恺撒加密术
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   char c1='C',c2='h',c3='i',c4='n',c5='a';//此处也可换成其他英文字母
 8   c1+=4;                            //c1+=4即c1=c1+4，这种写法更简洁
 9   c2+=4;                            
10   c3+=4;
11   c4+=4;
12   c5+=4;
13   cout<<c1<<c2<<c3<<c4<<c5<<endl;
14   return 0;
15 }

在运算符“=”之前加上其他运算符，称为复合运算符，例如：

a+=3;∥等价于a=a+3
x%=3;∥等价于x=x%3

如果是包含若干项的表达式，则相当于它有圆括号，例如x%=y+4 相当于x%=(y+4)，即x=x%(y+4)而不是x=x%y+4。

1.3.6　改进的加密术（encryption）

【题目描述】

请编写一个程序，使用cin语句输入任意5个英文字符和任意一个值t（-8＜t＜8），则原先的5个英文字符将分别用其后面的第t个英文字符代替并输出（暂不考虑替代的字符跳过“界”的问题）。

【输入格式】

第1行输入5个英文字符，字符间以空格间隔。

第2行输入1个整数t。

【输出格式】

输出加密后的英文字符，字符间无须空格间隔。

【输入样例】

C h i n a

4

【输出样例】

Glmre

参考伪代码如下所示，请根据伪代码的思路编写C++程序完成本题。

 1 定义5个字符变量
 2 定义t
 3 输入5个字符变量的值
 4 输入t的值
 5 5个字符依次以其后面的第t个字符代替
 6 输出5个加密后的字符

C++还允许一种特殊形式的字符常量，就是以“\”开头的字符序列。例如前面已经用过的'\n'，它代表换行符。这是一种“控制字符”，是不能在显示器上显示的，在程序中也无法用一般形式的字符表示，只能采用特殊形式的字符表示。

以“\”开头的常用特殊字符（转义字符）如表1.5所示。

表1.5

通过转义字符，就可以输出诸如“\”“'”“"”之类的字符了。

例如要输出“\”，代码应该为cout<<“\\”。

1.3.7　输出特殊字符（special）

【题目描述】

请输出图1.20所示的字符串，注意所有的字符均为英文半角形式。

图1.20

【输入格式】

无输入。

【输出格式】

见输出样例，注意除单词之间以一个空格间隔外，无任何多余空格，以换行结束。

【输入样例】

无。

【输出样例】

He said:"The symbol is '\'."

为了更好地处理字符串，C++提供了string类，它提供了添加、删除、插入和查找等丰富的操作方法。

string类的部分操作方法如下所示。

 1 //string类的部分操作方法
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   string s="Hi,..morn";                    //定义了名为s的string类并初始化
 8   s=s+"ing";                               //尾部添加字符串"ing"
 9   cout<<"添加字符串:"<<s<<endl;             //输出"Hi,..morning"
10   s.erase(3,2);                            //删除第3个字符后的2个字符
11   cout<<"删除字符串:"<<s<<endl;             //输出"Hi,morning"
12   int f=s.find("Hi,");                      //查找"Hi,"在s中的位置，-1为无法找到
13   s.insert(f+3,2,'G');                     //在第3个字符后插入单个字符'G'2次
14   cout<<"插入两字符:"<<s<<endl;             //输出"Hi,GGmorning"
15   s.insert(5,",MM,");                      //在第5个字符后插入字符串",MM,"
16   cout<<"插入字符串:"<<s<<endl;             //输出”Hi,GG,MM,morning”
17   string v=s.substr(4,3);                  //取s中第4个字符后的3个字符给v
18   cout<<"字符串子串:"<<v<<endl;             //输出"G,M"
19   cout<<"string长度:"<<v.length();         //输出3,即v的长度
20   return 0;
21 }

输出结果如图1.21所示。

图1.21

1.3.8　费解的对话（chat）

【题目描述】

宠物机器人的单词库被病毒感染了，第一种感染方式是圆括号内的内容没有被破坏，但是圆括号外面加入了一些奇怪的数字，例如“（Mary）”变成了“253(Mary)5”；第二种感染方式是在单词中加了一个“...”子串，例如“hello”变成了“he…llo”。请修复它。

使用“内容市场”App扫描看视频

【输入格式】

输入两行字符串（字符串中无空格）。第一行是被第一种感染方式感染的字符串，第二行是被第二种感染方式感染的字符串。

【输出格式】

输出一行对应的正确字符串，两个字符串间以逗号间隔。

【输入样例】

23453(Mary)24565

mor…ning

【输出样例】

Mary,morning

1.4　输入/输出及格式控制

扫码看视频

getchar()函数（字符输入函数）的作用是从终端（键盘）获取输入的字符。

putchar()函数（字符输出函数）的作用是向终端（显示器）输出字符。例如下面的程序在运行时，如果用键盘输入字符后按Enter键，显示器上就会输出该字符。

 1 //getchar()函数和putchar()函数的使用演示
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   char c;
 8   c=getchar();                           //输入字符赋值给c
 9   putchar(c);                            //输出字符变量c
10   return 0;
11 }

cin读取一行字符串时，遇到空格就会停止。如果读取一行包含空格符的字符串，可以使用getline()函数。例如将“I am here”赋值给string类的例程如下所示。

 1 //使用getline()函数读取string类字符串
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 
 5 int main()
 6 { 
 7   string str;                   //string类可用getline()函数读取
 8   getline(cin,str);             //读取一行包含空格符的字符串赋值给str
 9   cout<<str;
10   return 0;
11 }

某些情况下，程序需要以八进制数或十六进制数的形式输出结果。C++提供了简单的实现方法：只要在输出流中输出dec（对应十进制）、oct（对应八进制）或hex（对应十六进制）即可。下面的程序演示了不同进制数之间的相互转换。

 1 //进制转换
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int n=314;
 8   cout<<"十进制："<<dec<<n<<endl;  //n本身为十进制数，所以可省略dec
 9   cout<<"八进制："<<oct<<n<<endl;
10   cout<<"十六进制:"<<hex<<n<<endl;
11   cin>>oct>>n;                     //输入八进制形式的n值
12   cout<<dec<<n;                    //转换为十进制形式的n值输出
13   return 0;
14 }

C++提供的setprecision()函数可以控制浮点数的输出精度，其中的参数代表输出的位数。试分析以下程序的执行结果。

 1 //setprecision()函数的使用
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   double a=234.1234567890;
 8   cout<<a<<endl;
 9   cout<<setprecision(4)<<a<<endl;
10   cout<<setprecision(5)<<a<<endl;
11   cout<<setprecision(6)<<a<<endl;
12   cout<<setprecision(7)<<a<<endl;    
13   cout<<setprecision(8)<<a<<endl;
14   cout<<setprecision(9)<<a<<endl;  
15   cout<<setprecision(15)<<a<<endl; 
16   return 0;
17 }

输出结果如图1.22所示。

图1.22

可见，单纯使用setprecision()函数，控制输出的位数是整数部分与小数部分相加的位数，如果想真正精确地控制小数点后的位数，需添加fixed()函数，见以下程序。

 1 //fixed()函数的使用
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   float a=111.2345678;
 8   cout<<setprecision(5)<<fixed<<a<<endl;   //输出111.23457，有误差
 9   return 0;
10 }

1.4.1　精确到小数点（fixed）

【题目描述】

输入一个双精度浮点数，保留其小数点后5位输出。例如输入1.23，输出1.230 00。

【输入格式】

输入一个双精度浮点数。

【输出格式】

将输入的双精度浮点数保留其小数点后5位输出。

【输入样例】

1.0

【输出样例】

1.00000

1.5　一些运算规则

扫码看视频

整数和浮点数可以混合运算，并且由于字符可以与整数通用，因此，整数、浮点数、字符可以混合运算，例如134+'a'+3.4-45.8* 'c'是合法的。

在运算时，系统会自动将不同类型的数据转换成同一类型的数据后再进行运算。转换的规则如图1.23所示。

图1.23

运算顺序为由左到右。例如10+'a'+int*float-double/long的运算顺序如下。

（1）进行10+'a'的运算，先将'a'转换成整数，结果为107。

（2）由于“*”比“+”优先，先进行int*float的运算，将两数都转换为双精度浮点数。

（3）107与int*float的积相加，先将整数转换为双精度浮点数，结果为双精度浮点数。

（4）将变量long转换为双精度浮点数，double/long的结果为双精度浮点数。

（5）将10+'a'+int*float的结果与double/long的商相减，结果为双精度浮点数。

C++语言还规定了运算符的优先级和结合性，在表达式求值时，先按运算符的优先级高低顺序执行，例如先乘除后加减。如果一个运算对象两侧的运算符的优先级相同，例如a-b+c，则按规定的“结合方向”执行。

大多数算术运算符的结合方向为“先左后右”，即左结合性，例如a-b+c中，b两侧的“-”和“＋”两种算术运算符的优先级相同，按先左后右的结合方向，b先与减号结合，执行a-b的运算，再执行加c的运算。有些运算符（例如赋值运算符“=”）的结合方向为“自右向左”，即右结合性，例如语句int a,b=1,c=2;a=b=c中，a=b=c相当于a=(b=c)，即a=2。

C++语言的自增自减运算符“++”和“--”的作用是使变量的值加1或减1，例如：

++i，--i（在使用i之前，使i的值加/减1）；

i++，i--（在使用i之后，使i的值加/减1)。

“++”和“--”不能用于常量或表达式，例如5++或(a+b)++都是不合法的。

“++”和“--”的结合方向是自右向左。

粗略地看，++i和i++的作用相当于i=i+1，但它们的不同之处在于++i是执行i=i+1后再使用i的值，而i++是使用i的值后再执行i=i+1。例如，假设i的原值等于3，分别执行下面的赋值语句的区别如下。

（1）j=++i;。此赋值语句执行时，i的值先变成4，再赋给j，j的值为4。

（2）j=i++;。此赋值语句执行时，先将i的值3赋给j，j的值为3，然后i的值变为4。

例如当i=3时，cout<<++i的结果为4。若改为cout<<i++则输出结果为3。

例如当i=1时，i=(++i)+(++i);，执行cout<<i的结果为6，因为最后i的值为3，i＝(i)+(i)即i=3+3=6。

试运行下面的程序并分析结果。

 1 //i++与++i
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int i=1;
 8   cout<<++i<<endl;
 9   cout<<i++<<endl;
10   cout<<i<<endl;
11   cout<<(++i)+(++i)<<endl;
12   cout<<(i++)+(i++);  //编译器不同，值可能为10或11，所以要避免这样写
13   return 0;
14 }

C++语言提供一种特殊的运算符──逗号运算符，用它将两个表达式连接起来，例如：

3+5，6+8

逗号表达式的求解过程是：先求解表达式1，再求解表达式2。整个逗号表达式的值是表达式2的值，例如cout<<(3+5,6+8)输出的值为14。

之前定义变量时已经使用过逗号表达式了，例如：

int a,b=0,c,d=34;　　　//这相当于一句代码

double x,y,z; 　　　　　//这相当于一句代码