пятница, 16 марта 2012 г.

Длинная арифметика

Стандартный алгоритм вычисления суммы длинных чисел можно оформить в виде посимвольного сложения цифр из строк и запоминанием цифры 1 для переноса в следующий разряд. Перед работой рекомендуется выровнять длину строк, т.е. заполнить строку слева нулями.
program summa;
var a,b,c:string; p,d,l1,l2,i,z,x,y:integer;
begin
readln (a); readln (b);//каждая строка чисел считывается отдельно
l1:=length (a); l2:=length (b);//определение длины строки
while l1>length(b) do b:='0'+b; l2:=length (b);
while l2>length(a) do a:='0'+a; l1:=length (a);//выравниваем длины строк
d:=0; //переменная для хранения переноса
c:=''; //результирующая строка
for i:=l2 downto 1 do begin //просматриваем с конца
  x:=ord(b[i])-ord('0'); //выделяем цифру
  y:=ord(a[i])-ord('0');
  z:=x+y+d; p:=z mod 10; d:=z div 10;//вычисление суммы и выделение разряда и переноса
  c:=chr(p+ord('0'))+c;//перевод числа в символ и добавление к сумме слева
end;
if d>0 then c:='1'+c;
writeln(c);
end.

Немного о переводе символа в число: известно, что в кодовой таблице числа как символы идут подряд от 0 до 9. Таким образом, зная только код числа 0 ord('0') и код нужного числа ord(a[i]), можно вычислить саму цифру:
   y:=ord(a[i])-ord('0');
И наоборот, зная код цифры p и нуля, можно получить символ:
   chr(p+ord('0')).

Можно воспользоваться и стандартными функциями перевода:
val(a[i],y,code); - перевод символа в число,
str(p,cp); - перевод числа в строку символов.

Но при этом нужно вводить лишние переменные:
var code:integer; cp:string;
И кроме этого с процедурой нельзя работать внутри выражений, т.е. использовать ее как функцию. В Delphi и Lazarus такая проблема снята - там есть функции:
strtoint(a[i]) и inttostr(p).

По аналогии запишем алгоритм умножения больших чисел. Здесь выравнивать числа не обящательно, а результат вычислений лучше сразу хранить в массиве чисел.
program multiplay;
type massiv =array[1..1000]of byte;
var a,b:string; c:massiv; j,i,l1,l2:integer; p,w,d,z,x,y,q:byte;
begin
readln (a); readln (b);
l1:=length (a); l2:=length (b);
w:=0;//перенос при сложении
for i:=1 to (l1+l2) do c[i]:=0;//обнуление массива
for i:=l2 downto 1 do begin
x:=ord(b[i])-ord('0');
d:=0;//перенос при умножении
for j:=l1 downto 1 do begin
y:=ord(a[j])-ord('0');
z:=x*y+d; p:=z mod 10; d:=z div 10;
q:=c[i+j]+p+w; c[i+j]:=q mod 10; w:=q div 10;
end;
if d>0 then begin q:=c[i]+w+d;c[i]:=q mod 10; w:=q div 10; end;
end;
if w>0 then begin c[1]:=w; end;
for i:=1 to (l1+l2) do write (c[i]); writeln;
end.

Все эти программы можно переписать с использованием массива или стека.
Вот пример реализации со стеком умножения длинного числа на 2. Стек реализован с помощью массива (можно и через указатели).

Например, 123456*2=246912

            6                      2

            5                      4

            4                      6

            3                      9
            2                      1

            1                      2

 Const max = 501;
type arr=array[1..max] of byte;
Var  stack,result:arr;
     i: integer;
     tos: integer;
     ch:string[1];code:integer;
     ost,k,tor:integer;
{tos - содержит значение индекса для следующего помещаемого в стек эл-та}
{помещение объекта в стек }
procedure Push(i:byte;var stack:arr;var tos:integer);
begin
   if tos>=MAX then WriteLn('Stask full')
   else  begin
     stack[tos]:=i;
     tos:=tos+1;
   end;
end;

{ выборка объекта из стека }
function Pop(stack:arr; var tos:integer): byte;
begin
    tos:=tos-1;
    if tos<1 then begin
      WriteLn('Stack underflow (стек пуст)');
      tos:=tos+1;
      Pop:=0;
    end
    else Pop := stack [tos];
end;

Begin
   tos:=1;tor:=1;
   while not eoln do begin
     read(ch);  val(ch,i,code);
     if code=0 then push(i,stack,tos);
   end;
   readln;
   ost:=0;
   while tos>1 do begin
     i:=pop(stack,tos);
     k:=i*2+ost;
     i:=k mod 10;
     ost:=k div 10;
     push(i,result,tor);
   end;
   if ost<>0 then push(ost,result,tor);
   while tor>1 do write(pop(result,tor));
End.

2 комментария:

  1. есть ошибки, например при умножении 12*895 выводит 00740, хотя должно 10740

    ОтветитьУдалить