C/C++算法实现：数论与图论算法详解

“算法大全(C\C++)” 在“算法大全”中，我们主要探讨了两个关键领域的算法：数论算法和图论算法。数论算法主要用于处理与数字性质相关的复杂问题，而图论算法则关注于网络和结构之间的关系。以下是这两个领域的详细介绍： 一、数论算法 1. 最大公约数(GCD)：在C或C++中，我们可以使用欧几里得算法来计算两个整数的最大公约数。例如，给定的代码段展示了如何实现GCD函数，通过递归方式不断将较大的数除以较小的数，直到余数为0，此时较小的数就是最大公约数。 ```cpp // 欧几里得算法计算最大公约数 int gcd(int a, int b) { if (b == 0) return a; else return gcd(b, a % b); } ``` 2. 最小公倍数(LCM)：最小公倍数是两个或多个整数共有的倍数中的最小一个。在C++中，可以通过最大公约数来计算最小公倍数，即LCM = |a * b| / GCD(a, b)。代码示例中，首先确保a大于等于b，然后使用循环找到满足条件的最小公倍数。 ```cpp // 计算最小公倍数 int lcm(int a, int b) { if (a < b) std::swap(a, b); int lcm = a; while (lcm % b != 0) { lcm += a; } return lcm; } ``` 3. 判断素数：素数是指大于1且除了1和它自身以外没有其他正因数的自然数。提供的代码中，有两个函数用于判断是否为素数。`prime()`函数检查一个整数是否为素数，通过遍历从2到该数平方根的所有整数来验证。`getprime()`函数则生成一个指定范围内的所有素数列表。 ```cpp // 判断一个整数是否为素数 bool prime(int n) { for (int i = 2; i <= std::sqrt(n); ++i) { if (n % i == 0) { return false; } } return true; } // 生成前50000个素数 void getPrime() { // ... 省略填充数组和循环逻辑 ... } ``` 二、图论算法 4. 最小生成树（Prim算法）：Prim算法是一种用于寻找加权无向图的最小生成树的算法。在这个例子中，`prim()`函数用于计算给定起始节点v0的最小生成树。它维护了一个cost数组来存储当前节点到已连接节点的最低成本，并使用closest数组记录最近的邻居。算法通过迭代逐步构建最小生成树，每次选择与当前树连接的边中成本最低的一条。 ```cpp // Prim算法求最小生成树 void prim(int v0) { // ... 初始化lowcost和closest数组 ... for (int k = 1; k < n; ++k) { min = INT_MAX; for (i = 1; i <= n; ++i) { if (lowcost[i] < min && closest[i] != 0) { min = lowcost[i]; j = i; } } // 将节点j添加到树中 // ... 更新lowcost和closest数组 ... } } ``` 这些算法是计算机科学中基础且重要的组成部分，对于解决各种实际问题，如数据压缩、密码学、网络路由等都有着广泛的应用。掌握并理解这些算法能够提升编程能力和解决问题的效率。