Завдання:

Використовуючи відсікання, невдачу і заперечення, написати програму:

1. Написати програму-класифікатор, яка б спортсменів деякого клубу поділяла б на групи:

а) переможці  ті, хто жодного разу не програв жодного бою;

б) бійці  ті, хто і вигравав, але й був переможеним;

в) спортсмени  ті, хто поки не виграв жодного бою, якщо даний предикат переміг (хто, кого).

Яке рішення має бути визначений предикат клас (хто, група)

2. Написати програму обчислення з альтернативами:

1. знайти найбільше (найменше) значення з двох чисел;

2. знайти найбільше (найменше) значення з трьох чисел;

3. знайти найбільше (найменше) значення з шести чисел.

3. Написати програму обчислення з альтернативами:

1. визначити, чи задовольняють довжини трьох відрізків умові прямокутного трикутника;

2. визначити, чи задовольняють довжини трьох відрізків умові трикутника.

4. Написати програму обчислення з альтернативами:

1. два трикутники задані довжинами сторін. Визначити найбільшу сторону з найменших у цих трикутниках;

2. знайти модуль числа Х.

5. Написати програму обчислення з альтернативами:

- Описати мовою Прологу обчислення функції, заданої співвідношенням:

F (x) =

6. Написати програму обчислення максимального з трьох чисел, використовуючи результат завдання 2.

7. Гравці в деякому тенісному клубі розбиті на три ліги і можуть викликати на змагання тільки членів своєї ліги або ж стоять на одну лігу нижче (якщо така є). Написати програму, яка друкуватиме всі можливі пари між гравцями в такій формі:

nik викликає liz.

Використовувати відсікання, щоб не друкувалися одночасно пари гравців:

nik викликає liz і

liz викликає nik.

8. Дано результати складання іспитів для групи з п'яти учнів:

1. побудувати базу знань стосовно результатів іспитів, визначивши в ній такі правила:

1. Відмінник (людина, у якої з усіх предметів п'ятірки).

2. Двієчник (є хоча б одна двійка).

3. Математик (з алгебри та з геометрії вчиться на 4 і 5).

2. отримати відповіді на такі запитання:

1. Чи є Вяткін відмінником?

2. Визначити всіх відмінників.

3. Визначити всіх двієчників.

4. Чи є Соснін математиком?

3. визначити всіх учнів, що мають погані оцінки з історії;

4. визначити всіх двієчників.

Використати, наприклад такі дані:

Прізвище	Предмети
	алгебра	геометрія	історія
Антонов	5	5	5
Бобров	5	3	2
Вяткін	5	5	5
Кріт	2	3	3
Соснін	4	4	4

9. Побудувати базу знань «Робоча зміна»:

1. Марія працює в денну зміну;

2. Сергій працює у вечірню зміну;

3. Борис працює у вечірню зміну;

4. Валентин працює у вечірню зміну.

5. Два службовців знають один одного, якщо вони працюють в одну зміну. визначити:

1) Чи знає Сергій Бориса?

2) Кого знає Валентина?

3) Кого знає Марія?

4) Хто не знайомий один з одним?

10. Скласти базу знань «Знайомства» з таких фактів і правил:

1. Мері чарівна.

2. Джон добрий.

3. Джон мужній.

4. Джон сильний.

5. Хтось щасливий, якщо багатий чи подобається жінкам.

6. Чоловік подобається жінці, якщо жінка подобається чоловікові, і він добрий, або чоловік добрий і сильний.

7. Чоловікові подобається жінка, якщо вона чарівна.

8. Сформулювати питання:

Чи щасливий Джон?

Знайти чоловіків, які можуть подобатися жінкам.

Логічні задачі:

1) Коля і Саша носять прізвища Шилов та Гвоздьов. Яке прізвище носить кожен з них, якщо Саша з Шиловим живуть у різних будинках?

2) У змаганнях з бігу Юра, Гриша і Толя посіли три перших місця. Яке місце посів кожен хлопець, якщо Гриша посів не друге і не третє місце, а Толя  не третє?

