Длинная арифметика , [Pascal] продолжение

[Морской Ёж]

Недавно решал задачи про длинную арифметику. Написал еще 2 процедуры - это длинное вычитание и деление длинного на короткое. Вот:

procedure longsub(a,b:tlong; var c:tlong);
var k,i,p:longint;
begin
  fillchar(c,sizeof(c),0);
  if a[0]>b[0] then k := a[0] else k := b[0];
  p := 0;
  for i := 1 to k do
    begin
      c[i]:=a[i]-b[i]-p;
      if c[i]<0 then
        begin
          p := 1;
          inc(c[i],osn);
        end
      else p:=0;
    end;
  for i := k downto 1 do
    if c[i]<>0 then break;
  c[0]:=i;
end;

procedure longdiv(a:tlong; b:longint; var c:tlong);
var
  p:longint;
  i,j,ost:integer;
begin
  fillchar(c,sizeof(c),0);p:=0;
  i := 1;
  j := a[0];
  while i<j do
    begin
      swap(a[i],a[j]);
      inc(i);
      dec(j);
    end;
  ost:=0;
  for i := 1 to a[0] do
    begin
      c[i]:=(Longint(ost)*osn+a[i])div b;
      ost :=(Longint(ost)*osn+a[i])mod b;
    end;
  if c[1]=0 then
    begin
      c[0]:=a[0]-1;
      for i := 1 to c[0] do c[i]:=c[i+1];
      c[c[0]+1]:=0;
    end
  else c[0]:=a[0];
  i := 1;
  j := c[0];
  while i<j do
    begin
      swap(c[i],c[j]);
      inc(i);
      dec(j);
    end;
end;

Прошу приобщить все это к основной статье.

Сообщение отредактировано: Jin X - 17.11.16, 15:18

[Romtek]

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

[Морской Ёж]

ну хорошо. начнем с вычитания.

Цитата Arsuit @ 20.04.06, 17:40

if a[0]>b[0] then k := a[0] else k := b[0];

в этой строчке мы в переменную k записываем max(a[0],b[0]) - для границы цикла.

Затем мы запускаем цикл от 1 до k.
Переменная p служит для того, чтобы мы знали, занимали ли мы из соседнего разряда, или нет. (Если занимали, то p=1, иначе p=0 (все помнят вычитание столбиком?)).

Цитата Arsuit @ 20.04.06, 17:40

c[i]:=a[i]-b[i]-p;

Текущему разряду ответа присваиваем разность текущих разрядов вычитаемого и ... ну как его... то, что вычитают. Не помнь я как оно называется. Скажите пожалуйста, кто помнит. Ну так вот. Текущему разряду разности присваиваем разности вичитаемого, то, что вычитают и, если мы из этого разряда занимали, то вычитаем еще и единицу. Затем мы проверяем, если разность получилась отрицательной (if c[i]<0) то занимаем из соседнего разряда, а к текущему разряду ответа прибавляем основание (т. к. он стал отрицатльным).

и наконец вот эти

Цитата Arsuit @ 20.04.06, 17:40

for i := k downto 1 do
if c[i]<>0 then break;
c[0]:=i;

строки определяют кол-во цивр в ответе.
Ну вот с вычитанием мы вроде немного разобрались. Теперь деление. (Чтобы понять все, что здесь написано, вы должны помнить, как делятся числа столбиком )

Цитата Arsuit @ 20.04.06, 17:40

i := 1;
j := a[0];
while i<j do
begin
swap(a[i],a[j]);
inc(i);
dec(j);
end;

начнем с этих строк. Они переворачивают делимое. (если кто помнит, в длинной арифметике все числа записаны задом на перед - так с ними удобнее работать, в данном же случае (в случае деления) с длинным числом как раз таки удобнее работать, если оно записано в нормальном виде).

В переменной ost хранится остаток от деления разряда делимого на делитель. На каждом шаге цикла от 1 до a[0] мы к текущему остатку приписываем цифру из текущего разряда делимого (Longint(ost)*osn+a[i]), и делим все это на делитель (div b) и записываем в разряд частного. А в переменную, хранящую остаток мы записываем остаток от деления (Longint(ost)*osn+a[i]) на делитель.
Все. число поделено.


if c[1]=0 then
begin
c[0]:=a[0]-1;
for i := 1 to c[0] do c[i]:=c[i+1];
c[c[0]+1]:=0;
end
else c[0]:=a[0];
если a[1]<b то получится так, что c[1] будет равно 0. Ведущие нули нам не нужны, так что если это так, то сдвигаем все число на разряд влево. А заодно и опредиляем кол-во цифр в ответе.
В конце алгоритма мы переворачиваем число обратно.

