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

"C C++ 算法实例大全包含数论算法和图论算法的实现。数论算法部分涵盖求最大公约数、最小公倍数以及素数判断方法。图论算法部分提及了最小生成树的Prim算法。" 在C/C++编程中，算法是解决问题的关键工具，本实例大全提供了数论和图论两个领域的算法实例。首先，数论算法包括： 1. 求两数的最大公约数（Greatest Common Divisor, GCD）：通过欧几里得算法实现，递归地计算较小数与两数模运算结果的GCD，直到模运算结果为0，此时较大数即为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）：首先确保a大于或等于b，然后通过循环不断累加a，直至lcm能被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. 素数判断：提供了两种方法。A. 对于小范围内的数，通过遍历2到平方根(n)之间的所有数，若n能被其中任意数整除，则不是质数。B. 大范围内的素数判断，可以先构建一个50000以内的素数表，然后根据该表判断任意数是否为素数。 ```cpp function prime(n: integer): Boolean; var I: integer; begin for I := 2 to trunc(sqrt(n)) do if n mod I = 0 then begin prime := false; exit; end; prime := true; end; // 构建素数表 procedure getprime; var i, j: longint; p: array[1..50000] of boolean; begin // ...填充代码... end; function prime(x: longint): integer; var i: integer; begin prime := false; // ...查询素数表代码... end; ``` 接着，图论算法部分提到了最小生成树的Prim算法，这是一种用于寻找加权无向图的最小生成树的方法，其基本思想是从一个顶点开始，逐步加入边，使得每次加入的边连接的是当前生成树与图中未包含的顶点，并且这条边的权重最小。 ```cpp procedure prim(v0: integer); var lowcost, closest: array[1..maxn]ofinteger; i, j, k: integer; // ...填充Prim算法实现... end; ``` 这些算法实例涵盖了基础的数学计算和图论问题解决，对于学习和理解C/C++算法有着很好的实践价值。通过这些实例，开发者可以加深对算法原理的理解，并能将其应用到实际项目中。