算法训练营入门篇(全彩版) (陈小玉)（Z-Library）

内 容 简 介 本书图文并茂、通俗易懂，详细讲解常用的算法知识，又融入了大量的竞赛实例和解题技 巧，可帮助读者熟练应用各种算法解决实际问题。 本书总计 9章。第 1章讲解 C++基础知识，涉及语法、数组、字符串、结构体和指针等； 第 2章带读者感受算法之美，涉及算法复杂度、函数和递归；第 3章讲解线性表的应用，涉及 顺序表、链表、栈和队列，以及 STL 中的常用函数和容器；第 4章讲解树的应用，涉及树、二 叉树、二叉树遍历、哈夫曼树和二叉搜索树；第 5章讲解图论基础，涉及图的存储和图的遍历； 第 6章讲解算法入门知识，涉及贪心算法和分治算法；第 7章讲解高精度计算，涉及高精度加 法、高精度减法、高精度乘法和高精度除法；第 8章讲解搜索算法入门知识，涉及二分算法、 深度优先搜索和广度优先搜索；第 9章讲解动态规划入门知识，涉及动态规划秘籍、背包问题、 线性动态规划和区间动态规划。 本书面向对算法感兴趣的读者，无论是想扎实内功或参加算法竞赛的学生，还是想进入名 企的学生、求职者，抑或是想提升核心竞争力的在职人员，都可以参考本书。若读者想进一步 学习数据结构与算法，则可参考《算法训练营：提高篇》（全彩版）和《算法训练营：进阶篇》 （全彩版）。 未经许可，不得以任何方式复制或抄袭本书之部分或全部内容。 版权所有，侵权必究。 图书在版编目（CIP）数据 算法训练营. 入门篇 : 全彩版 / 陈小玉著. 北京 : 电子工业出版社， 2024. 10. -- ISBN 978-7-121- 48757-6 Ⅰ. TP301.6 中国国家版本馆 CIP 数据核字第 2024QB4286 号 责任编辑：张国霞 印 刷： 装 订： 出版发行：电子工业出版社 北京市海淀区万寿路 173信箱 邮编 100036 开 本：720×1000 1/16 印张：17.25 字数：352.8千字 版 次：2024年 10月第 1版 印 次：2024年 10月第 1次印刷 印 数：3000册 定价：128.00元 凡所购买电子工业出版社图书有缺损问题，请向购买书店调换。若书店售缺，请与本社发 行部联系，联系及邮购电话：（010）88254888，88258888。 质量投诉请发邮件至 zlts@phei.com.cn，盗版侵权举报请发邮件至 dbqq@phei.com.cn。 本书咨询联系方式：faq@phei.com.cn。

前 言 III 前 言 目前，信息技术已被广泛应用于互联网、金融、航空、军事、医疗等各个领域， 未来的应用将更加广泛和深入。并且，很多中小学都开设了计算机语言课程，越来越 多的中小学生对编程、算法感兴趣，甚至在 NOIP、NOI 等算法竞赛中大显身手，进 入名校深造。对信息技术感兴趣的大学生通常会参加 ACM-ICPC、CCPC、蓝桥杯等 算法竞赛，其获奖者更是被各大名企所青睐。 学习算法，不仅可以帮助我们具备较强的思维能力及解决问题的能力，还可以帮 助我们快速学习各种新技术，拥有超强的学习能力。 写作背景 很多读者都觉得算法太难，市面上晦涩难懂的各种教材更是“吓退”了一大批读 者。实际上，算法并没有我们想象中那么难，反而相当有趣。 每当有学生说看不懂某个算法的时候，笔者就会建议其画图。画图是学习算法最 好的方法，因为它可以把抽象难懂的算法展现得生动形象、简单易懂。笔者曾出版《算 法训练营：海量图解+竞赛刷题》（入门篇）和《算法训练营：海量图解+竞赛刷题》 （进阶篇），很多读者非常喜欢其中的海量图解，更希望看到这两本书的全彩版。经过 一年的筹备，笔者对上述书中的所有图片都重新进行了绘制和配色，并精选、修改、 补充和拆分上述书中的内容，形成了《算法训练营：入门篇》（全彩版）、《算法训练 营：提高篇》（全彩版）和《算法训练营：进阶篇》（全彩版），本书就是其中的《算 法训练营：入门篇》（全彩版）。在此衷心感谢各位读者的大力支持！ 本书详细讲解常用的算法知识，特别增加了 C++基础知识和 STL 部分的内容。如 果读者已经熟悉 C++，则可跳过其中的基础章节。本书不是知识点的堆砌，也不是粘 贴代码而来的简单题解，而是将知识点讲解和对应的竞赛实例融会贯通，读者可以在 轻松阅读本书的同时进行刷题实战，在实战中体会算法的妙处，感受算法之美。

