C++算法实践：数论与图论经典实例解析

"这篇资源是关于C++编程中的一些算法实例，包括数论算法和图论算法，提供了具体的代码实现。实例涵盖了求最大公约数、最小公倍数、判断素数的方法，以及Prim算法用于寻找图的最小生成树。这些实例具有较高的学习和参考价值，适合想要提升C++算法能力的读者。" 详细内容: 1. 数论算法 - 最大公约数 (GCD)：在C++中，可以使用递归的方式来实现欧几里得算法求两个整数的最大公约数。如代码所示，当`b`等于0时，返回`a`作为结果；否则，继续求`b`和`a mod b`的GCD。 ```cpp int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } ``` - 最小公倍数 (LCM)：为了找到两个整数`a`和`b`的最小公倍数，可以首先判断`a`是否小于`b`，然后使用`a`不断加上自身的值，直到能被`b`整除。最后的`lcm`值即为最小公倍数。 ```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; } ``` 2. 素数判断 - 判断小范围内的素数：对于较小的整数`n`，可以通过遍历从2到`sqrt(n)`来检查是否有因子，如果存在则不是素数，否则是素数。 ```cpp bool isPrime(int n) { for (int i = 2; i * i <= n; ++i) { if (n % i == 0) return false; } return n > 1; } ``` - 判断大范围素数：对于较大的整数范围，可以使用筛法（例如埃拉托斯特尼筛法）预先计算并存储一定范围内的素数，然后通过查找这个列表来判断给定数是否为素数。 3. 图论算法 - 最小生成树 (Minimum Spanning Tree, MST) 在图论中，Prim算法用于找出带权重无向图的最小生成树。该算法从一个节点开始，每次添加一条连接到当前树中的节点与未加入树的节点之间的边，使得这条边的权重最小。以下是一个简单的Prim算法实现： ```cpp void prim(int v0) { vector<pair<int, int>> edges; // 初始化距离数组 vector<int> dist(graph.size(), INT_MAX); dist[v0] = 0; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; pq.push({0, v0}); while (!pq.empty()) { int u = pq.top().second; pq.pop(); for (auto &e : graph[u]) { int v = e.first, weight = e.second; if (dist[v] > weight) { dist[v] = weight; pq.push({dist[v], v}); } } } } ``` 这里假设`graph`是一个邻接矩阵表示的图，`edges`用于存储找到的最小生成树的边。 这些实例展示了C++在算法实现方面的灵活性和效率，对于学习和实践C++算法非常有帮助。理解并掌握这些算法可以提高解决实际问题的能力，尤其在数据结构和算法相关的编程竞赛或软件开发中。