木有BUG!站点正常运行(ノ゚▽゚)ノ | 最近更新:质数筛 | 更新时间:2023-09-20

有关于C++的基础教程,该教程建立在学习过C语言的基础上,进行对比学习,了解不同的特性和更多新内容,学习设计类和面向对象程序设计

注:该教程建立在学习过 C 语言的基础上,因此很多提过的细节会忽略,主要学习一些 C 语言没有或不同的特性,建议先学习C 语言基础教程

本文中没有特殊重申的,大多语句和特性都与 C 语言相同,C++是 C 的超集,兼容了 C 的大多数特性


开始


章节概要:编写一个简单的 C++程序;初识输入输出;使用 C++ 版本的 C 标准库头文件;类简介

阅读更多
C++基础语法

有关于C语言的基础教程,包括基本语法、基础的底层逻辑知识与部分数据结构内容,比较适合有一定学习经验的初学者上手

初识 C 语言


章节概要:C 语言的特点;计算机工作原理;高级计算机语言;编译器;编程步骤;C 编程机制

特点
  • 设计特性

    C 语言融合了计算机科学理论实践的控制特性
    C 语言的设计理念让用户轻松完成自顶向下的规划结构化编程模块化设计

阅读更多
C语言基础语法

使用质数筛快速判断质数,掌握埃氏筛和欧拉线性筛的思路和代码实现

素数判断


  • 素数判断

    1、最简单的判断质数的方式,便是从 2~x 依次尝试,如果尝试到有因子,则其不是质数。需要特判 2 为质数小于 2 的都不是质数(质数范围是大于 1 的自然数)
    2、朴素筛法可以简单进行优化,实际需要尝试的因子最多只到sqrt(x)。比如判断 25 时,易知只需要判断 2~5 有没有因子,因此不需要重复判断大于sqrt(x)的因子。提前使用变量记录sqrt(x),可以避免循环中重复计算sqrt的开销
    3、但假如要计算 2 ~ 106有多少个质数时,只使用素数判断效率很低(106 - 218ms),其额外判断了大量无用的数据,所以需要效率更高的筛法

阅读更多
C++数学质数筛

学习构建和使用二叉查找树,再进一步学习AVL树。了解哈夫曼树和哈夫曼编码

二叉查找树


  • 二叉查找树

    1、二叉查找树:又称二叉排序树/二叉搜索树,其任意节点与其左右子节点大小关系都有左 < 中 < 右,其中序遍历会得到一个递增序列,常用于元素的排序和查找,如下图
    2、查找元素二叉查找树是以二分查找为原型的数据结构,因此其查找操作时间复杂度为 O(log2n)。其查找元素的动作为从根节点起,如果要查找的值比根小,则继续查找左子树,否则查找右子树
    3、插入元素:与查找元素类似。如在下面的二叉查找树插入新元素 12,应放在元素 11右子节点处(从根节点依次比较 12 与 10、13、11 的关系)
    4、删除元素:实质是保持中序遍历(即递增序列)的顺序不变从中删除节点,重点在于如何填补空缺。如下图展示了三棵二叉树,分别代表三种删除情景情景一要删除节点 6(只有一边子树),可以直接将子树整体上移情景二要删除节点 7(两边都有子树),可以将其中序遍历前/后一个节点(即节点 6 或 8)填充到此处;情景三要删除节点 10,如果选择填充节点 14(其仍有子树),则还应递归处理 14 的空缺(按照前两种情景选择方法处理)

阅读更多
C++二叉查找树AVL树哈夫曼树二叉树

学习树这种数据结构,学习二叉树的遍历、构造等实现,学习线索二叉树

树的知识


  • 认识树结构

    1、:指有层次关系N 个节点有限集合(如下图);对于空树N = 0;对于非空树,有且仅有一个根。除外,可分为多个互不相交有限集合,称为子树
    2、节点:每个数据就是一个节点节点可分为分为根节点分支节点叶子结点。在两个节点的关系上分为前驱(父节点)和后继(子节点)
    3、在树中用来表明两个节点之间的层次关系(父子关系);高度指的是深度(层次),树的高度指的是整个树最深的层次数,如下图E 的高度为 3树的高度为 4指的是边的个数(子节点的个数),树的度指的是整个树各节点度的最大值,如下图A 的度为 3C 的度为 1树的度为 3

阅读更多
C++二叉树

运用乘法逆元解决模意义下的除法问题,将其转换为模意义下的乘法,了解多种求乘法逆元的思路

乘法逆元介绍


  • 引入

    1、对于模意义下的运算,例如我们知道(a + b) % p = (a % p) + (b % p)或者(a * b) % p = (a % p) * (b % p)成立,但是对于模意义下的除法不成立(a / b) % p != (a % p) / (b % p)。不过,我们可以把模意义的除法转换成模意义的乘法
    2、举例探讨:(7 / 2) % 5 中,把除法转成乘法写作 (7 * (1/2)) % 5,再将分数写成幂的形式写作 (7 * 2-1) % 5
    3、由于取模运算结果一定是整数,所以 (7 * 2-1) % 5 结果一定是整数,即说明必定能把 2-1 这个分数转换成某个整数。所以,问题的关键就在于能转换成哪个整数
    4、这时便需要引入乘法逆元的概念了,它可以辅助我们完成模意义的除法模意义的乘法转换

阅读更多
C++数学乘法逆元

学习求 gcd 和 lcm 的方法,学习拓展欧几里得算法

gcd 最大公约数


  • 欧几里得算法

    1、求两个数的最大公约数,除了分解质因数法,我们通常使用欧几里得算法(即辗转相除法),其思路如下
    2、求m,n 的最大公约数,就计算 m / n,然后m = nn = m % n,继续循环计算。直到n = 0时停止,这时的m就是最大公约数;或者提前一步,到m % n == 0(结果余数为 0)时停止,这时的n就是最大公约数(推荐后者,在写拓展欧几里得算法时更方便)
    3、gcd 的性质gcd(a, b) = gcd(a, k*a+b)gcd(k*a, k*b) = k * gcd(a, b)a / gcd(a, b)b / gcd(a, b)互素多个整数最大公约数gcd(a, b, c) = gcd(gcd(a, b), c)

阅读更多
C++gcdlcm数学

使用快速幂(二进制取幂)快速计算大指数幂的结果,了解幂取模、矩阵快速幂

快速幂


  • 引入

    1、假设我们要计算 an 的值,最朴素的做法是循环 n 次,每次在结果上乘以 a。显然这种做法的时间复杂度为 O(n),但当n 非常大时这种做法的效率仍然较低,而快速幂可以解决这个问题
    2、我们先从一个特例引入:当n 是 2 的幂时,例如求 a64 的值,我们可以按照下表的方式计算。每次将上一次循环得到的结果自乘,就得到了指数下一级 2 的幂的结果,以此类推,便很快就能得到指数所求 2 的幂的结果
    3、而对于任意的 n,例如求 a105 的值,我们可以将指数 n 拆分成多个 2 的幂之和,例如 a105 = a1 + 8 + 32 + 64 = a1 * a8 * a32 * a64,而单独计算这些幂便十分简单了,因此最终只需要将需要的 2 的幂的结果相乘即可
    4、因此,快速幂又称二进制取幂(平方法),其英文为Binary Exponentiation,其时间复杂度仅需 O(log n) 对数级

阅读更多
C++数学快速幂