算法训练营 入门篇（全彩版） IV 学习建议 学习算法的过程，应该是通过大量实例充分体会遇到问题时该如何分析：用什么 数据结构，用什么算法和策略，算法复杂度如何，是否有优化的可能，等等。这里有 以下几个建议。 第 1 个建议：学经典，多理解。 算法书有很多，初学者最好选择图解较多的入门书，当然，也可以选择多本书， 从多个角度进行对比和学习。先看书中的图解，理解各种经典问题的求解方法，如果 还不理解，则可以看视频讲解，理解之后再看代码，尝试自己动手上机运行。如有必 要，则可以将算法的求解过程通过图解方式展示出来，以加深对算法的理解。 第 2 个建议：看题解，多总结。 在掌握书中的经典算法之后，可以在刷题网站上进行专项练习，比如练习贪心算 法、分治算法、动态规划等方面的题目。算法比数据结构更加灵活，对同一道题目可 以用不同的算法解决，算法复杂度也不同。如果想不到答案，则可以看题解，比较自 己的想法与题解的差距。要多总结题目类型及最优解法，找相似的题目并自己动手解 决问题。 第 3 个建议：举一反三，灵活运用。 通过专项刷题达到“见多识广”，总结常用的算法模板，熟练应用套路，举一反 三，灵活运用，逐步提升刷题速度，力争“bug free”（无缺陷）。 本书特色 本书具有以下特色。 （1）完美图解，通俗易懂。本书对每个算法的基本操作都有全彩图解。通过图解， 许多问题都变得简单，可迎刃而解。 （2）实例丰富，简单有趣。本书结合了大量竞赛实例，讲解如何用算法解决实际 问题，使复杂难懂的问题变得简单有趣，可帮助读者轻松掌握算法知识，体会其中的 妙处。 （3）深入浅出，透析本质。本书透过问题看本质，重点讲解如何分析和解决问题。 本书采用了简洁易懂的代码，对数据结构的设计和算法的描述全面、细致，而且有算 法复杂度分析及优化过程。 （4）实战演练，循序渐进。本书在讲解每个算法后都进行了实战演练，使读者在 实战中体会算法的设计思路和使用技巧，从而提高独立思考、动手实践的能力。书中

前 言 V 有丰富的练习题和竞赛题，可帮助读者及时检验对所学知识的掌握情况，为从小问题 出发且逐步解决大型复杂性工程问题奠定基础。 （5）网络资源，技术支持。本书为读者提供了配套源码、课件、视频，并提供了 博客、微信群、QQ 群技术支持，可随时为读者答疑解惑。 建议和反馈 写书是极其琐碎、繁重的工作，尽管笔者已经竭力使本书内容、网络资源和技术 支持接近完美，但仍然可能存在很多漏洞和瑕疵。欢迎读者反馈关于本书的意见，因 为这有利于我们改进和提高，以帮助更多的读者。如果对本书有意见和建议，或者有 问题需要帮助，则都可以加入 QQ 群 281607840，也可以致信 rainchxy@126.com 与笔 者交流，笔者将不胜感激。 对于本书提供的读者资源，可通过本书封底的“读者服务”获取。 致谢 感谢笔者的家人和朋友在本书写作过程中提供的大力支持。感谢电子工业出版社 工作严谨、高效的张国霞编辑，她的认真、负责促成了本书的早日出版。感谢提供了 宝贵意见的同事们，感谢提供了技术支持的同学们。感恩遇到这么多良师益友！

