На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное DigiMania RSS
msm.ru
! Правила ЧаВо (FAQ) разделов Паскаля
В этом разделе разрешено создавать только темы, в которых описано РЕШЕНИЕ какой-либо общей проблемы, или описание какого-либо аспекта языка Паскаль.
Обсуждение уже созданных тем разрешено, но только конструктивное, например указание на ошибку или уточнение имеющегося текста.

Также читать Требования к оформлению статей
Модераторы: Romtek, volvo877
  
    > Длинная арифметика - решение математики, ...и не только
      Длинная Арифметика

      При написании программ на паскале часто приходится сталкиваться с такой проблемой, что стандартных типов не хватает для работы с большими числами. Даже типа int64, который есть в TMT паскале, может не хватить во многих случаях. Чтобы работать с большими числами существует прием, который называется длинной арифметикой. Для наглядного объяснения сразу начнем писать модуль для работы с длинной арифметикой. Для начала напишем следующее банальное выражение:
      ExpandedWrap disabled
        unit Long;
        interface
        const
          osn = 10000;   {Порядок каждого числа}
          MaxDig = 1000; {Максимальное количество элементов}
        type
          TLong = array[0..MaxDig] of integer; {Длинное число}
        implementation
        end.


      Длинное число хранится в массиве типа TLong. В каждом элементе хранится по i цифр длинного числа. i вычисляется по формуле:

      i = lg(osn)

      При osn = 10000 i равно 4.

      В нулевом элементе массива хранится количество задействованных элементов, а само число записывается в массив в обратном порядке. То есть если мы запишем в массив А число 123456789, то массив будет выглядеть так:
      ExpandedWrap disabled
        a[0] = 3
        a[1] = 6789;
        a[2] = 2345;
        a[3] = 1;


      Теперь надо написать две самые необходимые процедуры. Это процедуры чтения и вывода длинных чисел.

      ExpandedWrap disabled
        procedure Long_Read(var f:text; var a:TLong); {Читает длинное число из консоли или из файла}
        var                                 {откуда будет производиться чтение, зависит от переменной F}
          ch:char;
          i:integer;
        begin
          FillChar(a,Sizeof(A),0);         {Заполняем массив нулями}
          repeat                           {Пропускаем НЕ цифры вначале файла}
            Read(f,ch);                    
          until ch in ['0'..'9'];
          while ch in ['0'..'9'] do        {Начинаем читать цифры}
            begin
              for i := a[0] downto 1 do
                begin
                  a[i+1] := a[i+1]+(Longint(a[i])*10) div osn;  {Записываем цифры в массив}
                  a[i]   := (Longint(a[i])*10) mod osn;
                end;
              a[1] := a[1]+Ord(ch)-ord('0');
              if a[a[0]+1]>0 then inc(a[0]); {Если элемент текущий элемент заполнили, то переходим к следующему}
              Read(f,ch)                   {Читаем след. символ}  
            end
        end;
        {-----------------------------------------------------------------------------------------}
        procedure Long_Write(var f:text; const a:TLong);     {Выводит число в файл или в консоль}
        var
          ls,s:string;
          i:integer;
        begin
          Str(Osn div 10,ls);  {Преобразуем в стоку osn div 10}
          Write(f,A[A[0]]);    {Выводим последний элемент}
          for i := a[0]-1 downto 1 do
            begin
              Str(a[i],s);     {Преобразуем в стороку каждый след. элемент}
              while Length(s)<Length(ls) do s := '0'+s;  {Если длина строки не равна lg(osn), то ставим перед ней 0}
              Write(f,s);             {Печатаем строку}
            end;
          WriteLn
        end;


      Процедура Long_Read читает длинное число из текстового файла в переменную А, а Long_Write записывает число из А в файл.
      Если поставить input(output для Long_Write) в качестве первого параметра, то чтение и запись будут выполняться с консоли.

      Чтобы можно было с этими считанными числами что-то делать, надо написать процедуры сложения, вычитания, умножения, деления, операции больше, меньше и т. п.

      Арифметические операции производятся столбиком (вспоминаем 3 класс). Операции "больше-меньше" реализованы на том же уровне, т.е. поразрядное сравнение. Все это скомпонованное, отлаженное, проверенное я кладу в модуле LongMath.pas, в который добавлены операции с комплексными числами.

      ...и вот на всякий случай маленький примерчик...
      ExpandedWrap disabled
        uses LongMath;
        var
          a,b,c : TLong;
          x,y,z : TComplex;
          
        begin
          WriteLn ('Введите 2 длинных числа:');
          Long_Read(input,a); {Читаем с клавиатура а и b}
          Long_Read(input,b);
          if Long_Equal(a,b) then WriteLn('Числа a и b равны') {Сравниваем числа}
          else
            begin
              if Long_Less(a,b) then WriteLn('a меньше b');
              if Long_Above(a,b) then WriteLn('a больше b');
            end;
          WriteLn ('Нажмите Ввод для продолжения');
          ReadLn;
         
          Long_Add(a,b,c);    {c := a+b}
          WriteLn('Сумма x и y равна '); {Выводим сумму на экран}
          Long_Write (output, c);
         
          WriteLn ('Нажмите Ввод для продолжения');
          readln;
        end.


      (V. Приведенный модуль работает с беззнаковыми числами, впрочем в задачах, в которых нужны именно ОЧЕНЬ большие числа, они почти всегда больше нуля.)
      Сообщение отредактировано: Romtek -

      Прикреплённый файлПрикреплённый файлLongMath.zip (2 Кбайт, скачиваний: 1281)
      Я не алкоголик
        ИМХО, копирайты-то поставить надо. Это код из книги С.М.Окулова.

        и const osn - имелся ввиду не порядок, а основание системы счисления, в которой оперируем.
        MaxDig - мкасимальное количество цифр.
        Everything in this room is *eat*able. Even I'm *eat*able. But that is called cannibalism, my dear children, and is in fact frowned upon in most societies (c) Уилли Уонка.
        0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
        0 пользователей:


        Рейтинг@Mail.ru
        [ Script Execution time: 0,1117 ]   [ 17 queries used ]   [ Generated: 24.08.19, 13:43 GMT ]