高精度计算Word格式文档下载.docx
- 文档编号:6788367
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:15
- 大小:18.78KB
高精度计算Word格式文档下载.docx
《高精度计算Word格式文档下载.docx》由会员分享,可在线阅读,更多相关《高精度计算Word格式文档下载.docx(15页珍藏版)》请在冰点文库上搜索。
varla:
b:
lb:
longint);
{利用过程实现}
var
i,x:
begin
ifla>
=lb
thenx:
=la
elsex:
=lb;
=1toxdo
a[i]:
=a[i]+b[i];
a[i+1]:
=a[i+1]+a[i]div10;
=a[i]mod10;
end;
whilea[x+1]<
0do
x:
=x+1;
=x;
{最高位若有进位,则长度增加}
高精度减法运算(a>
b)
依照由低位至高位的顺序进行减法运算。
在每一次位运算中,若出现不够减的情况,则向高位借位。
在进行了la位的减法后,若最高位为零,则a的长度减1(一位一位测试,直到确切长度)。
a,b:
la,lb:
longint;
procedureminus(vara:
i:
word;
ifa[i]<
b[i]
thenbegin
dec(a[i+1]);
=a[i]+10;
=a[i]-b[i];
while(a[la]=0)and(la>
1)do
dec(la);
高精度乘法运算
按照乘法规则,从a的第1位开始逐位与c(c为字节型)相乘。
在第i位乘法运算中,a的i位与c的乘积必须加上i-1位的进位,然后规整积的i-1位。
其中C为小于10的整数,如果不是小于10的整数,则按位分解该数。
numtype=array[1..1000]ofword;
proceduremultiply(vara:
c:
word);
a[1]:
=a[1]*c;
=2tolado
=a[i]*c;
=a[i]+a[i-1]div10;
a[i-1]:
=a[i-1]mod10;
whilea[la]>
=10do
inc(la);
a[la]:
=a[la-1]div10;
a[la-1]:
=a[la-1]mod10;
压位高精度
扩大进制数改善高精度运算效率
朴素高精度采用1位一存的朴素方法,那为什么不能充分利用已经很快的longint计算呢?
要知道,算1+1=2和10+10=20时间上不会差很多的!
把数字看成10000位数字用longint存
把数字看成100000000位数字用int64存
把数字看成2^k位数字采用位运算快速运算
用整数数组每一个元素表示一个十进制整数的方法存在的缺点是:
如果十进制的位数很多,则对应的数组的长度会很长,并增加了高精度计算的时间。
如果用一个元素记录2位数字、3位数字或更多位数字,则数组的长度可以明显缩小,但是还要考虑数的取值范围问题,必须保证程序运行过程中不越界。
在权衡了两方面的情况后得出:
用一个longint记录4位数字是最佳的方案。
那么这个数组就相当于一个10000进制的数,其中每一个元素都是10000进制下的一位数。
一、数据类型定义:
numtype=array[1..10000]oflongint;
{可以存储40000位十进制数}
a,n:
la,ln:
ansistring;
{任意长度的字符串类型}
二、整数数组的建立和输出
readln(s);
k:
fori:
=1tokdo
j:
=(k-i+4)div4;
n[j]:
=n[j]*10+ord(s[i])-48;
end;
ln:
=(k+3)div4;
当得出最后结果n后,必须按照次高位到最低位的顺序,将每一位元素由10000进制数转换成十进制数,即必须保证每个元素对应4位十进制数。
例如n[i]=0015(0<
=i<
=ln-2),对应的十进制数不能为15,否则会导致错误结果。
可以按照如下方法输出n对应的十进制数:
write(n[ln]);
=ln-1downto1do
write(n[i]div1000,(n[i]div100)mod10,(n[i]div10)mod10,n[i]mod10);
三、基本运算
两个10000进制整数的加法和减法与前面的十进制运算方法类似,只是进制变成了10000进制。
1、整数数组减1(n:
=n-1,n为整数数组)
从n[1]出发寻找第一个非零的元素,由于接受了低位的借位,因此减1,其后缀全为9999。
如果最高位为0,则n的长度减1。
j:
=1;
while(n[j]=0)doinc(j);
{寻找第一个非零的元素}
dec(n[j]);
{该位接受低位的借位,因此减1}
=1toj-1do
n[i]:
=9999;
{其后缀全为9999}
if(j=ln)and(n[j]=0){如果最高位为0,则n的长度减1}
thendec(ln);
2、整数数组除以整数(a:
=adivi,a为整数数组,i为整数)
按照从高位到低位的顺序,逐位相除,把余数乘进制后加到下一位继续相除。
如果最高位为0,则a的长度减1。
l:
=0;
forj:
=ladownto1do
inc(a[j],l*10000);
=a[j]modi;
a[j]:
=a[j]divi;
whilea[la]=0dodec(la);
3、两个整数数组相乘(a:
=a*n,a和n为整数数组)
按照从高位到低位的顺序,将数组a的每一个元素与n相乘。
proceduremultiply(a,b:
la,lb:
vars:
varls:
i,j:
=1tolbdo
s[i+j-1]:
=s[i+j-1]+a[i]*b[j];
=1tola+lb-1do
s[i+1]:
=s[i+1]+s[i]div10000;
s[i]:
=s[i]mod10000;
ifs[la+lb]=0
thenls:
=la+lb-1
elsels:
=la+lb;
2.计算结果位数确定
用数学方法确定。
利用对数函数(ln)。
3.进位与借位处理
加法:
ifa[i]>
10thenbegina[i]=a[i]-10;
a[i+1]=a[i+1]+1
减法:
ifa[i]<
b[i]thenbegina[i]=a[i]+10;
a[I1]=a[i+1]-1
乘法:
y=a[i]*b[i]+c;
c=ydiv10;
a[i]=ymod10
4.商与余数处理
除法:
商=ADIVB,余数=AMODB
运算符重载
Operator运算符(a,b:
数据类型):
数据类型
Overload可加可不加
顺带提一下Overload的妙用
ProcedureSwap(vara,b:
longint);
hp);
overload;
可以用同样的过程名表示不同的过程
自定义高精度类型typehp=array[0..1000]oflongint
数字位数用a[0]贮存
如果需要符号位用a[-1]贮存
Operator+(a,b:
HP)c:
HP;
Vari,l:
Begin
ifa[0]>
b[0]thenl:
=a[0]elsel:
=b[0];
fillchar(c,sizeof(c),0);
Fori:
=1toldo
Begin
inc(c[i],(a[i]+b[i])ModKM);
c[i+1]:
=(a[i]+b[i])DivKM;
End;
ifc[l+1]<
0theninc(l);
c[0]:
=l;
End;
Operator*(a,b:
Vari,j,l:
=1toa[0]do
Forj:
=1tob[0]do
inc(c[i+j-1],a[i]*b[j]);
inc(c[i+j],c[i+j-1]DivKM);
c[i+j-1]:
=c[i+j-1]ModKM;
=a[0]+b[0]+1;
while(l>
1)and(c[l]=0)dodec(l);
Operator*(a:
b:
longint)c:
inc(c[i],a[i]*b);
=c[i]divKM;
c[i]:
=c[i]modKM;
=a[0];
whilec[l]>
KMdo
c[l+1]:
=c[l]divKM;
c[l]:
=c[l]modKM;
inc(l);
Operator/(a:
Var//d:
i,l:
d:
=ldownto1do
=d*KM+a[i];
=ddivb;
=dmodb;
While(L>
Operator>
(a,b:
boolean;
vari:
b[0]thenexit(true)else
ifa[0]<
b[0]thenexit(false);
=a[0]downto1do
ifa[i]>
b[i]thenexit(true)else
b[i]thenexit(false);
exit(false);
练习题:
用高精度计算出s=1!
+2!
+3!
+...+100!
programjiecheng;
s,t:
ls,lt,i:
=a[i+1]+a[i]div10000;
=a[i]mod10000;
=a[i]+a[i-1]div10000;
=a[i-1]mod10000;
=10000do
=a[la-1]div10000;
=a[la-1]mod10000;
lt:
t[1]:
ls:
=1to100do
multiply(t,lt,i);
plus(s,ls,t,lt);
write(s[ls]);
=ls-1downto1do
write(s[i]div1000,(s[i]div100)mod10,(s[i]div10)mod10,s[i]mod10);
writeln;
保留100位有效数字
【题目描述】
输入任意两个整数a,b(a,b均在长整型范围内),计算a/b的结果,保留100位有效数字,最后一位要求四舍五入。
【输入格式】
两个数a,b
【输出格式】
a/b的商,保留100位有效数字
【输入样例】
12913
【输出样例】
9.923076923076923076923076923076923076923076923076923076923076923076923076923076923076923076923076923
窗体顶端
【解题思路】
窗体底端
保留100位有效数字不代表保留100位小数。
比如说,商的整数部分为5位数,则只应算到小数点后第95位;
而如果商的第1个有效数字从万分位开始,则应算到小数点后第103位。
programproject11;
a:
extended;
read(a,b);
c:
=adivb;
r:
=amodb;
ifc=0
thenlc:
=0
elsebegin
str(c,s);
lc:
write(c,'
.'
=1to100-lcdo
=i;
=r*10;
ifr<
thenwhiler<
bdo
x[i]:
=i+1;
=rdivb;
x[j]:
=c;
=rmodb;
write(x[i]);
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 高精度 计算