经典算法普及——基础篇

kon3155

（本帖部分题目及解答来自信息学竞赛网站） 1.排序算法 选择排序 快速排序 2.高精度运算 存储方法 加法运算 减法运算 乘法运算 扩大进制数 习题与练习 3.搜索算法 枚举算法 深度优先搜索 广度优先搜索 8数码问题 n皇后问题 4.搜索算法习题 枚举法习题 聪明的打字员 量水问题 染色问题 跳马问题 算24点 5.图论算法 最小生成树算法(Prim算法) 单源最短路径算法(Dijkstra算法) 任意结点最短路径算法(Floyd算法) 求有向带权图的所有环 Bellman-Ford算法 计算图的连通性 计算最佳连通分支 计算拓扑序列 6.图论算法习题 网络建设问题 最短变换问题 挖地雷 乌托邦城市 乌托邦交通中心 7.动态规划 最短路径问题 动态规划概念 骑士游历问题 最长递增子序列 合唱队形 石子合并问题 能量项链 0/1背包问题 开心的金明 金明的预算方案 加分二叉树 字串编辑距离 花瓶插花 凸多边形三角划分 快餐店

kon3155

选择排序是一种简单而有效的排序算法，在问题规模不是很大的情况下就大胆的使用这个算法吧。 算法主过程如下：

1. PROCEDURE selectsort;
2. VAR
3. i,j,k,temp:integer;
4. BEGIN
5. FOR i:=1 to n-1 DO
6. BEGIN
7. k:=i;
8. FOR j:=i+1 to n DO
9. IF a[k]>a[j]
10. THEN k:=j;
11. IF k<>i
12. THEN BEGIN
13. temp:=a[k];
14. a[k]:=a[i];
15. a[i]:=temp;
16. END;
17. END;
18. END;

复制代码

[ 本帖最后由 kon3155 于 2009-2-25 10:56 编辑 ]

kon3155

快速排序是基于分治排序算法，在数据规模很大的情况下一般使用该算法。 算法主过程如下：

1. procedure qsort(L,R:longint);
2. var
3. i,j,mid,temp:longint;
4. begin
5. i:=L;
6. j:=R;
7. mid:=a[L+random(R-L+1)]; {随机选择一个数组中的数作为对比数}
8. repeat
9. while a[i]< mid do inc(i); {在左半部分寻找比中间数大的数}
10. while mid< a[j] do dec(j); {在右半部分寻找比中间数小的数}
11. if i< =j then {若找到一组与排序目标不一致的数对则交换它们}
12. begin
13. temp:=a[i];
14. a[i]):=a[j];
15. a[j]:=temp;
16. inc(i);dec(j); {继续找}
17. end;
18. until i >j;
19. if L< j then qsort(L,j); {若未到两个数的边界，则递归搜索左右区间}
20. if i< R then qsort(i,R);
21. end;

复制代码

注意:主程序中必须加randomize语句。

kon3155

由于待处理的数据超过了任何一种数据类型所能容纳的范围，因此必须采用数串形式输入，并将其转化为数组。该数组的每一个元素对应一个十进制数，由其下标顺序指明位序号。由于高精度运算可能使得数据长度发生变化，因此除要用整数数组存储数据外，还需要一个整数变量纪录整数数组的元素个数，即数据的实际长度。

1. type
2. numtype=array[1..255] of byte;
3. var
4. a:numtype;
5. la:byte;
6. s:string;
7. begin
8. readln(s);
9. la:=length(s);
10. for i:=1 to la do
11. a[la-i+1]:=ord(s[i])-ord('0');
12. end.

复制代码

kon3155

高精度加法运算 首先，确定a和b中的最大位数x，然后依照由低位至高位的顺序进行加法运算。在每一次运算中，a当前位加b当前位的和除以10，其整商即为进位，其余数即为和的当前位。在进行了x位的加法后，若最高位有进位(a[x+1]<>0)，则a的长度为x+1。 以下只列出关键程序：

