русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Сцепление (конкатенация) списков.


Дата добавления: 2013-12-23; просмотров: 3374; Нарушение авторских прав


Определим отношение:

конк(L1,L2,L3), где L1 и L2 – два списка, а L3 – список, получаемый при их сцеплении.

Например: конк([a,b], [c,d], [a,b,c,d]) истинно,

конк([a,b], [c,d], [a,b,a,c,d]) ложно,

конк([a,b], [c,d], [a,b,d,c]) ложно.

Нам придётся рассмотреть два случая в зависимости от вида первого аргумента L1.

1) Если первый аргумент пуст, тогда второй и третий аргументы представляют собой один и тот же список.

На Прологе: конк([ ], L, L).

2) Если первый аргумент отношения «конк» не пуст, то он имеет голову и хвост и выглядит так: [G|Hvost1].

Рассмотрим графически, как происходит сцепление списка [G|Hvost1] с произвольным списком L2.

G Hvost1   L2
 
G Hvost3

 

Hvost1=L1=[G|Hvost1],

L2=L2

Hvost3=L3=[G|Hvost3], где Hvost3 получен путём сцепления Hvost1 и L2.

На Прологе: конк([G,Hvost1], L2, [G|Hvost3]) :- конк(Hvost1, L2, Hvost3).

Отношение «конк» можно использовать в обратную сторону, т.е. для разбиения заданного списка на две части.

Например, если задать Пролог-системе вопрос: ?конк(L1,L2,[a,b,c]),

то Пролог-система выдаст последовательно все варианты разбиения:

L1=[ ] | L1=[a] | L1=[a,b] | L1=[a,b,c]

L2=[a,b,c] | L2=[b,c] | L2=[c] | L2=[ ]

 



Также, отношение конк можно использовать для поиска в списке комбинации элементов, отвечающей некоторому условию, задаваемому в виде шаблона или образца.

Например, можно найти все месяцы, предшествующие данному, и все месяцы, следующие за ним, сформулировав цель:

?конк(Do, [“май” | Posle], [“янв”, “февр”, “март”, “апр”, “май”, “июнь”, “июль”, “авг”, “сент”, “окт”, “нояб”, “дек”]).

Ответ: Do=[“янв”, “февр”, “март”, “апр”]

Posle=[“июнь”, “июль”, “авг”, “сент”, “окт”, “нояб”, “дек”]

 



Вопрос: что мы узнаём, задав вопрос:

?конк( _, [M1, “май”, M2 | _], [“янв”, “февр”, “март” …“дек” ].

Ответ: мы узнаём месяц, непосредственно предшествующий маю и следующий за маем.

М1=”апрель”

М2=”июнь”.

 



Вопрос: удалить из списка L1 всё, что следует за тремя последовательными вхождениями элемента Z в L1 вместе с этими тремя Z.

? L1=[a,b,z,z,c,[z,z,z|d,e],

конк(L2,[z,z,z| _ ], L1).

Ответ: L1=[a,b,z,z,c,z,z,z,d,e]

L2=[a,b,z,z,c]

 



С помощью отношения “конк” можно также определить отношение принадлежности

принадлежит2(X,L) :- конк(L1,[X|L2],L).

Элемент X принадлежит списку L, если список L можно разбить на два списка таким образом, чтобы элемент X являлся головой второго из них.

 



Задание:

1) Используя отношение “конк”, напишите цель, соответствующую вычёркиванию трёх последних элементов списка L. Результат – новый список L1

Ответ: конк(L1,[ _, _, _], L).

 



2) Напишите последовательность целей для нахождения списка L2, получающегося из списка L вычёркиванием его трёх первых и трёх последних элементов.

Ответ: 1 вариант: конк([ _, _, _],L1, L),

конк([ _, _, _], L1).

2 вариант: конк([ _, _, _],L2),[ _, _, _], L).

3) Определить отношение последний(EL, SP) так, чтобы элемент EL являлся последним элементом списка SP.

Ответ: 1 вариант: последний(EL, SP) :- конк( _ , [EL], SP).

2 вариант: последний(EL, [First|Ost]) :- последний(EL, Ost).

 



Управление перебором в Пролог-системе.

  1. Предикат отсечения ! – обозначение.

В процессе достижения целей Пролог-система осуществляет автоматический перебор вариантов, делая возврат при неуспехе какого-либо из них. Такой перебор – полезный механизм, который освобождает пользователя от необходимости программировать его самому. С другой стороны неограниченный перебор может стать источником неэффективности программы. Поэтому иногда его следует ограничить или исключить полностью. Для этого в Прологе используется конструкция отсечение.

