В этом тексте обсуждаются задачи, в которых возникает необходиость работать с натуральными числами, которые настолько велики, что не входят ни в один тип данных. Мы будем предполагать, что все числа не превосходят 1000 символов.
Как хранить число
Разобьем число на отдельные цифры и запишем каждую из них в отдельный элемент массива, причем записывать будем справа налево. Скажем, число 20134 запишется так:
…
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
a[8]
a[9]
Такой способ хранения решает сразу две проблемы. Во-первых, при сложении и умножении “столбиком” числа не придется “выравнивать”, разряды единиц, десятков, сотен, … А во-вторых, при переносе в старший разряд (когда результат длиннее исходных чисел), для него всегда есть место справа. Для удобства мы заведем массив из 2000 элементов.
Обратите внимание: так реализация, которую мы здесь обсуждаем, требует, чтобы все “пустые” ячейки были заполнены нулями. Следите за этим внимательно!
Сложение двух чисел
Сложение выполняется “столбиком”:
a[1]
a[2]
a[3]
a[4]
a[5]
…
+
b[1]
b[2]
b[3]
b[4]
b[5]
…
с[1]
с[2]
с[3]
с[4]
с[5]
c[6]
…
При этом нужно позаботиться о переносах:
1) перенос сразу записывается в другой разряд
2) при сложении учитывается перенос из предыдущего разряда
Код получается очень простой и симметричный:
s := a[i] + b[i] + c[i]; // складываем a[i] c b[i], учитываем перенос из предыдущего разряда
с[i] := s mod 10; // последнюю цифру s записываем в c[i]
c[i+1] := s div 10; // записываем перенос в следующий разряд
Это мы делаем циклом для всех i от 1 до 1000. Именно здесь нам и будет важен тот факт, что пустые ячейки массивов a и b были заполнены нулями. Тогда и все ненужные ячейки массива с также будут заполнены нулями.
Вывод числа на экран
Вывод длинного числа состоит из двух этапов.
1) Идя по массиву справа налево найдем “начало” (старший разряд) числа:
i:=1000;
while s[i]=0 do // ищем первую ненулевую цифру
I := i+1
2) Выводим все цифры справа налево, начиная с найденной:
for j := I downto 1 do
write(s[i]);
Умножение длинного числа на короткое
Коротким мы будем называть число, которое помещается в стандартный тип данных (при этом нам необходимо, чтобы после умножения на цифру результат так же не выходил за пределы стандартного типа данных).
Разобьем этот алгоритм на две части:
1) Умножим каждую цифру длинного числа a на короткое k и сохраним результаты в массиве c, не заботясь о переносах:
c[i] := a[i] * k;
2) Пройдем по полученному массиву и “сделаем переносы”:
for i:=1 to 1000 do begin //следующие строки важно выполнить именно в таком порядке
c[i+1]:=c[i+1]+(c[i] div 10);
c[i]:=c[i] mod 10;
end;
Умножение длинного числа на длинное
Алгоритм будет похоже на предыдущий, с той лишь разницей, что сначала мы умножим каждую цифру первого числа на каждую цифру второго числа:
for i:=1 to 1000 do
for j:=1 to 1000 do
c[…] := с[…] + a[i] * b[j];
(Именно здесь мы используем то, что объявлен массив длины 200 – это упростит код.)
Подумаем, что нужно поставить вместо многоточия.
При умножении 1-й цифры a на первую цифру b результат нужно положить в первую цифру c (разряд единиц).
При умножении 1-й цифры a на вторую цифру b результат нужно положить во вторую цифру c (в разряд десятков).
При умножении 2-й цифры a на вторую цифру b результат нужно положить в третью цифру с (разряд сотен).
Можно заметить, что при умножении i-й цифры a на j-ю цифру b результат нужно положить в (i+j-1)-ю цифру с, то есть на место каждого многоточия надо вписать i+j-1.
После этого мы точно так же, как и в предыдущем разделе, проходим по массиву с и делаем переносы.
Ввод длинного числа с клавиатуры
Поскольку мы не можем прочитать вводимое число ни в какой стандартный целочисленный тип, прочитаем его в строку:
s : string;
…
readln(s); //если вы собираетесь читать несколько строк, то важно не забыть “ln”
После этого каждый символ строки превратим в цифру и запишем ее в массив:
for i:=length(s) downto 1 do
a[length(s) - i] := StrToInt (s[i]);
Обратите внимание: последний символ попадает в первый элемент массива, предпоследний – во второй и т.д.
Для использования функции StrToInt, переводящей строку в число, необходимо подключить соответствующую библиотеку:
uses SysUtils;
Не забудьте изначально обнулить массив с!
Несколько слов о реализации
Рассмотрив (в самом простом варианте) основные алгоритмы, поговорим немного об их реализации. Ясно, что каждый алгоритм удобно оформить в виде соответствующей функции или процедуры. Для того, чтобы передавать им массив, объявим новый тип:
type
MyNumber = array [1..2000] of integer;
После этого будем передавать аргументы наших арифметических операций как константы (они не будут меняться), а переменную, в которую будет попадать результат – с модификатором var:
Procedure Add (const a,b : MyNumber; var c : MyNumber);
Для удобства можно ввести константу – максимальную длину числа:
Const
Maxlen = 1000;
В этом случае нам не придется вносить исправления по всей программе, если мы захотим изменить это число.
Заключение
Мы рассмотрели самый простой (и потому самый неэффективный) способ работы с длинными числами. Тем не менее, во многих приложениях его вполне хватает. Если же требуется увеличить скорость работы, то можно двигаться в нескольких направлениях:
- хранить не по одной, а по несколько последовательных цифр числа в одном элементе массива;
- обрабатывать массив не до конца, а вместо этого хранить реальную длину каждого числа;
- использовать более эффектинвые алгоритмы (например, быстрое умножение, работающее быстрее, чем за произведение длин множителей).