高精度运算--Pascal语言.ppt

高精度运算,为什么要进行高精度运算？,PASCAL语言中整数：最小的为byte型，范围：0.255，占用一个字节；integer类型，范围：-32768.32767，占用二个字节；longint类型，范围：-2147483648.2147483647，四个字节实数：real类型，达到10的38次方，占用六个字节；doubel型，达到10的308次方，占用8个字节；extended型，达到10的4932次方，占用10个字节。,很多情况下仍然不够用，只能采用高精度运算。,两个大整数之间的四则运算,例：9999999999+8888888888,这两个整数都是普通类型无法读入的，也不能用普通的整数数组直接读入。,一般采用字符串类型读入，然后转化为整数数组，最后用数组模拟的方法运算。,本节主要内容,高精度算法的基本思想-分割、模拟：将无法直接处理的大整数，分割成若干个可以直接处理的小整数段，将原问题转化为对小整数段的处理。例如：3628800这个数字范围很大，但可以分割、转化为数组进行处理和输出。,S7,S6,S5,S4,S3,S2,S1,在处理之前，首先要解决输入的问题，对于范围特别大的数字一般通过字符串进行输入。,字符串string,字符串可以按照下标直接引用，如字符串S:“abcde888edcba”，S5即字符“e”。这种引用方法和数组是一样的，所以可以把字符串看成一种特殊的字符型数组。,但是，字符串有一些字符数组所没有的方便之处。其中，最方便的地方是编译系统通常都为字符串内置了许多常用的函数（对普通的字符数组则没有），这对编写程序有很大好处。而且，PASCAL语言内置的字符串函数比C语言要多一些。,一、字符串的定义关键字String,例:a,b,c:string;定义了三个字符串，默认长度为255；,例:d:string100;定义了一个长度为100的字符串；,二、字符串的输出不需要循环,例:Write(a);输出整个字符串aWrite(a2);输出字符串的第2个字符,三、字符串的常用函数,注：这些系统的内部函数仅对字符串string才有效，对字符数组和整数数组均无效。,（1）求串长函数length(s)s为string类型，返回s串的实际长度值(整数)。,（2）求子串函数copy(s,i,L)s为string类型，i和L为整数类型，返回类型为string。返回s串中，从第i个字符开始，长度为L的子串。,（3）搜索子串位置函数pos(s1,s2)s1和s2均为string类型，返回类型为整数。s1若是s2的一个子串，则返回s1中第一个字符在s2中的位置；若s1若不是s2的一个子串，则返回0。,常用！,ASCII表,四、将字符串转化为整数数组,注：仅限于“123456”这样的串；类似“abcde”的纯字符串不适合转化,假设s为一个串，如s=1234567890；K:=length(s);Fori:=1tokdodatak-i+1:=ord(si)ord(0);,函数ord求的是字符在ASCII表的位置，该位置减去字符0的位置，得到位置差。位置差就是该数字。,数组a,数组b,相加得数组c,这时直接输出会得到1717171717，显然不对，因此要逐位处理一下。,数组c,商往前进：ci+1:=ci+1+cidiv10;余数留下：ci:=cimod10;注意：上面两步的顺序不能颠倒！,数组c,数组c,数组c,数组c,逐位处理完毕后，就可以倒序输出了，但是为了避免输出左边没用的零，要先确定第一个有效的数字在什么位置。这个可以用While循环从高到低扫描，遇到第一个非零的数字，记录它的位置。,/寻找最高位避免输出0Top:=Max;Whilectop=0dotop:=top-1;,Topmax,TopTop-1,两个大整数的加法运算,constmax=100;Vars1,s2:string;a,b,c:array1.maxofinteger;i,top,k1,k2:integer;beginreadln(s1);k1:=length(s1);/输入字符串s1，并求它的长度readln(s2);k2:=length(s2);/输入字符串s2，并求它的长度Fori:=1tok1doak1-i+1:=ord(s1i)-ord(0);/字符串s1转化为数组aFori:=1tok2dobk2-i+1:=ord(s2i)-ord(0);/字符串s2转化为数组bFori:=1tomaxdoci:=ai+bi;/加法运算逐位处理和输出见下页,Fori:=1tomaxdo/逐位处理beginci+1:=ci+1+cidiv10;ci:=cimod10;end;top:=max;/寻找第一个有效数字的位置whilectop=0dotop:=top-1;fori:=topdownto1dowrite(ci);/倒序输出end.,试一试两个大整数的减法运算?cab(减法运算时不需要再做“进位”的处理，但是需要进行”借位”，先减再判断是否为负数，是的话被减数的高位数字减1，差数加10。)注：前面算法用在减法时的漏洞是无法处理小数减大数的情况,constmax=100;Vars1,s2:string;a,b,c:array1.maxofinteger;i,top,k1,k2:integer;beginreadln(s1);k1:=length(s1);readln(s2);k2:=length(s2);Fori:=1tok1doak1-i+1:=ord(s1i)-ord(0);Fori:=1tok2dobk2-i+1:=ord(s2i)-ord(0);Fori:=1tomaxdoci:=ai-bi;Fori:=1tomaxdobeginifci0thenbeginci:=ci+10;ci+1:=ci+1-1end;top:=max;whilectop=0dotop:=top-1;fori:=topdownto1dowrite(ci);end.,两个大数的乘法(选读),两个大整数的乘法运算,基本方法输入串S1和串S2，S1和S2分别转化为整数数组a和b乘法运算ca*b逐个进位处理判断最高位的位置,Vara,b,c:array1.10000oflongint;L1,L2,i,j,k:longint;s1,s2:string;Beginreadln(s1);L1:=length(s1);fori:=1toL1doaL1-i+1:=ord(s1i)-ord(0);/s1转化为整数数组areadln(s2);L2:=length(s2);fori:=1toL2dobL2-i+1:=ord(s2i)-ord(0);/s2转化为整数数组bfori:=L1downto1doforj:=L2downto1doci+j-1:=ci+j-1+ai*bj;/逐位相乘k:=L1+L2-1;/乘积的总长度至少是L1+L2-1，比如11*12是三位fo