Pascal:длинная арифметика
Содержание
Длинная арифметика(описание)
При решении определенного ряда задач, возникают ситуации, когда результаты или промежуточные вычисления не могут храниться ни в одном из допустимых типов языка программирования. Тогда необходимо обращаться к разделу программирования, который называется длинной арифметикой.
Для решения различных типов задач длинной арифметики применяется один и тот же принцип. Каждая цифра числа хранится в отдельном элементе массива. Для удобства добавления нового разряда числа хранятся в обратном порядке, причем длину числа можно хранить в отдельной переменной или в нулевом элементе массива.
Задача сложения
Алгоритм решения
Задача решается таким же образом, как и при сложении в столбик. Производим сложение по каждому разряду отдельно. Если сумма больше 9, берем остаток от деления числа на 10 и не забываем прибавить количество десятков к следующему по старшинству разряду
Программный код
program A+B;
var
s1,s2:string;
a,b:array[1..100] of integer;
len,i,c:integer;
f1,f2:text;
begin
Assign(f1,'INPUT.TXT'); Reset(f1);
Assign(f2,'OUTPUT.TXT'); ReWrite(f2);
c:=0;
ReadLn(f1,s1);
ReadLn(f1,s2);
close(f1);
len:=length(s1); {разбиение строк в елементы массивов}
for i:=1 to len do
a[len-i+1]:=Ord(s1[i])-48;
len:=length(s2);
for i:=1 to len do
b[len-i+1]:=Ord(s2[i])-48;
if length(s1)>length(s2) then len:=length(s1)
else len:=length(s2);
for i:=1 to len do
begin
c:=c+a[i]+b[i]; {переменная c будет в дальнейшем использоваться для переноса числа в следующия ряд}
a[i]:=c mod 10; {результат сложения запишем в массив а}
c:=c div 10;
end;
if c>0 then begin
len:=len+1;
a[len]:=c;
end;
for i:=len downto 1 do {вывод результата в файл}
Write(f2,a[i]);
close(f2);
end.
Задача вычитания
Данная программа осуществляет нахождения разности двух целых чисел не позволяющих хранить их в переменных допустимых типов какого-либо языка программирования.
Алгоритм решения
В отличии от задачи сложения, мы не можем выбирать по длине какого числа будем двигаться, поэтому прежде требует проверить конечный результат на его знак. Это освобождает от дальнейших трудностей. Непосредственно нахождения разности ничем не отличается от нахождения разности путем "вычитания в столбик".
Программный код
program A-B;
Function CompLong(s1,s2:string):integer; {функция CompLong сравнивает две строки как большие числа}
var
a,len1,len2,i:integer;
b:boolean;
begin
a:=0;
b:=true;
len1:=length(s1);
len2:=length(s2);
if len1>len2 then begin a:= 1; b:=false; end;
if len1<len2 then begin a:=-1; b:=false; end;
if b then
for i:=1 to len1 do
begin
if Ord(s1[i])-48>Ord(s2[i])-48 then begin a:= 1; break; end;
if s1[i]<s2[i] then begin a:=-1; break; end;
end;
CompLong:=a;
end;
var
s1,s2:string;
i,len,c,x:integer;
a,b:array[1..1000] of integer;
f1,f2:text;
begin
Assign(f1,'INPUT.TXT'); Reset(f1);
Assign(f2,'OUTPUT.TXT'); ReWrite(f2);
ReadLn(f1,s1); c:=0;
ReadLn(f1,s2);
close(f1);
len:=length(s2);
for i:=1 to len do
b[len-i+1]:=Ord(s2[i])-48;
len:=length(s1);
for i:=1 to len do
a[len-i+1]:=Ord(s1[i])-48;
if Complong(s1,s2)<0 then begin
Write(f2,'-');
len:=length(s2);
for i:=1 to len do begin
x:=a[i];
a[i]:=b[i];
b[i]:=x;
end;
end;
for i:=1 to len do
begin
c:=c+a[i]-b[i]+10;
a[i]:= c mod 10; {результат будет храниться в массиве a}
if c < 10 then c:=-1 else c:=0;
end;
while (a[len]=0) and (len>1) do len:=len-1;
for i:=len downto 1 do {вывод результата в файл}
Write(f2,a[i]);
close(f2)
end.
А*В
Следующая программа проводит умножение двух больших чисел
program A*B;
var
f1,f2:text;
s1:string;
b,i,c:integer;
a:array[0..105] of integer;
begin
Assign(f1,'INPUT.TXT'); Reset(f1);
Assign(f2,'OUTPUT.TXT'); ReWrite(f2);
c:=0;
ReadLn(f1,s1);
ReadLn(f1,b);
close(f1);
a[0]:=length(s1);
for i:=1 to a[0] do
a[a[0]-i+1]:=Ord(s1[i])-48;
for i:=1 to a[0] do
begin
a[i]:=c+a[i]*b;
c:=a[i] div 10;
a[i]:=a[i] mod 10;
end;
While c>0 do
begin
a[0]:=a[0]+1;
a[a[0]]:=c mod 10;
c:=c div 10;
end;
if a[a[0]]=0 then Write(f2,0)
else
for i:=a[0] downto 1 do
Write(f2,a[i]);
close(f2);
end.
Примечание
На основе этих программ могут быть созданы программы нахождения факториала, возведения в степень и т.д. позводяющие работать с большими числами. Следует также учесть, что для экономии памяти в каждой ячейке массива можно хранить больше чем одну цифру числа.