经典算法普及——基础篇
基础但很经典的算法集中介绍（本帖部分题目及解答来自信息学竞赛网站）1.排序算法
选择排序
快速排序
2.高精度运算
存储方法
加法运算
减法运算
乘法运算
扩大进制数
习题与练习
3.搜索算法
枚举算法
深度优先搜索
广度优先搜索
8数码问题
n皇后问题
4.搜索算法习题
枚举法习题
聪明的打字员
量水问题
染色问题
跳马问题
算24点
5.图论算法
最小生成树算法(Prim算法)
单源最短路径算法(Dijkstra算法)
任意结点最短路径算法(Floyd算法)
求有向带权图的所有环
Bellman-Ford算法
计算图的连通性
计算最佳连通分支
计算拓扑序列
6.图论算法习题
网络建设问题
最短变换问题
挖地雷
乌托邦城市
乌托邦交通中心
7.动态规划
最短路径问题
动态规划概念
骑士游历问题
最长递增子序列
合唱队形
石子合并问题
能量项链
0/1背包问题
开心的金明
金明的预算方案
加分二叉树
字串编辑距离
花瓶插花
凸多边形三角划分
快餐店 选择排序是一种简单而有效的排序算法，在问题规模不是很大的情况下就大胆的使用这个算法吧。
算法主过程如下： PROCEDURE selectsort;
VAR
i,j,k,temp:integer;
BEGIN
FOR i:=1 to n-1 DO
BEGIN
k:=i;
FOR j:=i+1 to n DO
IF a>a
THEN k:=j;
IF k<>i
THEN BEGIN
temp:=a;
a:=a;
a:=temp;
END;
END;
END;
[ 本帖最后由 kon3155 于 2009-2-25 10:56 编辑 ] 快速排序是基于分治排序算法，在数据规模很大的情况下一般使用该算法。
算法主过程如下： procedure qsort(L,R:longint);
var
i,j,mid,temp:longint;
begin
i:=L;
j:=R;
mid:=a; {随机选择一个数组中的数作为对比数}
repeat
while a< mid do inc(i); {在左半部分寻找比中间数大的数}
while mid< a do dec(j); {在右半部分寻找比中间数小的数}
if i< =j then {若找到一组与排序目标不一致的数对则交换它们}
begin
temp:=a;
a):=a;
a:=temp;
inc(i);dec(j); {继续找}
end;
until i >j;
if L< j then qsort(L,j); {若未到两个数的边界，则递归搜索左右区间}
if i< R then qsort(i,R);
end;注意:主程序中必须加randomize语句。 由于待处理的数据超过了任何一种数据类型所能容纳的范围，因此必须采用数串形式输入，并将其转化为数组。该数组的每一个元素对应一个十进制数，由其下标顺序指明位序号。由于高精度运算可能使得数据长度发生变化，因此除要用整数数组存储数据外，还需要一个整数变量纪录整数数组的元素个数，即数据的实际长度。type
numtype=array of byte;
var
a:numtype;
la:byte;
s:string;
begin
readln(s);
la:=length(s);
for i:=1 to la do
a:=ord(s)-ord('0');
end. 高精度加法运算
首先，确定a和b中的最大位数x，然后依照由低位至高位的顺序进行加法运算。在每一次运算中，a当前位加b当前位的和除以10，其整商即为进位，其余数即为和的当前位。在进行了x位的加法后，若最高位有进位(a<>0)，则a的长度为x+1。
以下只列出关键程序：type
numtype=array of byte;
var
a,b:numtype;
la,lb:byte;
procedure plus(var a:numtype;var la:byte;b:numtype);{利用过程实现}
var
i,x:byte;
begin
if la>=lb
then x:=la
else x:=lb;
for i:=1 to x do
begin
a:=a+b;
a:=a+a div 10;
a:=a mod 10;
end;
while a<>0 do
x:=x+1;
la:=x; {最高位若有进位，则长度增加}
end;
高精度减法运算（a>b）
依照由低位至高位的顺序进行减法运算。在每一次位运算中，若出现不够减的情况，则向高位借位。在进行了la位的减法后，若最高位为零，则a的长度减1。
以下只列出关键程序：type
numtype=array of byte;
var
a,b:numtype;
la,lb:byte;
procedure minus(var a:numtype;var la:byte;b:numtype);
var
i:byte;
begin
for i:=1 to la do
begin
if a<b
then begin
dec(a);
a:=a+10;
end;
a:=a-b;
end;
while (a=0) and (la>1) do
dec(la);
end; 高精度乘法运算
按照乘法规则，从a的第1位开始逐位与c（c为字节型）相乘。在第i位乘法运算中，a的i位与c的乘积必须加上i-1位的进位，然后规整积的i-1位。
以下只列出关键程序：type
numtype=array of word;
var
a,b:numtype;
la,lb:byte;
procedure multiply(var a:numtype;c:byte);
var
i:byte;
begin
a:=a*c;
for i:=2 to la do
begin
a:=a*c;
a:=a+a div 10;
a:=a mod 10;
end;
while a>=10 do
begin
inc(la);
a:=a div 10;
a:=a mod 10;
end;
end;
扩大进制数改善高精度运算效率
用整数数组每一个元素表示一个十进制整数的方法存在的缺点是：如果十进制的位数很多，则对应的数组的长度会很长，并增加了高精度计算的时间。
如果用一个元素记录2位数字、3位数字或更多位数字，则数组的长度可以明显缩小，但是还要考虑数的取值范围问题，必须保证程序运行过程中不越界。在权衡了两方面的情况后得出：用一个longint记录4位数字是最佳的方案。那么这个数组就相当于一个10000进制的数，其中每一个元素都是10000进制下的一位数。
一、数据类型定义：type
numtype=array of longint;{可以存储40000位十进制数}
var
a,n:numtype;
la,ln:byte;
s:ansistring; {任意长度的字符串类型}二、整数数组的建立和输出readln(s);
k:=length(s);
for i:=1 to k do
begin
j:=(k-i+4) div 4;
n:=n*10+ord(s)-48;
end;
ln:=(k+3) div 4;
当得出最后结果n后，必须按照次高位到最低位的顺序，将每一位元素由10000进制数转换成十进制数，即必须保证每个元素对应4位十进制数。例如n=0015(0<=i<=ln-2)，对应的十进制数不能为15，否则会导致错误结果。可以按照如下方法输出n对应的十进制数：write(n);
for i:=ln-1 downto 1 do
write(n div 1000,(n div 100) mod 10,(n div 10) mod 10,n mod 10);
三、基本运算
两个10000进制整数的加法和减法与前面的十进制运算方法类似，只是进制变成了10000进制。
1、整数数组减1(n:=n-1,n为整数数组)
从n出发寻找第一个非零的元素，由于接受了低位的借位，因此减1，其后缀全为9999。如果最高位为0，则n的长度减1。
j:=1;
while (n=0) do inc(j); {寻找第一个非零的元素}
dec(n); {该位接受低位的借位，因此减1}
for i:=1 to j-1 do
n:=9999; {其后缀全为9999}
if (j=ln) and (n=0) {如果最高位为0，则n的长度减1}
then dec(ln);
2、整数数组除以整数(a:=a div i,a为整数数组，i为整数)
按照从高位到低位的顺序，逐位相除，把余数乘进制后加到下一位继续相除。如果最高位为0，则a的长度减1。
l:=0;
for j:=la downto 1 do
begin
inc(a,l*10000);
l:=a mod i;
a:=a div i;
end;
while a=0 do dec(la);3、两个整数数组相乘（a:=a*n，a和n为整数数组）
按照从高位到低位的顺序，将数组a的每一个元素与n相乘。procedure multiply(a,b:numtype;la,lb:longint;var s:numtype;var ls:longint);
var
i,j:longint;
begin
for i:=1 to la do
for j:=1 to lb do
s:=s+a*b;
for i:=1 to la+lb-1 do
begin
s:=s+s div 10000;
s:=s mod 10000;
end;
if s=0
then ls:=la+lb-1
else ls:=la+lb;
end;
[ 本帖最后由 kon3155 于 2009-2-25 13:11 编辑 ] 习题与练习
一、用高精度计算出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<W≤30000）是事先给定的。
问：满足上述条件的不同的r共有多少个？
我们再从另一角度作些解释：设S是长度为w 的01字符串（即字符串S由w个“0”或“1”组成），S对应于上述条件（3）中的q。将S从右起划分为若干个长度为k 的段，每段对应一位2k进制的数，如果S至少可分成2段，则S所对应的二进制数又可以转换为上述的2k 进制数r。
例：设k=3，w=7。则r是个八进制数（23=8）。由于w=7，长度为7的01字符串按3位一段分，可分为3段（即1，3，3，左边第一段只有一个二进制位），则满足条件的八进制数有：
2位数：高位为1：6个（即12，13，14，15，16，17），高位为2：5个，…，高位为6：1个（即67）。共6+5+…+1=21个。
3位数：高位只能是1，第2位为2：5个（即123，124，125，126，127），第2位为3：4个，…，第2位为6：1个（即167）。共5+4+…+1=15个。
所以，满足要求的r共有36个。
【输入文件】
输入文件digital.in只有1行，为两个正整数，用一个空格隔开：
k W
【输出文件】
输出文件digital.out为1行，是一个正整数，为所求的计算结果，即满足条件的不同的r的个数（用十进制数表示），要求最高位不得为0，各数字之间不得插入数字以外的其他字符（例如空格、换行符、逗号等）。
（提示：作为结果的正整数可能很大，但不会超过200位）
【输入样例】
3 7
【输出样例】
36
【题目分析】
考虑一个首位为r、位数为n且除最后一位每一位严格小于右边的2k进制数，它的种数等于从2k-(r+1)个自然数中选出n-1个升序排列。
而题目所求答案等于首位为1..2w mod k-1、位数为w/k+1且符合要求的2k进制数种数，加上首位任意、位数不超过w/k不低于2的且符合要求的2k进制数种数。(当w mod k=0时直接考虑后者即可)
因为k,W是指定的,则可以确定2k进制数r的最长位数是w div k +1，设d=w div k，则d位2k进制数组成的2位以上d位以下的升序排列数应该是:
http://www.zjtg.cn/itjs/suanfa/images/6_6.gif
这里还要比较d与的2k-1大小，必须保证d<=2k-1。
最后考虑首位的情况，显然首位的最大二进制位数是w mod k，则最大值m=2w mod k- 1，则首位不大于m，总位数是d+1位的升序排列数应是：http://www.zjtg.cn/itjs/suanfa/images/6_6_1.gif
这里也要比较d与的2k-1大小，必须保证d<=2k-1-m。
两者相加即所求，因为最终的运算结果可能会很大，所以必须使用高精度运算。
【参考程序】
【NIOP满分程序】
[ 本帖最后由 kon3155 于 2009-2-25 11:27 编辑 ] 枚举法(通常也称穷举法)是指在一个有穷的可能的解的集合中，枚举出集合中的每一个元素，用题目给定的约束条件去判断其是否符合条件，若满足条件，则该元素即为整个问题的解；否则就不是问题的解。
【枚举算法解题必须满足下列条件】
⑴ 可预先确定解元素的个数n，且问题的规模不是很大；
⑵ 对于每个解变量A1，A2，…An的可能值必须为一个连续的值域。
【枚举算法实现】
通常使用嵌套的FOR结构循环语句枚举每个变量的取值，在最里层的循环中判断是否满足给定的条件，若满足则输出一个解。
【枚举算法优化】
⑴ 减少枚举的变量。
在使用枚举法之前，先考虑一下解元素之间的关联，将那些能由已枚举解元素推算出来的变量直接用计算表达式代替。
⑵ 减少枚举变量的值域。
通过各枚举变量间的数学关系定义解元素的值域，在保证不遗漏的情况下越小越好。
⑶ 分解约束条件。
将拆分的约束条件嵌套在相应的循环体间，即尽可能根据约束条件减少变量个数和缩小值域。