Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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




Обчислення суми елементів списку

Видалення зі списку всіх входжень заданого значення.

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

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

Крок рекурсії заснований на тім, що:

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

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

delete_all(_,[],[]).

delete_all(X,[X|L],L1):-

delete_all (X,L,L1).

delete_all (X,[Y|L],[Y|L1]):-

X<>Y,

delete_all (X,L,L1).

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

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

delete_one(_,[],[]).

delete_one(X,[X|L],L):-!.

delete_one(X,[Y|L],[Y|L1]):-

delete_one(X,L,L1).

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

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

delete_one(_,[],[]).

delete_one(X,[X|L],L):-!.

delete_one(X,[Y|L],[Y|L1]):-

delete_one(X,L,L1).

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

 

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

 

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

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

S і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. Створіть предикат, що транспонує матрицю, задану списком списків.




Поделиться с друзьями:


Дата добавления: 2014-01-07; Просмотров: 781; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.009 сек.