算法训练营 入门篇（全彩版） VI 目 录 第 1 章 C++基础知识 ..................... 1 1.1 开启算法之旅 ................................. 1 1.2 常用的数据类型 ............................. 2 1.3 玩转输入和输出 ............................. 2 1.4 常用的运算符 ................................. 3 1.5 选择结构语句 ................................. 5 1.5.1 if 条件语句 ......................... 5 1.5.2 switch 条件语句 ................. 9 1.6 循环结构语句 ............................... 10 1.6.1 for 语句 ............................. 10 1.6.2 while 语句 ........................ 13 1.6.3 do while 语句 ................... 14 1.7 巧用数组 ....................................... 15 1.7.1 一维数组 .......................... 15 1.7.2 二维数组 .......................... 17 1.8 玩转字符串 ................................... 18 1.8.1 C 风格的字符串 ............... 19 1.8.2 C++ string 类型的 字符串 .............................. 20 1.9 结构体的应用 ............................... 21 1.10 指针的应用 ................................. 22 第 2 章 算法之美 .......................... 24 2.1 算法复杂度 ................................... 24 2.1.1 时间复杂度 ...................... 27 2.1.2 空间复杂度 ....................... 27 2.2 函数 ............................................... 30 2.2.1 标准函数 ........................... 30 2.2.2 传值参数 ........................... 31 2.2.3 引用参数 ........................... 31 2.2.4 数组参数 ........................... 32 2.3 递归 ............................................... 33 2.3.1 递归函数 ........................... 33 2.3.2 递归的原理 ....................... 33 第 3 章 线性表的应用 .................. 37 3.1 顺序表 ........................................... 37 3.1.1 插入 ................................... 38 3.1.2 删除 ................................... 39 3.2 链表 ............................................... 40 3.2.1 单链表 ............................... 40 3.2.2 双向链表 ........................... 43 3.2.3 循环链表 ........................... 45 3.2.4 静态链表 ........................... 46 3.3 栈 ................................................... 49 3.3.1 入栈 ................................... 49 3.3.2 出栈 ................................... 49 3.3.3 取栈顶元素 ....................... 50 3.4 队列 ............................................... 50 3.4.1 顺序队列 ........................... 51 3.4.2 循环队列 ........................... 53

目 录 VII 3.5 STL 中的常用函数和容器 ........... 56 3.5.1 sort() .................................. 57 3.5.2 vector（向量） ................ 58 训练 角谷猜想 .......................... 59 3.5.3 stack（栈） ...................... 60 训练 数字游戏 .......................... 60 3.5.4 queue（队列） ................. 61 训练 骑士移动 .......................... 61 3.5.5 list（双向链表）.............. 63 训练 新兵队列训练 .................. 64 第 4 章 树的应用 .......................... 66 4.1 树 ................................................... 66 4.1.1 树的存储 .......................... 68 4.1.2 树、森林与二叉树的 转换 .................................. 71 4.2 二叉树 ........................................... 73 4.2.1 二叉树的性质 .................. 74 4.2.2 满二叉树和完全二 叉树 .................................. 75 4.2.3 二叉树的存储结构 .......... 78 4.3 二叉树遍历 ................................... 80 4.3.1 先序遍历 .......................... 80 4.3.2 中序遍历 .......................... 83 4.3.3 后序遍历 .......................... 86 4.3.4 层次遍历 .......................... 90 训练 1 新二叉树 ....................... 92 训练 2 二叉树遍历 ................... 93 4.4 哈夫曼树 ....................................... 95 4.4.1 哈夫曼编码 ...................... 95 4.4.2 哈夫曼编码的长度 计算方法 ........................ 108 训练 1 围栏修复 ..................... 109 训练 2 信息熵 ......................... 110 4.5 二叉搜索树 .................................. 112 4.5.1 二叉搜索树原理详解 ..... 112 4.5.2 查找 ................................. 112 4.5.3 插入 ................................. 115 4.5.4 创建 ................................. 116 4.5.5 删除 ................................. 117 训练 1 落叶 .............................. 122 训练 2 完全二叉搜索树 .......... 124 第 5 章 图论基础 ....................... 127 5.1 图的存储 ..................................... 128 5.1.1 邻接矩阵 ......................... 128 5.1.2 边集数组 ......................... 129 5.1.3 邻接表 ............................. 130 5.1.4 链式前向星 ..................... 133 5.1.5 图的存储技巧 ................. 136 5.2 图的遍历 ..................................... 136 5.2.1 广度优先遍历 ................. 136 5.2.2 深度优先遍历 ................. 140 训练 1 最大的节点 .................. 144 训练 2 油田 .............................. 145 第 6 章 算法入门 ....................... 149 6.1 贪心算法 ..................................... 149 6.1.1 贪心算法秘籍 ................. 149 6.1.2 最优装载问题 ................. 150 训练 1 部分背包问题 .............. 152 训练 2 排队接水 ...................... 153 训练 3 线段覆盖 ...................... 154 6.2 分治算法 ..................................... 156 6.2.1 分治算法秘籍 ................. 156 6.2.2 合并排序 ......................... 156 6.2.3 快速排序 ......................... 161 训练 1 排序（模板） .............. 168 训练 2 求第 k 小的数 .............. 169

算法训练营 入门篇（全彩版） VIII 第 7 章 高精度计算 .................... 171 7.1 高精度加法 ................................. 171 7.1.1 接收和存储数据 ............ 171 7.1.2 处理进位 ........................ 171 训练 A+B Problem .................. 174 7.2 高精度减法 ................................. 175 7.2.1 比较大小 ........................ 175 7.2.2 接收和存储数据 ............ 175 7.2.3 处理借位 ........................ 175 训练 A-B Problem .................. 177 7.3 高精度乘法 ................................. 178 7.3.1 接收和存储数据 ............ 178 7.3.2 处理进位 ........................ 178 训练 A*B Problem .................. 179 7.4 高精度除法 ................................. 180 7.4.1 接收和存储数据 ............ 180 7.4.2 按位相除 ........................ 181 训练 A/B Problem ................... 181 第 8 章 搜索算法入门 ................ 183 8.1 二分算法 ..................................... 183 8.1.1 二分查找 ........................ 183 8.1.2 二分答案 ........................ 186 训练 1 查找 ............................. 187 训练 2 跳石头游戏 ................. 189 训练 3 花环 ............................. 193 8.2 深度优先搜索 ............................. 195 8.2.1 回溯法的原理 ................ 195 8.2.2 回溯法模板 .................... 197 训练 1 01 背包问题 ................. 198 训练 2 图的 m 着色问题 ......... 205 训练 3 n 皇后问题 ................... 213 8.3 广度优先搜索 .............................. 227 8.3.1 分支限界法的原理 ......... 227 8.3.2 分支限界法秘籍 ............. 227 训练 1 迷宫问题 ...................... 228 训练 2 01 背包问题 ................. 229 第 9 章 动态规划入门 ................ 235 9.1 动态规划秘籍 .............................. 235 9.1.1 动态规划的三个要素 ..... 236 9.1.2 动态规划的设计方法 ..... 236 9.2 背包问题 ..................................... 237 9.2.1 01 背包问题 .................... 238 9.2.2 完全背包问题 ................. 246 训练 1 骨头收藏家 .................. 246 训练 2 存钱罐 .......................... 248 9.3 线性动态规划 .............................. 250 训练 1 超级楼梯 ...................... 250 训练 2 数字三角形 .................. 251 训练 3 最长上升子序列 .......... 253 训练 4 最长公共子序列 .......... 256 训练 5 最大连续子段和 .......... 257 9.4 区间动态规划 .............................. 259 训练 1 回文 .............................. 259 训练 2 括号匹配 ...................... 261 训练 3 乘法难题 ...................... 263 训练 4 猴子派对 ...................... 265

第 1 章 C++基础知识 1 第 1 章 C++基础知识 虽然算法不依赖任何计算机语言，但要上机实现它，至少需要学会一门计算机语 言。C++集面向对象编程、泛型编程和过程化编程于一体，在 C语言的基础上扩展了 自己特有的知识库。C++简单易学，非常适合作为编程入门语言。在初学 C++时可以 使用 Dev C++、CodeBlocks等编译器。 1.1 开启算法之旅 首先以如下图所示的程序截图开启算法之旅。 输入/输出头文件 使用标准命名空间 主函数 输出hello word! 返回0，程序正常结束 第 1行：头文件。进行输入和输出时需要引入 iostream头文件，iostream表示输 入/输出流。 第 2行：命名空间。using表示使用，namespace表示命名空间，std表示 standard （标准的）。在 C++标准库中，所有标识符都被定义于一个名为 std的命名空间中，std 被称为“标准命名空间”。 第 3行：主函数。主函数 main()是程序运行的入口，每个程序都有一个主函数， 返回值为 int类型。 第 4行：输出语句。cout表示输出，“<<”后面是输出的内容，endl表示换行。 第 5行：返回语句。主程序在运行正确的情况下返回 0。

算法训练营 入门篇（全彩版） 2 1.标识符与关键字 标识符用来标识变量、函数、类、模块或用户自定义项目的名称。标识符由字母、 数字或下画线组成，以字母或下画线开头。 关键字是具有特殊含义的保留字，例如 for、while、if、else、break等，用于特殊 目的，不能用作标识符。 2.常量与变量 变量是一个可供程序操作的存储空间标识，用变量可以灵活地保存和访问数据。 一旦定义了常量，该常量的值在程序执行期间就不能改变了。 3.注释 注释包括单行注释和多行注释。单行注释用于注释单行代码，一般位于单行代码 的后面或者上面，注释形式为“//单行注释”。多行注释用于注释多行代码，例如注释 程序或函数，注释形式为“/*多行注释*/”。 1.2 常用的数据类型 C++中常用的数据类型及其标识符、所占字节数和数值范围如下表所示。 数据类型 标 识 符 所占字节数 数值范围 布尔型 bool 1（8位） 1（真）或 0（假） 短整型 short 2（16位） -32 768 ~ 32 767 整型 int 4（32位） -2 147 483 648 ~ 2 147 483 647 长整型 long 4（32位） -2 147 483 648 ~ 2 147 483 647 超长整型 long long 8（64位） -9 223 372 036 854 775 808 ~ 9 223 372 036 854 775 807 单精度实型 float 4（32位） 1.1e-38 ~ 3.4e+38 双精度实型 double 8（64位） 2.2e-308 ~ 1.7e+308 长双精度实型 long double 16（128位） 3.3e-4932 ~ 1.1e+4932 1.3 玩转输入和输出 在 C++中，cin和 cout用于处理标准输入和输出。要在程序中输入内容和输出结 果，就需要在程序的开头引入头文件#include<iostream>。 1.cin cin用于处理标准输入，与提取运算符“>>”结合使用。例如： int a,b; cin>>a>>b;

