"Довга" арифметика
Відомо, що арифметичні дії, виконувані комп'ютером в обмеженому числі розрядів, не завжди дозволяють отримати точний результат. Більш того, ми обмежені розміром (величиною) чисел, з якими можемо працювати. А якщо нам необхідно виконати арифметичні дії над дуже великими числами, наприклад,
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. </p>
Це уявлення наштовхує на думку про масиві, представленому в табл. 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
третій крок
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]
...