3) Три подруги вийшли в білих, зелених і синіх сукнях і туфлях. Відомо, що тільки у Ані кольори суконь і туфель збігалися. Ні туфлі, ні сукні Валі не були білими. Наташа була в зелених туфлях. Визначити кольори сукні і туфель на кожній з подруг.

4) На заводі працювали троє друзів: слюсар, токар і зварювальник. Їхні прізвища Борисов, Іванов і Семенов. У слюсаря немає ні братів, ні сестер. Він наймолодший із друзів. Семенов, одружений на сестрі Борисова. Він старший від токаря. Назвати прізвища слюсаря, токаря і зварювальника.

5) У пляшці, склянці, глечику і банці знаходяться молоко, лимонад, квас і вода. Відомо, що вода і молоко не в пляшці, посудина з лимонадом знаходиться між глечиком і посудиною з квасом, у банці - НЕ лимонад і не вода. Стакан знаходиться близько банки і посудини з молоком. Як розподілені ці рідини по посудинах?

6) У Івана машина червона, у Петра  не чорна, не синя, і не блакитна, у Михайла  чорна і синя, в Олександра є машини будь-якого кольору (з усіх вищеперерахованих), у Бориса  білого і синього кольорів. У кого якого кольору машина, якщо всі юнаки були на машинах різного кольору?

7) Троє друзів посіли перше, друге і третє місця у змаганнях універсіади. Друзі різної національності, звуть їх по-різному і люблять вони різні види спорту. Майкл грає в баскетбол краще, ніж американець. Ізраїльтянин Саймон грає краще за тенісиста. Гравець у крикет посів перше місце. Хто є австралійцем? Яким спортом захоплюється Річард?

8) Одного разу в Артеку за круглим столом зібралося п'ятеро хлопців родом з Москви, Санкт-Петербурга, Новгорода, Пермі і Томська: Юра, Толя, Альоша, Миколка і Вітя. Москвич сидів між томичанином та Вітею, санкт-петербуржець  між Юрою і Толею, а навпроти нього сиділи перм'як і Альоша. Коля ніколи не бував у Санкт-Петербурзі, а Юра не бував у Москві і Томську, а томичанин з Толею регулярно переписуються. Визначте, у якому місті живе кожен з хлопців.

9) Воронов, Павлов, Левицький і Сахаров  чотири талановиті молоді хлопці. Один з них танцюрист, інший  художник, третій  співак, а четвертий  письменник. Про них відомо наступне:

 Воронов і Левицький сиділи в залі консерваторії в той вечір, коли співак дебютував у сольному концерті.

 Павлов і письменник разом позували художнику.

 Письменник написав біографічну повість про Сахарова і збирається написати про Воронова.

 Воронов ніколи не чув про Левицького. Хто чим займається?

10) Три дівчинки  Роза, Маргарита і Анюта представили на конкурс квітникарів кошики вирощених ними троянд, маргариток і братків. Дівчинка, яка виростила маргаритки, звернула увагу на те, що в жодної з дівчаток ім'я не збігається з назвою улюблених квітів. Які квіти виростила кожна з дівчаток?

11) Винуватець нічної дорожньо-транспортної пригоди зник з місця аварії. Перший з опитаних свідків сказав працівникам ДАІ, що це були "Жигулі", перша цифра номера машини  одиниця. Другий свідок сказав, що машина була марки "Москвич", а номер починався з сімки. Третій свідок заявив, що машина була іноземна, номер починався не з одиниці. При подальшому розслідуванні з'ясувалося, що кожен із свідків правильно вказав або тільки марку машини, або тільки першу цифру номера. Якої марки була машина і з якої цифри починався номер?

12) П'ятеро однокласників: Ірена, Тимур, Камілла, Ельдар і Залім стали переможцями олімпіад школярів з фізики, математики, інформатики, літератури та географії. Відомо, що:

• переможець олімпіади з інформатики вчить Ірену і Тимура роботі на комп'ютері;

• Камілла і Ельдар теж зацікавилися інформатикою;

