 |
Індивідуальні завдання (по варіантам)
|
|
|
|
Лабораторна робота №4
Тема: Рекурсія, відсікання (отсечение).
Методичні вказівки
Спосіб розв’язання задачі полягає в тому, щоб розбити вихідну задачу на більш дрібні підзадачі, розв’язати їх, а потім об'єднати підзадачі для того, щоб одержати розв’язок вихідної задачі. Якщо підзадача є зменшеним варіантом вихідної задачі, то спосіб її розбивки і розв’язання ідентичні способу, застосованому до вихідної задачі. Такий процес називається рекурсією.
Розв’язок задачі складається з фази розбивки і фази розв’язання.
І фаза: задача розбивається доти, поки остання підзадача не стане досить примітивною з відомим розв’язком.
Загальна рекурсія (нисхідна стратегія)
ІІ фаза: виконується розв’язання більш складної задачі на основі наочності розв’язання простої підзадачі.
Хвостова рекурсія (висхідна стратегія).
f(N,S): - f(N,S,N0,S0)
Два додаткових параметри
Мета роботи.
Знаходження суми числового ряду методом рекурсії.
1. Створити проект для обчислення факторіалу числа.
Кроки виконання:
- замінити інформацію, що міститься в файлі main.cl на наступну
Бачимо, що додана один рядок factorial: (integer N, integer F) procedure (i,o)., який визначає бінарний предикат factorial з відомим першим на невідомим другим аргументами.
Ключове слово procedure описує поведінку предиката, вказуючи, що його розв’язок буде успішним та буде знайдено один єдиний розв’язок, так, що відкати не знадобляться.
В main.pro знаходиться власне визначення нового предикату.
Для кожного його виклику є два можливі відповідності - з нульовим або довільним перший аргументом. Visual Prolog перебирає формули в порядку їх появи в коді, так що якщо перший аргумент дорівнює нулю, перевірка починається з першої формули factorial(0,F). Перше правило формули - !, Так зване відсікання, використання якого запобігає відкат до другої формули і таким чином забезпечує наявність рівно одного рішення предиката. Після цього змінна F, що містить рішення предиката, встановлюється в 1 і виводиться на друк. Друга формула factorial(N,F) рекурсивно обчислює F1 як факторіал N-1, встановлює рішення предиката рівним N * F1 і виводить його на друк. Нарешті, stdio::nl друкує новий рядок.
|
|
|
При виконанні основної програми предикат factorial виконується рівно один раз для N=12. З кожним викликом рекурсії N зменшується на одиницю, пока не буде дорівнювати 0. Після цього значення факторіалів повертаються в виводяться на друк в порядку зростання. Програма буде виконувати запит тільки до 12!, так як спроба обчисли 13! викличе помилку переповнення цілочисленного типу.
2. Скласти і налагодити програму обчислення суми числового ряду методом загальної і хвостової рекурсії:
Sum = 1+2+3+4+...+n -сума числового ряду.
| Загальна рекурсія | Хвостова рекурсія |
| Sum(0,0). Sum(N,S): - N1 = N –1, Sum(N1,S1), S = S1+N, N1>=0. | Sum(N,S): - Sm(N,S,1,0). Sm(N,S,N0,S0): - N0 <= N, N1=N0 + 1, S1= N0 + S0, Sm(N,S,N1,S1). Sum(_,S,_,S). |
Індивідуальні завдання (по варіантам)
|
|
|
