第一讲:高精度运算加减法篇
类型数值范围占字节数 Byte 0 .. 255 1
Word 0..65535 2
Shortint -128 .. 127 1 Integer -32768..32767; 2 Longint -2147483648 .. 2147483647 4
Longword 0..4294967295 4
Int64 -9223372036854775808 ..
9223372036854775807 8
QWord 0 .. 18446744073709551615 8
//在竞赛学会的最新规定中由于int64在文件操作的不稳定性已经不推荐用了;而且当数据超过1020以后我们就必须要用到高精度运算
高精度算法入门
?高精度运算是指参与运算有数或运算结果远远超过计算机语言中能够表示的数的范围的特殊运算。
?例如:编程解决求A+B的值,其中A,B的值<=1040; ?高精度运算的思想就是运用字符串和一维数组的方式模拟运算
?口诀就是:用字符串读入数据，转化数据类型,用数组存储数据,并加以运算：
高精度运算涉及到的问题：
1、数据的输入。
2、数据的存储。
3、数据的运算：进位和借位。
4、结果的输出：小数点的位置、处理多于的0等。
一、高精度运算：加法题目要求：
输入：
第一行：正整数a。
第二行：正整数b。已知：a和b（<10240）。
输出：a＋b的值。
样例输入：
99
999
样例输出：
1098
高精度加法解决的问题：１、数据的输入。
２、数据的存储。
３、加法运算，注意进位处理。４、结果的输出。
１、数据的输入。
a和b（<10240）
字符串输入：
Var s1,s2:string; Readln(s1);
Readln(s2);
２、数据的存储。
为了计算方便，采用数组存储。
Var a,b:array[1..240] of integer;
将字符串转换为数组存储。
用a存s1，b存s2。
A[1]存个位，便于以后计算和进位处理
S1=’3 4 5 2 3 4 5’
….a[3] a[2] a[1]
len1:=length(s1);
for i:= 1 to len1 do a[i]:=ord(s1[len1+1-i])-48; len2:=length(s2);
for i:= 1 to len2 do b[i]:=ord(s2[len2+1-i])-48;
３、加法运算，注意进位处理。
把计算结果存到数组c中：c：array[1..241] of integer; 先计算。
…….a[3] a[2] a[1]
……b[3] b[2] b[1]
+
……c[3] c[2] c[1]
if len1>len2 then len:=len1 else len:=len2;
for i:=1 to len do c[i]:=a[i]+b[i];{直接先计算}
计算后的c[i]可能>=10,怎样处理？
处理进位：
for i:=1 to len do
begin
c[i+1]:=c[i+1]+c[i] div 10;
c[i]:=c[i] mod 10;
end;
４、结果的输出：数组c。
if c[len+1]>0 then len:=len+1;
for i:=len downto 1 do write(c[i]);
onst maxn=240; {c=a+b,先加，然后再处理进位}
var
s1,s2:string;
a,b:array[1..maxn] of integer;
c:array[1..maxn+1] of integer;
len,len1,len2,k,j,i:integer;
begin
readln(s1); {输入}
readln(s2);
len1:=length(s1); {数据的保存}
for i:= 1 to len1 do a[i]:=ord(s1[len1+1-i])-48;
len2:=length(s2);
for i:= 1 to len2 do b[i]:=ord(s2[len2+1-i])-48;
if len1>len2 then len:=len1 else len:=len2;
for i:=1 to len do c[i]:=a[i]+b[i];
for i:=1 to len do
begin
c[i+1]:=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]);
end.//如果两个数字的长度超过255那么我们在数据的输入的过程中只能用字符数组来完成存储了!
算法改进一：边计算边处理进位。
{c=a+b,边加边处理进位}
const maxn=240;
var
s1,s2:string;
a,b:array[1..maxn] of integer;
c:array[1..maxn+1] of integer;
len,len1,len2,k,j,i:integer;
begin
readln(s1);
readln(s2);
len1:=length(s1);
for i:= 1 to len1 do a[i]:=ord(s1[len1+1-i])-48; len2:=length(s2);
for i:= 1 to len2 do b[i]:=ord(s2[len2+1-i])-48; if len1>len2 then len:=len1 else len:=len2; for i:=1 to len do
begin
c[i+1]:=(a[i]+b[i]+c[i]) div 10;
c[i]:=(a[i]+b[i]+c[i]) mod 10;
end;
if c[len+1]>0 then len:=len+1;
for i:=len downto 1 do write(c[i]);
end.
算法改进二：结果存在数组a中，不再定义多余的数组c，减少存储空间。（最好的方法：a=a+b）
begin
readln(s1);
readln(s2);
len1:=length(s1);
len2:=length(s2);
fillchar(a,sizeof(a),0);
fillchar(b,sizeof(b),0);
for i:=1 to len1 do a[i]:=ord(s1[len1-i+1])-48;
for i:=1 to len2 do b[i]:=ord(s2[len2-i+1])-48;
if len1>len2 then len:=len1 else len:=len2;
for i:=1 to len do
begin
a[i+1]:=a[i+1]+(a[i]+b[i]) div 10;
a[i]:=(a[i]+b[i]) mod 10;
end;
if a[len+1]>0 then len:=len+1;
for i:=len downto 1 do write(a[i]);
writeln;
end.
高精度加法的应用
Fibonacci数列
Fibonacci数列的代表问题是由意大利著名数学家Fibonacci于1202年提出的“兔子繁殖问题”(又称“Fibonacci问题”)。
问题的提出：有雌雄一对兔子，假定过两个月后便每个月可繁殖雌雄各一的一对小兔子。问过n个月后共有多少对兔子？
已知：N<=93。
F(i):第i个月后共有的兔子对数。
F(1)=1;
F(2)=1;
F(i)=f(i-2)+f(i-1)
f(3)=2;
f(4)=3;
f(5)=5;
f(6)=8;
{N<=93}// qword可以处理1021只内的正数运算var f:array[1..100] of qword;
var n,i:integer;
begin
readln(n);
f[1]:=1;
f[2]:=1;
for i:=3 to n do
f[i]:=f[i-2]+f[i-1];
writeln(f[n]);
end.
N<=1000}
var
n,len,i,k:integer;
f1,f2,f:array[1..210] of integer;
begin
fillchar(f1,sizeof(f1),0); fillchar(f2,sizeof(f2),0); readln(n);
f1[1]:=1;
F2[1]:=1;
len:=1; for k:=3 to n do
begin
fillchar(f,sizeof(f),0);
for i:=1 to len do
begin
f[i+1]:=(f1[i]+f2[i]+f[i]) div 10;
f[i]:=(f1[i]+f2[i]+f[i]) mod 10;
end;
if f[len+1]>0 then len:=len+1;
f1:=f2;//算法描述
f2:=f;
end;
writeln(len);
for i:=len downto 1 do write(f[i]); end.
二、高精度减法运算
问题表述：
输入a ，b （<10240）两个数，输出a-b 的值。
样例
2输入： 999 1000
样例2输出： -1
样例1输入： 456 409
样例1输出： 47
算法：
1、读入被减数s1；
2、读入减数s2；
3、如果s1 4、把s1存到数组a； 5、把s2存到数组b； 6、从低到高位计算a[i]=a[i]-b[i];注意借位。 7、输出数组a就是运算结果。 解决的问题： 1、输入、保存。 2、比较a和b的大小。从而确定结果的正负号 3、借位问题。 4、输出。
相关主题
文本预览