• Тимур завжди побоювався фізики;

• Камілла, Тимур і переможець олімпіади з літератури займаються плаванням;

• Тимур і Камілла привітали переможця олімпіади з математики;

• Ірена жалкує про те, що у неї залишається мало часу на літературу.

Переможцем якої олімпіади став кожен із учасників?

13) Ірена любить морозиво з фруктами. У кафе був вибір із таких варіантів:

• пломбір з горіхами;

• пломбір з бананами;

• пломбір з чорницею;

• шоколадне з чорницею;

• шоколадне з полуницею.

У чотирьох варіантах Ірені не подобалися або тип морозива, або наповнювач, а в одному варіанті їй не подобалися ні морозиво, ні наповнювач. Вона попросила приготувати з наявних продуктів порцію за своїм смаком. Яке ж морозиво і з якими фруктами любить Ірена?

14) На черговому етапі автоперегонів «Формула 1» перші чотири місця зайняли Шумахер, Алезі, Хілл та Кулхардт. Телерепортер, що запізнився до місця нагородження встигнув зняти пілотів, які посіли друге та третє місця. Вони поливали один одного шампанським. У цей час Шумахер з четвертим гонщиком тиснули один одному руки. Далі в кадр потрапив мокрий Хілл, що вітає пілота, посів друге місце. Наостанок оператор зняв сцену, у якій Шумахер і Кулхардт намагалися витягнути на п’єдестал пошани пілота, який посів четверте місце. Переглядаючи відзнятий матеріал, режисер спортивного випуску швидко розібрався, хто з пілотів яке місце посів. Він сказав, що, відповідно до церемонії нагородження переможців гонок, пілоти, які посіли перші три місця, поливають одни одного шампанським із великих пляшок відомої фірми – спонсора змагань. Яке ж місце зайняв кожен пілот?

15) У деякому царстві почав Змій Горинич розбій чинити. Послав цар чотирьох богатирів погубити Змія, а нагороду за те обіцяв велику. Повернулися богатирі з перемогою, а цар питає в них: «Так хто ж з вас головний переможець, кому дістанеться царева дочка та півцарства?». Засоромилися добрі молодці та дали туманні відповіді:

Ілля Муромець сказав: «Це все Альоша Попович, цар-батюшка».

Альоша Попович заперечив: «То був Микула Селянинович».

Микула Селянинович: «Не правий Альоша, не я це».

Підвернулася тут Баба Яга і говорить царю: «А правий лише один із богатирів, бачила я всю битву своїми очима».

Хто ж із богатирів переміг Змія Горинича?

16) При складанні розкладу на п’ятницю були висловлені побажання, щоб інформатика була першим чи другим уроком, фізика – першим чи третім, історія – другим чи третім. Чи можна задовольнити одночасно всі побажання?

17) Обговорюючи конструкцію нового тримоторного літака, троє конструкторів по черзі висловили такі припущення:

1) у разі відмови другого двигуна потрібно приземлятися, а у разі відмови третього можна продовжити політ.

2) у разі відмови першого двигуна летіти можна, або у разі відмови третього двигуна летіти не можна.

3) у разі відмови третього двигуна летіти можна, проте у разі відмови хоча б одного із інших  треба сідати.

Льотні випробування підтвердили правоту кожного з конструкторів. Визначте, у разі відмови якого з двигунів не можна продовжувати політ.

18) У змаганнях з плавання брали участь Андрій, Віктор, Саша та Діма. Їх друзі висловили припущення щодо ймовірних переможців:

1) першим буде Саша, Віктор буде другим;

2) другим буде Саша, Діма буде третім;

3) Андрій буде другим, Діма буде четвертим;

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

19) Для тривалої міжнародної експедиції на навколоземній космічній станції потрібно із восьми претендентів відібрати шість спеціалістів: з аеронавтиці, космонавігації, біомеханіки, енергетики, медицини та астрофізики. Умови польоту не дозволяють поєднувати роботи за різними спеціальностями, хоча деякі претенденти володіють двома спеціалізаціями. Обов’язки аеронавта можуть виконувати Герреті та Нам; космонавігатора – Кларк і Фріш; біомеханіка – Фріш і Нам; енергетика – Депардьє і Леонов; лікаря – Депардьє і Хорхес; астрофізика – Волков і Леонов.