1. type
2. numtype=array[1..255] of byte;
3. var
4. a,b:numtype;
5. la,lb:byte;
6. procedure plus(var a:numtype;var la:byte;b:numtype); {利用过程实现}
7. var
8. i,x:byte;
9. begin
10. if la>=lb
11. then x:=la
12. else x:=lb;
13. for i:=1 to x do
14. begin
15. a[i]:=a[i]+b[i];
16. a[i+1]:=a[i+1]+a[i] div 10;
17. a[i]:=a[i] mod 10;
18. end;
19. while a[x+1]<>0 do
20. x:=x+1;
21. la:=x; {最高位若有进位，则长度增加}
22. end;

复制代码

kon3155

高精度减法运算（a>b） 依照由低位至高位的顺序进行减法运算。在每一次位运算中，若出现不够减的情况，则向高位借位。在进行了la位的减法后，若最高位为零，则a的长度减1。 以下只列出关键程序：

1. type
2. numtype=array[1..255] of byte;
3. var
4. a,b:numtype;
5. la,lb:byte;
6. procedure minus(var a:numtype;var la:byte;b:numtype);
7. var
8. i:byte;
9. begin
10. for i:=1 to la do
11. begin
12. if a[i]<b[i]
13. then begin
14. dec(a[i+1]);
15. a[i]:=a[i]+10;
16. end;
17. a[i]:=a[i]-b[i];
18. end;
19. while (a[la]=0) and (la>1) do
20. dec(la);
21. end;

复制代码

kon3155

高精度乘法运算 按照乘法规则，从a的第1位开始逐位与c（c为字节型）相乘。在第i位乘法运算中，a的i位与c的乘积必须加上i-1位的进位，然后规整积的i-1位。 以下只列出关键程序：

1. type
2. numtype=array[1..255] of word;
3. var
4. a,b:numtype;
5. la,lb:byte;
6. procedure multiply(var a:numtype;c:byte);
7. var
8. i:byte;
9. begin
10. a[1]:=a[1]*c;
11. for i:=2 to la do
12. begin
13. a[i]:=a[i]*c;
14. a[i]:=a[i]+a[i-1] div 10;
15. a[i-1]:=a[i-1] mod 10;
16. end;
17. while a[la]>=10 do
18. begin
19. inc(la);
20. a[la]:=a[la-1] div 10;
21. a[la-1]:=a[la-1] mod 10;
22. end;
23. end;

复制代码

kon3155

扩大进制数改善高精度运算效率 用整数数组每一个元素表示一个十进制整数的方法存在的缺点是：如果十进制的位数很多，则对应的数组的长度会很长，并增加了高精度计算的时间。 如果用一个元素记录2位数字、3位数字或更多位数字，则数组的长度可以明显缩小，但是还要考虑数的取值范围问题，必须保证程序运行过程中不越界。在权衡了两方面的情况后得出：用一个longint记录4位数字是最佳的方案。那么这个数组就相当于一个10000进制的数，其中每一个元素都是10000进制下的一位数。

2. 一、数据类型定义：type
3. numtype=array[1..10000] of longint; {可以存储40000位十进制数}
4. var
5. a,n:numtype;
6. la,ln:byte;
7. s:ansistring; {任意长度的字符串类型}

复制代码

二、整数数组的建立和输出

