Студопедия

КАТЕГОРИИ:


Архитектура-(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)

Решение задачи о размещения на Прологе

План

ПРОЛОГ. РЕКУРСИВНЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ

1. Рекурсия

2. Задача о размещениях

3. Задача о сумме

4. Задача о кроликах (числа Фибоначчи)

5. Задача о Ханойской башне

6. Задача о предках и правнуках

7. Восходящие методы решения

 

Рекурсия является мощным средством программирования. В Прологе она приобретает особую важность, поскольку в нем отсутствуют циклические конструкции while.. do и repeat.. until, присущие обычным языкам программирования.

Рекурсия это сведение решения задачи к ней же, но меньшей размерности. Новую задачу можно свести к еще меньшей размерности и этот процесс продолжается до тех пор, пока задача не станет настолько простой, что ее можно решить непосредственно. Способ, при котором решение состоит из двух фаз: первая фаза – разбиения на подзадачи, вторая фаза – решение подзадач, называется нисходящей стратегией. Он прост, но не всегда эффективен.

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

Например, имеются следующие факты о том, какая валюта котируется выше:

doroje(dollar, rubl). - дороже

doroje(evro, rubl).

doroje(rubl, iena).

doroje(funt, euro).

Выполним запрос:

? doroje(evro, rubl).

Yes

Будет получен утвердительный ответ, поскольку такой факт явно описан в программе. Если же сделать запрос,

? doroje(evro, iena).

То ответ будет отрицательный, поскольку такой факт отсутствует. Аналогичным будет ответ на вопрос:

? doroje(funt, rubl).

Избежать противоречий здесь можно введением правила, в котором допустимо сравнение между собой не только двух, но и трех объектов:

doroje1(X, Y):- doroje(X, Y). /* два объекта */

doroje1(X, Y):- doroje(X, Z), doroje(Z, Y). /* три объекта */

Второе правило описывает, очевидно, вариант, когда X>Z, а Z>Y, откуда делается вывод, что X>Y.

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

doroje2(X, Y):- doroje(X, M), doroje(M, K), doroje(K, Z), doroje(Z, Y).

Описывать такие длинные правила неудобно. Здесь выгоднее применить рекурсию, обратившись к правилу из самого этого правила:

doroje1(X, Y):- doroje(X, Y).

doroje1(X, Y):- doroje(X, Z), doroje1(Z, Y).

Первое предложение в этой конструкции определяет момент прекращения рекурсивных вызовов.

Второе правило описывает возможности рекурсивных вызовов, когда существуют непроверенные варианты решения.

Вообще, любая рекурсивная процедура должна содержать хотя бы одну из двух компонент:

1. Нерекурсивную фразу, определяющую правило, применяемое в момент прекращения рекурсии.

2. Рекурсивное правило, первая подцель которого вырабатывает новые значения аргументов, а вторая – рекурсивная подцель – использует эти значения.

База правил просматривается сверху вниз. Сначала делается попытка выполнения нерекурсивной фразы. Если условие окончания рекурсии не указано, то правило может работать бесконечно.

 

Задача о размещениях

Например, приглашено n гостей. Необходимо рассадить их с учетом привязанностей, характеров и т.п. Сколько вариантов надо перебрать? То есть сколькими способами можно разместить гостей? Задача легко решается рекурсивно.

Пусть известно, что рассадить n-1 гостей можно F(n-1) способами. Куда можно посадить n-того гостя? Перед первым, перед вторым,..., перед последним и после последнего. Всего n вариантов. Тогда общее количество вариантов – F(n-1) = F(n)*n. А какая самая простая подзадача? – рассадить одного человека. Ее решение F(1) = 1.

Окончательное решение

F(n-1) = F(n)*n

F(1) = 1

Это всем известная формула для факториала n! = (n-1)!*n.

predicates

fact(integer, integer)

clauses

fact(1, 1).

fact(N, P):-N1=N-1, fact(N1, P1), P=P1*N.

 

Предикат fact включает два аргумента. Первый аргумент – размер задачи (число гостей), второй – результат (число размещений). В Прологе первым всегда пишется предикат для решения простого случая. В данном случае при аргументе n=1, результат тоже равен единице. Второе правило состоит из трех подцелей. Первая – это уменьшение размерности задачи (к сожалению Пролог запрещает писать в качестве параметров предиката арифметические выражения). Вторая подцель – рекурсивное обращение с уменьшенным значением аргумента n. Третья подцель – формирование общего решения из только, что полученного.

