Відомо, що арифметичні дії, виконувані комп'ютером в обмеженому числі розрядів, не завжди дозволяють отримати точний результат. Більше того, ми обмежені розміром (величиною) чисел, з якими можемо працювати. А якщо нам необхідно виконати арифметичні дії над дуже великими числами, наприклад,
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 В також прозора.
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; {AB [0] + sdvig Then More: = 0
Else
If A [0] <B [0] + sdvig Then More: = l
Else Begin
i: = A [0];
While (i> sdvig) And
(A [i] = B [i-sdvig]) Do Dec (i);
If i = sdvig Then Begin
More: = 0;
{Збіг чисел з урахуванням зсуву}
For i: = 1 To sdvig Do
If A [i]> 0 Then Exit;
More: = 2;
{Числа рівні, "хвіст" числа А дорівнює нулю}
End
Else More: = Byte (A [i] <B [i-sdvig])
End
End;
П'яте завдання. Множення довгого числа на короткий. Під коротким розуміється ціле число типу LongInt.
Процедура дуже схожа на процедуру складання двох довгих чисел.
Procedure Mul (Const A: TLong; Const К: Longlnt; Var З: TLong);
Var i: Integer;
{Результат - значення змінної З}
Begin
FillChar (С, SizeOf (С), 0);
If K = 0 Then Inc (С [0]) {множення на нуль}
Else Begin
For i: = l To A [0] Do
Begin
C [i + l]: = (LongInt (A [i]) * K + C [i]) Div Osn;
C [i]: = (LongInt (A [i]) * K + C [i]) Mod Osn
End;
If C [A [0] +1]> 0 Then C [0]: = A [0] + 1
Else C [0]: = A [0]
{Визначаємо довжину результату}
End
End;
Шоста завдання. Віднімання двох довгих чисел з урахуванням зсуву
Якщо поняття зсуву поки не зрозуміло, то залиште його в спокої, насправді віднімання з урахуванням зсуву буде потрібно при реалізації операції ділення. На початку подальші логіку роботи процедури при нульовому зсуві.
Введемо обмеження: число, з якого віднімають, більше числа, яке віднімається. Працювати з "довгими" негативними числами ми не вміємо.
Процедура була б схожа на процедури додавання і множення, якщо б не одне "але" - запозичення одиниці зі старшого розряду замість перенесення одиниці в старший розряд. Наприклад, у звичайній системі числення ми віднімаємо 9 з 11 - йде запозичення 1 з розряду десятків, а якщо з 10000 віднімаємо 9 - процес запозичення дещо складніше.
Procedure Sub (Var A: TLong; Const B: TLong; Const sp: Integer);
Var i, j: Integer;
{З А віднімаємо В з урахуванням зсуву sp, результат віднімання в А}
Begin
For i: = l To B [0] Do
Begin Dec (A [i + sp], B [i]);
j: = i; {*}
{Реалізація складного запозичення}
while (A [j + sp] <0) and (j Ost