内容简介

本书系统性地总结了C++编程与信息学竞赛所需的数学知识体系，包括初等数学基础、数列问题及递推和递归、初等几何、进制及进制转换、数论基础、初等代数、集合论、组合数学、图论基础、树及二叉树、概率论基础、逻辑学基础、编码及译码、博弈论基础、算法及算法复杂度等核心内容。本书涵盖GESP、电子学会等级考试、CSP-J/S、NOIP、NOI等信息学竞赛所需的数学基础知识。本书配备了完善的题库、课件、教学视频等资源，可以作为中小学信息学竞赛集训队的训练教材，也可以作为少儿编程培训机构的培训教材，还可以作为少儿编程等级考试和信息学竞赛的辅导教材。

目录

目 录

第1章 初等数学基础

1．1 数的认识（1）——自然数、整数

1．2 数的四则运算

1．3 整数的除法：商和余数

1．4 构成像钟表一样的环状序列

1．5 倍数和因数

1．6 合数和质数

1．7 哥德巴赫猜想

1．8 大数的认识

1．9 时间和日期中的数学知识

1．10 平方和平方根、立方和立方根

1．11 幂运算

1．12 数的认识（2）——分数

1．13 数的认识（3）——小数

1．14 整数商和浮点数商

1．15 小数在计算机中无法精确表示

1．16 数的认识（4）——有理数和无理数

1．17 整数的放大与缩小

1．18 小数的放大与缩小

1．19 分数和百分数

1．20 向上取整和向下取整

1．21 取整和四舍五入

1．22 浮点数的整数商和余数

1．23 累加∑和连乘∏

1．24 上标和下标

1．25 递推

1．26 数学和生活中的循环

1．27 一些特殊的数

1．28 函数的初步认识

1．29 幂函数和指数函数

1．30 增长很快的运算：指数运算和阶乘

1．31 其他数学知识

第2章 数列问题及递推和递归

2．1 数列及相关问题

2．2 等差数列和等比数列

2．3 斐波那契数列

2．4 数列递推的例子

2．5 数学归纳法

2．6 递归和递归函数

2．7 递归方法应用实例

2．8 数列问题实例——递推和递归求解

2．9 递推和递归总结

2．10 递归存在的问题及解决方法

2．11 整数划分问题

第3章 初等几何

3．1 三角形的判定

3．2 多边形的判定

3．3 凸多边形和凹多边形

3．4 勾股定理

3．5 勾股数

3．6 锐角三角形和钝角三角形的判定

3．7 周长、面积、表面积和体积

3．8 圆周率的故事

3．9 内角和、角度和弧度

3．10 海伦—秦九韶公式

3．11 直角坐标系和距离公式

3．12 网格坐标系

3．13 从一维到二维再到三维

第4章 进制及进制转换

4．1 数位和计数单位

4．2 科学记数法及浮点数的由来

4．3 进制及十进制

4．4 二进制

4．5 二值的表示

4．6 计量数据大小的单位

4．7 八进制和十六进制

4．8 其他进制

4．9 二进制、八进制和十六进制的相互转换

4．10 其他进制转换成十进制

4．11 十进制转换成其他进制

4．12 理解整型(int， long long)的范围

4．13 位运算及应用

4．14 原码、反码、补码

4．15 标准模板库中的位组

4．16 有符号和无符号整数的溢出问题

第5章 数论基础

5．1 整除、因数和倍数

5．2 质数及筛选法

5．3 带余数除法

5．4 最大公约数理论及应用

5．5 格点问题

5．6 扩展欧几里得算法

5．7 唯一分解定理及应用

5．8 求n!的标准质因数分解式

5．9 同余理论及应用

5．10 数论倒数——a对模m的逆

5．11 同余方程及同余方程组

5．12 欧拉函数

5．13 快速幂算法

第6章 初等代数

6．1 初等代数的研究内容

6．2 单项式与多项式

6．3 一元一次方程

6．4 一元二次方程

6．5 二元一次方程组

6．6 不定方程（组）

6．7 线性方程组

6．8 矩阵和矩阵的乘法运算

第7章 集合论

7．1 集合的概念

7．2 子集及幂集

7．3 集合的运算

7．4 STL中的集合（set）

