5、数学

5.1 数及其运算

5.1.1 数的概念，算术运算（加、减、乘、除、求余）

数是用来计数、测量和标记量的概念。数可以用于描述物体的数量、尺寸、重量、速度、时间等。数可以分为自然数、整数、有理数和实数等不同类型。

算术运算是指数学中的四则运算，包括加、减、乘、除和求余。这些运算常常在日常生活中被广泛使用，是数学的基本概念。下面分别介绍这些运算：

加法（+）：加法是指将两个数相加，得到它们的和。例如，\(2+3=5\)，\(4+(-2)=2\)。
减法（-）：减法是指将一个数减去另一个数，得到它们的差。例如，\(5-2=3\)，\(4-(-2)=6\)。
乘法（*）：乘法是指将两个数相乘，得到它们的积。例如，\(2\times3=6\)，\((-4)\times(-2)=8\)。
除法（/）：除法是指将一个数除以另一个数，得到它们的商。例如，\(6\div2=3\)，\((-8)\div4=-2\)。需要注意的是，除数不能为零。
求余（%）：求余是指将一个数除以另一个数，得到它们的余数。例如，\(7\bmod2=1\)，\((-10)\bmod3=2\)。求余的结果是一个整数，其值为被除数减去除数乘以商后的余数。

5.1.2 数的进制：二进制、八进制、十六进制和十进制及其转换

数的进制是指一个数所表示的基数，通常表示为 \(n\) 进制，其中 \(n\) 表示基数，例如 2 进制、8 进制、10 进制和 16 进制。

在计算机领域中，常见的进制有二进制（binary）、八进制（octal）、十进制（decimal）和十六进制（hexadecimal）。

二进制：使用 0 和 1 两个数字表示数值，是计算机最基本的进制，常用于表示计算机中的开关状态、编码等。

八进制：使用 0 到 7 共 8 个数字表示数值，常用于 Unix/Linux 操作系统的文件权限和用户组的表示。

十进制：使用 0 到 9 共 10 个数字表示数值，是我们平时最常用的进制。

十六进制：使用 0 到 9 和 A 到 F 共 16 个数字表示数值，常用于计算机中表示颜色、内存地址等。

各个进制之间的转换可以通过位数上的规律进行计算，例如：

二进制转十进制：将二进制数每一位乘以对应位的权值（\(2^0,2^1,2^2,\dots\)）并求和，即可得到十进制数。
十进制转二进制：使用“除以 2 取余倒序排列”法，即将十进制数每次除以 2，得到的余数倒序排列，即为二进制数。
八进制和十六进制与二进制的转换：将八进制或十六进制数每一位转换为对应的二进制数，然后将所有二进制数拼接起来即可。

需要注意的是，不同进制之间的数值大小是不一样的，例如在十进制中 10 和 2 在数值大小上差了一个数量级，但在二进制中 10 表示的是十进制的 2，两者数值相等。因此，在进行不同进制之间的数值比较时需要先将它们转换为同一进制。

5.1.3 编码：ASCII码，哈夫曼编码，格雷码

ASCII码是一种将字符映射到数字的编码方式，使用7位二进制数表示128种不同的字符。ASCII码是计算机中最基本、最常用的编码之一，它将所有的字母、数字、标点符号等符号都用二进制数进行了编码，方便计算机处理和存储。

哈夫曼编码是一种可变长度编码，它根据字符出现的频率来构建编码表，出现频率高的字符使用较短的编码，出现频率低的字符使用较长的编码，从而使得整个编码串的长度更短。哈夫曼编码广泛应用于数据压缩和加密领域。

格雷码是一种二进制数码系统，它将相邻的两个数的二进制码只有一位不同，比如3的二进制码为011，4的二进制码为100，它们的差异只有一位，因此在格雷码中它们的编码也只有一位不同。格雷码在数字转换、数字传输等领域有着广泛的应用。

5.2 初中数学

5.2.1 初中代数

初中代数主要包括方程、不等式、函数等基本概念和运算。以下是对这些概念和运算的简要介绍：

