备战NOIP不得不看的算法.

在备战NOIP（全国青少年信息学奥林匹克联赛）的过程中，掌握一系列关键算法是至关重要的。根据提供的部分内容，我们将深入探讨数论算法与图论算法中的一些核心概念与实践方法。 ### 数论算法 #### 1. 求两数的最大公约数（GCD） 最大公约数是指两个或多个整数共有约数中最大的一个。在NOIP竞赛中，掌握高效的求解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（a > b）的最大公约数等于b和a mod b的最大公约数。 #### 2. 求两数的最小公倍数（LCM） 最小公倍数则是指能同时被几个整数整除的最小正整数。计算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; ``` 然而，更高效的方法是利用已知的GCD关系式：`LCM(a, b) * GCD(a, b) = a * b`。 #### 3. 素数的求法 素数在NOIP中同样占据重要地位，特别是当涉及到加密、密码学或某些数学问题时。以下是两种常用的判断素数的方法： - **小范围内判断一个数是否为质数**：通过遍历从2到√n的所有整数来检查是否存在因子。 ```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; ``` - **判断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; ``` ### 图论算法 图论算法在解决网络、路径优化等问题中极为重要，NOIP竞赛中常见的图论问题包括最小生成树、最短路径等。 #### 最小生成树 - **Prim算法**：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; ``` - **Kruskal算法**：另一种著名的最小生成树算法，Kruskal算法也是基于贪心策略。它首先将所有的边按照权重从小到大排序，然后依次添加不会形成环的边，直到所有顶点都被包含在一个连通分量中。 通过以上详尽的介绍，我们可以看到，在备战NOIP过程中，熟练掌握这些算法不仅是理论上的要求，更是实际解决问题的关键。无论是数论算法中的GCD、LCM和素数判定，还是图论算法中的Prim和Kruskal算法，都是NOIP参赛者必须掌握的核心技能。