高精度运算资料.docVIP

Jsoi2007春季函授 B层次讲义（2） PAGE 10/ NUMPAGES 10 高精度运算 一、引言 利用计算机进行数值运算，经常会遇到数值太大，超出Longint、int64等系统标准数据类型的有效范围，如计算mn，而m、n≤100；有时又会遇到对运算的精度要求特别高的情况，如计算圆周率π，要求精确到小数点后100位，此时real、double等数据类型也无能为力。这些情况下，我们都要用“高精度运算”来解决。 高精度运算首先要解决存储问题。一般都是定义一个一维数组来存储一个高精度数，用每一个数组元素存储该数的每一位。 高精度数的读入可以采用两种方法，一是采用字符串（String,AnsiString）方式一起读入，再逐位处理成数字存储在数组中；另一种方法是一位一位读入并存储到数组中。在实际使用时，请大家注意比较各自的优、缺点。 高精度运算一般都是采用模拟的方法解决。输出时一定要注意格式和精度。 二、高精度运算 1、编程实现高精度加法 [问题描述] 输入两个正整数（最多250位），输出它们的和。 比如输入：999999999999999999999999999999999999999999999999999999 12345678999999999999999999999999 输出：add=1000000000000000000000012345678999999999999999999999998 [问题分析] 只要模拟“加法运算”的过程，从低位（对齐）开始逐位相加，最后再统一处理进位即可。 [参考程序] Program ex1(input,output); const max=250; var s1,s2:string; {最多255位} a,b,c:array[1..max] of byte; l1,l2,l,i:integer; begin writeln(input two large integer:); readln(s1); readln(s2); {用字符串方式读入两个高精度数} l1:=length(s1); l2:=length(s2); for i:=1 to max do begin a[i]:=0;b[i]:=0;c[i]:=0;end; {注意一定要初始化} for i:=1 to l1 do a[i]:=ord(s1[l1+1-i])-48; {ord(‘0’)=48 } for i:=1 to l2 do b[i]:=ord(s2[l2+1-i])-48; {以上是把两个高精度数逐位处理并转存到a、b两个数组中} if l1l2 then l:=l1 else l:=l2; for i:=1 to l do c[i]:=a[i]+b[i]; {对应位相加} for i:=1 to l do {从低位到高位，统一处理进位} if c[i]=10 then begin c[i]:=c[i]-10; c[i+1]:=c[i+1]+1; end; if c[l+1]0 then l:=l+1; write(add=); {输出} for i:=l downto 1 do write(c[i]); readln; end. [思考和练习] 如果要一边加一边进位，程序怎么修改？你觉得好不好？ 如果输入的数再大一点，比如1000位，还好用String类型读入吗？程序怎么修改？ 请你编写一个高精度减法的程序，注意结果的正负。 2、高精度乘法 例2、编程求n!的值，n1000。 [问题分析] 假如100!算好了（这个结果显然是一个高精度数），那么101！就只要在这个值的基础上再乘以101即可（相对于高精度数，101这个数称为单精度数），一般我们把这种高精度乘法称为“高精度数乘以单精度数”。程序如下： [参考程序] Program ex2(input,output); const max=10000; {数组的长度必须要开的足够大，为什么？} var a:array[1..max] of integer; {能否把integer改成byte，为什么？} n,h,i,j:integer; begin write(‘input n:’