高精度运算与排序算法

1高精度运算和排序算法2Pascal标准数据类型1、整型类型数值范围占字节数Byte0..2551Word0..655352Shortint-128..1271Integer-32768..327672Longint-2147483648..21474836474Longword0..42949672954Int64-9223372036854775808..92233720368547758078QWord0..184467440737095516158Qword:[0,1.8*1019]Int64：[-9.0*1018,9.0*1018]32、实数类型范围有效位数占用字节Real2.9e-39..1.7e3811..126Single1.5E-45..3.4E387-84Double5.0E-324..1.7E30815-168Extended1.9E-4951..1.1E493219-2010Comp-2E64+1..2E63-119-208如果参与运算的数值超出了标准数据类型能表示的范围呢？例如：计算两个1000位整数的和。4高精度运算：整数的加、减、乘、除、比较主要解决的问题：1、高精度数的输入和保存。2、运算时的进位与借位。3、运算结果的位数确定。4、运算结果的输出。5高精度数的输入和保存。字符串读入，数组保存。Vars1,s2:string;a,b:array[1..240]ofinteger;readln(s1);la:=length(s1);{s1的长度}fori:=1toladoa[i]:=ord(s1[la+1-i])-48;{保存读入的高精度数，a[1]保存个位}如：s1=‘32456345’保存：32456345a[8]a[7]a[6]a[5]a[4]a[3]a[2]a[1]6高精度加法运算：求a+b的值。编程实现：输入正整数a和b，输出a+b的值。a，b10240输入：第一行：a第二行：b输出：a+b的值。7Vara,b,c:array[1..241]ofinteger;la,lb,lc:integer;加法运算时的进位。………a[5]a[4]a[3]a[2]a[1]+……..b[5]b[4]b[3]b[2]b[1]………c[5]c[4]c[3]c[2]c[1]8iflalbthenlc:=lathenlc:=lb;{lc是s1和s2的较大位数}m:=0;{进位}fori:=1tolcdobeginc[i]:=(a[i]+b[i]+m)mod10;m:=(a[i]+b[i]+m)div10;end;方法一：最后一个进位m的处理：Ifm0then//m=1begininc(lc);c[lc]:=m;end;9运算结果的输出:fori:=lcdownto1dowrite(c[i]);writeln;fori:=lcdownto2dowrite(c[i]);writeln(c[1]);10fori:=1tolcdoc[i]:=a[i]+b[i];//先逐位相加fori:=1tolcdo//从低位依次处理进位beginc[i+1]:=c[i+1]+c[i]div10;c[i]:=c[i]mod10;end;ifc[lc+1]0thenlc:=lc+1;方法二：11a-a+b//节省空间iflblathenla:=lb;fori:=1toladobegina[i+1]:=a[i+1]+(a[i]+b[i])div10;a[i]:=(a[i]+b[i])mod10;end;ifa[la+1]0theninc(la);方法三：12二、高精度减法运算：求a-b的值。编程实现：输入正整数a和b，输出a-b的值。a，b10240输入：第一行：a第二行：b输出：a-b的值。13输入与保存和加法运算一样1、比较a和b的大小。从而确定结果的正负号ifabthen+ifabthen-ifa=bthen02、借位问题。需解决的问题：141、比较a和b的大小，从而确定结果的正负号：readln(s1);readln(s2);ifs1=s2thenbeginwrite(0);halt;end;la:=length(s1);lb:=length(s2);if(lalb)or((la=lb)and(s1s2))then{ba交换}beginfh:='-';s:=s1;s1:=s2;s2:=s;end;la:=length(s1);lb:=length(s2);len:=la;152、借位问题len:=la;fori:=1tolendobeginifa[i]b[i]thenbegina[i+1]:=a[i+1]-1;a[i]:=a[i]+10;end;a[i]:=a[i]-b[i];end;whilea[len]=0dodec（len）;16高精度乘单精度：求c=a*b。（a：10240,b：integer)17m:=0;fori:=1tolendobeginc[i]:=(a[i]*b+m)mod10;m:=(a[i]*b+m)div10;end;whilem0dobegin{处理最高位的进位}inc(len);c[len]:=mmod10;m:=mdiv10;end;vari,len:integer;s:string;b,m:integer;a,c:array[1..250]oflongint;18高精度乘高精度：c=a*bfori:=1toladoforj:=1tolbdobeginc[i+j-1]:=c[i+j-1]+a[i]*b[j];c[i+j]:=c[i+j]+c[i+j-1]div10;c[i+j-1]:=c[i+j-1]mod10;end;len:=la+lb;while(len1)and(c[len]=0)dodec(len);19练习：给出两个不超过240位整数a、b，一个运算符号op（’+’或’-’），计算aopb的结果。输入：第一行：a第二行：b第三行：op输出：aopb的值。其中，a,b若是正整数，’+’可能省略。约定：输出结果中的’+’省略。样例输入：+89-样例输出：-120什么是排序？排序是处理数据过程中一种很常用的运算，是将一组原本无序的数据元素，通过一定的方法，按照某个域的值（关键字）递增或递减的次序重新排列的过程。排序的目的之一是为了方便查找：对无序数据进行查找的时间复杂度为O(n)；在排序的基础上进行查找，其时间复杂度为O(logn)。排序的分类：根据排序过程中是否使用外存储器，可以把排序分为外排序和内排序。下面主要讨论几种常见的内排序算法：选择排序、冒泡排序、插入排序和快速排序。211.选择排序选择排序是一种简单的排序方法。其基本思想是：把待排序的n个元素看作一个有序部分和一个无序部分。开始时有序部分为空，无序部分包含n个元素。排序时每次从无序部分中选出最小的元素，把它与无序部分的第一个元素交换位置，那么该元素必大于（或等于）有序部分中的所有元素，从而使有序部分元素个数增1，无序部分元素个数减1。经过n-1次选择和交换后，有序部分有n-1个元素，无序部分只有1个元素，且该元素大于（或等于）有序部分中的所有元素，整个排序过程结束。22初始关键字：[2252204119024218542231]第一趟排序后：41[22022519024218542231]第二趟排序后：4142[225190242185220231]第三趟排序后：4142185[190242225220231]第四趟排序后：4142185190[242225220231]第五趟排序后：4142185190220[225242231]第六趟排序后：4142185190220225[242231]第七趟排序后：4142185190220225231242排序过程演示23programselectsort;constmx=10000;vard:array[1..mx]oflongint;n,i,j,k:longint;beginreadln(n);fori:=1tondoread(d[i]);fori:=1ton-1dobegink:=i;forj:=i+1tondo//d[k]为d[i]..d[n]的最小元素ifd[j]d[k]thenk:=j;j:=d[k];d[k]:=d[i];d[i]:=j;//交换end;fori:=1tondowriteln(d[i]);end.可见，选择排序的时间复杂度为O(n2)的，需要进行n*(n-1)/2次比较和n-1次交换。优化：分析上面的排序过程可以发现，如果d[i]是d[i]..d[n]中的最小值，即k=i,那么不需要交换d[k]和d[i]。24programselectpro;constmx=10000;vard:array[1..mx]oflongint;n,i,j,k:longint;beginreadln(n);fori:=1tondoread(d[i]);fori:=1ton-1dobegink:=i;forj:=i+1tondo//d[k]为d[i]..d[n]的最小元素ifd[j]d[k]thenk:=j;ifkithen//交换beginj:=d[k];d[k]:=d[i];d[i]:=j;end;end;fori:=1tondowriteln(d[i]);end.可见，选择排序至多需要n-1次交换。252.冒泡排序冒泡排序也是一种简单的排序方法。其基本思想是：通过相邻元素之间的比较和交换使较小的元素逐渐从后向前移动，就像水底的气泡一样逐渐向上冒。具体过程如下：首先比较d[n]和d[n-1]，若d[n]d[n-1]，则交换，使较小的元素前移，较大的元素后移；接着比较d[n-1]和d[n-2]，以此类推，直到比较d[2]和d[1]并使较小的元素前移，第一趟排序结束,则d[1]为最小的元素。然后在d[2]..d[n]间进行第二趟排序，使第二小元素前移到d[2]位置；n-1趟排序后，整个冒泡排序结束。26初始关键字：[2252204119024218542231]不交换d[8]和d[7]：[2252204119024218542231]交换d[7]和d[6]：[2252204119024242185231]交换d[6]和d[5]：[2252204119042242185231]交换d[5]和d[4]：[2252204142190242185231]不交换d[4]和d[3]：[2252204142190242185231]交换d[3]和d[2]：[2254122042190242185231]交换d[2]和d[1]：[4122522042190242185231]排序过程演示27第一趟排序后：41[22522042190242185231]第二趟排序后：4142[225220185190242231]第三趟排序后：4142185[225220190231242]第四趟排序后：4142185190[225220231242]第五趟排序后：4142185190220[225231242]第六趟排序后：4142185190220225[231242]第七趟排序后：414218519022022523124228programmaopaosort;constmx=10000;vard:array[1..mx]oflongint;n,i,j,k:longint;beginreadln(n);fori:=1tondoread(d[i]);fori:=1ton-1dobeginforj:=n-1downtoidoifd[j+1]d[j]thenbegin//相邻元素交换k:=d[j];d[j]:=d[j+1];d[j+1]:=k;end;end;fori:=1tondowriteln(d[i]);end.可见，其时间复杂度也是O(n2)的。不难发现，如果某趟排序中没有发生交换，就意味着任意两个相邻元素都是有序的，那么全部元素就已经有序了。