ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 17.04.2019
Просмотров: 2339
Скачиваний: 1
61
i
←
i+1
Until i > N
Х[N]
←
1
Repeat
Sum
←
0
i
←
1
Repeat
Sum
←
Sum + S[i] *
Х[i]
i
←
i+1
Until i > N
if Sum = V
FL
←
true
Return (
Х,FL)
j
←
N
While
Х[j] = 1
Х[j] = 0
j
←
j-1
Х[j]
←
1
Until
Х[0] = 1
Return(
Х,FL)
7.3
Аналіз
алгоритму
точного
рішення задачі
про суму
Розглянемо найкращий і найгірший випадок для даного алгоритму:
а) У кращому випадку, коли останній елемент масиву збігається зі
значенням V : V = S [N], необхідно виконати тільки одне підсумовування, що
призводить до оцінки:
F
a
ˇ(N)=Q(N);
б) У гіршому випадку, якщо рішення взагалі немає, то доведеться
перевірити всі варіанти, і
F
a
ˆ(N) = Q (N*2
N
).
62
Отримаємо детальну оцінку для гіршого випадку, використовуючи
прийняту методику підрахунку елементарних операцій у вигляді:
F
a
ˆ(N) = 2+N*(3+2)+2+(2
N
-1)*{2+N*(3+5)+1+1+f
cnt
+2+2} (7.2)
Для отримання значення fcnt
–
кількості операцій, необхідних для
збільшення лічильника на «1» розглянемо по кроках проходи циклу While, в
якому виконується ця операція:
Х
кількість проходів в While
операцій
001
1
6+2
010
0
2
011
2
2*6+2
100
0
2
101
1
6+2
110
0
2
111
3
3*6+2
Таким чином:
f
cnt
= (1/2)*(2)+(1/2)*(2)+(1/2)*((1/2)*1*6+(1/4)*2*6+(1/8)*3*6+…) =
=2 + 1/2 * 6 * (1/2
1
+2/2
2
+3/2
3
+…) = 2+ 3 * (
∑
k/2
k
);
Оскільки
∑
k*x
k
= x/(1-x)
2
, [5]
то
∑
k*(1/2)
k
= (1/2)/(1-(1/2))
2
= 2,
і, відповідно:
f
х
= 8
(! і не залежить від довжини лічильника)
Підстановка f
х
в (7.2) дає:
Fˆ
A
(N) = 4+5*N+(2
N
-1)*(8*N+16),
і остаточно:
Р-парних
Р-непарних
вихід з
While
fˇ
х
=2
fˆ
х
=N*6+2
f
=
Θ(1)
∞
k=1
63
Fˆ
A
(N) =8*N*2
N
+16*2
N
-3*N-12,
що узгоджується з асимптотичною оцінкою – формула (1).
7.4
Питання для
самоконтролю
1)
Формулювання завдання про суму.
2)
Асимптотична оцінка складності алгоритму для прямого перебору.
3)
Алгоритм розв'язання задачі про суму.
4)
Підалгоритм збільшення на одиницю довічного лічильника.
5)
Оцінки трудомісткості для кращого і гіршого випадку.
6) Функція трудомісткості алгоритму для вирішення завдання про суму в
гіршому випадку.
64
8. РЕКУРСИВНІ ФУНКЦІЇ І АЛГОРИТМИ
8.1 Рекурсивні функції
Однією з ідей
процедурного
програмування,
яка
оформилася
на початку
шістдесятих років ХХ століття, стало активне застосування в практиці
програмування деякого методу, заснованого на організації серій взаємних
звернень програм (функцій) один до одного. Питання про ефективність
використання даного методу при розробці алгоритмічних моделей актуальні і
в даний час, незважаючи на існування різних парадигм програмування,
створення нових і вдосконалення існуючих мов програмування. Мова йде про
рекурсивному методі в програмуванні, який розглядається альтернативним по
відношенню до
ітераційного
.
По суті один і той же метод, стосовно до різних областей носить різні
назви – це індукція, рекурсія і рекурентні співвідношення – відмінності
стосуються особливостей використання.
Під індукцією розуміється метод доведення тверджень, який будується
на базі індукції при n = 0,1, потім твердження покладається правильним при n
= n
b
і проводиться доказ для n +1.
Рекурсія – це визначення об'єкта через звернення до самого себе.
Рекурсивний алгоритм – це алгоритм, в описі якого прямо або побічно
міститься звернення до самого себе. У техніці процедурного програмування
дане поняття поширюється на функцію, яка реалізує рішення окремого блоку
завдання за допомогою виклику зі свого тіла інших функцій, в тому числі і
себе самої. Якщо при цьому на черговому етапі роботи функція організовує
звернення до самої себе, то така функція є рекурсивною.
Термін рекурентні співвідношення пов'язаний з американським
науковим стилем і визначає математичне завдання функції за допомогою
рекурсії.
Пряме звернення функції до самої себе припускає, що в тілі функції
міститься виклик цієї ж функції, але з іншим набором фактичних параметрів.
Такий спосіб організації роботи називається прямою рекурсією. Наприклад,
щоб знайти суму перших n натуральних чисел, треба суму перших (n-1) чисел
скласти з числом n, тобто має місце залежність: Sn = Sn-1 + n. Обчислення
65
відбувається за допомогою аналогічних міркувань. Такий ланцюжок взаємних
звернень в кінцевому підсумку зведеться до обчислення суми одного першого
елемента, яка дорівнює самому елементу.
При непрямому зверненні функція містить виклики інших функцій зі
свого тіла. При цьому одна або декілька з викладенихя функцій на певному
етапі звертаються до вихідної функції зі зміненим набором вхідних
параметрів. Така організація звернень називається непрямою рекурсією.
Наприклад, пошук максимального елемента в масиві розміру n можна
здійснювати як пошук максимуму з двох чисел: одне з них – це останній
елемент масиву, а інше є максимальним елементом в масиві розміру (n-1).
Для знаходження максимального елемента масиву розміру (n-1)
застосовуються аналогічні міркування. У підсумку рішення зводиться до
пошуку максимального з перших двох елементів масиву.
Рекурсивний метод в програмуванні передбачає розробку рішення задачі,
грунтуючись на властивостях рекурсивності окремих об'єктів або
закономірностей. При цьому вхідна задача зводиться до вирішення
аналогічних підзадач, які є більш простими і відрізняються іншим набором
параметрів.
Розробці рекурсивних алгоритмів передує рекурсивна тріада – етапи
моделювання завдання, на яких визначається набір параметрів і
співвідношень між ними. Рекурсивну тріаду складають параметризація,
виділення бази і декомпозиція.
На етапі параметризації з постановки задачі виділяються параметри, які
описують вхідні дані. При цьому деякі подальші розробки рішення можуть
вимагати введення додаткових параметрів, які не обумовлені в умови, але
використовуються при складанні залежностей. Необхідність у додаткових
параметрах часто виникає також при вирішенні завдань оптимізації
рекурсивних алгоритмів, в ході яких скорочується їхня тимчасова складність.
Виділення бази рекурсії припускає знаходження в розв'язуваній задачі
тривіальних випадків, результат для яких очевидний і не потребує
проведення розрахунків. Вірно знайдена база рекурсії забезпечує
завершеність рекурсивних звернень, які в кінцевому підсумку зводяться до
базового випадку. Перевизначення бази або її динамічне розширення в ході
рішення задачі часто дозволяють оптимізувати рекурсивний алгоритм за
рахунок досягнення базового випадку за більш короткий шлях звернень.