第 1 章 C++基础知识 3 2.cout cout用于处理标准输出，与插入运算符“<<”结合使用。例如： string s="C++"; cout<<"Hello world!"<<endl; cout<<a<<b<<endl; //输出 a、b cout<<s<<endl; //输出 s 在算法比赛中，为提高运行速度，还经常使用 C风格的输入和输出语句。在程序 的开头引入头文件#include<cstdio>。输入语句为“scanf(格式控制符,地址列表);”，输 出语句为“printf(格式控制符,输出列表);”。 若不想写多个头文件，则可以使用万能头文件#include<bits/stdc++.h>。 训练 1（B2014）：输入圆的半径 r，输出其直径、周长和面积。 #include<bits/stdc++.h> //万能头文件 using namespace std; const double PI=3.14159; //圆周率（常量） int main(){ double r,a,b,c; //半径、直径、周长、面积 scanf("%lf",&r); //输入半径 a=2*r; b=2*PI*r; c=PI*r*r; printf("%.4f %.4f %.4f",a,b,c); //在输出结果中保留 4位小数 return 0; } 1.4 常用的运算符 （1）常用的算术运算符及其运算、范例、结果如下表所示。 算术运算符 运 算 范 例 结 果 + 正号 a=+3; a=3; - 负号 b=4; a=-b; a=-4; b=4; + 加 a=5+5; a=10; - 减 a=6-4; a=2; * 乘 a=3*4; a=12; / 除 a=5/5; a=1; % 取余 a=7%5; a=2; ++ 自增（前） a=2; b=++a; //a=a+1;b=a;先加 1后赋值 a=3; b=3; ++ 自增（后） a=2; b=a++; //b=a; a=a+1;先赋值后加 1 a=3; b=2; -- 自减（前） a=2; b=--a; //先减 1后赋值 a=1; b=1; -- 自减（后） a=2; b=a--; //先赋值后减 1 a=1; b=2;

算法训练营 入门篇（全彩版） 4 （2）常用的赋值运算符及其运算、范例、结果如下表所示。 赋值运算符 运 算 范 例 结 果 = 赋值 a=3; b=2; a=3; b=2; += 加等于 a=3; b=2; a+=b; //相当于 a=a+b; a=5; b=2; -= 减等于 a=3; b=2; a-=b; //相当于 a=a-b; a=1; b=2; *= 乘等于 a=3; b=2; a*=b; //相当于 a=a*b; a=6; b=2; /= 除等于 a=3; b=2; a/=b; //相当于 a=a/b; a=1; b=2; %= 模等于 a=3; b=2; a%=b; //相当于 a=a%b; a=1; b=2; （3）常用的关系运算符及其运算、范例、结果如下表所示。关系运算符用于对两 个数值或变量进行比较，其结果是一个逻辑值（逻辑值只有“真”或“假”，用 1代表 真，用 0代表假）。 关系运算符 运 算 范 例 结 果 = = 相等于 4==3 0 != 不等于 4!=3 1 < 小于 4<3 0 > 大于 4>3 1 <= 小于或等于 4<=3 0 >= 大于或等于 4>=3 1 （4）常用的逻辑运算符及其运算、范例、结果如下表所示。逻辑运算符用于判断 数据的真假，其结果也是一个逻辑值，即“真”或“假”。 逻辑运算符 运 算 范 例 结 果 ! 非 !a 若 a为假，则!a为真；若 a为真，则!a为假 && 与 a&&b 若 a和 b都为真，则结果为真，否则为假 || 或 a || b 若 a和 b有一个为真，则结果为真；若两者均为假，则结果为假 注意 千万不要将逻辑运算符“==”写成赋值运算符“=”。例如，若将 if(a==b) 写成 if(a=b)，虽然系统不会有错误提示，却存在逻辑错误。 逻辑运算符的优先级如下： ● “&&”的优先级高于“||”； ● “&&”“||”的优先级低于关系运算符； ● “！”的优先级高于所有关系运算符和算术运算符。