方程：方程是一个含有未知数的等式，通常用来解决未知数的值。常见的方程有一元一次方程、一元二次方程等。一元一次方程的一般形式是ax+b=0，其中a和b是已知数，x是未知数。解一元一次方程的方法包括平移消元法、代入法、等式法等。
不等式：不等式是一种比较大小的关系，通常包括大于号、小于号、大于等于号、小于等于号等符号。与方程类似，不等式也可以用来解决未知数的取值范围。一元一次不等式的一般形式是ax+b>c或ax+b<c，其中a、b、c是已知数，x是未知数。解一元一次不等式的方法包括平移消元法、代入法、符号法等。
函数：函数是一种数学关系，通常表示为y=f(x)，其中x是自变量，y是因变量，f(x)是函数的表达式。函数的图像通常是一条曲线。初中所学的函数包括一次函数、二次函数、反比例函数等。一次函数的一般形式是y=kx+b，其中k和b是已知数，x和y是自变量和因变量。
基本运算：初中代数的基本运算包括加法、减法、乘法、除法和取余运算。其中，加法和乘法是满足交换律、结合律和分配律的运算，减法和除法都有对应的逆运算。取余运算是指将一个数除以另一个数后，得到余数的运算。
方程组：方程组是由多个方程组成的系统，其中每个方程都包含多个未知数。初中阶段主要学习一元二次方程组和二元一次方程组的解法，其中一元二次方程组是指方程组中每个方程都是一元二次方程，而二元一次方程组是指方程组中每个方程都是两个未知数的一次方程。解方程组的方法包括代入法、消元法等。

5.2.2 初中平面几何

初中平面几何主要包括点、线、面、角等基本概念以及平面图形的性质和计算方法。

基本概念
点：空间中没有大小的位置，用大写字母表示，如A、B、C。
线：由无数个点沿着同一方向排列而成的图形，用小写字母表示，如a、b、c。
面：由无数个点组成的、有一定形状和大小的平面图形，用大写字母表示，如ΔABC、矩形ABCD。
角：由两条射线共同确定的图形，用∠表示，如∠ABC。
平面图形的性质和计算方法
直线和射线：直线是一条无限长的线段，射线是一个端点为起点，沿着某一方向无限延伸的线段。
三角形：三角形是一个有三条边的平面图形，根据三角形内角和定理，三角形内角之和等于180度。另外，还有勾股定理、正弦定理、余弦定理等可以用来计算三角形的边长和角度。
矩形：矩形是一种特殊的平行四边形，它有四个内角都是直角，相邻两边长度相等，对角线长度相等。
平行四边形：平行四边形是一种有两组平行的边的四边形，对边相等，对角线互相平分。
梯形：梯形是一种至少有一组平行的边的四边形，它有两个底角和两个顶角，底角之和等于180度。
圆：圆是一个平面图形，由一条与平面内某一定点距离相等的曲线组成。圆的周长等于直径与圆周率的乘积，面积等于半径的平方与圆周率的乘积。
正多边形：正多边形是一个内角相等、边长相等的多边形，对于n边形，它的内角为(180度×(n-2))/n。

初中平面几何主要涉及上述的基本概念和平面图形的性质及计算方法，掌握这些内容可以帮助我们更好地理解和计算几何问题。

5.3 初等数论

5.3.1 整除、因数、倍数、指数、质数、合数、同余等概念

整除、因数、倍数、指数、质数、合数、同余是数论中常见的概念，下面逐一介绍：

1.整除

设\(a,b\)是整数，若存在整数\(c\)，使得\(a=bc\)，则称\(a\)能被\(b\)整除，\(a\)是\(b\)的倍数，记作\(b|a\)。

2.因数

设\(a,b\)是整数，若存在整数\(c\)，使得\(a=bc\)，则称\(b\)是\(a\)的因数，\(a\)是\(b\)的倍数。一个数的因数是能够整除这个数的整数，比如\(6\)的因数为\(1,2,3,6\)。

3.倍数

设\(a,b\)是整数，若存在整数\(c\)，使得\(a=bc\)，则称\(a\)是\(b\)的倍数，\(b\)是\(a\)的因数。\(a\)的倍数是能够被\(a\)整除的整数，比如\(6\)的倍数为\(6,12,18,\cdots\)。

4.指数

指数是数学中的一个重要概念，表示一个数被乘方的次数。比如，\(2^3\)中的\(3\)就是指数。

5.质数

质数是指只能被\(1\)和自身整除的正整数，也称素数。比如，\(2,3,5,7\)都是质数。

