КАТЕГОРИИ: Архитектура-(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 Программу на Прологе составить самостоятельно.
Задача о числах Фибоначчи Фибоначчи – итальянский математик (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; Просмотров: 1027; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |