- •1. Вступ в логічне програмування
- •1.1. Виникнення логічного програмування
- •1.2. Сучасний стан логічного програмування
- •Опис задачі на пролозі. Факти і правила
- •2.1. Опис задачі на пролозі
- •2.2. Факти
- •Цільове твердження
- •Умовні твердження
- •Приклад програми на пролозі
- •2.6. Виконання програми на пролозі
- •2.7. Статична та динамічна бази даних
- •2.8. Підготовка фактів для внутрішньої бази даних
- •2.9. Опис фактів внутрішньої бази даних
- •2.10. Предикати роботи з внутрішньою базою даних
- •2.11. Приклади використання внутрішньої бази даних
- •3. Основні поняття visual-prolog
- •3.1. Загальні відомості
- •3.3. Домени елементарних об’єктів
- •3.4. Терми
- •3.4.1. Константа
- •Анонімна змінна
- •3.4.3. Структури
- •3.5. Програма на пролозі
- •4. Механізми прологу
- •Механізм узгодження цілі з базою даних
- •4.2. Механізм звороту
- •4.3. Механізм звороту і відсік
- •4.4. Рекурсія
- •4.4.1. Рекурсивний метод розв’язку задач
- •Рекурсивні методи 2-х доменів:
- •Застосуємо висхідний метод рекурсії до розв’язку задачі:
- •Висхідна рекурсія
- •4.4.4. Предикат repeат
- •Міркування про те, як треба писати програму
- •5. Обробка рядків
- •5.1. Загальні відомості
- •1.1 Стандартні предикати обробки рядків
- •5.3. Лексиграфічне порівняння рядків
- •2Низхідна рекурсія
- •6.1. Метод низхідної рекурсії
- •6.2. Загальна характеристика рекурсивних методів
- •6.3. Низхідна та висхідна рекурсії
- •7. Робота зі списками
- •7.1. Списки. Оголошення списків
- •7.2. Увід-вивід списків
- •7.3. Основна операція на списках
- •7.4. Формування списків стандартним предикатом
- •Процедура з’єднує два списки.
- •Процедура розділяє список на два за вказаним елементом.
- •2.1 Сортування списків на пролозі
- •Сортування методом пухирця
- •7.8. Складені списки
- •8. Предикати вводу-вивіду
- •8.1. Предикати вводу
- •8.2. Предикати виводу
- •9. Файли
- •9.1. Символічне ім’я файлу
- •9.2. Вхідний і вихідний потоки
- •9.3. Організація файлу та методи доступу до файлу
- •9.4. Робота з файлами різними методами доступу
- •9.5. Закриття файлу
- •9.6. Предикати роботи з каталогами
- •9.7. Предикати, що працюють з атрибутами файлів
- •Література
4.4. Рекурсія
4.4.1. Рекурсивний метод розв’язку задач
Операції, що повторюються можуть виконуватися також за допомогою рекурсивного метода. Назва „рекурсія” означає повторний рух.
Рекурсивними можуть бути як дані, так і процедури. До рекурсивних даних відносяться списки, рядки, дерева.
Дані називаються рекурсивними, якщо після відділення якоїсь частини даного, дане залишається того ж типу. Наприклад,
L = [1, 2, 3, 4, 5] список
L = [2, 3, 4, 5] список
Рекурсивні типи даних зручно оброблювати рекурсивними процедурами. Процедура називається рекурсивною, якщо в її тілі знаходиться виклик себе.
При утворенні рекурсивних процедур використовують
Рекурсивні методи 2-х доменів:
Висхідний метод рекурсії;
Низхідний метод рекурсії.
Розглянемо приклади застосування рекурсивних методів.
Задача: визначити факторіал 5.
Застосуємо висхідний метод рекурсії до розв’язку задачі:
Одиницю умножимо на множник двійку. Одержаний добуток умножимо на наступне число 3 Далі дії повторюються поки множник не дорівнюватиме 5.
5! = 1*2*3*4*5
Для реалізації такого методу необхідно мати початкове граничне значення( в прикладі - 1); мати кінцеве граничне значення(в прикладі - 5) та виконати дії, що повторюються, для значень від початкової граничної умови до кінцевої граничної умови ( дії в прикладі - умножити добуток на наступний множник).
Дії розглянуті в прикладі називають фазою одержання рішення висхідного метода рекурсії.
Застосуємо низхідний метод рекурсії до розв’язку задач:
Розіб’ємо задачу „знайти 5!”на дві задачі. Перша задача: знайти 4!. Друга задача: умножити результат першої підзадачі на 5. Другу задачу не можна розв’язати поки не буде знайдено розв’язок першої. Тому спочатку треба знайти 4!. Але 4! не можна знайти поки не знайдеться розв’язок задачі 3!, тощо. Породження задач припиняється, якщо буде одержано задачу, що розв’яжеться тривіально 1!=1. Таким чином, щоб одержати розв’язок основної задачі 5! треба спочатку розв’язати підзадачі: 1!, 2!, 3!, 4!.
Для розв’язку кожної підзадачі, крім 1!, треба розв’язати дві задачі подібні задачам вказаним для 5!. Перша задача: Знайти факторіал попереднього числа. Друга задача: Умножити результат першої задачі на число.
Використовуючи тривіальний розв’язок підзадачі 1!=1 і розв’язав другу задачу(умножити результат на 2), знайдемо розв’язок підзадачі 2! = 1!*2 = 1*2 =2. Дії будемо повторювати до тих пір, поки не буде одержано розв’язок основної задачі.
5! = 4!*5 5! = 24*5 = 120
4! = 3!*4 4! = 6*4 = 24
3! = 2!*3 3! = 2*3 = 6
2! = 1!*2 2! = 1*2 = 2
1! = 1 1! = 1
Дії по розбивання задачі на підзадачі називають редукцією. Метод редукції часто використовують для розв’язку будь - яких задач. Метод редукції, що використовують в низхідній рекурсії називають фазою – редукції.
Дії по знаходженню рішення називають фазою одержання рішення.
Таким чином: Висхідна рекурсія має одну фазу – фазу одержання рішення.
Низхідна рекурсія має дві фази: фазу редукції і фазу одержання рішення.
4.4.2. РЕКУРСИВНІ ПРОЦЕДУРИ
Рекурсивні процедури обов'язково мають граничну умову і рекурсивну умову. Рекурсивна умова виконує дії, що повторюються. Без граничної умови рекурсія буде не результативною. Рекурсія також не результативна, якщо не досягається гранична умова. Для досягнення граничної умови параметри рекурсивної умови повинні сходитися до параметрів граничної умови.
Рекурсивний метод написання процедур має перевагу перед використанням механізму звороту. При рекурсії можна зберігати значення змінних для кожного виклику. Механізм звороту звільнює значення змінних після закінчення роботи ітерації. Проте використовуючи динамічні бази даних чи файли можна зберігати дані і при роботі з механізмом звороту.
Розглянемо приклади простих рекурсивних процедур, які написано висхідним та низхідним методом.
Завдання: Вивести на екран числа від 0 до 9.
Висхідний метод рекурсії
Predicates
number (integer )
Goal
number (0 ).
Clauses
number (10). (1)
number (N ):- write (N), N1=N+1, number (N1 ). (2)
Предикати, що стоять в тілі правила (2) реалізують фазу одержання рішення. Останнім предикатом при висхідній рекурсії є рекурсивний виклик процедури. Дії правила виконуються до тих пір, поки початкова гранична умова -0 стане дорівнювати граничній кінцевій умові - 10.
Низхідний метод рекурсії
Predicates
number (integer )
Goal
number (10 ).
Clauses
number (0). (1)
number (N ):-N1=N-1, number (N1), write(N1) (2)
Фаза редукції – це виконання в тілі правила предикатів N1=N-1 і number(N1). Фаза виконується до тих пір, поки рекурсивний виклик не зіставиться з фактом і стане істинним.
Предикат write(N1) реалізує фазу одержання рішення.