Зважаючи на особливості їх сумлінності психологічно, лікарі рекомендують поєднати польоти Фріша і Кларка, а також Леонова з Хорхесом і Депардьє. Навпаки, не бажано, щоб Депардьє опинився в одній експедиції з Намом, а Волков – з Кларком. Кого потрібно включити до складу експедиції?

ЛАБОРАТОРНА РОБОТА № 3 ПОВТОРИ І РЕКУРСІЇ

3.1 Пошук з поверненням як реалізація повтору

/*Файл Lab3_1.pro*/

predicates

country(symbol)

print_countries

clauses

country(england).

country(france).

country(germany).

country(denmark).

print_countries :-

country(X),

write(X), /* записати значення X */

nl, /* почати новий рядок */

fail.

goal

print_countries.

3.2 Пошук з поверненням у замкнених системах

Реалізуємо за допомогою стандартного предикату repeat, що визначається так:

repeat.

repeat :- repeat.

Мета предикату repeat  допустити нескінченний пошук з поверненням.

Розглянемо приклад використання repeat для збереження введених із клавіатури символів і вивід їх на екран до тих пір, доки не буде натиснута клавіша Enter (Ввід).

/*Файл Lab3_2.pro*/

predicates

repeat

typewriter

clauses

repeat.

repeat :- repeat.

typewriter :-

repeat,

readchar(C), /* Зчитати символ, його значення привласнити С*/

write(C),

C='\r',!.

goal

typewriter(),nl.

Ця програма дозволяє вводити символи з клавіатури до тих пір, доки не буде натиснутий ВВІД.

Правило typewriter працює так:

1. Виконується repit (котрий нічого не робить).

2. Привласнює змінній C значення символу.

3. Відображає C.

4. Перевіряє, чи відповідає C коду 13.

5. Якщо відповідає, то закінчення. Якщо ні – повертається та шукає альтернативи. Оскільки ні write, ні readchar не є альтернативами, постійно відбувається повернення до repeat, який завжди має альтернативне рішення.

6. Тепер обробка може знову рухатися вперед: зчитувати наступний символ, відображати його та перевіряти на відповідність коду 13 в ASCII.

3.3 Рекурсивні правила та процедури

3.3.1. Рекурсивні правила

Рекурсія – алгоритмічний метод, часто використовуваний в Пролозі. У рекурсивному правилі більш складні вхідні аргументи виражаються через менш складні.

Класичним прикладом рекурсивного визначення в Пролозі може бути програма «Предок», що складається з двох правил (1) і (2):

предок (А, В) : - (1)

батько (А, В).

предок (А, В) : - (2)

батько(С, В),

предок (А, С).

Сукупність цих правил визначає два способи, згідно з якими одне обличчя (А) може бути предком іншого (В). Відповідно до першого правила,

А є предком В, якщо А – батько В.

Відповідно до другого правила, А буде предком В, якщо А є предком батька В, тобто предком С.

Відношення, зображене в заголовку другого правила, залежить від більш простої версії самого себе – від підцілі «предок».

Припустимо, що є база даних «батьки» :

батьки (Анна, Вова).

батьки (Анна, Гена).

батьки (Гена, Витя).

батьки (Витя, Саша).

Нижченаведені запроси ілюструють використання правила «предок»:

Чи є Анна предком Гени?

? предок (Анна, Гена)

Так

Знайти усіх потомків Анни.

?  предок (Анна, Х)

Х= Вова

Х= Гена

Х= Вітя

Х= Саша

/*Програма Lab3_3.pro */

predicates

predok(symbol, symbol)

roditel(symbol, symbol)

clauses

roditel(anna, vova).

roditel(anna, gena).

roditel(gena, victor).

roditel(victor, sasha).