6.合数

合数是指能被\(1\)和自身以外的正整数整除的正整数。比如，\(4,6,8,9\)都是合数。

7.同余

同余是指两个数除以同一个正整数所得的余数相等。比如，\(5\)和\(11\)在模\(3\)意义下同余，记作\(5\equiv 11\pmod{3}\)。在计算机科学中，同余通常用于哈希算法的实现。

这些概念在数学和计算机科学中都有着广泛的应用，对于理解算法和数据结构都具有重要的作用。

5.3.2 唯一分解定理

唯一分解定理，又称质因数分解定理，指出每个大于1的自然数都可以唯一地表示为一些质数的乘积，其中每个质数因子都有一个确定的指数。

具体地，唯一分解定理可以表述为：任何一个大于1的自然数N，都可以被表示成N = p1^k1 * p2^k2 * ... * pn^kn，其中p1、p2、...、pn都是质数，k1、k2、...、kn都是正整数，且表示方法是唯一的。

例如，30可以被表示为2¹ * 3¹ * 5¹，64可以被表示为2⁶，120可以被表示为2³ * 3¹ * 5¹。

唯一分解定理在数论和离散数学中具有重要地位，不仅可以帮助我们研究整数性质，也在密码学、编码和计算机科学等领域有广泛应用。

5.3.3 欧几里得算法（辗转相除法）

欧几里得算法，也称辗转相除法，是求两个数的最大公约数的一种算法。它的基本思想是，用较大的数除以较小的数，再用除数（余数）去除出现的余数，直到余数为 0 时，最后的除数即为这两个数的最大公约数。

例如，求 18 和 24 的最大公约数，可以采用以下步骤：

用 24 除以 18，得到商 1，余数 6；
用 18 除以 6，得到商 3，余数 0。

由此可知，18 和 24 的最大公约数是 6。

欧几里得算法可以通过递归或循环实现。以下是递归实现的 C++ 代码：

C++
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

以下是循环实现的 C++ 代码：