Заметим, что этот алгоритм деления можно несколько усовершенствовать. Можно не переворачивать число, и начать деление с конца. Но выигрыш во времени от этого будет не значительный, а запутаться можно. Так что решайте сами, что вам важнее.

Добавлено 21.04.06, 14:21
ну вот. заценивайте статейку.

[Морской Ёж]

ну так это будут приобщать к общей статье?

[volvo877]

Будут, когда ты это оформишь как следует. В таком виде ничего присоединяться не будет.

[Морской Ёж]

Хорошо, я уже работаю над этим.

[Морской Ёж]

Посмотрел я на свою бывшую статью и ужаснулся... Решил все полностью переписать. Вот гляньте, что я пока написал. Оформлю я все пото, когда допишу все до конца. пока прошу просто посмотреть, почитать, дополнить.

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

Что нужно знать, чтобы понять весь изложенный здесь материал:
1. Что такое одномерные массивы
2. Что такое системы счисления, остатки.
3. Уметь складывать, вычитать, умножать, делить числа столбиком.


Начальные сведения.

Когда вы пишите программы на каком либо языке программирования, бывает такое, что стандартных типов данных не хватает, для решения той или иной задачи. Такое бывает, например, если программа использует какой-либо комбинаторный алгоритм, или просто калькулятор длинных чисел.… Здесь уже стандартных типов данных (longint, int64 для паскаля/дельфи и long long для СИ) не хватит. Есть, конечно, типы с плавающей точкой (double, extended), но и их иногда может не хватить…

Именно для таких случаев существует замечательный способ, который называется длинной арифметикой. Длинная арифметика подразумевает собой хранение длинного числа поразрядно, в одномерном массиве. При том способ хранения может быть разный. Некоторые хранят в одном элементе по одной цифре, другие же хранят в одном элементе несколько цифр в целях экономии памяти, т. к. процессор выполняет арифметические операции с различными числами за одно и то же время (это относится к сравнительно коротким числам, которые хранятся в стандартных типах). Я предпочитаю хранить несколько цифр (при этом я считаю, что оптимальное число цифр – 4), и ниже будут примеры, реализующие именно этот способ. Но выбирать, чем пользоваться, все же вам. Однако стоит отметить, что в этом способе ЗНАЧИТЕЛЬНО усложняется процедура чтения длинного числа. Кроме всего прочего, число в массиве записывается «задом на перед» - так удобнее. То есть если у меня есть число 123456789012345, и я храню в элементе по 4 цифры, то оно у меня будет выглядеть так:
2345’8901’4567’123.

В паскале длинные числа стоит описывать так:

const
  osn=10000; //основание. Так как в элементе массива мы храним 4 цифры, то можно сказать, что оно записано в osn-ичной системе счисления.
  max=100; //кол-во элементов массива
type
  TLong=array[0..max] of integer; // собственно сам массив с длинным числом.

Для удобства в нулевом элементе храним кол-во занятых элементов массива (как в стандартном типе string).


Чтение/вывод

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

Чтение.
Для тех, кто хранит в одном элементе массива одну цифру тут все совсем просто. Читаем посимвольно число, преобразуем символы в цифры, записываем в массив. Затем массив переворачиваем (ведь мы храним число «задом на перед», вы не забыли?). Пример:

Procedure Long_read(var a:tlong);
var
  c:char;
  i,j:integer;
  a:array[1..100] of byte;
begin
  fillchar(a,sizeof(a),0);
  repeat
    read(c);
  until c in ['0'..'9'];//пропускаем не цифры
  i := 1;
  while c in ['0'..'9'] do//пока цифры
    begin
      inc(i);
      a[i]:=ord(c)-ord('0'); //преобразуем символ в цифру
      read(c); //читаем еще символ.
    end;
  a[0]:=i;
  j := i;
  i := 1;
  while i<j do //переворачиваем.
    begin
      swap(a[i],a[j]);
      inc(i);
      dec(j);
    end;
end;

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

procedure longread(var a:tlong);
var
  c:char;
  i:longint;
begin
  fillchar(a,sizeof(a),0); //заполняем массив нулями.
  repeat
    read(c);
  until c in ['0'..'9'];  //пропускаем не символы.
  while c 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(c)-ord('0'); // в конец первого разряда записываем полчтенную цифру.
      if a[a[0]+1]>0 then inc(a[0]); // если мы заняли еще один элемент массива, то увеличиваем нулевой элемент
      read(c);  //читаем очередной символ.
    end;
end;

P.S. извиняюсь, что так долго пишу - я школу заканчиваю, экзамены, выпускные, поступление на носу...