第 1 章 C++基础知识 5 1.5 选择结构语句 在 C++中，我们经常需要对一些条件做出判断，决定执行什么操作，这时就需要 使用选择结构语句，比如 if条件语句和 switch条件语句。 1.5.1 if 条件语句 if条件语句有三种语法格式，如下图所示。 （1）if语句——单分支结构，其运行逻辑如下图所示。 结束 判断条件 真 假 语句体 开始 （2）if…else语句——双分支结构，其运行逻辑如下图所示。 结束 判断条件 真 假 开始 语句 2语句 1 （3）if语句的嵌套。在一个 if语句中还可以包含一个或多个 if语句，这叫作“if 语句的嵌套”，其运行逻辑如下图所示。

算法训练营 入门篇（全彩版） 6 开始 结束 条件1 条件2 …… 条件n 真 假 真 真 真 假 假 假 语句1 语句2 …… 语句n 语句n+1 训练 2（B2050）：给定三条线段的长度（正整数），判断这三条线段能否构成一 个三角形。 #include<bits/stdc++.h> //万能头文件 using namespace std; int main(){ int a,b,c; //整型变量 a、b、c分别代表三条线段的长度 cin>>a>>b>>c; //输入三条线段的长度 if(a+b>c && a+c>b && b+c>a) //是否满足“两边之和大于第三条边 ” cout<<1<<endl; //是则输出 1 else cout<<0<<endl; //否则输出 0 return 0; } 训练 3（B2037）：给定一个整数 n，判断 n是奇数还是偶数。若 n是奇数，则输 出 odd；若 n是偶数，则输出 even。 #include<iostream> using namespace std; int main(){ int n; cin>>n; if(n%2) //n除以 2余数不为 0 cout<<"odd"<<endl; else cout<<"even"<<endl; return 0; }

第 1 章 C++基础知识 7 训练 4（P5711）：输入一个年份，判断其是否是闰年，是则输出 1，否则输出 0。 #include<iostream> using namespace std; int main(){ int year; cin>>year; if((year%4==0&&year%100!=0)||year%400==0) //能被 4整除但不能被 100整除，或者能被 //400整除 cout<<"1"<<endl; else cout<<"0"<<endl; return 0; } 训练 5（P5714）：BMI指数是国际上常用的衡量人体胖瘦程度的一个指标。BMI= m/h2，其中 m指体重（千克），h指身高（米）。不同体型的 BMI指数判断逻辑如下。 ● 小于 18.5：体重过轻，输出 Underweight。 ● 大于或等于 18.5且小于 24：正常体重，输出 Normal。 ● 大于或等于 24：肥胖，首先输出 BMI指数，然后换行，再输出 Overweight。 输入体重和身高数据，根据 BMI指数判断体型并输出对应的判断结果。 #include<iostream> using namespace std; int main(){ float m,h,bmi; cin>>m>>h; bmi=m/(h*h); if(bmi<18.5) cout<<"Underweight"; else if(bmi<24) cout<<"Normal"; else cout<<bmi<<"\nOverweight"; return 0; } 训练 6（B2043）：给定一个整数 x，判断它能否被 3、5、7 整除，并输出相应的 信息。 ● 能同时被 3、5、7整除：直接输出 3 5 7，每两个数之间都有一个空格，下同。 ● 只能被其中两个数整除：按从小到大的顺序输出这两个数，例如 3 5或者 3 7 或者 5 7。 ● 只能被其中一个数整除：输出这个数。 ● 不能被其中的任何一个数整除：输出小写字符“n”。