predok (А, В) :-

roditel (А, В).

predok (А, В) :-

roditel (С, В),

predok (А, С).

goal

predok (A, В).

Будь-яка рекурсивна процедура має містити хоча б одну з перерахованих нижче компонент:

1. Не рекурсивну фразу, що визначає вихідний вид процедури, тобто вид процедури на момент закінчення рекурсії. У нашому випадку це правило (1). Як тільки ця фраза стане істиною, подальша рекурсія припиниться.

2. Рекурсивне правило. Перша підціль, розміщена в тілі цього правила, виробляє нові значення аргументів. Далі розміщується рекурсивна підціль, у якій використовуються нові значення аргументів. У нашому прикладі це правило (2). Під час кожного виклику дане правило піднімається на одне покоління вгору. Підціль батько(С, В), що входить у тіло цього правила, виробляє значення змінної С. Потім розміщується підціль предок (А, С), у якій використовується цей новий аргумент.

Непрацездатна версія процедури «предок»

Назвемо цю процедуру «нпредок», вона відрізняється від процедури «предок» лише рядком підцілей у тілі фрази (2):

нпредок (А, В) : - (1’)

батько (А, В).

нпредок (А, В) : - (2’)

нпредок (А, С),

батько (С, В).

З декларативної точки зору сенс процедур «предок» та «нпредок» однаковий. Але при процедурній трактовці сенс процедур «предок» та «нпредок» суттєво відрізняється.

В процедурі «предок» «батько(С, В)» рекурсивного привила виробляє нове значення змінної С, яке потім використовується в рекурсивній підцілі предок (А, С). З іншого боку, у процедурі «нпредок» змінна С не конкретизована в момент обробки рекурсивної підцілі предок(А, С). Це означає що інтерпретатор буде намагатися виконати запит до процедури «нпредок». Спершу він знайде правильні відповіді, а потім буде виконувати рекурсивні дії до повного вичерпання доступного обсягу пам’яті:

?  нпредок(Анна,Х)

Х = Вова

Х = Гена

Х = Витя

Х = Саша

Попередження: Вичерпана стекова пам’ять.

Процедура «нпредок» має назву процедура з лівою рекурсією, оскільки у фразі (2’) рекурсивна підціль стоїть першою, тобто вона знаходиться ліворуч від інших підцілій. Пролог не може надійно обробляти ліворекурсійні процедури, що пояснюється закладеною в нього стратегією вирішення задач.

3.2.2. Рекурсивні процедури

Рекурсивна процедура – це процедура, котра викликає сама себе. Розглянемо обчислення факторіала числа N:

Якщо N дорівнює 1, то факторіал дорівнює 1.

Інакше знайти факторіал N-1 та помножити його на N.

Отже, щоб знайти факторіал 3, необхідно знайти факторіал 2, який потрібно знайти обчисливши факторіал 1. Можна знайти факторіал 1 без звернення до інших факторіалів, тому повторення не почнуться.

Якщо є факторіал 1, то він помножується на 2, щоб отримати факторіал 2, а факторіал 2 у свою чергу помножується на 3, щоб отримати факторіал 3.

У Турбо Пролозі це має такий вигляд: /* Файл Lab3_4.PRО Рекурсивна програма обчислення факторіалів..(Рекурсивний алгоритм)*/

predicates

factorial(unsigned, real)

clauses

factorial(1, 1) :- !.

factorial(X, FactX) :-

Y = X-1,

factorial (Y, FactY),

FactX = X*FactY.

goal

X=3,

factorial (X, FactX).

Розглянемо приклад реалізації обчислення факторіала але за допомогою ітеративного алгоритму, коли аргументи використовуються в якості змінних циклу.

/* Файл Lab3_5.PRО Рекурсивна програма обчислення факторіалів.

(Ітеративний алгоритм)*/

predicates

factorial(unsigned, long)

factorial(unsigned, long, unsigned, long)

clauses

factorial(N, FactN) :-

factorial(N, FactN, 1, 1).

factorial(N, FactN, N, FactN) :- !.