Задача о сумме натуральных чисел S = 1 + 2 + 3 + … + n.

Получим рекуррентную формулу для вычисления суммы. Для этого вычтем из Sn Sn-1

Sn = 1 +2 +... + (n-1) + n

Sn-1 = 1 + 2 +... + (n-1)

- - - - - - - - - - - - - - - - - - - - - -

Sn – Sn-1 = n

 

Sn = Sn-1 + n

S0 = 0

Программу на Прологе составить самостоятельно.

Общая Хвостовая
Sum(0,0). Sum(N,S): - N1 = N –1, Sum(N1,S1), S = S1+N, N1>=0. Sum(N,S): - Sm(N,S,1,0). Sm(N,S,N0,S0): - N0 <= N, N1=N0 + 1, S1= N0 + S0, Sm(N,S,N1,S1). Sum(_,S,_,S).

 

Задача о числах Фибоначчи

Фибоначчи – итальянский математик (12 век). Решая задачу о размножении кроликов, получил ряд чисел, названых в честь него – числами Фибоначчи. Система счислении на числах Фибоначчи. Золотое сечение – lim F(n+1)/F(n) при n ® ¥.

Семья кроликов приносит ежемесячно приплод, начиная со 2 месяца. Сколько кроликов будет на n-том месяце, если вначале была одна семья, кролики не умирают и не съедаются.

F(n) = F(n-1) + F(n-2)

F(1) = 1

F(2) = 2

 

predicates

fib(integer, integer)

clauses

fib(1, 1).

fib(2, 1).

fact(N, F):- N1=N-1, N2=N-2, fib(N1, F1), fib(N2,F2), F =F1 + F2.

 

Задача о ханойской башне

Рассмотрим задачу «Ханойская башня» которую, как говорят, придумал в 1883 г. французский математик Люка.

Имеются три стержня, на одном из которых помещены N колец разного диаметра, при этом, чем меньше диаметр кольца, тем выше оно лежит (рис. 1). Например, для четырех колец получается картинка:

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

Если ввести обозначения:

<a,b> элементарная операция-перемещение диска со стержня с номером a на стержень b,

(m,a,b) программа перемещения m дисков с a на b.

(1,a,b) → <a,b> перемещение одного диска – элементарная операция.

Очевидно можно записать:

(m,a,b) → (m-1,a,c) <a,b> (m-1,c,b)

Т. е. для перемещения m-дисков с a на b нужно:

1) Переместить m-1 – диск с a на c (с – вспомогательный стержень).

2) Переместить нижний диск с номером m с a на b.

3) Переместить m-1 – диск с c на b (с – вспомогательный стержень).

Здесь возникает рекурсия – целевое действие определяется через промежуточные действия того же вида.

Например, пусть m = 3, т. е. имеется три кольца. Тогда:

(3,1,3)→(2,1,2)<1,3>(2,2,3)

Можно переписать в виде

(3,1,3)→ (2,1,2) <1,3> (2,2,3)

→ (1,1,3)<1,2>(1,3,2) <1,3> (1,2,1)<2,3>(1,1,3)

Окончательно:

<1,3><1,2><3,2><1,3><2,1><2,3><1,3>

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

 

Существует «восточная легенда» (которую, как говорят, придумал тот же математик Люка), согласно которой в одной из пещер Гималаев три буддийских монаха решают эту задачу для 64 колец. Когда они переложат все кольца, наступит конец света.

Решение задачи требует 2n-1 действий. Если считать, что одно действие выполняется за 1 с, то уже для 40 колец должно потребоваться более 2000000 лет, что звучит достаточно оптимистически.

Программа 3 решает задачу «Ханойская башня» на ПРОЛОГе.

Программа 3

DOMAINS

loc =right;middle;left

PREDICATES

hanoi(integer)

move(integer,loc,loc,loc)

inform(loc,loc)

GOAL

hanoi(5).

CLAUSES

hanoi(N):- move(N,left,middle,right).

move(1,A,_,C):- inform(A,C),!.

move(N,A,B,C):- N1=N-1, move(N1,A,C,B), inform(A,C),

move(N1,B,A,C).

inform(Loc1, Loc2):- nl,write(“Диск с”, Loc1, “ на “, Loc2).

 

<== предыдущая лекция | следующая лекция ==>
Хорновские дизъюнкты | Сутність і класифікація ризиків
Поделиться с друзьями:


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


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



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




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