算法训练营 入门篇（全彩版） 8 #include<bits/stdc++.h> using namespace std; int main(){ int x; cin>>x; if(x%3==0) //能被 3整除 cout<<"3 "; if(x%5==0) //能被 5整除 cout<<"5 "; if(x%7==0) //能被 7整除 cout<<"7"; if(x%3 && x%5 && x%7) //不能被 3、5、7中的任何一个数整除 cout<<"n"; return 0; } 训练 7（B2047）：编写程序，计算下列分段函数 y=f(x)的值。 ● 当 0≤x<5时，y=-x+2.5。 ● 当 5≤x<10 时，y=2-1.5(x-3)(x-3)。 ● 当 10≤x<20时，y=x/2-1.5。 输入一个浮点数 x（0≤x<20），输出 x对应的分段函数值 f(x)，结果保留 3位小数。 #include<bits/stdc++.h> using namespace std; int main(){ float x,y; cin>>x; //0<=x<20 if(x<5) y=-x+2.5; else if(x<10) y=2-1.5*(x-3)*(x-3); else y=x/2-1.5; cout<<fixed<<setprecision(3)<<y; //结果保留 3位小数 return 0; } 训练 8（B2048）：请根据邮件的重量和用户要求，选择是否加急计算邮费。计算 规则如下。 ● 重量在 1000克以内（包括）：基本邮费 8元。 ● 超过 1000克的部分：每 500克加收超重邮费 4元，不足 500克的部分按 500 克计算。 ● 用户选择加急：多收 5元。

第 1 章 C++基础知识 9 输入以空格隔开的正整数 x和字符 c（y或 n），分别表示重量、是否选择加急。 若字符是 y，则表示选择加急；若字符是 n，则表示未选择加急。 #include<bits/stdc++.h> using namespace std; int main(){ int x,ans=8; //基本邮费 8元 char c; cin>>x>>c; if(x>1000){ x-=1000; ans+=((x-1)/500+1)*4; //向上取整：n/k向上取整的计算方法为(n-1)/k+1 } if(c=='y') //用户选择加急，多收 5元 ans+=5; cout<<ans; return 0; } 1.5.2 switch 条件语句 除了 if 条件语句，switch 条件语句也是一种常用的选择结构语句。与 if 条件语句 不同，switch条件语句只能针对某个表达式的值做出判断，从而决定程序执行哪段代码。 …… 结束 执行case语句1 执行case语句2 执行case语句n 值1 值2 值n 开始 注意 switch 条件语句在执行完一个 case 语句之后不会自动停止，需要使用 break 语句停止；switch 条件语句中的每个 case 语句都必须对应一个单独的值，该值 必须是整数或字符，不能是浮点数。若涉及取值范围、浮点数或比较，则先使用 if… else语句转换。 训练 9（P5716）：输入年份和月份，输出这一年的这个月有多少天（需要考虑闰 年）。 #include<bits/stdc++.h> using namespace std; int main(){

算法训练营 入门篇（全彩版） 10 int y,m; //年、月份 scanf("%d%d",&y,&m); switch(m){ case 1:case 3:case 5:case 7:case 8:case 10:case 12: printf("31"); //1、3、5、7、8、10、12月有 31天 break; case 4:case 6:case 9:case 11: //4、6、9、11月有 30天 printf("30"); break; case 2: if(y%400==0||(y%4==0&&y%100!=0)) //判断是否为闰年 printf("29"); //闰年的 2月有 29天 else printf("28"); //平年的 2月有 28天 break; } return 0; } 1.6 循环结构语句 在实际生活中，我们经常会将同一件事情重复做很多次。在 C++中也经常需要重 复执行同一代码块，这时就需要使用循环结构语句。循环结构语句包括 for、while和 do while语句。 1.6.1 for 语句 for语句的示例及其运行逻辑如下图所示。 初始化 循环更新 循环体 循环条件 for(int i=1; i<=n; i++) { cout<<i<<endl; } 真 结束 假 循环条件 循环体 循环更新 开始 初始化 训练 10（P5722）：计算 1+2+3+…+(n-1)+n的值，其中，正整数 n不大于 100。 #include<iostream> using namespace std;