C C++算法实例

内容包括数论算法、图论算法，数据结构相关算法、排序算法，贪心算法、进制转换、数的遍历、高精度计算、背包问题等十五大块的内容 涉及的算法包括n皇后，Hanoi塔、折半查找、7种排序算法、各种背包问题、最短路径、最小生成树、Dijkstra 算法等各种经典算法实例。 ### 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; ``` **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; ``` **3. 素数的求法** 素数是指仅能被1和自身整除的大于1的自然数。求素数的方法有多种，包括试除法、埃拉托斯特尼筛法等。 - **试除法**： ```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; ``` - **埃拉托斯特尼筛法**： ```pascal procedure get_prime; 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; ``` #### 图论算法 图论算法涉及图的表示以及在图上执行的各种操作，如最小生成树、最短路径等。 **1. 最小生成树** 最小生成树（Minimum Spanning Tree, MST）是指在一个加权无向图中选取若干边，使选取的边可以连通图中的所有顶点，并且这些边的权重之和最小。常用的最小生成树算法有两种：Prim算法和Kruskal算法。 - **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算法按照边的权重从小到大排序，依次考虑每条边是否加入生成树，如果加入这条边不会形成环，则加入；否则舍弃。 ```pascal function find(v: integer): integer; var i: integer; begin i := 1; while (i <= n) and (not vin 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; ``` **2. 最短路径** 最短路径问题是在图中找到两个顶点之间的最短路径。常用的算法包括标号法、Dijkstra算法等。 - **标号法**（Bellman-Ford算法） 标号法是一种适用于带负权边但不含负权环的图的最短路径算法。 ```pascal var a: array[1..maxn, 1..maxn] of integer; d: array[1..maxn] of integer; n, m, s: integer; i, j: integer; begin // 初始化 for i := 1 to n do d[i] := infinity; d[s] := 0; // 迭代 for i := 1 to n - 1 do for j := 1 to m do if d[e[j].v1] + e[j].w < d[e[j].v2] then d[e[j].v2] := d[e[j].v1] + e[j].w; // 检查是否存在负权环 for j := 1 to m do if d[e[j].v1] + e[j].w < d[e[j].v2] then writeln('存在负权环'); // 输出结果 for i := 1 to n do writeln('从', s, '到', i, '的最短距离是:', d[i]); end; ``` 以上介绍了C/C++中几种常见的算法实例，包括数论算法、图论算法等。这些算法在解决实际问题时非常有用，了解并掌握它们对于编程学习来说非常重要。