Материал: 1-23

ВІД АВТОРА

Даний навчальний посібник є логічним продовженням посібника «Методи побудови алгоритмів та їх аналіз. Необчислювальні алгоритми». Після ознайомлення з різноманітними алгоритмами, які можна назвати базовими для побудови складних алгоритмів, слід переходити до побудови оптимізаційних алгоритмів.

Володіючи базовими алгоритмічними структурами - ліній­ ними, розгалуженими і циклічними, можна побудувати алго­ ритм розв'язку практично будь-якої задачі. Розв'язання склад­ них алгоритмічних задач, метою яких є пошук кращого з усіх можливих варіантів розв'язків, може бути реалізовано за допо­ могою повнопереборних алгоритмів. Однак існують різні мето­ ди, які дають змогу оптимізувати такі задачі і розв'язати їх за мінімальний час. Методи розв'язування таких задач представ­ лені в інформатиці різними розділами: теорія графів, лінійне та динамічне програмування тощо.

Метою створення даного навчального посібника є не тільки ознайомлення читача з вказаними вище розділами інформати­ ки, а й вироблення у нього навичок грамотного тестування роз­ роблених алгоритмів, уміння точно оцінити ефективність робо­ ти алгоритмів, вибирати найбільш підходящі для кожної кон­ кретної задачі оптимізаційні методи.

Аналіз значної кількості робіт відомих авторів, присвяче­ них питанням вивчення методів розв'язування складних алго­ ритмічних задач, дав мені змогу підійти до розгляду методів побудови алгоритмів з різних точок зору і розташувати ма­ теріал у найбільш логічній і зручній послідовності.

Оскільки даний навчальний посібник у першу чергу орієнто­ вано на учнів загальноосвітніх навчальних закладів і молод­ ших курсів вищих навчальних закладів, то його матеріал мак­ симально адаптований саме для цієї вікової категорії читачів.

До посібника увійшли не тільки теми, передбачені програ­ мою поглибленого вивчення інформатики, а й матеріал, не­ обхідний для підготовки до олімпіад, турнірів, конкурсів тощо.

Достатній досвід роботи з учнями Чернівецького міського ліцею № 1, робота з обдарованими дітьми під час підготовки до різного рівня олімпіад з інформатики дають підстави сподіва­ тися, що даний навчальний посібник буде корисним учителям, тренерам та їхнім учням.

Тетяна Караванова

З

Дані алгоритми мають коротку і влучну назву - довга ариф­ метика. Про що йдеться? Ми вже розглядали питання обмеже­ ності значень різних типів даних і наводили приклад обчислен­ ня значень га! для га > 7 у разі, коли результат описано як цілу змінну. При цьому матимемо неправильну відповідь. І все це тому, що значення 8! = 40 320, а тип integer має верхню межу значень 32 767. Під час обчислення відповіді для га = 8 за допо­ могою простенької програми

program factorial; varf, і, n: integer;

begin read(n); f: = 1;

for і := 1 to n do f =f * j-

і . і i,

writeln(f)

end;

отримаємо результат -25 216, який демонструє описану ситуацію. Отже, ми вийшли за межу значень даного типу і не можемо отри­ мати правильний результат. Така ситуація може трапитися не ли­ ше під час обчислення факторіала, а, наприклад, при спробах отри­ мати значення аь при цілих, але великих значеннях аргументів.

Вихід із цієї ситуації є, якщо подати число у вигляді масиву окремих його цифр. Алгоритми довгої арифметики передба­ чають поцифрову обробку заданих чисел, а тому є циклічними. Оскільки йдеться про арифметику, то й алгоритми, які реалізу­ ються над довгими числами, - це алгоритми додавання, віднімання, множення та ділення. І ще одна умова - розгляда­ тимемо лише цілочислову арифметику.

Отже, нам потрібно буде реалізувати алгоритми виконання арифметичних дій над числами, що подані у вигляді масивів цифр. Розглядаючи системи числення, ми раніше реалізовува­ ли ці алгоритми для систем числення з основами Р. Нагадаємо їх та дещо модифікуємо.

Розглянемо ті арифметичні дії, які найчастіше трапляються в задачах, а саме: додавання, віднімання і множення.

Додавання довгих цілих чисел

Нехай задано масиви At, Вр і = 1, 2, ..., п, елементами яких є цифри 10-ї системи числення. Розробимо алгоритм додавання цих двох довгих чисел. Для цього необхідно порозрядно дода­ вати цифри двох чисел і контролювати отриманий результат: якщо він менший за 10, то це і є наступна цифра числа-ре- зультату; якщо ні, то необхідно відокремити цифри одиниць і десятків отриманого результату і продовжити додавання на­ ступних розрядів.

Запишемо у словесній формі алгоритм додавання у стовпчик двох десяткових чисел.

1.Нехай п - кількість цифр у першому числі, а т - у друго­ му. Тоді визначимо k = max(n, т).

2.Визначити і := 1, с := 0 (с - кількість десятків у додаванні попереднього розряду).

3.Нехай аі - і-та цифра першого доданка, bt - другого, а rezi - результату. Визначити с := at + bt + с.

4.Якщо с < 10, тоді визначити rezi := с і перейти до п. 6.

5.Якщо с > 10, тоді визначити значення і-го розряду числа-

результату як rezt := <кількість одиниць числа с> , а значення, яке необхідно буде додати у наступному розряді, - як с := к і л ь ­ кість десятків числа с > .

6.Якщо і < k, то і := і + 1 та перейти до п. 3.

7.Якщо с > 0, то k := k + 1, rezk := с, що означатиме збіль­ шення розрядності числа-результату.

8.Вивести елементи масиву гаг.

Реалізуємо фрагмент цього алгоритму (п. 1-6) у вигляді про­ цедури:

procedure add(var a: mas; b: mas; var k: word); var i: word;

begin

if n > m t h e n k := n e l s e k := m; {Визначення максимальної довжини двох чисел.}

с:=0;

for і := 1 to k do

5