信息学奥赛经典算法VIP专享

一、 排序算法 1.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[k]>a[j] THEN k:=j; IF k<>i THEN BEGIN temp:=a[k]; a[k]:=a[i]; a[i]:=temp; END; END; END; 1.2 快速排序 • 快速排序是基于分治排序算法，在数据规模很大的情况下一般使用该算法。 算法主过程如下： procedure qsort(L,R:longint); var i,j,mid,temp:longint; begin i:=L; j:=R; mid:=a[L+random(R-L+1)]; {随机选择一个数组中的数作为对比数} repeat while a[i]< mid do inc(i); {在左半部分寻找比中间数大的数} while mid< a[j] do dec(j); {在右半部分寻找比中间数小的数} if i< =j then {若找到一组与排序目标不一致的数对则交换它们} begin temp:=a[i]; a[i]):=a[j]; a[j]:=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 语句。 二、 高精度算法 1.2 存储方法 由于待处理的数据超过了任何一种数据类型所能容纳的范围，因此必须采用数串形式输入，并将其转化为数组。该数组的每一个元素对应一个十进制数，由其下标顺序指明位序号。由于高精度运算可能使得数据长度发生变化，因此除要用整数数组存储数据外，还需要一个整数变量纪录整数数组的元素个数，即数据的实际长度。 type numtype=array[1..255] of byte; var a:numtype; la:byte; s:string; begin readln(s); la:=length(s); for i:=1 to la do a[la-i+1]:=ord(s[i])-ord('0'); end. 1.3 加法运算 高精度加法运算 首先，确定a和b中的最大位数x，然后依照由低位至高位的顺序进行加法运算。在每一次运算中，a当前位加b当前位的和除以 10，其整商即为进位，其余数即为和的当前位。在进行了 x位的加法后，若最高位有进位(a[x+1]<>0)，则 a的长度为 x+1。 以下只列出关键程序： type numtype=array[1..255] of word; var a,b,s:numtype; la,lb,ls:word; procedure plus(var a:numtype;var la:word;b:numtype;lb:word); {利用过程实现} var i,x:wor...