Язык логического программирования ПРОЛОГ. Бураков М.В. - 20 стр.

UptoLike

Составители:

Рубрика:

рекладывания верхнего диска с одного из стержней на другой стержень.

При этом больший диск никогда нельзя ставить на меньший диск.

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

<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 колец. Когда они пе-

реложат все кольца, наступит конец света.

Рис. 1

12 3