C/C++算法集锦：数论与图论

"C/C++算法大全PDF是一个包含多种常用算法的资料，主要涉及数论算法和图论算法。这份PDF旨在分享经典算法，帮助学习者掌握C++编程中的核心算法知识。" 在C/C++编程中，算法是解决问题的关键，它们能够提高代码效率和程序性能。以下是对标题和描述中提及的部分内容的详细解释： ### 1. 数论算法 #### (1) 最大公约数(Greatest Common Divisor, GCD) `gcd(a, b)` 函数采用欧几里得算法计算两个整数 `a` 和 `b` 的最大公约数。如果 `b` 为0，返回 `a`；否则，递归调用 `gcd(b, a mod b)` 直到 `b` 为0。 #### (2) 最小公倍数(Lowest Common Multiple, LCM) `lcm(a, b)` 函数首先检查 `a` 是否小于 `b`，如果小于则交换两者。然后，初始化 `lcm` 为 `a`，并使用一个循环来不断累加 `a`，直到 `lcm` 能够被 `b` 整除，此时的 `lcm` 就是两者的最小公倍数。 #### (3) 素数的求法 - **小范围判断**：对于较小的整数 `n`，可以使用循环从2遍历到 `sqrt(n)` 来判断是否为素数。如果 `n` 能被任何2到 `sqrt(n)` 之间的数整除，则不是素数。 - **大范围判断**：对于较大的整数，如 `longint` 范围内的数，可以预先计算一个素数表，然后通过查表来快速判断。`getprime` 函数创建了一个包含50000个素数的数组，并使用了Sieve of Eratosthenes算法，将所有非素数标记为 `false`。 ### 2. 图论算法 #### (1) 最小生成树 最小生成树算法用于找到加权无向图的边，使得这些边连接所有顶点且总权重最小。这里提到了Prim算法： - `prim(v0)` 函数从指定的顶点 `v0` 开始，维护一个低代价矩阵 `lowcost` 和一个最近邻节点数组 `closest`。初始时，每个顶点与自身相连，`lowcost[v] = 0` 表示顶点 `v` 已加入最小生成树，其他值表示从 `v0` 到其他顶点的边的权重。在每次迭代中，找到未加入树的顶点中与树中顶点连接的边的最小权重，将该顶点加入树中。 以上是部分C/C++算法的介绍，实际的PDF可能还包括排序算法、搜索算法、动态规划、字符串处理等更多内容。学习这些算法能够提升编程能力，解决复杂问题，并有助于理解和应用数据结构。