c/c++算法大全pdf

根据提供的文档内容，我们可以归纳总结出以下几个重要的C/C++编程语言中的算法知识点： ### 数论算法 #### 1. 求两数的最大公约数 最大公约数（Greatest Common Divisor, GCD）是指能同时整除两个或多个整数的最大正整数。 **实现代码**: ```pascal function gcd(a, b: integer): integer; begin if b = 0 then gcd := a else gcd := gcd(b, a mod b); end; ``` 这段代码使用了递归的方式计算两个整数`a`和`b`的最大公约数。其基本思路是利用辗转相除法，即不断用较小的数去除较大的数，直到余数为0为止，此时较小的数即为两数的最大公约数。 #### 2. 求两数的最小公倍数 最小公倍数（Least Common Multiple, LCM）是指能被几个给定的数共同整除的最小正整数。 **实现代码**: ```pascal 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; ``` 该函数首先通过交换确保`a`大于等于`b`，然后从`a`开始逐次增加`a`的值，直到找到能同时被`a`和`b`整除的第一个数，即为最小公倍数。 #### 3. 素数的求法 **A. 小范围内判断一个数是否为质数**: ```pascal 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; ``` 此方法通过遍历从2到`sqrt(n)`之间的所有整数来判断`n`是否能被整除。如果存在任何整数可以整除`n`，那么`n`不是素数；否则`n`是素数。 **B. 判断longint范围内的数是否为素数**: ```pascal procedure getPrime; var i, j: longint; p: array[1..50000] of boolean; begin fillchar(p, sizeof(p), true); p[1] := false; i := 2; while i < 50000 do begin if p[i] then begin j := i * 2; while j < 50000 do begin p[j] := false; inc(j, i); end; end; inc(i); end; l := 0; for i := 1 to 50000 do if p[i] then begin inc(l); pr[l] := i; end; end; function prime(x: longint): boolean; var i: integer; begin prime := false; for i := 1 to l do if pr[i] >= x then break else if x mod pr[i] = 0 then exit; prime := true; end; ``` 该段代码实现了埃拉托斯特尼筛法（Sieve of Eratosthenes），通过这种方法可以找出指定范围内所有的素数。`getPrime`函数用于生成50000以内的素数列表，而`prime`函数则利用该列表来快速判断一个数是否为素数。 ### 图论算法 #### 1. 最小生成树 **A. Prim算法**: ```pascal procedure prim(v0: integer); var lowcost, closest: array[1..maxn] of integer; i, j, k, min: integer; begin for i := 1 to n do begin lowcost[i] := cost[v0, i]; closest[i] := v0; end; for i := 1 to n - 1 do begin min := maxlongint; for j := 1 to n do if (lowcost[j] < min) and (lowcost[j] <> 0) then begin min := lowcost[j]; k := j; end; lowcost[k] := 0; for j := 1 to n do if cost[k, j] < lowcost[j] then begin lowcost[j] := cost[k, j]; closest[j] := k; end; end; end; ``` Prim算法是一种贪婪算法，它通过不断地选择距离当前生成树最近的顶点加入生成树，从而构建出一棵最小生成树。初始时选择一个顶点作为起始点，并标记每个顶点到起始点的距离。在每次循环中，选择距离当前生成树最近的顶点加入生成树，并更新其他顶点的距离。 **B. Kruskal算法**: ```pascal function find(v: integer): integer; var i: integer; begin i := 1; while (i <= n) and (not v in vset[i]) do inc(i); if i <= n then find := i else find := 0; end; procedure kruskal; var tot, i, j: integer; begin for i := 1 to n do vset[i] := [i]; p := n - 1; q := 1; tot := 0; sort; while p > 0 do begin i := find(e[q].v1); j := find(e[q].v2); if i <> j then begin inc(tot, e[q].len); vset[i] := vset[i] + vset[j]; vset[j] := []; dec(p); end; inc(q); end; writeln(tot); end; ``` Kruskal算法同样是一种基于贪婪思想的算法，它的核心思想是按照边的权重从小到大排序，然后依次考虑每条边是否加入最小生成树中。对于每条边，如果这条边的两端不属于同一个集合，则将这条边加入最小生成树中，并将这两个集合合并成一个新的集合。 #### 2. 最短路径 **A. 标号法求解单源点最短路径**: 这部分代码缺失，但是可以简单介绍下标号法的基本原理。标号法通常用来解决单源点最短路径问题，其主要思想是从起点出发，通过逐步扩展搜索范围，为每一个节点打上一个标号，这个标号表示从起点到该节点的最短路径长度。随着搜索过程的进行，如果发现从起点到某个节点的更短路径，则更新该节点的标号。当所有能够到达的节点都被正确标号后，搜索结束，此时每个节点的标号即为从起点到该节点的最短路径长度。 以上是对给定文档中的算法知识点的详细解析，这些算法是C/C++程序设计中非常基础且重要的部分，在实际编程中有着广泛的应用。