Задачі на
довгу арифметику
Розглянемо
досить популярну в програмуванні завдання на роботу з
"довгими" числами. Реально з "астрономічними" або
"мікроскопічними" числами доводиться стикатися не так вже й
часто. Тим не менше, вправи, що розглядаються в цій публікації, можуть
послужити хорошою тренуванням в області програмування і зайняти гідне
місце в класах з поглибленим вивченням інформатики або на гуртках з програмування.
Алгоритми, представлені нижче, записані на Turbo Pascal, версія7.0. При
бажанні або необхідності вони можуть легко бути адаптовані до будь-якої іншої
програмному середовищі.
Діапазон
подання цілих чисел (Integer, Word, LongInt) обмежений, про що не раз вже
говорилося (втім, для дійсних величин це зауваження теж актуально).
Тому при вирішенні завдань завжди доводиться діяти з осторогою, - як би не
допустити виникнення помилки виходу за діапазон або переповнення. Наприклад,
обчислюючи факторіал (n! = 1 * 2 * 3 * ... * n), в діапазоні подання величин типу
Integer вдасться правильно отримати тільки 7! = 5040, а в діапазоні подання
типу LongInt - 12! = 479001600. Для більших значень, звичайно, можна використовувати
дійсні типи даних, але це вже не гарантує точного результату.
Тому корисно для отримання точних значень при дії з багатозначними
числами розробити інші способи представлення таких чисел, алгоритми
виконання арифметичних та інших операцій, процедури введення та виведення
результатів і т.д.
Покажемо
реалізацію рішення такого роду завдань на прикладі множення одного багатозначного
числа на інше. Саме ця арифметична операція найбільш часто використовується
при вирішенні інших завдань.
Найбільш
природним способом представлення багатозначного числа є запис кожного
його розряду у вигляді окремого елемента лінійного масиву (або списку, де
пам'ять під цифру буде приділятися в міру потреби, в той час як в масиві
доводиться наперед задавати максимальну кількість елементів у ньому). Нехай
(для зручності подальших дій) розряди "довгого" числа при
записи в масив нумеруються з одиниці, починаючи з розряду одиниць, тобто фігура з
розряду одиниць - елемент масиву з номером один, цифра з розряду десятків - елемент
масиву з номером два і т.д. Визначимо для роботи з "довгими"
невід'ємними числами тип даних:
Const MNax = 2000;
Type
Digit = 0 .. 9;
DlChislo = Array [1 .. Nmax] Of Digit;
Для вирішення
поставленого завдання необхідно вміти виконувати наступні дії:
1) введення
"довгого" числа;
2) власне
множення двох "довгих" чисел;
3) висновок
"довгого" числа;
4) визначення
кількості цифр у записі числа.
Кожну з
підзадач реалізуємо у вигляді окремої підпрограми. Почнемо з введення. Ввести велике
число доцільно у вигляді рядка, а в подальшому перетворити в масив цифр.
У процедурі врахований вказаний вище спосіб розміщення "довгого" числа в
масиві, тобто з точки зору користувача число записується як би у зворотному
порядку.
(Процедура перетворення
довгого числа, записаного
у вигляді рядка, в масив цифр; мінлива OK
приймає значення True,
якщо в запису числа немає сторонніх символів,
відмінних від десяткових
цифр, інакше - false)
Procedure Translate (S: String; Var
A: DlChislo; Var OK: Boolean);
Var I: Word;
Begin
Zero (A); I
: = Length (S); OK: = True;
While (I
> = 1) And OK Do
Begin
If
S [I] In ['0 '.. '9']
Then
A [Length (S) - I + 1]: = Ord (S [I]) - 48
Else
OK: = False; I: = I - 1
End
End;
У процедурі
викликається підпрограма Zero (A), призначення якої - запис нуля в кожен
розряд довгого числа. Ось текст цієї процедури:
(Процедура обнулення довгого числа)
Procedure Zero (Var A: DlChislo);
Var I:
Integer;
Begin
For I
: = 1 To NMax Do A [I]: = 0;
End;
Таким чином,
довге число записано в масив, де попереду (як елементи з великими
номерами) стоять незначущий нулі. При виконанні дій і виведення відповіді вони не
враховуються.
Зараз
розробимо функцію визначення кількості значущих цифр у записі числа,
оскільки вона буде потрібно при реалізації підпрограми множення.
(Функція визначення кількості цифр у
запису довгого числа)
Function Dlina (C: DlChislo):
Integer;
Var I:
Integer;
Begin
I: =
NMax;
While (I
> 1) And (C [I] = 0) Do I: = I - 1;
Dlina: =
I
End;
При її
розробці було використане таке міркування: якщо кількість не дорівнює нулю,
то кількість цифр у його записи одно номером перші цифри, відмінною від нуля,
якщо перегляд числа здійснюється від старшого розряду до молодшого. Якщо ж
довге число дорівнює нулю, то виходить, що кількість цифр у його записи одно
одній, що і було потрібно.
Ну і, нарешті,
головна процедура, заради якої і була зроблена вся попередня робота. При
складанні алгоритму використовується ідея множення "стовпчиком", хоча в
нашому варіанті складання виконується не після закінчення множення, а по ходу його,
тобто перемноживши чергові цифри, відразу ж додаємо результуючу цифру в
потрібний розряд і формуємо перенесення в наступний розряд.
(Процедура
множення довгих чисел.
A, B - множники, C - твір)
Procedure Multiplication (A, B:
DlChislo; Var C: DlChislo);
Var I, J:
Integer; P: Digit; VspRez: 0 .. 99;
Begin
Zero (C);
For I: = 1
To Dlina (A) Do (Цикл за кількістю цифр
в першому числі)
Begin
P: = 0; (Спочатку перенесення дорівнює
нулю)
For J: = 1 To Dlina (B) Do (Цикл по
кількістю цифр
в другому
числі)
Begin
VspRez: = A [I] * B [J] + P + C [I + J - 1];
C [I + J - 1]: = VspRez Mod 10; (Чергове
значення цифри в
розряді I + J - 1)
P: = VspRez Div 10 (Перенесення в наступний розряд)
End;
C [I + J]: = P (останній перенесення може
бути відмінний від нуля,
запишемо його в поки що
вільний розряд)
End
End;
Зараз приведемо
лістинг програми цілком.
Program DlUmn;
Const NMax = 2000;
Type Digit = 0 .. 9; DlChislo = Array [1 .. Nmax] Of Digit;
Var S: String;
M, N, R, F
: DlChislo;
I, MaxF:
Word;
Logic: Boolean;
(Процедура
обнулення довгого числа)
Procedure Zero (Var A: DlChislo);
Var I: Integer;
Begin
For I: = 1
To NMax Do A [I]: = 0;
End;
(Функція
визначення кількості цифр у записі довгого числа)
Function Dlina (C: DlChislo): Integer;
Var I: Integer;
Begin
I: = NMax;
While (I
> 1) And (C [I] = 0) Do I: = I - 1;
Dlina: = I
End;
(Процедура
друку довгого числа)
Procedure Print (A: DlChislo);
Var I: Integer;
Begin
For I: =
Dlina (A) DownTo 1 Do Write (A [I]: 1);
WriteLn
End;
(Процедура
перетворення довгого числа в масив цифр)
Procedure Translate (S: String; Var A: DlChislo;
Var OK: Boolean);
Var I: Word;
Begin
Zero (A); I
: = Length (S); OK: = True;
While (I
> = 1) And OK Do
Begin
If S [I]
In ['0 '.. '9']
Then
A [Length (S) - I + 1]: = Ord (S [I]) - 48
Else OK: =
False;
I: = I --
1
End
End;
Procedure Multiplication (A, B: DlChislo; Var C:
DlChislo);
Var I, J: Integer; P: Digit; VspRez: 0 .. 99;
Begin
Zero (C);
For I: = 1 To
Dlina (A) Do
Begin P: = 0;
For J
: = 1 To Dlina (B) Do
Begin
VspRez: = A [I] * B [J] + P + C [I + J - 1];
C [I + J - 1]: = VspRez Mod 10;
P: = VspRez Div 10
End;
C [I +
J]: = P
End
End;
(Основна
програма)
Begin
Repeat (повторюємо введення, поки число не буде
введено правильно)
Write ( 'Введіть перший множник:');
ReadLn (S); Translate (S, M, Logic)
Until Logic;
Repeat
Write ( 'Введіть другий множник:');
ReadLn (S); Translate (S, N, Logic)
Until Logic;
Multiplication (M, N, R); Print (R)
End.
У наведеному
лістингу Print - процедура виведення довгого числа. Надамо читачеві
самостійно розібратися в алгоритмі її роботи.
Повернемося до
обчислення факторіалу. Використовуючи розроблені підпрограми, визначимо,
значення факторіалу якого максимального числа можна розмістити в пам'яті при
таке подання довгих чисел.
Ось змінений
фрагмент основної програми, що вирішує поставлене завдання.
Begin
MaxF: =
810;
Zero (F);
F [1]: = 1;
For I: = 1
To MaxF Do
Begin
Str (I, S); (перетворення числа I до
строковому типу S)
Translate (S, M,
Logic);
Multiplication (F, M, F);
Print (F);
WriteLn ( 'Факторіал числа', I: 4, 'містить', Dlina (F), 'цифр .')
End
End.
Розрахунки
показали, що можна обчислювати факторіали до значення 810! включно, в
запису якого 1999 цифр. Далі знову виникає переповнення. Розрахунки за
програмі тривають близько 5 хвилин (IBM PC з процесором Pentium-100).
Нижче буде
запропонований список завдань для самостійного виконання. З них, на думку
автора, найбільшу складність представляють реалізації алгоритмів поділу одного
довгого числа на інше і витяг квадратного кореня. Алгоритм добування
квадратного кореня докладно описаний у довіднику В.А. Гусєва та А.Г. Мордковіча
[7]. У деяких випадках складені програми можуть виступати як
підпрограми при розробці алгоритмів вирішення інших, більш складних (як у
прикладі з факторіали), завдань. Крім авторських задач і завдань зі списку
літератури тут наведені завдання з олімпіад школярів з програмування,
що проводилися в Пермської області в 1989-99гг.
Завдання для
самостійного рішення
Скласти
програму порівняння двох багатозначних чисел (кількість знаків у записі чисел
более20).
Скласти
програму, що підсумовує два натуральних багатозначних числа з кількістю знаків
более20.
Скласти
програму обчислення ступеня an, якщо a> MaxInt, n> 10.
Скласти
програму обчислення числа 264 - 1, в результаті зберегти всі цифри.
Скласти
програму обчислення 100!.
Скласти програму
витягу точного квадратного кореня з n-розрядного числа (n> 40).
Скласти
програму обчислення точного значення n!, де n> 12.
Скласти
програму обчислення точного значення nn, де n> 10.
Скласти
програму ділення числа a на число b, якщо a, b - багатозначні числа.
Обчислити 100!
+ 2100.
Обчислити 100!
- 2100.
Обчислити 7123.
Зустрічаються чи
серед цифр числа 211213 - 1 дві поспіль йдуть дев'ятки?
Обчислити
2-200.
Скласти
програму знаходження приватного та залишку від ділення m-значного числа на
n-значне (m, n> 20).
З'ясувати, яке
з чисел am, bn більше і на скільки (a, b <= 40000; m, n <= 10).
Знайти n знаків
в десяткового запису квадратного кореня з цілого числа m (n> = 50).
Знайти
кількість дільників n-значний натурального числа (n> 20).
Обчислити
точне значення (n!)! (n> = 3).
Скласти
програму обчислення точного значення суми 1! + 2! + 3! + ... + N! при
n> 10.
Скласти
програму обчислення точного значення суми дробів
при n> 10.
Відповідь має бути представлений у вигляді несократімой дробу P/Q, де P, Q --
натуральні числа.
Обчислити
точне значення (nn)! при n> = 3.
Скласти
програму обчислення точного значення суми перших n членів послідовності
1, k, k2, k3, ..., kn (n> MaxInt). Вказівка: використовуйте формулу суми n
членів геометричної прогресії.
Скласти
програму обчислення точного значення суми перших n членів послідовності
чисел, кратних даного натурального числа k (n> MaxInt). Вказівка:
використовуйте формулу суми n членів арифметичної прогресії.
Обчислити
точне значення суми 12 + 22 + 32 + ... + n2 (n> = 20000).
Обчислити
точне значення суми 1n + 2n + 3n + ... + Nn (n> = 10).
Знайти першу
просте число, яке більше 1011.
Скласти
програму обчислення точного значення многочлена anxn + an - 1xn - 1 + ... +
a1x + a0, де aiіx - цілі числа більше 1011.
Знайти
найбільший спільний дільник і найменше спільне кратне чисел m і n (m,
n> = 1011).
Перевірити,
чи є числа m і n (m, n> = 1011) взаємно простими.
Доведіть, що
число 219936 * (219937 - 1) є досконалим, тобто дорівнює сумі всіх своїх
дільників, крім самого себе.
"Обертове
число ". Написати програму, яка знаходить число, що володіє наступними
властивостями:
1) число
закінчується на 5;
2) при
примноження його на 5 утворюється нове число, яке може бути отримано з
вихідного викресленням цифри 5 на кінці і переписуванням її в початок числа.
33. Дана
послідовність, задана рекурентних формулою
an + 1 = 7an mod 2023, a1 = 1,
де x mod y
означає залишок від розподілу x на y. Написати програму, яка обчислює an при
1 <= n <= 1000000000000000000000.
Дана
послідовність
Написати
програму, що знаходить точне значення an при 1 <= n <= 150.
Приклад. При n =
58 отримуємо an = 10359022039470231387111424.
35. Напишіть
програму перекладу багатозначного числа (з кількістю знаків більше 20) в
системи числення з основою два, вісім, шістнадцять.
36. Розкласти
на прості множники натуральне число з кількістю знаків більш 11.
37. Множення
періодичної дробу. Задана деяка позитивна правильна періодична
дріб Q і натуральне число N. Числа Q і N такі, що кількість цифр,
використовуються для їх опису, не перевершує 100. При зображенні дробу Q періодична
частина полягає в круглі дужки.
Потрібно
написати програму, яка визначає результат множення Q на N, тобто
неперіодичних частину і мінімальний період числа Q * N.
У разі
отримання результату множення у вигляді кінцевої дробу дужки опускаються.
Приклад роботи
правильної програми
Введіть
періодичну дріб: 0.1 (6)
Введіть
натуральне число: 2
Відповідь: 0. (3)
Список
літератури
Абрамов С.А.,
Гнездилова Г.Г., Капустина Е.Н., Селюн М.І. Завдання з програмування. М.:
Наука, 1988.
Олімпіади з
інформатики. Завдання й рішення. Методичні рекомендації для вчителів і
учнів шкіл. Красноярськ, 1991.
Пильщиків В.Н.
Збірник вправ з мови Паскаль. М.: Наука, 1989.
Касаткин В.Н.
Інформація. Алгоритми. ЕОМ. М.: Просвещение, 1991.
Хонсбергер Р.
Математичні родзинки. М.: Наука, 1992.
Семакін І.Г.,
Шестаков А.П. Лекції з програмування. Перм: изд-во ПГУ, 1998.
Гусєв В.А.,
Мордковіч А.Г. Математика. Довідкові матеріали. М.: Просвещение, 1990.
Гладков В.П.
Курс лабораторних робіт з програмування. Перм: изд-во ПДТУ, 1998.
Шестаков А.П.
Завдання на довгу арифметику/
Для підготовки
даної роботи були використані матеріали з сайту http://www.comp-science.narod.ru/
