Pascal:длинная арифметика — различия между версиями

Материал из synset
Перейти к: навигация, поиск
 
Строка 129: Строка 129:
 
</pre>
 
</pre>
  
== А*В ==
+
== Задача умножения ==
  
Следующая программа проводит умножение двух больших чисел
+
=== Программный код ===
 
<pre class="brush:pascal; gutter: false;">
 
<pre class="brush:pascal; gutter: false;">
 
program A*B;
 
program A*B;

Текущая версия на 20:21, 5 февраля 2011

Длинная арифметика(описание)

При решении определенного ряда задач, возникают ситуации, когда результаты или промежуточные вычисления не могут храниться ни в одном из допустимых типов языка программирования. Тогда необходимо обращаться к разделу программирования, который называется длинной арифметикой.

Для решения различных типов задач длинной арифметики применяется один и тот же принцип. Каждая цифра числа хранится в отдельном элементе массива. Для удобства добавления нового разряда числа хранятся в обратном порядке, причем длину числа можно хранить в отдельной переменной или в нулевом элементе массива.

Задача сложения

Алгоритм решения

Задача решается таким же образом, как и при сложении в столбик. Производим сложение по каждому разряду отдельно. Если сумма больше 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.

Примечание

На основе этих программ могут быть созданы программы нахождения факториала, возведения в степень и т.д. позводяющие работать с большими числами. Следует также учесть, что для экономии памяти в каждой ячейке массива можно хранить больше чем одну цифру числа.