factorial(N, FactN, I, P) :-

NewI = I+1,

NewP = P*NewI,

factorial(N, FactN, NewI, NewP).

goal

X=3,

factorial (X, FactX).

Проміжна інформація зберігається в ділянці пам’яті «стек», яка створюється кожного разу під час виклику правила. Коли виконання правила завершується, зайнята його стеком пам’ять повертається загальному обсягу пам’яті, та виконання продовжується зі стеком, котрий використався до виклику.

Переваги рекурсії:

• Може виражати алгоритми, які неможливо зручно виразити по  іншому.

• Логічно простіша від методу ітерацій.

• Широко поширюється в обробці списків.

Рекурсія  гарний спосіб для опису задач, що містять у собі під задачу того ж типу.

Але у рекурсії є один великий недолік – вона з’їдає пам’ять. Кожного разу, коли одна процедура викликає іншу, інформація про виконання процедури виклику має зберігатися для того, щоб вона (процедура виклику) могла після виконання викликаної процедури відновити виконання на тому же місці, де зупинилася.

Цьому можна запобігти, коли процедура може викликати сама себе без збереження інформації про свій стан, якщо викликаючи процедура не збирається відновлювати роботу після викликаної процедури.

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

Наприклад, процедура А викликає процедуру В, а В викликає С свій останній крок. Коли В викликає С, В не має більше нічого робити. Тому, замість того щоб зберегти для С поточний стан процедури В, ви можете перемістити інформацію із стеку В (який більше не потрібен) у поточний стек С. Коли С закінчить виконання, вона вважатиметься викликаною безпосередньо процедурою А.

А зараз припустимо, що на останньому кроці виконання процедура В, замість процедури С, викликає сама себе. Як нам відомо якщо В викликає В, стек, який викликає В має заміщуватися стеком для викликаної В. Ця операція полягає у присвоєнні аргументам нових значень та поверненні процесору до початку процедури. Тому, для процедури це означає лише оновлення керуючих змінних у циклі.

Ця операція має назву оптимізація хвостової рекурсії, або оптимізація середнього виклику.

Щоб задати хвостову рекурсію, потрібно:

1. Виклик був найостаннішою «підціллю предложения».

2. Раніше «у запиті» не було зворотних точок.

Приклад:

count(N) :  % хвостова рекурсія, яка не вичерпує пам’яті.

write(N), nl,

NewN = N+1,

count(NewN).

Ціль count(0) буде друкуватиме цілі числа, починаючи з 0, і ніколи не зупиниться, що з часом у результаті похибки округлення призведе до друку неточних чисел, проте зупинка не здійсниться.

Помилкові способи хвостової рекурсії:

1. Якщо рекурсивний виклик не є останнім кроком, процедура не є хвостовою рекурсією:

badcount1(X) :-

write(‘\r’, X),

NewX = X+1,

badcount1(NewX),

nl.

2. Другий спосіб зупинити хвостову рекурсію – залишити альтернативу неперевіреною під час виконання рекурсивного виклику. Тоді стек має зберегтися, як у разі невдалого завершення рекурсивного виклику. Процедура може повернутися та шукати альтернативу. Наприклад:

badcount2(X) :-

write(‘\r’, X),

NewX = X+1,

badcount2(NewX).

badcount2(X) :-

X < 0,

write("X is negative.").

3. Для зупинки хвостової рекурсії не обов’язково мати рекурсивну процедуру окремим реченням. Неперевірена альтернатива може також бути і в інших викликаних реченнях.

Наприклад:

badcount3(X) :-

write(‘\r’, X),

NewX = X+1,

check(NewX),

badcount3(NewX).

check(Z) :- Z >= 0.

check(Z) :- Z < 0.

Припустимо, що Х позитивна, як це звичайно буває. Тоді, коли badcount3 викликає себе, перше речення check досягає цілі, а друге речення check ще не виконано. Тому badcount3 зберігає свій стек незмінним, щоб повернутися та виконати друге речення check, немов рекурсивний виклик завершився невдало.