高精度运算--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 这个数字范围很大，但可以分割、转化为数组进行处理和输出。 3 6 2 8 8 0 0 S[7] S[6] S[5] S[4] S[3] S[2] S[1] 在处理之前，首先要解决输入的问题，对于范围特别大的数字一般通过字符串进行输入。 　字符串 string 　　字符串可以按照下标直接引用，如字符串S: “abcde888edcba”，S[5]即字符“e”。这种引用方法和数组是一样的，所以可以把字符串看成一种特殊的字符型数组。 　　但是，字符串有一些字符数组所没有的方便之处。其中，最方便的地方是编译系统通常都为字符串内置了许多常用的函数（对普通的字符数组则没有），这对编写程序有很大好处。而且，PASCAL语言内置的字符串函数比C语言要多一些。 一、字符串的定义 关键字 String 　例: a, b, c: string;  定义了三个字符串，默认长度为255； 　例: d : string[100];  定义了一个长度为100的字符串； 二、字符串的输出 不需要循环 　例: Write (a); 输出整个字符串a  Write (a[2]); 输出字符串的第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);For i:=1 to k do data[k-i+1] := ord(s[i]) － ord(‘0’) ; 函数ord求的是字符在ASCII表的位置，该位置减去字符’0’的位置，得到位置差。位置差就是该数字。 0 0 9 9 9 9 9 数组a 0 0 8 8 8 8 8 数组b 0 0 17 17 17 17 17 相加得数组c 这时直接输出会得到1717171717，显然不对，因此要逐位处理一下。 数组c 0 0 17 17 17 17+1 7 商 往前进：c[i+1]:=c[i+1] + c[i] div 10 ; 余数 留下：c[i]:=c[i] mod 10 ; 注意：上面两步的顺序不能颠倒！！！ 数组c 0 0 17 17 17+1 8 7 数组c 0 0 17 17+1 8 8 7 数组c 0 0 17+1 8 8 8 7 数组c 0 1 8 8 8 8 7 逐位处理完毕后，就可以倒序输出了，但是为了避免输出左边没用的零，要先