高精度运算及其应用.doc

Jsoi2010春季函授讲义（B2）/NUMPAGES13
高精度运算及其应用

一、引言
利用计算机进行数值运算，经常会遇到数值太大，超出Longint、int64等系统标准数据类型的有效范围，如计算mn，而m、n≤100；有时又会遇到对运算的精度要求特别高的情况，如计算圆周率π，要求精确到小数点后100位，此时real、double等数据类型也无能为力。这些情况下，我们都要用“高精度运算”来解决。
一般我们将小数点后几百位或者更多，当然也可能是几千亿几百亿的大数字统称为高精度数。
高精度运算首先要解决存储问题。一般都是定义一个一维数组来存储一个高精度数，用每一个数组元素存储该数的每一位或某几位。
高精度数的读入可以采用两种方法，一是采用字符串（String,AnsiString）方式一起读入，再逐位处理成数字存储在数组中；另一种方法是一位一位读入并存储到数组中。在实际使用时，请大家注意比较各自的优、缺点。
高精度运算一般都是采用模拟的方法解决。输出时一定要注意格式和精度。

二、高精度运算
1、编程实现高精度加法
[问题描述]输入两个正整数（最多250位），输出它们的和。
比如输入：999999999999999999999999999999999999999999999999999999
12345678999999999999999999999999
输出：add=1000000000000000000000012345678999999999999999999999998

[问题分析]
只要模拟“加法运算”的过程，从低位（对齐）开始逐位相加，最后再统一处理进位即可。

[参考程序]
Programex1(input,output);
constmax=250;
vars1,s2:string;
a,b,c:array[1..max]ofbyte;
l1,l2,l,i:integer;
begin
writeln('inputtwolargeinteger:');
readln(s1);
readln(s2);{用字符串方式读入两个高精度数}
l1:=length(s1);
l2:=length(s2);
fori:=1tomaxdobegina[i]:=0;b[i]:=0;c[i]:=0;end;{注意一定要初始化}
fori:=1tol1do
a[i]:=ord(s1[l1+1-i])-48;
fori:=1tol2do
b[i]:=ord(s2[l2+1-i])-48;{以上是把两个高精度数逐位处理并转存到a、b两个数组中}

ifl1>l2thenl:=l1elsel:=l2;
fori:=1toldoc[i]:=a[i]+b[i];{对应位相加}

fori:=1toldo{从低位到高位，统一处理进位}
ifc[i]>=10then
begin
c[i]:=c[i]-10;
c[i+1]:=c[i+1]+1;
end;
ifc[l+1]>0thenl:=l+1;

write('add=');{输出}
fori:=ldownto1dowrite(c[i]);
readln;
end.

[思考和练习]
如果要一边加一边进位，程序怎么修改？你觉得好不好？
如果输入的数再大一点，比如1000位，还好用String类型读入吗？程序怎么修改？
请你编写一个高精度减法的程序，注意结果的正负。

2、高精度乘法
例2、编程求n!的值，n<1000。
说明：n!表示1*2*3*…*n，例如3！=1*2*3，5！=1*2*3*4*5
[问题分析]
假如100!算好了（这个结果显然是一个高精度数），那么101！就只要在这个值的基础上再乘以101即可（相对于高精度数，101这个数称为单精度数），一般我们把这种高精度乘法称为“高精度数乘以单精度数”。程序如下：

[参考程序]
Programex2(input,output);
constmax=10000;{数组的长度必须要开的足够大，为什么？}
vara:array[1..max]ofinteger;{能否把integer改成byte，为什么？}
n,h,i,j:integer;
begin
write(‘inputn:’);
readln(n);
fori:=1tomaxdoa[i]:=0;{数组初始化}
a[1]:=1;{1！=1}
h:=1;{h表示n!的位数}
fori:=2tondo{模拟乘的过程}
begin
forj:=1tohdoa[j]:=a[j]*i;{逐位乘}
forj:=1tohdo{以下为统一处理进位}
ifa[j]>=10thenbegin
a[j+1]:=a[j+1]+a[j]div10;{和高精度加法有何区别？}
a[j]:=a[j]m