设有2个10进制的n(n>10)位正整数,设计其适当的数据结构与算法,实现这2个数的加法

设有2个10进制的n(n>10)位正整数,设计其适当的数据结构与算法,实现这2个数的加法
设有2个10进制的n(n>10)位正整数,设计其适当的数据结构与算法,实现这2个数的加法

设有2个10进制的n(n>10)位正整数,设计其适当的数据结构与算法,实现这2个数的加法
pascal 高精度
高精度运算是指:当参与运算的数范围大大超出了标准数据类型（整型,实型）能表示的范围的运算时,通过数组、字串的形式,进行适当处理的方法.
&>16; 高精度加法
1、加数、减数、运算结果的输入和存储
用数组和字符串表示数据、结果.
（1）数组表示：每个数组元素存储1位,有多少位就需要多少个数组元素；（优化重点）
优点：每一位都是数的形式,可以直接加减；运算时非常方便
缺点：数组不能直接输入；输入时每两位数之间必须有分隔符,不符合数值的输入习惯；
（2）字符串表示：字符串的最大长度是255,可以表示255位.
优点：能直接输入输出,输入时,每两位数之间不必分隔符,符合数值的输入习惯；
缺点：每一位是一个字符,不能直接进行运算,必须先将它转化为数值再进行运算；
（3）综合以上所述,对两种数据结构取长补短：用字符串读入数据,用数组存储数据：
var s:string;{字符串最多可以表示255位}
a,b,c:array [1..260] of integer; {定义数组存放数字}
i,la,lb:integer;
begin
readln(s); {读入第一个字符串}
la:=length(s);{求出s的长度,也即第一个数的位数； }
for i:=1 to la do {将字符串的每一位字符转化为数字,并倒序存入数组a}
a[i]:=ord(s[la-i+1])-ord(‘0’)
readln(s);
lb:=length(s);{求出s的长度,也即第二个数的位数； }
for i:=1 downto lb do
a[i]:=ord(s[lb-i+1])-ord(‘0’)
end;
2、运算过程：模拟手工计算
（1）运算顺序：从低位向高位运算；先计算低位再计算高位；
（2）运算规则：同一位的两个数相加再加上从低位来的进位,成为该位的和；这个和去掉向高位的进位就成为该位的值；如上例：3+8+1=12,向前一位进1,本位的值是2；可借助MOD、DIV运算完成这一步；
（3）最后一位的进位：如果完成两个数的相加后,进位位值不为0,则应添加一位；
（4）如果两个加数位数不一样多,则按位数多的一个进行计算；
if la>=lb then len:=la else len:=lb;
y:=0 {y表示进位,初值为0}
for i:=1 to len do do
begin
x:=a[i]+b[i]+y; c[i]:=x mod 10; y:=x div 10;
// c[i]:=a[i]+b[i]+c[i];c[i+1]:=c[i] div 10; c[i]:=c[i] mod 10
end;
if y0 then len:=len+1;
//if c[len+1]>0 then len:=len+1;
3、结果的输出（优化重点）:按运算结果的实际位数输出
for i:=len downto 1 do write(c[i]);
完整程序:高精度加法
program bigPlus;
var
a,b,c: array[1..260] of integer;
la,lb,len,i:integer;
s:string;
procedure init;
begin
fillchar(a,sizeof(a),0);
fillchar(b,sizeof(b),0);
fillchar(c,sizeof(c),0);
readln(s);
la:=length(s);
for i:=1 to la do a[la-i+1]:=ord(s[i])-ord('0');
readln(s);
lb:=length(s);
for i:=1 to lb do b[lb-i+1]:=ord(s[i])-ord('0');
if la>=lb then len:=la else len:=lb;
end;
begin
init; {调用初始化过程}
for i:=1 to len do
begin
c[i]:=a[i]+b[i]+c[i];
c[i+1]:=c[i] div 10;
c[i]:=c[i] mod 10;
end;
if c[len+1]0 then len:=len+1;
for i:=len downto 1 do write(c[i]);
readln;
end.
4、优化：
以上的方法的有明显的缺点：
（1）浪费空间：一个整型变量（-32768~32767）只存放一位（0~9）；
（2）浪费时间：一次加减只处理一位；
针对以上问题,我们做如下优化：一个数组元素存放四位数；（integer的最大范围是32767,5位的话可能导致出界）.具体方法：
a.初始化过程要改变:
procedure init;
begin
fillchar(a,sizeof(a),0);
fillchar(b,sizeof(b),0);
fillchar(c,sizeof(c),0);
readln(s);
la:=length(s)
for i:=1 to la do
begin
j:=(la-i)div 4+1;
a[j]:=a[j]*10+ord(s[i])-48;
end;
readln(s);
lb:=length(s);
for i:=1 to lb do
begin
j:=(lb-i)div 4 +1;
b[j]:=b[j]*10+ord(s[i])-48;
end;
la:=(la+3) div 4;
lb:=(lb+3) div 4;
if la>=lb then len:=la else len:=lb;
end;
b.运算过程要改变 mod 10000 div 10000
c.输出要改变:
if c[len+1]>0 then len:=len+1;
write(c[len]);
for i:=len-1 downto 1 do
begin
if c[i]b[0] then len:=a[0] else len:=b[0];
for i:=1 to len do begin
inc(c[i],a[i]+b[i]);
if c[i]>10 then begin dec(c[i],10); inc(c[i+1]); end; {进位}
end;
if c[len+1]>0 then inc(len);
c[0]:=len;
end;{plus}

2．高精度减法
procedure substract(a,b:hp;var c:hp);
var i,len:integer;
begin
fillchar(c,sizeof(c),0);
if a[0]>b[0] then len:=a[0] else len:=b[0];
for i:=1 to len do begin
inc(c[i],a[i]-b[i]);
if c[i]1) and (c[len]=0) do dec(len);
c[0]:=len;
end;

3．高精度乘以低精度
procedure multiply(a:hp;b:longint;var c:hp);
var i,len:integer;
begin
fillchar(c,sizeof(c),0);
len:=a[0];
for i:=1 to len do begin
inc(c[i],a[i]*b);
inc(c[i+1],(a[i]*b) div 10);
c[i]:=c[i] mod 10;
end;
inc(len);
while (c[len]>=10) do begin {处理最高位的进位}
c[len+1]:=c[len] div 10;
c[len]:=c[len] mod 10;
inc(len);
end;
while (len>1) and (c[len]=0) do dec(len); {若不需进位则调整 len}
c[0]:=len;
end;{multiply}

4．高精度乘以高精度
procedure high_multiply(a,b:hp; var c:hp}
var i,j,len:integer;
begin
fillchar(c,sizeof(c),0);
for i:=1 to a[0] do
for j:=1 to b[0] do begin
inc(c[i+j-1],a[i]*b[j]);
inc(c[i+j],c[i+j-1] div 10);
c[i+j-1]:=c[i+j-1] mod 10;
end;
len:=a[0]+b[0]+1;
while (len>1) and (c[len]=0) do dec(len);
c[0]:=len;
end;

5．高精度除以低精度
procedure devide(a:hp;b:longint; var c:hp; var d:longint);
{c:=a div b; d:= a mod b}
var i,len:integer;
begin
fillchar(c,sizeof(c),0);
len:=a[0]; d:=0;
for i:=len downto 1 do begin
d:=d*10+a[i];
c[i]:=d div b;
d:=d mod b;
end;
while (len>1) and (c[len]=0) then dec(len);
c[0]:=len;
end;

6．高精度除以高精度
procedure high_devide(a,b:hp; var c,d:hp);
var
i,len:integer;
begin
fillchar(c,sizeof(c),0);
fillchar(d,sizeof(d),0);
len:=a[0];d[0]:=1;
for i:=len downto 1 do begin
multiply(d,10,d);
d[1]:=a[i];
while(compare(d,b)>=0) do {即 d>=b}
begin
Subtract(d,b,d);
inc(c[i]);
end;
end;
while(len>1)and(c.s[len]=0) do dec(len);
c.len:=len;
end;