plc编程常用算法
常用算法
一.基本概念：
1.算法：就是解决问题方法的精确描述。并不是所有问题都有算法，
有些问题经研究可行，则相应有算法；而有些问题不能说明可行，
则表示没有相应算法。
算法具有以下性质：是一有穷动作的序列；
动作序列仅有一个初始动作；
序列中每个动作的后继动作是确定的；
序列的终止表示问题得到解答或问题没有解答
2.算法的分类：数值的和非数值的
数值的算法是以数学方式表示的问题求数值解的方法，如：代数方程计算、矩阵计算、线性方程组求解、函数方程求解等；
非数值的算法是求非数值解的方法，如排序查找、模式匹配、排列模拟、表格处理、文字处理等。
3.算法设计：主要是针对各类具体问题设计良好的算法及研究设计算
法的规律和方法。
4.常用的算法设计方法：
数值算法：迭代法、递归法、插值法等；
非数值算法：分治法、贪婪法、回溯法等。
5.算法分析：是对设计出的每一个具体的算法，利用数学工具，讨论
各种复杂度。算法的复杂度分时间复杂度和空间复杂度。
二.常用数值计算算法
1.迭代法
迭代法适用于方程(或方程组)求解，是使用间接方法求方程近似根的一种常用算法。(参见清华版《PASCAL程序设计P89练习4.23》设方程f(x)=0，该方法将方程表示为等价形式：x=g(x)，或一般地将f(x)拆成两个函数f1、f2，即f(x)= f1(x)-f2(x) =0，因而有f1(x)=f2(x)。
其中f1(x)是这样一个函数，对于任意数c，容易求出f1(x)=c的精确度很高的实根。迭代法求解算法如下：
(1).首先选一个x的近似根x0，从x0出发，代入右面函数，并解
方程f1(x)=f2(x0)得到下一个近似根x1;
(2).将上次近似根x1代入右面函数，并解方程f1(x)=f2(x1)，得到
又一个近似根x2
(3).重复(2)的计算，得到一系列近似根x0,x1,x2,…,x i,x i+1,…,x n,…；
O / \ t1 t2 若方程有根，这数列收敛于方程的根，若满足ε 1--n n x x ，则认为x n 是方程的近似根。
例1：迭代计算n!、Fibonacci(斐波那契)数列 (详见清华版《PASCAL 程序设计》P59-62例4.3,4.4)
例2：计算......!
7!5!3)sin(7
53+-+-=x x x x x 直到最后一项的绝对值小于10-7时停止计算，x 由键盘输入。(详见清华版《PASCAL 程序设计》P72例4.11)
练习：清华版《PASCAL 程序设计习题与选解》P18习题4.23,4.38
2. 递推法
递推法实际上是需要抽象为一种递推关系求解，此方法通常表现为两种方式：方式一是从简单推到一般；
方式二是将一个复杂问题逐步推到一个已知解的简单问题。这两种方式反映了两种不同的递推方向，前者往往用于计算级数，后者与“回归”配合成为一种特殊的算法――递归法。
3. 递归法
在数学中几个熟知的递归定义：
(1). ?
??≠-==时当时当0 !)1(0 1!n n n n n (2). 树结构：a)O 是树(空树)；b)若t1和t2是树，则
是树。
例3：递归计算n!；(详见清华版《PASCAL 程序设计》P108例5.8) 例4：第二届初中组一、6
第二届初中组一、7
提示：利用y=((((A N X+A N-1)X+A N-2)X+A N-3)+……+A 1)X+A 0
第七届初中组三、1
练习：计算Fibonacci(斐波那契)数列?????>+===--时当1 1
02110n Fib Fib Fib Fib Fib n n n 4. 插值法
也称为内插法。在实际问题中出现的函数f(x)，往往只知道它在某区间中若干点的函数值，这时作出适当的特定函数，使得在这些点上取已知值，并且在这区间内其它各点上就用这特定函数所取的值作为函数f(x)的近似值，这方法称为“插值法”。如果这特定函数是多项式，就称之为“插值多项式”或“内插多项式”。(常见用于高等代数中的计算)
三.常用非数值计算算法
1.穷举搜索法
穷举所有可能情形，并从中找出符合要求的解。最直观的是联系循环的算法。
例5：百钱买百鸡问题；第一届初中组3(也可用累加法)
第七届初中组四、2
输出1-100内的素数；验证哥德巴赫猜想(详见清华版
《PASCAL程序设计》P82-86例4.16,4.17)
例6：找出n个自然数(1,2,3,……,n)中r个数的组合
当n=5,r=3时，约定前一个数应大于后一个数，
有：543 542 541 532 531 521 432 431 421 321
可简单地用三重循环进行搜索，算法如下：
for i:=5 downto 1 do
for j:=5 downto 1 do
for k:=5 downto 1 do
if ((i<>j) and (i<>k) and (j<>k) and (i>j) and (j>k))
then writeln(i,j,k);
或者
for i:=5 downto 3 do
for j:=i-1 downto 3-1 do
for k:=j-1 downto 1 do
if ((i<>j) and (i<>k) and (j<>k) and (i>j) and (j>k))
then writeln(i,j,k);
2.递归法
例如：在例6中，可首先固定第一位数(如5)，其后是在另4个数中再“组合”2个数。这就将“5个数中3个数的组合”推到了“4个数中2个数的组合”上去了。第一位数可以是n→r(如5→3)，n个数中r个数组合递推为n-1个数中r-1个数的组合，这是一个递归的算法：procedure comb(n,r:integer);
var i,temp:integer;
begin
for i:=n downto r do
if ((i<>n) and (k<>r)
then begin temp:=1
while temp<=(k-r)*3 do {k为过程外定义的}
begin
write(‘‘); temp:=temp+1
end;
end;
write(i);
if (I>1) then comb(i-1,r-1) {递推到下一情形}
else writeln;
end;
例7：求m与n的最大公约数；汉诺塔游戏(Tower of Hanoi) (详见清华版《PASCAL程序设计》P109-P112例5.9,5.10)
例8：第六届初中组二、2 第五届高中组二、第五届初中组五3.回溯法
一种选优搜索法，按选优条件向前搜索，以达到目标。但当搜索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足条件的某个状态的点称为“回溯点”。
例如：在例6中将自然数排列在数组A中：
A[1] A[2] A[3]
5 4 3
5 4 2
……
3 2 1
排数时从A[1]→A[2]→A[3]，后一个至少比前一个数小1，并且应满足r i+A[r i]>r这个关系。若r i+A[r i]≤r就要回溯，该关系就是回溯条件。为直观起见，当输出一组组合数后，若最后一位为1，也应作一次回溯(若不回，便由上述回溯条件处理)。算法如下：
procedure comb2(n,r,a[m]:integer);
var j,ri:integer;
begin
ri=1;a[1]=n;
repeat
if (ri<>r) {没有搜索到底}
then if (ri+a[ri]>r) {是否回溯}
then begin
a[ri+1]:=a[ri]+1;ri:=ri+1
end;
else begin
ri:=ri-1; a[ri]:=a[ri]-1 {回溯}
end;
else begin
c a b f e
d for j:=1 to r do write(a[j]);
writeln;
if (a[r]=1) {是否回溯}
then begin
ri:=ri-1; a[ri]:=a[ri]-1 {回溯}
end;
else a[ri]:=a[ri]-1
end;
until (a[1]<>r-1)
end;
例9：八皇后问题(详见清华版《PASCAL 程序设计》P165)
练习：清华版《PASCAL 程序设计》P172习题7.19跳马问题和7.20迷宫问题、四色问题
例10：第三届初中组二、3
4. 贪婪法
一种可以快速得到满意解(但不一定是最优解)的方法。方法的“贪婪”性反映在对当前情况，总是作最大限度的选择。即满足条件的均选入，然后分别展开，最后选得一个问题解。这方法不考虑回溯，也不考虑某次选择并不符合最优条件，但最终能得到最优结果的选择。
例11：用贪婪法求解“货郎担问题”。所
谓货郎担问题是指，给定一个无向图，并已
知各边的权，在这样的图中，要找一个闭合回路，使回路经过图中的每一个点，而且回路各边的权之和为最小，如右图所示。如
a,b,c,d,e,f 这6个点，坐标分别为(0,0)、(4,3)、
(1,7)、(15,7)、(15,4)、(18,0)，这是最优解。(算法程序略)
求解步骤一般如下：
(1). 计算各点间距离（邻接矩阵）；
(2). 距离关系表排序；
(3). 贪婪法选择边，入选的边应符合如下两条件：每个端点不能
联系两条以上的边；不会使入选的边形成回路，除非入选正
好是边数等于端点数。为此引入端点关系表
(4). 如果由(3)得不到解，应调整距离关系表中距离相同的边的次
序，再试；
(5). 若有解，则按端点关系表给出回路的轨迹。
例12：旅行路线选择。设有n 个城市(或景点)，今从某市出发遍历各城市，使之旅费最少(即找出一条旅费最少的路径)。
例13：背包问题。从n 件不同价值、不同重量的物品中选取一部
分，在不超过规定重量的原则下，使该部分价值最大。
例14：第三届初中组一、8； 第七届高中组四、2
5. 分治法
是应用十分广泛的一种算法设计方法，其基本思想是把一个规模为n 的问题分成若干个规模较小的问题，使得从这些较小问题的解易于构造出整个问题的解。
例15：找一个集合的极大元和极小元。集合S 含有n 个元素，其中n=2k (k ≥1)。算法思路如下：
procedure MAXIM(S);
begin
1. if ||S||=2 {集合S 的元素个数为2}
then begin
2. 设 S={a,b};
3. return (MAX(a,b),MIN(a,b))
end
else begin
4. 把S 分为两个子集S 1和S 2，各有一半元素；
5. (max1,min1)←MAXMIN(S 1)；
6. (max2,min2)←MAXMIN(S 2)；
7. return (MAX(max1,max2),MIN(min1,min2))
end
end;
注意到，需要在集合S 的元素间进行比较的步骤只是步骤3(在此比较两个元素)及步骤7(在此把max1与max2及min1与min2进行比较)，设T(n)是用MAXMIN 在一个具有n 个元素的集合中找极大元和极小元时，需要在S 的元素间进行比较的次数。显然，T(2)=1，如果n>2，则T(n)是在大小为n/2的集合上两次调用MAXMIN(第5、6步所需的比较次数加上第7步的两次比较所得的总次数，即
?
??>+==2n 2)2/(22n 1)(当当n T n T 。经递推T(n)=3n/2-2，对于在集合S 的元素间进行比较的次数来说，这种算法是最优的。
例16：设有n 个选手的循环比赛(n=2m )，要求每名选手要与其他n-1名选手都赛一次。每名选手每天比赛一次，循环赛共进行n-1天，要求每天没有选手轮空。例如m=3，见下表，用分治法将(2m *2m )矩阵分成四块，每块是(2m-1*2m-1)的矩阵，它应是对称的(A B B
A )，再对A
与B 均是(2m-1*2m-1)的矩阵分成四块，直至(2*2)的矩阵定出每个元素
四. 排序
1. 插入排序
设待排序的记录为(R 1,R 2,…,R n )，插入排序的基本思想是把记录R i (2≤i ≤n)插入到一列已排好序的记录R 1,R 2,…,R i-1(1≤i ≤n)中，使得长度为I 的一系列记录也是排好序的。
(1). 直接插入排序
若记录R 1,R 2,…,R i-1已按关键码有
序，即对应的关键码有K 1≤K 2≤…≤
K i-1，将K i 与K i-1 ,K i-2 ,…,K 1依次比较，
一旦K i 大于或等于某个K j （1≤j ≤
i-1）时，把R j+1, R j+2,…, R i-1后移一
个位置，并将R j 插在第j+1个位置上。
在直接插入排序中，若待排序的记录已有序，总共比较C ＝n-1
次；若记录是完全反序的，则比较C ＝2＋3＋…＋n ＝
()()2
21+-n n 次。直接插入排序可用顺序存储和链接存储。
例17：清华版《PASCAL 程序设计》P171习题7.8
(2).二分法插入排序
在直接插入算法中，确定R i（i=2,…,n）插入位置的方法是将它与前面i-1个记录依次比较，由于前i-1个记录已按关键码有序，
可以用二分法较快地找到R i的插入点。首先取
()
??
?
??
?-
+
=
2
1
1i
m，
比较R m与R i的关键码。若R i的关键码小于R m的关键码，则在[R1,R2,…,R m-1]范围内再用二分法，否则在[Rm+1,…,R n]范围内再用二分法。如此反复，直至最后找到R i的插入位置。
当n较大时，二分法插入排序比较次数比直接插入排序的最多比
较次数()()
2
2
1+
-n
n
少得多，但比直接插入排序的最少比较次数
（n-1）大。二分法插入排序只能采用顺序存储。
2.选择排序
又称为直接选择排序。在待排序的n个记录中先选出关键码最大的记录，将它送到第n个位置上，然后再从其余n-1个记录中选出关键码最大的记录送到第n-1个位置上，…，直至选择了n-1个记录。
选择排序比较次数共有C＝(n-1)+…+2=n(n-1)/2 (详见清华版《PASCAL程序设计》P145-147)
3.冒泡排序
这种排序方法从表的一端开始，依次比较相邻两个记录的关键码R[i].key和R[I＝1].key，若R[i].key＞R[I+1].key，则交换R[i]和R[i+1]。假设从表的左端开始，当i从0到n-2对表扫描一趟后，具有最大关键码的记录将被移到最右边的位置上。
作n-1趟扫描将完成对n个记录的排序，但完成n个记录的排序不一定都要进行n-1趟扫描，如果在某趟扫描中没有发生交换，则排序工作已完成，此后的扫描便不必进行。如果待排序的诸记录在排序前已按关键码排好序，则用冒泡排序算法只需一趟扫描便完成排序，比较次数为C＝n-1。如果待排序的记录完全反序，即已由大至小排序，则比较次数C＝n(n-1)/2 (详见清华版《PASCAL程序设计》P148-150) 4.希尔排序
在直接插入排序和冒泡排序中，只比较相邻的记录，一次比较至多将记录移动一个位置。希尔排序是对此两种排序的推广。算法先将记录按某个增量d分成若干组，每组中记录的下标相差d。对每组中的记录用某种方法（前两种）进行排序，然后再用一个较小的增量对记录进行分组，在每组中再进行排序，…，当增量减至1时，整个记录被分成一组，排序完成。
例如：设待排序的记录的关键码为：
94 32 40 90 99 80 46 21 69 28 64 73 85 54
取增量序列为：5，3，1，当增量d=5时，整个记录被分成五组：
再取增量为1，排序结果为：21 28 32 40 46 54 64 69 73 80 85 90 94 99 5.快速排序
选取表中某个记录的关键码K作为基准，将表划分成左、右两个子表：左子表中各记录的关键码都小于等于K，右子表中各记录的关键码都大于等于K，然后用同样的方法递归地处理这两个子表。比较次数C(1)=0,C(2)=2+C(1)=2,C(3)=3+C(2)=5,…,
C(n)=n+C(n-1)=(n+2)(n-1)/2
上图说明了13个记录的表进行第1次划分的过程。取表的中间一个记录的关键码275作为基准，划分时用两个指针变量i和j扫描表，变量i从表头向右扫描，直至遇到一个关键码大于或等于基准的记录；变量j从表尾向左扫描，直至遇到一个关键码小于或等于基准的记录；接着交换R i和R j。指针i和j继续向两端前进，进行比较、交换。当i和j交叉（即i处于j的右边）时，表中各记录都与基准比较过，表被分成左、右两部分，左边各记录的关键码小于或等于右边各记录的关键码。
6.堆排序
是对选择排序的改进。为了避免在选择排序中出现的每趟选择最大关键码的记录时的某些重复的比较，可以采用树形选择方法。设待排序的n个记录的关键码为K1,K2,…,K n，先两两比较K1:K2, K3:K4,…,
K n-1:K n，然后用同样的方法比较每对中的较小者，直至找出最小的关
另一种改进的堆排序方法是，
将待排序的n个记录(R1,R2,…,R n)
看成是有n个结点的一棵完全二
叉树，树中结点满足下列条件：任
何一个非叶结点的值（这个结点上
记录的关键码）都大于或等于它的
子女结点的值，因此堆的根在树中具有最大的关键码。这样得到的序列将是非递减的。
7.归并排序
是把两个或两个以上已排好序的表组合在一起，产生一个新的排好序的表。方法如下：
(1).若两个表有一个为空，则无须归并
(2).若两个表都非空，则比较p和q（两个表的头指针）所指结点
的关键码，将较小者插入第三个表中，并前进相应的指针。
重复这一步；
(3).若有一个表先到达表尾，则把另一个表的剩余部分插入到第
三个表中。
例18：第五届初中组五
8.各种排序方法的比较
?直接插入排序在记录数目较少且是基本有序时是最佳的；
?选择排序是比较次数不依赖记录的初始排列，且记录移动较少；
?冒泡排序的性能较差；
?希尔排序是对插入排序和冒泡排序的推广，在记录移动时可能消去多个反序，算法时间可能较短；
?快速排序是目前所有排序中平均性能最好的方法，但在最坏情况下年耗时间最多；
?堆排序在n较大时非常有效；
?归并排序可以看成是插入排序的扩充。
例19：第六届初中组1、10
9.其它排序方法
例20：第七届初中组四、1
五.查找
查找又称为检索，它往往是程序中最耗费时间的操作，使用何种存储结构和查找算法对程序的性能有本质的差别，因此，在讨论各种查找算法时都应指明所用的存储结构。
TYPE element=RECORD ｛定义记录类型｝
key: keytype ｛值为关键字的域｝
recs: rectype {记录的其它域}
END;
sqlist=ARRAY[0..n] OF element;
1.顺序查找
又称为线性查找，对给定的关键码值K，从表的一端开始，依次检查表中每个记录的关键码，直至找到所需灌到达表的另一端。
FUNCTION seqsrch(r:sqlist;K:keytype):integer;
Begin
r[0].key:=K; i:=n;
while r[I].key<>K do i:=i-1
return(i)
end;
{K 为给定值，函数seqsrch 值为关键码等于K 的记录在表r 中的序号，值为零时表明查找不成功}
（参考清华版《PASCAL 程序设计习题与选解》P35习题7.23）
2. 二分查找
又称为折半查找。当表中记录按关键码有序时（有序表），可以采用二分查找法。先确定待查记录的范围（区间），然后逐步缩小范围直到找到或找不到该记录为止。用两个指针low 和hig 分别指示待查元素所在范围的下界和上界，并用指针mid 指示中间元素
??
????+=2hig low mid 。在开始进行查找时，low 和hig 的初值分别指向第1个和第n 个元素。
FUNCTION binsrch(r:sqlist;K:keytype):integer;
Begin
low:=1; hig:=n;
while low<=hig do {判别区间大小}
begin
mid: =(low+hig ) div 2;
case
k>r[mid].key: low:=mid+1;
k=r[mid].key: return(mid); ｛查找成功｝
k end; return(0) end; （参考清华版《PASCAL 程序设计习题与选解》P35习题7.24） 例21：第七届初中组一、19；第六届初中组一、14 3. 分块查找 又称为索引顺序查找，是顺序查找的改进方法。是把表分成若干块，每块中记录的存储顺序是任意的，但块与块之间必须按关键码有序，即第一块中任一记录的关键 码都小于第二块中各记录的 关键码，如此类推。这种查找 方法要求除表本身外，尚需建 立一个索引表，索引表中的一 项对应于表的一块，它含有这 一块中的最大关键码的指向 块内第一个记录位置的指针，索引表中各项按关键码有序。 分块查找的过程分两步进行：先查找索引表（可以用上述两种方法），确定要找的记录在哪一块；然后再在相应的块中查找。