高精度运算及其应用
一、引言
利用计算机进行数值运算，经常会遇到数值太大，超出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:ax] 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
    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。
说明：c 字符串数组怎么定义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:ax] 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
      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位以内），输出它们的乘积。
[问题分析]
本题为一个高精度数乘以另一个高精度数。算法思想仍然是模拟乘法的过程，用一个数的每一位（从低位开始）逐位与另一个数的每一位相乘，同时处理进位。程序如下：
[参考程序]
Program  ex3(input,output);
const max=200;
var s1,s2:string;
    a,b:ax] of integer;
    c:ax*max] of integer;
    l1,l2,w,jw,h,i,j,f:longint;
begin
  assign(input,'t3.in');        {文件输入输出}
  assign(output,'t3.out');
  reset(input);
  rewrite(output);
  readln(s1);                    {读入及预处理}
  readln(s2);
  l1:=length(s1);
  l2:=length(s2);
  for i:=1 to max do begin a[i]:=0;b[i]:=0;end;
  for i:=1 to max*max do c[i]:=0;
  for i:=1 to l1 do
    a[i]:=ord(s1[l1+1-i])-48;
  for i:=1 to l2 do
    b[i]:=ord(s2[l2+1-i])-48;
  jw:=0;                          {逐位乘}
  for i:=1 to l1 do
    for j:=1 to l2 do

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。