Factorial(N,FactN,NewI,NewP)
мал.6.4.
6.1. Написати рекурсивну і нерекурсивну програми, які обчислюють значення F(M,N) для довільної пари цілих чисел M,N>=0, яке визначається наступним чином:
ì M+N+1 якщо M*N=0
F(M,N)=í
î F(M-1, F(M,N-1)) в іншому випадку
6.2. N-те число Фіббоначі визначається наступним чином
ì 0 якщо N=0
F(N)=í 1 якщо N=1
î F(N-1)+F(M,N-1)) в іншому випадку
Написати рекурсивну і некурсивну програми, які обчислюють N-те число Фіббоначі.
6.3. Найбільший спільний дільник G(M,N) двох цілих чисел M і N можна визначити наступною рекурсивною схемою
ì M якщо N=0
G(M,N)=í
î G(N, MOD(M,N)) якщо N¹0
Написати програму, яка використовує рекурсивно-визначений предикат G(M,N), для визначення найбільшого спільного дільника декількох пар чисел.
Лабораторна робота №7
РЕКУРСИВНІ СТРУКТУРИ ДАНИХ
Рекурсивними можуть бути не тільки правила, а й структури даних. Пролог належить до тих мов програмування, в яких дуже зручно можна організовувати, описувати і реалізовувати дані рекурсивного типу. Тип даних буде рекурсивним, якщо він представляє собою структуру, яка в своєму визначенні використовує структуру, подібну собі.
Найбільш використовуваною рекурсивною структурою є список, але ми його розглянемо трішки пізніше. В цьому розділі ми зосередимо свою увагу на структурі даних типу дерева і на її використанні.
Структура даних типу дерева.
Серед структур даних типу дерева можна виділити спеціальний клас найбільш вживаних дерев- бінарні дерева. Можна дати наступне рекурсивне визначення бінарного дерева:
1.Пусте дерево- бінарне дерево.
2.Кожний вузел бінарного дерева має не більше одного лівого бінарного піддерева і не більше одного правого бінарного піддерева.
Таку структуру даних в Пролозі можна визначити за допомогою двох предикатів:
treetype = tree(string,treetype,treetype) та empty
Останній використовується для позначення пустого дерева. Тому структура даних для задання бінарного дерева може бути описана наступним чином:
Domains
treetype= tree(string, treetype,treetype);
Empty
Наприклад, дерево зображене на мал.7.1
C a t h y
/ \
/ \
M i c h a e l m e l o d y
/ \ / \
/ \ / \
C h a r l e s h a s e l j i m e l e o n o r
Мал.7.1.
може бути описане:
tree('Cathy',tree('Michael',tree('Charles',empty, empty),
tree('Hazel' ,empty, empty)),
tree('Melody', tree('Jim',empty, empty),
tree('eleanor' ,empty, empty)))
Відмітимо, що це не є прологівсьгою фразою; це є тільки складною структурою даних.