« Назад

Мета: отримання основних навичок роботи з рекурсією

Хід виконання роботи

1. Запустити систему Пролог-Д.

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

Перший – приклад обчислення найбільшого загального дільника (НОД) двох чисел. Предикат, що виконується, якщо знайдено НОД двох даних чисел буде мати ім'я нод і три аргументи: числа a,b і значення НОД - c. Для опису обчислення НОД використаються наступні міркування. По-перше, якщо а=b, то c=a=b; По-друге, якщо а>b, те необхідно обчислити НОД для чисел b й a-b; По-третє, якщо b>a, те необхідно обчислити НОД для чисел a й b-a. Ці три твердження можуть бути записані на Пролог-Д:

Якщо до цієї бази знань поставити запитання:

?нод(10,15,x);

відповідь системи Пролог-Д:

x=5 ІНШИХ РІШЕНЬ НЕМАЄ

Предикат нод є оберненим.

Другий приклад – про обчислення елементів послідовності: 0, 1, 1, 2,

3, 5, 8, 13, 21, 34, 55, 89, 144,..., відомої як послідовність Фібоначі. Кожен елемент її визначається наступними правилами:

Перша формула відповідає твердженню про те, що значення нульового елемента послідовності дорівнює нулю. Це можна записати у вигляді факту: Фиб(0,0);. Другий рядок відповідає твердженню: перший елемент дорівнює 1. На Пролог-Д це можна записати так: Фиб(1,1);. Третій рядок являє собою запис рекурсивного співвідношення:

Дані речення складають базу даних мовою Пролог-Д, що дозволяє обчислювати значення елементів послідовності.

У відповідь на питання:

?Фиб(10,X);

відповідь системи Пролог-Д:

x=55 ІНШИХ РІШЕНЬ НЕМАЄ

Необхідно сказати, що такий шлях розв’язання даного завдання не є найкращим. Для знаходження N+1 числа Фібоначі потрібно 2*(N+1)-1 рекурсивне звернення. Але, цього можна уникнути, якщо перейти до іншої бази знань, у якій предикат з ім'ям "Фиб" визначений як триарний, тобто має три аргументи, що включає в себе у якості аргумента значення N-ого й N-1- ого елементів послідовності. Така база знань створюється у результаті перекладу на мову Пролог-Д тверджень.

1. 0-й елемент послідовності є 0, а (-1)-ший елемент не визначений. Фиб(0,x,0);. Другий аргумент позначений x. У цьому випадку значення x може бути довільним.

2. 1-й елемент послідовності є 1, а нульовий-0. Фиб(1,0,1);.

3. N-й член послідовності Фібоначі визначається через (N-1)-й член послідовності.

Фиб(N,F,f)<-БОЛЬШЕ(N,1),ВЫЧИТАНИЕ(N,1,M),Фиб (M,Ф,F), СЛОЖЕНИЕ (Ф, F, f);.

Звертання до цієї бази знань буде мати вигляд:

При роботі із цією базою знань для обчислення N-го числа Фібоначі необхідно всього лише N рекурсивних звертань.

У загальному випадку порядок речень у базі знань не має значення.

Але, у нижченаведеному прикладі це не так:

У першому реченні голова має те ж ім'я, що й одна з цілей – "родитель". У процесі пошуку відповіді в цій базі знань буде застосоване правило: речення, що є першим, буде й застосовано першим (принцип пошуку в глибину). Це призведе до того, що система буде звертатися тільки до першого речення бази знань і відповідь на питання ?родитель (Петя); не буде знайдена ніколи. Разом з тим, невелика зміна бази знань, перестановка двох речень місцями, призводить до вдалого пошуку рішення:

Необмежено-повторне звертання до речення може бути й більш замаскованим так, як це показано у прикладі:

Але, якщо третє речення стоїть на першому місці, то повторного звертання не відбудеться й відповідь буде знайдено. Така ситуація називається петля. При обчисленні елементів послідовності Фібоначі може з'являтися нескінченна петля при виконанні програми. Справді, якщо питання має вигляд:

?Фиб(0,x,y);

то перший можливий результат x =_0, y =1. Далі в спробі відшукати наступні розв’язки виникає нескінченна петля, тому що буде знаходитися Фиб(-1,x,y), Фиб(-2,...),... . Для контролю за подібною ситуацією необхідна модифікація бази знань. Перші два речення повинні бути записані у вигляді:

Фиб(0,x,1)<-!;

Фиб(1,1,1)<-!;

тоді при пошуку альтернативного розв’язку після одержання відповіді на питання:

Даний приклад ілюструє перше можливе використання предиката "ОТСЕЧЕНИЕ".

База знань на Пролог-Д буде виглядати краще, якщо речення з однаковими іменами розташовані в одному місці. Для порівняння наводяться дві бази знань:

Завдання

1. Написати мовою Пролог-Д базу знань, що описує обчислення факторіала.

2. Написати мовою Пролог-Д базу знань, що описує обчислення суми чисел натурального ряду.

3. Написати мовою Пролог-Д базу знань, що описує обчислення суми квадратів чисел натурального ряду.

4. Описати обчислення найменшого загального кратного.

5. Описати на Пролог-Д казку про попа, у якого був собака. "У попа був собака, він неї любив, вона з'їла шматок м'яса, він неї вбив на могилі написав...".

 

2. Оформити звіт, в який включити виконання завдань, Пролог- програму, ПИТАННЯ, представлені засобами Прологу, і відповіді на дані ПИТАННЯ, видані Пролог-системою.