C++算法详解：数论与图论算法

"C++算法大全和算法讲解" 这篇内容涵盖了C++中的各种算法，包括数论算法和图论算法。下面将对这些算法进行详细的解释和分析。 ### 数论算法 #### 1. 最大公约数 (Greatest Common Divisor, GCD) 最大公约数是两个或多个整数共有约数中最大的一个。提供的代码使用了欧几里得算法来计算GCD。算法的基本思想是：对于非负整数a、b，若存在整数c使得a = b × c，则GCD(a, b) = GCD(b, a mod b)，当b为0时，a即为GCD。 ```cpp function gcd(a, b: integer): integer; begin if b = 0 then gcd := a else gcd := gcd(b, a mod b); end; ``` #### 2. 最小公倍数 (Least Common Multiple, LCM) 最小公倍数是两个或多个整数共有的倍数中最小的一个。在C++中，可以通过GCD来计算LCM，公式为：LCM(a, b) = |a * b| / GCD(a, b)。但在这个例子中，作者使用了一个直接的方法，通过循环找到满足条件的最小值。 ```cpp function lcm(a, b: integer): integer; begin if a < b then swap(a, b); lcm := a; while lcm mod b > 0 do inc(lcm, a); end; ``` #### 3. 素数判断 素数是大于1且只有1和其本身两个正因数的自然数。提供了两种方法： - A. 对于小范围内的数，可以通过遍历从2到平方根(n)的所有整数，检查n是否能被这些数整除。 - B. 大范围内的素数判断通常采用筛法，如埃拉托斯特尼筛法。这个例子中，先初始化一个数组p，标记所有数为素数，然后从2开始，将所有2的倍数标记为非素数，接着检查下一个未标记的数，重复此过程直到所有50000以内的素数都被找出。 ### 图论算法 #### 1. 最小生成树 最小生成树是图中边的子集，它连接了图中的所有顶点，且总权重最小。这里提到了Prim算法，用于寻找加权无向图的最小生成树。Prim算法的基本思想是从一个顶点开始，逐步添加边，每次添加一条使得树的总权重增加最少的边。 ```cpp procedure prim(v0: integer); // ... ``` 由于这部分代码不完整，完整的Prim算法会涉及到一个`lowcost`数组记录每个顶点到当前生成树的最小代价，`closest`数组记录最近邻接顶点，以及一个`b`表示当前生成树的边数。 #### 以上只是部分算法的概述，实际的C++算法大全会涵盖更多主题，如排序算法（快速排序、归并排序等）、搜索算法（深度优先搜索、广度优先搜索）、动态规划、字符串处理、数据结构（链表、树、图、堆、队列、栈等）等。学习和理解这些算法对于提升C++编程能力至关重要，特别是在解决复杂问题和优化程序性能时。