Списки на Прологе Лекция 6. План 1.Метод поиска в глубину 2.Метод отката после неудачи 3.Отсечение и откат 4.Метод поиска, определяемый пользователем. - презентация

1 Списки на Прологе Лекция 6

2 План 1.Метод поиска в глубину 2.Метод отката после неудачи 3.Отсечение и откат 4.Метод поиска, определяемый пользователем

3 Описание [monday, tuesday, wednesday, thursday, friday, saturday, sunday] ["понедельник", "вторник", "среда", "четверг", "пятница", "суббота", "воскресенье"] [1, 2, 3, 4, 5, 6, 7] ['п', 'в', 'с', 'ч', 'п', 'с', 'в'] [] DOMAINS = * listI = integer* listR = real* listC = char* lists = string* listL = listI* /*[[1,3,7],[],[5,2,94],[–5,13]]*/

4 Описание [monday, 1, "понедельник"] DOMAINS element = i(integer); c(char); s(string) listE = element* [i(–15), s("Мама"),c('A'),s("мыла"),c('+'),s("раму"), i(48),c('!')]

5 Рекурсивное описание списка [1, 2, 3] = [1|[2, 3]] = [1|[2|[3]]] = [1|[2|[3|[ ]]]] = [1,2|[3]] = [1, 2, 3|[]] Определение в нотации Бэкуса-Науэра: Список ::= [ ]|[Элемент *]|[Голова|Хвост] Голова ::= Элемент * Хвост ::= Список

6 Вычисление длины списка length([], 0). length([_|T], L) :– length(T, L_T), L = L_T + 1. Внешняя цель: length([1,2,3],X).

7 Проверка принадлежности элемента списку member(X,[X|_]). member(X,[_|T]) :– member(X,T). member2(X,[X|_]). member2(X,[Y|T]):– XY, member2(X,T). member3(X,[X|_]):–!. member3(X,[_|T]):– member3(X,T).

8 Объединение двух списков conc([ ], L, L). conc([H|T], L, [H|T1]) :– conc(T,L,T1).

9 Соседние элементы списка neighbors(X,Y,L):– conc(_,[X,Y|_],L). neighbors2(X,Y,L):– conc(_,[X,Y|_],L); conc(_,[Y,X|_],L).

10 Обращение списка reverse([ ],[ ]). reverse([X|T],Z):– reverse(T,S), conc(S,[X],Z). rev([H|T],L1,L2):– rev(T,[H|L1],L2). rev([ ],L,L). reverse2(L1,L2):– rev (L1,[ ],L2).

11 Получение элемента списка по его номеру n_element([X|_],1,X). n_element([_|L],N,Y):– N1=N–1, n_element(L,N1,Y).

12 Удаление всех вхождений заданного значения из списка delete_all(_,[],[]). delete_all(X,[X|L],L1):– delete_all (X,L,L1). delete_all (X,[Y|L],[Y|L1]):– XY, delete_all (X,L,L1).

13 delete_one(_,[],[]). delete_one(X,[X|L],L):–!. delete_one(X,[Y|L],[Y|L1]):– delete_one(X,L,L1).