7．5 有限集的计数问题

7．6 容斥原理

7．7 元组

7．8 STL中的数对（pair）

7．9 笛卡儿积

7．10 关系

7．11 关系的表示——关系矩阵

7．12 等价关系

第8章 组合数学

8．1 加法原理和乘法原理

8．2 排列和组合

8．3 杨辉三角

8．4 全排列及排列的字典序

8．5 排列组合问题求解

8．6 特殊的排列组合问题

8．7 第二类斯特林数和Bell数

8．8 小球放盒子问题

8．9 卡特兰数列及其应用

8．10

前言/序言

亲爱的小朋友们，当你们打开这本书时，相信你们已经开始了C++编程的学习之旅，甚至可能正在进入算法学习的精彩阶段。你们中的许多人，或许正在为编程等级考试或信息学竞赛做准备。在学习过程中，你们可能发现了一个有趣的现象，很多编程题目都包含着丰富的数学知识，有些内容甚至超出了你们当前数学课程的进度，比如平方根、立方根、函数等概念。

你们可能会非常困惑。信息学竞赛为什么会用到这么多数学知识？参加信息学竞赛到底要掌握哪些数学知识？是不是奥数学好了，学习算法时就没有障碍了？现在我就来逐一解答这些困惑。

计算机（computer）最初就是为“计算”而设计的。世界上第一台电子计算机ENIAC诞生于1946年，当时研制计算机的目的是解决复杂的弹道计算问题。尽管现在的计算机功能非常强大，除了可以用来做科学计算，还可以用来办公、学习、娱乐，也可以运行当前各种炫酷的人工智能应用程序，但是，无论多复杂的功能，计算机都是将它们转换成各种计算。要理解和熟练应用这些计算，就需要学好数学。此外，信息学竞赛的核心是算法设计，而算法是建立在数学基础之上的。所以，信息学竞赛需要掌握很多数学知识。

信息学竞赛涉及的数学知识包括在小学阶段学的所有初等数学基础和初等几何知识，以及在小学阶段课本上基本学不到的数列问题及递推和递归、进制及进制转换、数论基础、集合论、组合数学、图论基础、树及二叉树、概率论基础、逻辑学基础、编码及译码、博弈论基础、算法及算法复杂度等。

这么多数学知识，中学生甚至小学生能掌握吗？我觉得是可以的，因为同学们只需要理解这些数学知识背后的思想和原理，不需要手工求解这些数学问题。我们的目标是根据数学原理，设计算法，编写程序，让计算机来帮我们解决这些问题。而且这些数学知识不是在学习C++和算法前就必须全部掌握的，也就是说不是预备知识，而是贯穿于C++和算法学习的整个阶段的。

以平方根为例，小学阶段的数学没法讲平方根运算，因为手工求、等是求不出来的，但同学们只要理解了平方根的含义，知道平方根是平方的相反运算，在C++程序中知道如何调用sqrt()函数求平方根就可以了。又如，组合数学中有很多复杂的排列组合问题，对小学生来说太难了，但是在信息学竞赛里主要应用的是组合数学里的一些原理，比如，加法原理、乘法原理、鸽巢原理等。

既然信息学竞赛需要掌握很多数学知识，那么同学们直接学奥数不就可以了吗？注意，C++编程与信息学竞赛中的数学不等于奥数。奥数更多的是训练学生的计算技巧和动手解决应用问题的能力，但是这些计算技巧在C++编程与信息学竞赛中完全没有用武之地。因为编程的目的之一就是把所有计算交给程序来实现，而且奥数里津津乐道的各种应用题，在信息学竞赛的试题里几乎不会出现，此外，奥数几乎不涉及算法。所以，同学们需要专门学习信息学竞赛的数学基础知识。

本书就是一本专门讲C++编程与信息学竞赛数学基础的书，既是数学书也是编程书，侧重数学原理在编程中的应用。为了降低门槛，本书把算法难度控制在基础级，只用到了枚举、模拟、递推、递归等简单算法，此外也用到C++语言标准模板库中的容器，包括位组（bitset）、集合（set）、数对（pair）等。

最后，祝小朋友们能感受到数学之美，体会到学习数学和编程的快乐，在快乐中学习。