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

算法主过程如下：PROCEDURE selectsort;V ARi,j,k,temp:integer;BEGINFOR i:=1 to n-1 DOBEGINk:=i;FOR j:=i+1 to n DOIF a[k]>a[j]THEN k:=j;IF k<>iTHEN BEGINtemp:=a[k];a[k]:=a[i];a[i]:=temp;END;END;END;1.2快速排序•快速排序是基于分治排序算法，在数据规模很大的情况下一般使用该算法。

算法主过程如下：procedure qsort(L,R:longint);vari,j,mid,temp:longint;begini:=L;j:=R;mid:=a[L+random(R-L+1)]; {随机选择一个数组中的数作为对比数}repeatwhile a[i]< mid do inc(i); {在左半部分寻找比中间数大的数}while mid< a[j] do dec(j); {在右半部分寻找比中间数小的数}if i< =j then {若找到一组与排序目标不一致的数对则交换它们}begintemp:=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存储方法由于待处理的数据超过了任何一种数据类型所能容纳的范围，因此必须采用数串形式输入，并将其转化为数组。

该数组的每一个元素对应一个十进制数，由其下标顺序指明位序号。

由于高精度运算可能使得数据长度发生变化，因此除要用整数数组存储数据外，还需要一个整数变量纪录整数数组的元素个数，即数据的实际长度。

typenumtype=array[1..255] of byte;vara:numtype;la:byte;s:string;beginreadln(s);la:=length(s);for i:=1 to la doa[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。

以下只列出关键程序：typenumtype=array[1..255] of word;vara,b,s:numtype;la,lb,ls:word;procedure plus(var a:numtype;var la:word;b:numtype;lb:word); {利用过程实现}vari,x:word;beginif la>=lbthen x:=laelse x:=lb;for i:=1 to x dobegina[i]:=a[i]+b[i];a[i+1]:=a[i+1]+a[i] div 10;a[i]:=a[i] mod 10;end;while a[x+1]<>0 dox:=x+1;la:=x; {最高位若有进位，则长度增加}end;1.4减法运算高精度减法运算（a>b）依照由低位至高位的顺序进行减法运算。

在每一次位运算中，若出现不够减的情况，则向高位借位。

在进行了la位的减法后，若最高位为零，则a的长度减1。

以下只列出关键程序：typenumtype=array[1..255] of longint;vara,b:numtype;la,lb:word;procedure minus(var a:numtype;var la:word;b:numtype;);vari:word;beginfor i:=1 to la dobeginif a[i]<b[i]then begindec(a[i+1]);a[i]:=a[i]+10;end;a[i]:=a[i]-b[i];end;while (a[la]=0) and (la>1) dodec(la);end;© 版权所有桐乡市高级中学计算机组王建献2005- 2011制作与维护：桐高计算机组王建献邮箱：omnislash2000@建议使用：800*600分辨率，IE5.0以上版本浏览器1.5乘法运算高精度乘法运算按照乘法规则，从a的第1位开始逐位与c（c为字节型）相乘。

在第i位乘法运算中，a 的i位与c的乘积必须加上i-1位的进位，然后规整积的i-1位。

以下只列出关键程序：typenumtype=array[1..1000] of word;vara:numtype;la:word;procedure multiply(var a:numtype;var la:word;c:word);vari:word;begina[1]:=a[1]*c;for i:=2 to la dobegina[i]:=a[i]*c;a[i]:=a[i]+a[i-1] div 10;a[i-1]:=a[i-1] mod 10;end;while a[la]>=10 dobegininc(la);a[la]:=a[la-1] div 10;a[la-1]:=a[la-1] mod 10;end;end;1.6扩大进制数扩大进制数改善高精度运算效率用整数数组每一个元素表示一个十进制整数的方法存在的缺点是：如果十进制的位数很多，则对应的数组的长度会很长，并增加了高精度计算的时间。

如果用一个元素记录2位数字、3位数字或更多位数字，则数组的长度可以明显缩小，但是还要考虑数的取值范围问题，必须保证程序运行过程中不越界。

在权衡了两方面的情况后得出：用一个longint记录4位数字是最佳的方案。

那么这个数组就相当于一个10000进制的数，其中每一个元素都是10000进制下的一位数。

一、数据类型定义：typenumtype=array[1..10000] of longint; {可以存储40000位十进制数}vara,n:numtype;la,ln:byte;s:ansistring; {任意长度的字符串类型}二、整数数组的建立和输出readln(s);k:=length(s);for i:=1 to k dobeginj:=(k-i+4) div 4;n[j]:=n[j]*10+ord(s[i])-48;end;ln:=(k+3) div 4;当得出最后结果n后，必须按照次高位到最低位的顺序，将每一位元素由10000进制数转换成十进制数，即必须保证每个元素对应4位十进制数。

例如n[i]=0015(0<=i<=ln-2)，对应的十进制数不能为15，否则会导致错误结果。

可以按照如下方法输出n对应的十进制数：write(n[ln]);for i:=ln-1 downto 1 dowrite(n[i] div 1000,(n[i] div 100) mod 10,(n[i] div 10) mod 10,n[i] mod 10);三、基本运算两个10000进制整数的加法和减法与前面的十进制运算方法类似，只是进制变成了10000进制。

1、整数数组减1(n:=n-1,n为整数数组)从n[1]出发寻找第一个非零的元素，由于接受了低位的借位，因此减1，其后缀全为9999。

如果最高位为0，则n的长度减1。

j:=1;while (n[j]=0) do inc(j); {寻找第一个非零的元素}dec(n[j]); {该位接受低位的借位，因此减1}for i:=1 to j-1 don[i]:=9999; {其后缀全为9999}if (j=ln) and (n[j]=0) {如果最高位为0，则n的长度减1}then dec(ln);2、整数数组除以整数(a:=a div i,a为整数数组，i为整数)按照从高位到低位的顺序，逐位相除，把余数乘进制后加到下一位继续相除。

如果最高位为0，则a的长度减1。

l:=0;for j:=la downto 1 dobegininc(a[j],l*10000);l:=a[j] mod i;a[j]:=a[j] div i;end;while a[la]=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);vari,j:longint;beginfor i:=1 to la dofor j:=1 to lb dos[i+j-1]:=s[i+j-1]+a[i]*b[j];for i:=1 to la+lb-1 dobegins[i+1]:=s[i+1]+s[i] div 10000;s[i]:=s[i] mod 10000;end;if s[la+lb]=0then ls:=la+lb-1else ls:=la+lb;end;1.7习题与练习：•习题与练习：•习题与练习•一、用高精度计算出s=1!+2!+3!+...+100!。

参考答案•二、输入任意两个整数a,b(a,b均在长整型范围内),计算a/b的结果,保留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。