"Длинная" арифметика
Известно, что арифметические действия, выполняемые компьютером в ограниченном числе разрядов, не всегда позволяют получить точный результат. Более того, мы ограничены размером (величиной) чисел, с которыми можем работать. А если нам необходимо выполнить арифметические действия над очень большими числами, например,
30! = 265252859812191058636308480000000?
В таких случаях мы сами должны позаботиться о представлении чисел в машине и о точном выполнении арифметических операций над ними.
Числа, для представления которых в стандартных компьютерных типах данных не хватает количества двоичных разрядов, называются "длинными". Реализация арифметических операций над такими "длинными" числами получила название "длинной арифметики".
Организация работы с "длинными" числами во многом зависит от того, как мы представим в компьютере эти числа. "Длинное" число можно записать, например, с помощью массива десятичных цифр, количество элементов в таком массиве равно количеству значащих цифр в "длинном" числе. Но если мы будем реализовывать арифметические операции над этим числом, то размер массива должен быть достаточным, чтобы разместить в нем и результат, например, умножения.
Существуют и другие представления "длинных" чисел. Рассмотрим одно из них. Представим наше число
30! = 265252859812191058636308480000000
в виде:
30! = 2 * (104)8 + 6525 * (104)7 + 2859 * (104) + 8121 * (104)5 + 9105 * (104)4 + 8636 * (104)3 + 3084 * (104)2 + 8000 * (104)1 + 0000 * (104)0.
Это представление наталкивает на мысль о массиве, представленном в табл. 1.
Таблица 1
| Номер элемента в массиве А | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| Значение | 9 | 0 | 8000 | 3084 | 8636 | 9105 | 8121 | 2859 | 6525 | 2 |
Мы можем считать, что наше "длинное" число представлено в 10000-10 системе счисления (десятитысячно-десятичная система счисления, приведите аналогию с восьмерично-десятичной системой счисления), а "цифрами" числа являются четырехзначные числа.
Возникают вопросы. Что за 9 в А [0], почему число хранится "задом наперед"? Ответы очевидны, но подождем с преждевременными объяснениями. Ответы на вопросы будут ясны из текста.
Примечание. Мы работаем с положительными числами!
Первая задача. Ввести "длинное" число из файла. Решение задачи начнем с описания данных.
Const MaxDig = 1000; {Максимальное количество цифр — четырехзначных!}
Osn = 10000; {Основание нашей системы счисления,
в элементах массива храним четырехзначные числа}
Type Tlong = Array[0..MaxDig] Of Integer;
{Максимальное количество десятичных цифр в нашем числе}
Алгоритм ввода "длинного" числа из файла рассмотрим на конкретном примере.
Пусть в файле записано число 23851674 и основанием (Osn) является 1000 (храним по три цифры в элементе массива А). Изменение значений элементов массива А в процессе ввода (посимвольного в переменную Ch) отражено в табл. 2.
Таблица 2
| А[0] | А[1] | А[2] | А[3] | Ch | Примечание |
| 3 | 674 | 851 | 23 | - | Конечное состояние |
| 0 | 0 | 0 | 0 | 2 | Начальное состояние |
| 1 | 2 | 0 | 0 | 3 | 1-й шаг |
| 1 | 23 | 0 | 0 | 8 | 2-й шаг |
| 1 | 238 | 0 | 0 | 5 | 3-й шаг |
| 2 | 385 | 2 | 0 | 1 | 4-й шаг: старшая цифра элемента А [1] перешла в пока "пустой" элемент А[2] |
| 2 | 851 | 23 | 0 | 6 | 5-й шаг |
| 2 | 516 | 238 | 0 | 7 | 6-й шаг |
| 3 | 167 | 385 | 2 | 4 | 7-й шаг |
| 3 | 674 | 851 | 23 |
Проанализируем таблицу (и получим ответы на поставленные выше вопросы).
1. В А[0] храним количество задействованных (ненулевых) элементов массива А — это уже очевидно.
2. При обработке каждой очередной цифры входного числа старшая цифра элемента массива с номером i становится младшей цифрой числа в элементе i+1, а вводимая цифра будет младшей цифрой числа из А[1]. В результате работы нашего алгоритма мы получили число, записанное "задом наперед".
Примечание (методическое): Можно ограничиться этим объяснением и разработку процедуры вынести на самостоятельное задание. Можно продолжить объяснение. Например, выписать фрагмент текста процедуры перенос старшей цифры из A[i] в младшую цифру А[i+1], т.е. сдвиг уже введенной части числа на одну позицию вправо:
For i := A[0] DownTo 1 Do
Begin
A[i+l] := A[i+l] + (Longint(A[i]) * 10) Div Osn;
A[i] := (LongInt(A[i]) * 10) Mod Osn;
End;
Пусть мы вводим число 23851674 и первые 6 цифр уже разместили "задом наперед" в массиве А. В символьную переменную считали очередную цифру "длинного" числа — это "7". По нашему алгоритму эта цифра "7" должна быть размещена младшей цифрой в А[1]. Выписанный фрагмент программы "освобождает" место для этой цифры. В таблице отражены результаты работы этого фрагмента.
| i | А[1] | А[2] | А[3] | ch |
| 2 | 516 | 238 | 0 | 7 |
| 2 | 516 | 380 | 2 | |
| 1 | 160 | 385 | 2 |
После этого остается только добавить текущую (считанную в ch) цифру "длинного" числа к А[1] и изменить значение А[0].
В конечном итоге процедура должна иметь следующий вид:
Procedure ReadLong(Var A : Tlong);
Var ch : char; i : Integer;
Begin
FillChar(A, SizeOf(A), 0) ;
Read(ch);
While Not(ch In ['0'..'9']) Do Read(ch);
{пропуск не цифр во входном файле}
While ch In ['0'..'9'] Do
Begin
For i := A[0] DownTo 1 Do
Begin
{"протаскивание" старшей цифры в числе из A[i]
в младшую цифру числа из A[i+l]}
A[i+l] := A[i+l] + (LongInt(A[i]) * 10) Div Osn;
A[i] := (LongInt(A[i]) * 10) Mod Osn
End;
A[1] := A[l] + Ord(ch) - Ord('0');
{добавляем младшую цифру к числу из А[1]}
If A[A[0]+1] > 0 Then Inc(A[0]);
{изменяем длину, число задействованных элементов массива А}
Read(ch)
End
End;
Вторая задача. Вывод "длинного" числа в файл или на экран.
Казалось бы, нет проблем — выводи число за числом. Однако в силу выбранного нами представления "длинного" числа мы должны всегда помнить, что в каждом элементе массива хранится не последовательность цифр "длинного" числа, а значение числа, записанного этими цифрами. Пусть в элементах массива хранятся четырехзначные числа. Тогда "длинное" число 128400583274 будет в массиве А представлено следующим образом:
| A[0] | A[1] | A[2] | A[3] |
| 3 | 3274 | 58 | 1284 |
При выводе "длинного" числа из массива нам необходимо вывести 0058, иначе будет потеря цифр. Итак, незначащие нули также необходимо выводить. Процедура вывода имеет вид:
Procedure WriteLong(Const A : Tlong);
Var ls, s : String; i : Integer;
Begin
Str(Osn Div 10, Is);
Write(A[A[0]]; {выводим старшие цифры числа}
For i := A[0] - l DownTo 1 Do
Begin
Str(A[i], s);
While Length(s) < Length(Is) Do s := '0' + s;
{дополняем незначащими нулями}
Write(s)
End;
WriteLn
End;
Третья задача. Предварительная работа по описанию способа хранения, вводу и выводу "длинных" чисел выполнена.
У нас есть все необходимые "кирпичики", например, для написания программы сложения двух "длинных" положительных чисел. Исходные числа и результат храним в файлах. Назовем процедуру сложения SumLongTwo.
Тогда программа ввода двух "длинных" чисел и вывода результата их сложения будет иметь следующий вид:
Var A, B, C : Tlong;
Begin
Assign(Input, 'Input.txt'); Reset(Input);
ReadLong(A); ReadLong(B) ;
Close(Input);
SumLongTwo(A, B, C);
Assign(Output, 'Output.txt');
Rewrite(Output);
WriteLong(C);
Close(Output)
End.
Алгоритм процедуры сложения можно объяснить на простом примере. Пусть А=870613029451, В=3475912100517461.
| i | A[i] | B[i] | C[1] | C[2] | C[3] | C[4] |
| 1 | 9451 | 7461 | 6912 | 1 | 0 | 0 |
| 2 | 1302 | 51 | 6912 | 1354 | 0 | 0 |
| 3 | 8706 | 9121 | 6912 | 1354 | 7827 | 1 |
| 4 | 0 | 3475 | 6912 | 1354 | 7827 | 3476 |
Алгоритм имитирует привычное сложение столбиком, начиная с младших разрядов. И именно для простоты реализации арифметических операций над "длинными" числами используется машинное представление "задом наперед".
Результат: С = 3476782713546912.
Ниже приведен текст процедуры сложения двух "длинных" чисел.
Procedure SumLongTwo(A, B : Nlong; Var C : Tlong);
Var i, k : Integer;
Begin
FillChar(C, SizeOf (C), 0) ;
If A[0] > B[0] Then k := A[0] Else k : =B[0];
For i := l To k Do
Begin С [i+1] := (C[i] + A[i] + B[i]) Div Osn;
C[i] := (C[i] + A[i] + B[i]) Mod Osn
{Есть ли в этих операторах ошибка?}
End;
If C[k+l] = 0 Then C[0] := k Else C[0] := k + l
End;
Четвертая задача. Реализация операций сравнения для "длинных" чисел (А=В, А<В, А>В, А<=В, А>=В).
Function Eq(A, B : TLong) : Boolean;
Var i : Integer;
Begin
Eq := False;
If A[0] <> B[0] Then Exit
Else Begin
i := l;
While (i <= A[0]) And (A[i] = B[i]) Do Inc(i);
Eq := i = A[0] + l
End
End;
Реализация функции А > В также прозрачна.
Function More(A, B : Tlong) : Boolean;
Var i : Integer;
Begin If A[0] < B[0] Then More := False
Else If A[0] > B[0] Then More := True
Else Begin
i := A[0];
While (i > 0) And (A[i] = B[i]) Do Dec(i);
If i = 0 Then More := False
Else If A[i] > B[i] Then More := True
Else More:=False
End
End;
Остальные функции реализуются через функции Eq и More.
Function Less(A, B : Tlong) : Boolean; {A < B}
Begin
Less := Not(More(A, B) Or Eq(A, B))
End;
Function More_Eq(A, B : Tlong) : Boolean; {A >= B}
Begin
More_Eq := More(A, B) Or Eq(A, B)
End;
Function Less_Eq(A, B : Tlong) : Boolean; {A <= B}
Begin
Less_Eq := Not More(A, B)
End;
Для самостоятельного решения может быть предложена следующая, более сложная, задача. Требуется разработать функцию, которая выдает 0, если А больше В, 1, если А меньше В, и 2 при равенстве чисел. Но сравнение должно быть выполнено с учетом сдвига. О чем идет речь? Поясним на примере. Пусть А равно 56784, а В — 634. При сдвиге числа В на 2 позиции влево функция должна сказать, что В больше А, без сдвига, что А больше В. Другой пример. При А равном 56700, а В — 567 и сдвиге 2 функция должна "сказать", что числа равны. Решение может иметь следующий вид: