高精度运算及其应用
- 格式：doc
- 大小：178.00 KB
- 文档页数：13
Jsoi2010春季函授讲义（B2） 1/13
高精度运算及其应用
一、引言
利用计算机进行数值运算，经常会遇到数值太大，超出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;
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;
for i:=1 to l2 do Jsoi2010春季函授讲义（B2） 2/13
b[i]:=ord(s2[l2+1-i])-48; {以上是把两个高精度数逐位处理并转存到a、b两个数组中}
if l1>l2 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.
[思考和练习]
1、 如果要一边加一边进位，程序怎么修改？你觉得好不好？
2、 如果输入的数再大一点，比如1000位，还好用String类型读入吗？程序怎么修改？
3、 请你编写一个高精度减法的程序，注意结果的正负。
2、高精度乘法
例2、编程求n!的值，n<1000。
说明：n!表示1*2*3*„*n，例如3！=1*2*3，5！=1*2*3*4*5
[问题分析]
假如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:’);
readln(n);
for i:=1 to max do a[i]:=0; {数组初始化}
a[1]:=1; {1！=1}
h:=1; {h表示n!的位数}
for i:=2 to n do {模拟乘的过程}
begin Jsoi2010春季函授讲义（B2） 3/13
for j:=1 to h do a[j]:=a[j]*i; {逐位乘}
for j:=1 to h do {以下为统一处理进位}
if a[j]>=10 then begin
a[j+1]:=a[j+1]+a[j] div 10; {和高精度加法有何区别？}
a[j]:=a[j] mod 10;
end;
while a[h+1]>0 do {最高位的进位处理，和高精度加法有何区别？}
begin
h:=h+1;
a[h+1]:=a[h] div 10;
a[h]:=a[h] mod 10;
end;
if a[h+1]>0 then h:=h+1;
end;
write(n,'!='); {输出}
for i:=h downto 1 do write(a[i]);
readln;
end.
[运行示例]
输入：input n:500
输出：
500!=1220136825991110068701238785423046926253574342803192842192413588385845373153881997605496447502203281863013616477148203584163378722078177200480785205159329285477907571939330603772960859086270429174547882424912726344305670173270769461062802310452644218878789465754777149863494367781037644274033827365397471386477878495438489595537537990423241061271326984327745715546309977202781014561081188373709531016356324432987029563896628911658974769572087926928871281780070265174507768410719624390394322536422605234945850129918571501248706961568141625359056693423813008856249246891564126775654481886506593847951775360894005745238940335798476363944905313062323749066445048824665075946735862074637925184200459369692981022263971952597190945217823331756934581508552332820762820023402626907898342451712006207714640979456116127629145951237229913340169552363850942885592018727433795173014586357570828355780158735432768888680120399882384702151467605445407663535984174430480128938313896881639487469658817504506926365338175055478128640000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
[思考和练习]
1、 如果要问你n!的结果有多少位，要不要做高精度运算，怎么做最好？请编程完成。
2、 如果要问你n!的结果后面有多少个连续的0，要不要做高精度运算，怎么做最好？请编程完成。
例3、输入两个高精度正整数m,n（m,n都在200位以内），输出它们的乘积。
[问题分析]
本题为一个高精度数乘以另一个高精度数。算法思想仍然是模拟乘法的过程，用一个数的每一位（从Jsoi2010春季函授讲义（B2） 4/13
低位开始）逐位与另一个数的每一位相乘，同时处理进位。程序如下：
[参考程序]
Program ex3(input,output);
const max=200;
var s1,s2:string;
a,b:array[1..max] of integer;
c:array[1..max*max] of integer;
l1,l2,w,jw,h,i,j,f:longint;
begin
assign(input,'t3.in'); {文件输入输出}