1. readln(s);
2. k:=length(s);
3. for i:=1 to k do
4. begin
5. j:=(k-i+4) div 4;
6. n[j]:=n[j]*10+ord(s[i])-48;
7. end;
8. ln:=(k+3) div 4;
10. 当得出最后结果n后，必须按照次高位到最低位的顺序，将每一位元素由10000进制数转换成十进制数，即必须保证每个元素对应4位十进制数。例如n[i]=0015(0<=i<=ln-2)，对应的十进制数不能为15，否则会导致错误结果。可以按照如下方法输出n对应的十进制数：[code]write(n[ln]);
11. for i:=ln-1 downto 1 do
12. write(n[i] div 1000,(n[i] div 100) mod 10,(n[i] div 10) mod 10,n[i] mod 10);
14. 三、基本运算
15. 两个10000进制整数的加法和减法与前面的十进制运算方法类似，只是进制变成了10000进制。
16. 1、整数数组减1(n:=n-1,n为整数数组)
17. 从n[1]出发寻找第一个非零的元素，由于接受了低位的借位，因此减1，其后缀全为9999。如果最高位为0，则n的长度减1。
18. j:=1;
19. while (n[j]=0) do inc(j); {寻找第一个非零的元素}
20. dec(n[j]); {该位接受低位的借位，因此减1}
21. for i:=1 to j-1 do
22. n[i]:=9999; {其后缀全为9999}
23. if (j=ln) and (n[j]=0) {如果最高位为0，则n的长度减1}
24. then dec(ln);
26. 2、整数数组除以整数(a:=a div i,a为整数数组，i为整数)
27. 按照从高位到低位的顺序，逐位相除，把余数乘进制后加到下一位继续相除。如果最高位为0，则a的长度减1。
28. l:=0;
29. for j:=la downto 1 do
30. begin
31. inc(a[j],l*10000);
32. l:=a[j] mod i;
33. a[j]:=a[j] div i;
34. end;
35. while a[la]=0 do dec(la);3、两个整数数组相乘（a:=a*n，a和n为整数数组）
36. 按照从高位到低位的顺序，将数组a的每一个元素与n相乘。[code]procedure multiply(a,b:numtype;la,lb:longint;var s:numtype;var ls:longint);
37. var
38. i,j:longint;
39. begin
40. for i:=1 to la do
41. for j:=1 to lb do
42. s[i+j-1]:=s[i+j-1]+a[i]*b[j];
43. for i:=1 to la+lb-1 do
44. begin
45. s[i+1]:=s[i+1]+s[i] div 10000;
46. s[i]:=s[i] mod 10000;
47. end;
48. if s[la+lb]=0
49. then ls:=la+lb-1
50. else ls:=la+lb;
51. end;

复制代码

[ 本帖最后由 kon3155 于 2009-2-25 13:11 编辑 ]

kon3155

习题与练习 一、用高精度计算出s=1!+2!+3!+...+100!。 参考答案 二、两个高精度数相乘。 参考答案 三、2k进制数（digital.pas）(NIOP2006第四题) 【问题描述】设r是个2k 进制数，并满足以下条件： （1）r至少是个2位的2k 进制数。 （2）作为2k 进制数，除最后一位外，r的每一位严格小于它右边相邻的那一位。 （3）将r转换为2进制数q后，则q的总位数不超过w。 在这里，正整数k（1≤k≤9）和w（k 这里还要比较d与的2k-1大小，必须保证d<=2k-1。 最后考虑首位的情况，显然首位的最大二进制位数是w mod k，则最大值m=2w mod k - 1，则首位不大于m，总位数是d+1位的升序排列数应是： 这里也要比较d与的2k-1大小，必须保证d<=2k-1-m。 两者相加即所求，因为最终的运算结果可能会很大，所以必须使用高精度运算。 【参考程序】 【NIOP满分程序】 [ 本帖最后由 kon3155 于 2009-2-25 11:27 编辑 ]

kon3155

枚举法(通常也称穷举法)是指在一个有穷的可能的解的集合中，枚举出集合中的每一个元素，用题目给定的约束条件去判断其是否符合条件，若满足条件，则该元素即为整个问题的解；否则就不是问题的解。 【枚举算法解题必须满足下列条件】 ⑴ 可预先确定解元素的个数n，且问题的规模不是很大； ⑵ 对于每个解变量A1，A2，…An的可能值必须为一个连续的值域。 【枚举算法实现】 通常使用嵌套的FOR结构循环语句枚举每个变量的取值，在最里层的循环中判断是否满足给定的条件，若满足则输出一个解。 【枚举算法优化】 ⑴ 减少枚举的变量。 在使用枚举法之前，先考虑一下解元素之间的关联，将那些能由已枚举解元素推算出来的变量直接用计算表达式代替。 ⑵ 减少枚举变量的值域。 通过各枚举变量间的数学关系定义解元素的值域，在保证不遗漏的情况下越小越好。 ⑶ 分解约束条件。 将拆分的约束条件嵌套在相应的循环体间，即尽可能根据约束条件减少变量个数和缩小值域。