Пошук максимального елемента списку

Сума_списку(L,S).

Тут S - сума елементів списку L.

сума_списку([],0).

сума_списку([H|T],S):- number(H),

сума_списку(T,S1), S = S1+H.

Декларативний зміст цього алгоритму: якщо список порожній, то сума його елементів дорівнює нулю, інакше список можна поділити на голову H і хвіст T; сума елементів такого списку S, сума елементів хвоста T є S1 й S=S1+H.

Тут знадобиться допоміжний предикат max, що вибирає максимальне значення із двох елементів:

max(X,Y,X):- X>=Y.

max(X,Y,Y):- X<Y.

Результуючий предикат maxlіst(LІST,MAX), де MAX - найбільший елемент списку LІST, визначається так:

maxlіst([X],X).

maxlіst([X,Y|T],MAX):-

maxlіst([Y|T],MAXT), max(X,MAXT,MAX).

Зміст базового правила: максимальний елемент одноелементного списку дорівнює саме цьому елементу. Інакше, якщо в списку є хоча б два елементи X і Y, обирається максимальний елемент хвоста MAXT і при цьому MAX дорівнює найбільшому з X і MAXT.

Самостійні завдання

1. Дати альтернативні визначення наведених відношень й їхнього застосування.

2. Наведіть приклади задач, що використають розглянуті відношення.

3. Напишіть процедури мовою Пролог для рішення наступних задач і наведіть приклади їхнього використання:

a. перестановки, сортування елементів списку чисел;

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

c. пошуку другого за величиною елемента списку;

d. формування нового списку з тих елементів даного списку, які займають непарні позиції. Наприклад, зі списку чисел [1, 2, 3, 4, 5, 6, 7] потрібно одержати наступний: [1, 3, 5, 7].

4. Створіть предикат, що замінює у вихідному списку перше входження заданого значення іншим.

5. Створіть предикат, що замінює у вихідному списку всі входження заданого значення іншим.

6. Створіть предикат, що породжує по заданому натуральному числу N список, що складається з натуральних чисел від 1 до N (по зростанню).

7. Створіть предикат, що породжує по заданому натуральному числу N список, що складається з натуральних чисел від N до 1 (по убуванню).

8. Створіть предикат, що породжує по заданому натуральному числу N список, що складається з N випадкових натуральних чисел із проміжку від 1 до 100.

9. Створіть предикат, що породжує по заданих числах N, M, K список, що складається з N випадкових натуральних чисел із проміжку від M до K.

10. Створіть предикат, що породжує по заданих числах M, K список, що складається з випадкової кількості випадкових чисел із проміжку від M до K.

11. Створіть предикат, що породжує список, який складається з випадкової кількості випадкових чисел.

12. Створіть предикат, що збільшує елементи вихідного списку на одиницю.

13. Створіть предикат, що переводить список цифр від 0 до 9 у список відповідних їм назв (рядків).

14. Створіть предикат, що переводить список чисел у список відповідних їм назв.

15. Створіть предикат, що переводить список цифр від 0 до 9 у список відповідних їм римських чисел.

16. Створіть предикат, що переводить список арабських чисел у список відповідних їм римських чисел.

17. Створіть предикат, що переводить список римських чисел у список відповідних їм арабських чисел.

18. Створіть предикат, що подвоює значення елементів списку.

19. Створіть предикат, що перетворює список, елементами якого є числа, у список, елементи якого не від'ємні.

20. Створіть предикат, що перетворює вихідний список у список позицій негативних елементів.

21. Створіть предикат, що видаляє з вихідного списку елементи з парними номерами.

22. Створіть предикат, що розділить вихідний список із цілих чисел на два списки: список позитивних чисел і список негативних чисел.

23. Створіть предикат, що розділяє вихідний список на два підсписка. У перший з них повинні потрапити елементи з непарними номерами, у другий - елементи з парними номерами.

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

25. Створіть предикат, що здійснює видалення зазначеної кількості останніх елементів вихідного списку.

26. Створіть предикат, що здійснює поділ вихідного списку на два подсписка. У перший з них повинна потрапити зазначена кількість елементів з початку списку, у другий - елементи, що залишились.

27. Створіть предикат, що здійснює поділ вихідного списку на два подсписка. У перший з них повинна потрапити зазначена кількість елементів з кінця списку, у другий - елементи, що залишилися.

28. Створіть предикат, що знаходить передостанній елемент списку.

29. Створіть предикат, що видаляє передостанній елемент списку.

30. Створіть предикат, що замінює у вихідному списку два однакових елементи, що йдуть підряд, одним.

31. Створіть предикат, що видаляє у вихідному списку всі повторні входження елементів.

32. Створіть предикат, що здійснює перестановку двох елементів списку із заданими номерами.

33. Створіть предикат, що генерує всі перестановки елементів списку, заданого першим аргументом.

34. Створіть предикат, що здійснює циклічне зрушення елементів списку на один уліво (вправо).

35. Створіть предикат, що здійснює циклічне зрушення елементів списку на задану кількість кроків уліво (вправо).

36. Створіть предикат, що здійснює поелементне перемножування відповідних елементів двох вихідних списків.

37. Створіть предикат, що обчислює скалярний добуток векторів, заданих списками цілих чисел.

38. Створіть предикат, що здійснює підрахунок числа входжень кожного елемента вихідного списку. Відповіддю повинен бути список пар, у яких перший компонент - елемент вихідного списку, другий - число його входжень у первісний список.

39. Створіть предикат, що визначає першу позицію підсписка в списку.

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

41. Створіть предикат, що за списком і двом числам M і N повертає підсписок вихідного списку, що складається з елементів з номерами від M до N.

42. Створіть предикат, що формує список простих чисел, що не перевершують дане число.

43. Створіть предикат, що транспонує матрицю, задану списком списків.

44. Сформировать список [2, 4, 6, 8, 10] и удалить из него введенное число.

45. Сформировать списки [1, 3, 5, 7, 9] и [2, 4, б, 8, 10] и объединить их в один.

46. Сформировать список [3, 6, 9, 12, 15, 18] и вставить в него введенное число.

47. Сформировать список из N натуральных чисел, начиная с 10. Каждое следующее на 5 больше предыдущего.

48. Сформировать список [3, 6, 9, 12, 15] и найти сумму его элементов

49. Сформировать список [6, 5, 4, 3, 2] и найти сумму его элементов

50. Сформировать список [7, 5, 3, 1] и найти произведение его элементов

51. Сформировать список из N последовательных натуральных чисел, начиная с 10. Найти сумму его элементов

Лекція 7

КЕРУВАННЯ ПОШУКОМ РІШЕНЬ

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

Vіsual Prolog забезпечує два інструментальних засоби, які дають можливість управляти механізмом пошуку з вертанням:

· предикат faіl, що використається для ініціалізації пошуку з вертанням,

· cut або відсікання (позначається знаком оклику!) - для заборони можливості вертання.

Використання предиката faіl

Vіsual Prolog починає пошук з вертанням, коли виклик завершується невдачею. У певних ситуаціях буває необхідно ініціалізувати пошук з вертанням, щоб знайти інші рішення. Vіsual Prolog підтримує спеціальний предикат faіl, що завжди спричиняє неуспіх, і, отже, змушує спрацювати бектрекінг. Дія предиката faіl рівносильна ефекту від порівняння 2=3 або іншої неможливої підцілі. Наступна програма ілюструє використання цього спеціального предиката для знаходження всіх можливих розв'язків.

domaіns

name = symbol

predіcates

Дата добавления: 2014-01-04