Question

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

Answer 1

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 y<>0 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]<1000 then write(‘0’) ;
if c[i]<100 then write(‘0’);
if c[i]<10 then write(‘0’);
write(c[i]);
end;

算法要相应改变：
（1）运算时：不再逢十进位，而是逢万进位（mod 10000; div 10000);
（2）输出时：最高位直接输出，其余各位，要判断是否足够4位，不足部分要补0；例如：1，23，2345这样三段的数，输出时，应该是100232345而不是1234567。

&>16; 高精度减法
1、和高精度加法相比，减法在差为负数时处理的细节更多一点：当被减数小于减数时，差为负数，差的绝对值是减数减去被减数；在程序实现上用一个变量来存储符号位，用另一个数组存差的绝对值。
2、算法流程：
（1）读入两个字符串S1，S2（字符串）；
（2）置符号位：判断被减数是否大于减数：大则将符号位置为空；小则将符号位置为“-”，交换减数与被减数；
（3）被减数与减数处理成数值，放在数组中；

（4）运算：
A、取数；
B、判断是否需要借位；
C、减，将运算结果放到差数组相应位中；
D、判断是否运算完成：是，转5；不是，转A；
（5）打印结果：符号位，第1位，循环处理第2到最后一位；

3、细化：
（1）如何判断被减数与减数的大小：
{首先将两个字符串的位数补成一样(因为字符串的比较是从左边对齐的；两个字符串一样长才能真正地比较出大小)：短的在左边补0}
la:=length(s1);
lb:=length(s2);
if la>lb then for i:=1 to la-lb do s2:='0'+s2
else for i:=1 to lb-la do s1:='0'+s1;
{接着比较大小：直接比较字符串大小，s1存被减数，fh存符号}
fh:='';
if s1<s2 then begin fh:='-';s:=s1; s1:=s2; s2:=s; end;
（2）将字符串处理成数值：
la:=length(s1);{求出s1的长度，也即s1的位数。}
for i:=l to la do
a[la-i+1]:=ord(s1[i])-48; {将字符转成数值并倒序放入数组a}
字符串s2的处理方法同上
（3）打印结果：去掉结果中多余的0

完整程序:高精度减法 (未优化,优化方法参照加法的优化)
program bigminus;
var
a,b,c: array[1..260] of integer;
la,lb,len,i:integer;
s1,s2:string;

procedure init;
begin
fillchar(a,sizeof(a),0);
fillchar(b,sizeof(b),0);
readln(s1);
readln(s2);
la:=length(s1);
lb:=length(s2);
if la>lb then for i:=1 to la-lb do s2:='0'+s2
else for i:=1 to lb-la do s1:='0'+s1;
if s1<s2 then begin s:=s1; s1:=s2; s2:=s; write('-');end;
if la>=lb then len:=la else len:=lb;
for i:=1 to len do a[len-i+1]:=ord(s[i])-ord('0');
for i:=1 to len do b[len-i+1]:=ord(s[i])-ord('0');
end;
begin
init; {调用初始化过程}
for i:=1 to len do
begin
c[i]:=a[i]-b[i]+c[i];
if c[i]<0 then
begin c[i]:=c[i]+10;c[i+1]:=c[i+1]-1;end;
end;
while (len>1)and(c[len]=0) then len:=len-1; {调整长度,输出时去掉多余的0}
for i:=len downto 1 do write(c[i]);
readln;
end.
高精度乘法:
(1) 高精度乘以低精度
(2) 高精度乘以高精度
高精度运算的过程汇总:
高精度数的定义：
type
hp=array[1..maxlen] of integer;
1．高精度加法
procedure plus ( 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]>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]<0 then begin inc(c[i],10);dec(c[i+1]); end;
while (len>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;