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

Фибоначчи – итальянский математик (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).