没有合适的资源?快使用搜索试试~ 我知道了~
高精度加减乘除算法.doc
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 47 浏览量
2022-05-07
10:08:25
上传
评论
收藏 74KB DOC 举报
温馨提示
试读
25页
高精度加减乘除算法.doc
资源推荐
资源详情
资源评论
高精度运算
所谓的高精度运算,是指参与运算的数(加数,减数,因子……)范围大大超出了标准数据类型(整型,实型)能表示的范
围的运算。例如,求两个 200 位的数的和。这时,就要用到高精度算法了。在这里,我们先讨论高精度加法。高精度
运算主要解决以下三个问题:
基本方法
1、加数、减数、运算结果的输入和存储
运算因子超出了整型、实型能表示的范围,肯定不能直接用一个数的形式来表示。在 Pascal 中,能表示多个数的数据
类型有两种:数组和字符串。
(1)数组:每个数组元素存储 1 位(在优化时,这里是一个重点!),有多少位就需要多少个数组元素;
用数组表示数的优点:每一位都是数的形式,可以直接加减;运算时非常方便
用数组表示数的缺点:数组不能直接输入;输入时每两位数之间必须有分隔符,不符合数值的输入习惯;
(2)字符串:字符串的最大长度是 255,可以表示 255 位。
用字符串表示数的优点:能直接输入输出,输入时,每两位数之间不必分隔符,符合数值的输入习惯;
用字符串表示数的缺点:字符串中的每一位是一个字符,不能直接进行运算,必须先将它转化为数值再进行运算;运
算时非常不方便;
(3)因此,综合以上所述,对上面两种数据结构取长补短:用字符串读入数据,用数组存储数据:
var s1,s2:string;
a,b,c:array [1..260] of integer;
i,l,k1,k2:integer;
begin
write('input s1:');readln(s1);
write('input s2:');readln(s2);
{————读入两个数 s1,s2,都是字符串类型}
l:=length(s1);{求出 s1 的长度,也即 s1 的位数;有关字符串的知识。}
k1:=260;
for i:=l downto 1 do
begin
a[k1]:=ord(s1)-48;{将字符转成数值}
k1:=k1-1;
end;
k1:=k1+1;
{————以上将 s1 中的字符一位一位地转成数值并存在数组 a 中;低位在后(从第 260 位开始),高位在前
(每存完一位,k1 减 1)}
对 s2 的转化过程和上面一模一样。
2、运算过程
在往下看之前,大家先列竖式计算 35+86。
注意的问题:
(1)运算顺序:两个数靠右对齐;从低位向高位运算;先计算低位再计算高位;
(2)运算规则:同一位的两个数相加再加上从低位来的进位,成为该位的和;这个和去掉向高位的进位就成为该位的
值;如上例:3+8+1=12,向前一位进 1,本位的值是 2;可借助 MOD、DIV 运算完成这一步;
(3)最后一位的进位:如果完成两个数的相加后,进位位值不为 0,则应添加一位;
(4)如果两个加数位数不一样多,则按位数多的一个进行计算;
if k1>k2 then k:=k1 else k:=k2;
y:=0;
for i:=260 downto k do
begin
x:=a+b+y;
c:=x mod 10;
y:=x div 10;
end;
if y<>0 then begin k:=k-1;c[k]:=y; end;
3、结果的输出(这也是优化的一个重点)
按运算结果的实际位数输出
for i:=k to 260 do write(c);
writeln;
求两个数的加法
program sum;
var s,s1,s2:string;
a,b,c:array [1..260] of integer;
i,l,k1,k2:integer;
begin
write('input s1:');readln(s1);
write('input s2:');readln(s2);
l:=length(s1);
k1:=260;
for i:=l downto 1 do
begin
a[k1]:=ord(s1)-48;
k1:=k1-1;
end;
k1:=k1+1;
l:=length(s2);
k2:=260;
for i:=l downto 1 do
begin
b[k2]:=ord(s2)-48;
k2:=k2-1;
end;
k2:=k2+1;
if k1>k2 then k:=k2 else k:=k1;
y:=0;
for i:=260 downto k do
begin
x:=a+b+y;
c:=x mod 10;
y:=x div 10;
end;
if y<>0 then begin k:=k-1;c[k]:=y;
end;
for i:=k to 260 do write(c);
writeln;
end.
优化:
以上的方法的有明显的缺点:
(1)浪费空间:一个整型变量(-32768~32767)只存放一位(0~9);
(2)浪费时间:一次加减只处理一位;
针对以上问题,我们做如下优化:一个数组元素存放四位数;(integer 的最大范围是 32767,5 位的话可能导致出
界)。具体方法:
l:=length(s1);
k1:=260;
repeat
s:=copy(s1,l-3,4);
val(s,a[k1],code);
k1:=k1-1;
s1:=copy(s1,1,l-4);
l:=l-4;
until l<=0;
k1:=k1+1;
而因为这个改进,算法要相应改变:
(1)运算时:不再逢十进位,而是逢万进位(mod 10000; div 10000);
(2)输出时:最高位直接输出,其余各位,要判断是否足够 4 位,不足部分要补 0;例如:1,23,2345 这样三段
的数,输出时,应该是 100232345 而不是 1234567。
改进后的算法:
program sum;
var s1,s2:string;
a,b,c:array [1..260] of integer;
i,l,k1,k2,code:integer;
begin
write('input s1:');readln(s1);
write('input s2:');readln(s2);
l:=length(s1);
k1:=260;
repeat
s:=copy(s1,l-3,4);
val(s,a[k1],code);
k1:=k1-1;
s1:=copy(s1,1,l-4);
l:=l-4;
until l<=0;
k1:=k1+1;
l:=length(s2);
k2:=260;
repeat
s:=copy(s2,l-3,4);
val(s,b[k2],code);
k2:=k2-1;
s2:=copy(s2,1,l-4);
l:=l-4;
until l<=0;
k2:=k2+1;
if k1<k2 then k:=k1 else k:=k2;
y:=0;
for i:=260 downto k do
begin
x:=a+b+y;
c:=x mod 10000;
y:=x div 10000;
end;
if y<>0 then begin k:=k-1;c[k]:=y;end;
write(c[k]);
for i:=k+1 to 260 do
begin
----if c<1000 then write('0');
----if c<100 then write('0');
----if c<10 then write('0');
----write(c);
end;
剩余24页未读,继续阅读
资源评论
老帽爬新坡
- 粉丝: 82
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功