Деление длинного числа на короткое
Как хранить число
Для хранения длинного числа можно использовать целочисленный массив, где в качестве элемента массива будет одна цифра числа. В 1-м элементе массива будем хранить последнюю цифру числа, во 2-м - предпоследнюю и т.д. до последней цифры. В 0-м элементе можно (но не обязательно) хранить общее количество цифр в числе.
Например, число 20134 запишется так:
| a[1] | a[2] | a[3] | a[4] | a[5] | a[6] | a[7] | a[8] | … |
| … |
Такой способ хранения решает сразу две проблемы. Во-первых, при сложении и умножении “столбиком” числа не придется “выравнивать”: разряды единиц, десятков, сотен, … А во-вторых, при переносе в старший разряд (когда результат длиннее исходных чисел), для него всегда есть место справа.
Обратите внимание: этот вариант реализации, который мы здесь обсуждаем, требует, чтобы все “пустые” ячейки были заполнены нулями (размерность массива зависит от условия задачи). Следите за этим внимательно!
Ввод длинного числа
ü поскольку мы не можем прочитать вводимое число ни в какой стандартный целочисленный тип, прочитаем его в строку;
ü обнулим массив для хранения числа;
ü в нулевой элемент массива или в дополнительную переменную запишем длину числа (строки);
ü каждый символ строки превратим в цифру и запишем ее в массив (в 1-ый элемент - последнюю цифру числа, во 2-ой - предпоследнюю и т.д.).
Вывод длинного числа
Выводим все элементы массива (цифры) справа налево, начиная с элемента с индексом равным длине числа, заканчивая первым элементом массива.
Сравнение двух длинных чисел
Первое на что мы обратим внимание, когда будем сравнивать числа, будет количество цифр в них. Если количество цифр различно, то больше то из них, которое содержит больше цифр. Если количество цифр одинаково, то нужно сравнивать, начиная со старшей цифры. При обнаружении первого различия (т. е. самая старшая цифра, в которой есть различие), можно определить какое из чисел больше. Если два числа не имеют различий, то они равны.
Сложение двух длинных чисел
Сложение можно организовать двумя способами:
1 способ - с использованием дополнительного массива, в котором будет храниться сумма.
| 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] | … |
Массив С заполняется суммой соответствующих элементов массивов А и B, начиная с 1-ого. Затем организуем перенос, начиная с 1-ого элемента массива: в каждой ячейке оставляем младшую цифру хранящегося там числа, а старшую суммируем с числом, находящимся справа.
2 способ – без использования дополнительного массива (в целях экономии памяти).
Например, организуем сложение двух длинных чисел, хранимых в массивах А и B. Длина числа хранится в нулевом элементе каждого массива. Результат сложения будем записывать в массив А.
Var
i, r : integer;
{r - обозначает сколько у нас "в уме"}
Begin
if a[0] < b[0] then a[0] := b[0];
{складывать нужно до размера большего числа}
r := 0;
{при сложение младших цифр в уме у нас 0}
for i := 1 to a[0] do
Begin
a[i] := a[i] + b[i] + r;
{сумма очередных цифр и переноса}
if a[i] >= 10
then {случай, когда происходит перенос в следующий разряд}
Begin
r := 1;
dec(a[i], 10);
End
else r := 0; {случай, когда переноса не происходит}
end;
{если после сложения остался еще перенос, то нужно добавить еще одну цифру}
if r > 0
Then
Begin
inc(a[0]);
a[a[0]] := r;
end;
Вычитание длинных чисел
Вычитание в столбик практически аналогично сложению. Если при вычитании двух цифр результат получается отрицательным, то мы занимаем единицу из старшего разряда. В отличие от сложения количество цифр в разности может уменьшиться, поэтому нужно будет пересчитать количество цифр.
Умножение длинных чисел
Говоря об умножении чисел, стоит рассмотреть два случая: умножение длинного числа на короткое (т. е. число, которое помещается в стандартный тип) и умножение двух длинных чисел.
Умножение на короткое число будет схоже с умножением на однозначное число. Будем последовательно умножать короткое число на каждую цифру длинного числа, начиная с младшей цифры, записывать результат и некоторую часть произведения переносить в следующий разряд.
При умножении двух длинных чисел в столбик, первое число последовательно умножается на каждую цифру. Результат умножения на i-тую цифру прибавляется к общему результату со сдвигом на i – 1.
Деление длинного числа на короткое
В младших классах в школе, все мы так же изучали деление столбиком. Мы будем рассматривать деление на короткое число b. При делении столбиком сначала выписывается старшая цифра, эту цифру делят на b. Частное дописывают к результату, а остаток пишут ниже. После этого к остатку приписывают следующую цифру, полученное значение делят на b. Аналогично, частное дописывают к ответу, а остаток пишут ниже. Процесс продолжается пока все цифры не будут использованы.
4531 | 7
42 ------
---- | 647
----
---
Остаток, к которому уже нельзя приписать цифру, будет остатком от деления.