C++
int gcd(int a, int b) {
    while (b != 0) {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

其中，a 和 b 分别为要求最大公约数的两个数。

5.3.4 埃氏筛法和线性筛法求素数

埃氏筛法和线性筛法都是用来求解素数的算法，下面分别介绍这两种算法的原理和代码实现。

1.埃氏筛法

埃氏筛法是一种简单的筛法，原理是先把从2开始的各个正整数顺序排列，每个数都可以看做是质数，然后将每个质数的倍数都标记成合数，依次往后筛选，最后剩下的就都是质数。

具体实现时，可以使用一个bool类型的数组来表示每个数是否是质数，初始时都设置为true，然后从2开始，对于每个质数p，将p的倍数标记为false，这样往后筛选时就可以直接跳过非质数了。

以下是埃氏筛法的C++代码实现：

C++
#include <iostream>
#include <vector>

using namespace std;

void EratosthenesSieve(int n) {
    vector<bool> is_prime(n + 1, true); // 标记每个数是否是质数，初始化为true

    for (int p = 2; p <= n; ++p) {
        if (is_prime[p]) { // 如果当前数p是质数
            cout << p << " "; // 输出p
            // 将p的倍数标记为非质数
            for (int i = p * 2; i <= n; i += p) {
                is_prime[i] = false;
            }
        }
    }
}

int main() {
    int n = 100;
    EratosthenesSieve(n);
    return 0;
}

2.线性筛法

线性筛法是一种快速求解素数的算法，它在埃氏筛法的基础上，采用了类似于动态规划的思想，避免了重复标记，从而更快地求出素数,相比于传统的筛法，其时间复杂度更低。其原理主要是根据每个合数只能被其最小质因子筛掉的性质，通过线性筛选的方式将所有的素数筛选出来。

具体实现步骤如下：

1.从小到大遍历每个整数，用一个 bool 数组标记其是否为素数。

2.若当前数 i 为素数，则将其所有的倍数（j = i * k）标记为合数，即非素数。

3.若当前数 i 不为素数，则说明其是之前某个素数的倍数，已经被标记过，因此可以跳过。

以下是线性筛法的C++代码实现：

C++
vector<int> getPrimes(int n) {
    vector<int> primes;
    vector<bool> isPrime(n + 1, true); // 标记是否为素数

    for (int i = 2; i <= n; ++i) {
        if (isPrime[i]) {
            primes.push_back(i); // 将素数加入结果集
        }
        for (int j = 0; j < primes.size() && i * primes[j] <= n; ++j) {
            isPrime[i * primes[j]] = false; // 标记素数的倍数为合数
            if (i % primes[j] == 0) {
                break; // 跳过之前已被标记过的合数
            }
        }
    }

    return primes;
}

其中，参数 n 表示要求解的素数的范围。首先用一个 bool 类型的数组 isPrime 标记每个整数是否为素数，初始时所有数都标记为素数。接下来从小到大遍历每个整数 i，若其为素数，则将其所有的倍数标记为合数；若其不为素数，则跳过。最后将所有标记为素数的整数加入结果集 primes 中并返回。

5.4 组合数学

5.4.1 加法原理

加法原理是指，如果一件事情可以分为 \(n\) 个步骤完成，第 \(i\) 步可以完成 \(a_i\) 种不同的选择，那么完成这件事情总共有 \(\sum_{i=1}^{n}a_i\) 种不同的选择方法。

举例来说，假设我们制作馒头有 3 个步骤，制作蛋糕有 4 个步骤，那么我们有多少步骤进行制作馒头和蛋糕呢？根据加法原理，总共有 \(3 + 4 = 7\) 个步骤。

在计数问题中，加法原理通常用于处理可以划分成多个步骤完成的问题，每个步骤可以选择不同的对象。它是组合计数中最基础的计数原理之一。

5.4.2 乘法原理

乘法原理是组合数学中的一条基本原理，指若一个事件要分为 k 步进行，第一步有 n₁ 种可能，第二步有 n₂ 种可能，...，第 k 步有 n_k 种可能，那么这个事件一共有 n₁ × n₂ × ... × n_k 种可能的结果。

乘法原理在计数问题中的应用非常广泛，例如：

从一个有 n 个元素的集合中取出 k 个元素，有多少种取法？
一场比赛需要从两个球队中各选出一个人作为队长，有多少种可能的对决方式？
一个由 n 个灯泡组成的房间，每个灯泡只有两个状态：开或关。求一共有多少种可能的开关状态组合？

这些问题中，我们都可以使用乘法原理来计算方案总数。

5.4.3 排列及计算公式

排列指从n个不同元素中取出m个元素进行排列的方案数，用P(n,m)表示，其中n为总数，m为取出元素的个数，顺序不同被视为不同的方案。计算公式为：

P(n,m) = n(n-1)(n-2)...(n-m+1) = n!/(n-m)!

例如，从6个不同的数字中取出3个进行排列，共有P(6,3) = 6×5×4 = 120种排列方式。

排列的计算可以使用递归、迭代等方式进行实现。

5.4.4 组合及计算公式

组合是从\(n\)个不同元素中取出\(m\)个元素（\(m\le n\)）并成一组的操作。通常用符号\(\binom{n}{m}\)表示，其计算公式为：

\[\binom{n}{m}=\frac{n!}{m!(n-m)!}\]

其中\(n!\)表示\(n\)的阶乘，即\(n!=n\times (n-1)\times (n-2)\times\cdots \times 1\)。

例如，从\(5\)个不同的元素中选取\(3\)个元素的组合数为：

\[\binom{5}{3}=\frac{5!}{3!2!}=\frac{5\times 4\times 3}{3\times 2\times 1}=10\]

表示从\(5\)个元素中选取\(3\)个元素有\(10\)种不同的组合方式。

5.4.5 杨辉三角公式

杨辉三角是一种数学上的图形，由一列数字开始，在下面每一行中，每个数字都是上面两个数字的和。杨辉三角的第n行的数字代表了组合公式（n,k）中的第k个数。这个数列被称为杨辉三角，是二项式系数在三角形中的一种几何排列。它是中国古代数学的一项成就，在中国被称为“杨辉三角”，因为它的早期记载者之一是中国明朝数学家杨辉。

杨辉三角的前几行为：

杨辉三角的计算公式是：

Text Only
C(n, k) = C(n-1, k-1) + C(n-1, k)

其中，C(n,k) 表示从 n 个元素中取 k 个元素的组合数。

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用