Пример.

Добавим:

отец (“Том”,”Боб”).

отец (“Том”,”Лиз”).

отец (“Боб”,”Пат”).

отец (“Боб”,”Энн”).

И отношение дед:

дед (X,Y) :- отец (Z,Y), отец (X,Z).

Вопрос:

? дед (Х,”Боб”).

Шаги вычисления:

1) Y=”Боб” отец (Z, ”Боб”), отец (X,Z).

2) Z=”Том” отец (X,”Том”).

3) отец (X,”Том”).

Fail – происходит возврат.

Чтобы остановить работу механизма возврата, после доказательства 1 цели в теле правила «дед» ставится предикат отсечения.

дед (X,Y) :- отец (Z,Y), !, отец (X,Z).

Не могут быть пересогласованы цели, стоящие до отсечения, даже если они включают и головную часть.

  1. Предикат fail – неуспех, true – успех. Это 2 предиката для управления перебором.

Предикат fail всегда терпит неудачу, true – заканчивается успешно.

Пример.

«Энн встречается со всеми своими родственницами, кроме Лиз».

встречается (“Энн”, Х) :- X=”Лиз”, !, fail.

встречается (“Энн”, Х) :- женщина (Х).

различны (Х, Х) :- !, fail.

различны (_, _).

различны (Х, Y) :- X=Y, !, fail; true.

  1. Предикат repeat. Это цель, которая всегда успешна и всегда может быть пересогласована при возврате.

имя :- repeat, nl, write (“Имя:”), readln(X), встречается (“Энн”, X).

nl – перемещение позиции ввода к началу текущей строки.

readln(X) – чтение

write(X) – вывод.

Решение головоломок методом «образовать и проверить».

Метод «образовать и проверить» - это общий приём, используемый при проектировании алгоритмов и программ. Суть его состоит в том, что один процесс или программа генерирует множество предполагаемых решений задачи, а другой процесс или программа проверяет эти предполагаемые решения, пытаясь найти те из них, которые действительно являются решениями задачи. Используя вычислительную модель Пролога, легко создавать логические программы, реализующие этот метод. Обычно такие программы содержат конъюнкцию двух целей, одна из которых действует как генератор предполагаемых решений, а вторая проверяет, являются ли эти решения приемлимыми:

find(X) :- generate(X), test(X).

Такая Пролог-программа действует подобно обычной процедурной программе, выполняющей генерацию вариантов и их проверку. Процесс продолжается итерационно до тех пор, пока при успешной проверке не будет найдено решение с характерными свойствами или генератор не исчерпает все альтернативные решения.

Однако, программисту нет необходимости интересоваться циклом «образовать и проверить». Он может рассматривать этот метод более абстрактно, как пример недетерминированного программирования. В качестве генератора обычно используется программа для предиката принадлежности:

member (X, [X|H]). /*предикат принадлежности

member (X, [_|H]) :- member (X,H).

Этот предикат порождает множество решений.

На вопрос ? member (X, [a,b,c]) будут даны в требуемой последовательности решения X=a X=b X=c.

Таким образом, предикат member можно использовать в программах, реализующих метод «образовать и проверить» для недетерминированного выбора корректного элемента из некоторого списка.

В качестве примера рассмотрим решение следующей логической головоломки:

Три друга заняли 1, 2 и 3 места в соревнованиях универсиады. Друзья – из разных стран, их зовут по-разному и любят они разные виды спорта. Известно, что:

1) Майкл предпочитает баскетбол и играет лучше, чем американец.

2) Англичанин Саймон играет лучше теннисиста.

3) Игрок в крикет занял первое место.

Необходимо ответить на вопросы:

1. Кто является австралийцем?

2. Каким спортом занимается Ричард?

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

Проанализируем первый ключ к разгадке: «Майкл предпочитает баскетбол и играет лучше, чем американец». Очевидно. Речь идёт о двух разных людях. Одного зовут Майклом и он занимается баскетболом, в то время как второй – американец. Кроме того, Майкл лучше играет в баскетбол, чем американец.

Предположим, что Friends – это структура данных, подлежащая конкретизации, тогда наш ключ может быть выражен следующей конъюнкцией целей:

play_best (Man1, Man2, Friends), /*играет лучше

name (Man1, “Майкл”), /*имя 1-го мужчины

sport (Man1, “Баскетбол”), /*Майкл предпочитает баскетбол

country (Man2, “Американец”), /*2-ой мужчина – американец.

Аналогично второй ключ можно представить конъюнкцией целей:

play_best (Man1, Man2, Friends),

name (Man1, “Саймон”),

country (Man1, “Англичанин”),

sport (Man2, “Теннис”),

Наконец, третий ключ к разгадке выразится следующим образом:

first (Friends, Man), /*первый

sport (Man, “Крикет”),

Базовая программа для решения головоломок имеет вид:

решить_головоломку (головоломка(Ключи,Вопросы,Решения)) :-

решить(Ключи),

решить (Вопросы).

решить ([Ключ|Ключи]) :-

Ключ,

решить (Ключи).

решить ([]).

Всё, что делает эта программа – это последовательное решение каждого ключа и вопроса, которые представляются как цели Пролога и выполняются с использованием метапеременных.

Ключи и вопросы для нашего примера à в программе №2. Но сначала рассмотрим структуру, представляемую ключами, для решения этой головоломки.

Каждый человек имеет 3 атрибута и может быть представлен структурой:

friend (Name, Country, Sport) /*друг (Имя, Страна, Спорт)

Есть три друга, распределение которых в итоге соревнований имеет существенное значение. Это наводит на мысль выбрать в качестве структуры данных для решения задачи упорядоченную последовательность из 3-х элементов, то есть список:

[friend(N1,C1,S1), friend(N2,C2,S2), friend(N3,C3,S3)]

Программа №2:

puzzle :- /*головоломка

structure (Struct), /*структура

key (Stuct), /*ключи

question (Struct, Name, Sport), /*вопросы

solution (Name, Sport). /*решение

structure([friend(_,_,_), friend(_,_,_), friend(_,_,_)]).

key (Friends) :-

play_best (Man1Kl1, Man2Kl1, Friends), /*ключ1

name (Man1Kl1, ”Майкл”),

sport (Man1Kl1, ”Баскетбол”),

country (Man2Kl1, “Американец”),

play_best (Man1Kl2, Man2Kl2, Friends), /*ключ2

name (Man1Kl2, ”Саймон”),

country (Man1Kl2, “Англичанин”),

sport (Man2Kl2, ”Теннис”),

first (Friends, ManKl3), /*ключ3

sport (ManKl3, ”Крикет”).

question (Friends, Name, Sport) :-

member (Man1, Friends), /*вопрос1

name (Man1, Name),

country (Man1, “Австралиец”),

member (Man2, Friends), /*вопрос2

name (Man2, “Ричард”),

sport (Man2, Sport),

solution (Name, Sport) :-

write (“Австралийца зовут ”), write (Name), nl,

write (“Ричард играет в ”), write (Sport).

play_best (A, B, [A,B,C]). /* играет лучше

play_best (A, C, [A,B,C]).

play_best (B, C, [A,B,C]).

name (friend (A, B, C), A). /*имя

country (friend (A, B, C), B). /*страна

sport (friend (A, B, C), C). /*спорт

first ([G|H], G). /*первый

member (X, [X|H]).

member (X, [_|H]) :- member (X, H).

Каждая из целей play_best и member имеет дело с людьми, а остальные цели обращаются к атрибутам людей. Какие функции они выполняют – генерацию или проверку, зависит от того, конкретизированы из аргументы или нет.

Задание; пользуясь изложенным выше методом, написать программу решения головоломки Эйнштейна:

В пяти домах, окрашенных в разные цвета, обитают мужчины разных национальностей. Они держат разных животных, предпочитают разные напитки и курят сигареты разных марок. Известно, что:

1) Англичанин живёт в красном доме.

2) У испанца есть собака.

3) Кофе пьют в зелёном доме.

4) Украинец пьёт чай.

5) Зелёный дом – первый по правую руку от дома цвета слоновой кости.

6) Курильщик «Уинстона» держит улиток.

7) Сигареты «Кул» курят в жёлтом доме.

8) Молоко пьют в среднем доме.

9) Норвежец живёт в крайнем слева доме.

10) Мужчина, курящий «Честерфилд», живёт в доме, соседним с домом мужчины, у которого есть лиса.

11) Сигареты «Кул» курят в доме, соседним с домом, где имеется лошадь.

12) Мужчина, предпочитающий «Лайки Страйк», пьёт апельсиновый сок.

13) Японец курит сигареты «Парламент».

14) Норвежец живёт в доме рядом с голубым домом.

Вопросы:

1. У кого есть зебра?

2. Кто пьёт воду?

man (Country, Color, Animal, Sigaret, Napitok).



<== предыдущая лекция | следующая лекция ==>
Удаление элемента. | Вопрос 1. Пропорции в костюме


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

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