Ханойские башни на Scheme

1 February, 2008 (21:02) | Задачи

Отвлечемся немного от решения упражнений (пятница, все же) и решим красивую задачку, которой в упражнениях к SICP нет (по крайней мере, пока не встретилось).

Задача о Ханойских башнях является классической алгоритмической задачей. Формулируется она следующим образом.

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

  1. за один раз можно перемещать только один диск;
  2. больший диск нельзя располагать на меньшем диске;
  3. снятый диск необходимо надеть на какой-либо шпиль перед тем, как будет снят другой диск.

Переносом дисков занимаются буддийские монахи и, по легенде, когда они закончат эту работу, наступит конец света (случится это, впрочем, не скоро).

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

Обозначим шпили буквами a, b и c. Отметим, что для того, чтобы перенести n дисков со шпиля a на шпиль b, используя шпиль c как вспомогательный, нам достаточно выполнить следующие действия:

  1. перенести n-1 диск со шпиля a на шпиль c, используя b как вспомогательный;
  2. перенести единственный оставшийся на шпиле a самый большой диск на шпиль b;
  3. перенести n-1 диск со шпиля c на шпиль b, используя a как вспомогательный.

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

Обозначая перенос диска со шпиля a на шпиль b как список из двух элементов (a b) и формируя план переноса дисков как список таких двухэлементных списков, можем записать элегантное и простое решение программы на языке Scheme:

(define (hanoi n src dest inter) 
  (if (= n 0) 
      null 
      (append (hanoi (- n 1) src inter dest) 
              (list (list src dest)) 
              (hanoi (- n 1) inter dest src))))

Для того, чтобы получить план переноса 64 дисков, достаточно будет сделать вызов (hanoi 64 1 2 3), где 1,2 и 3 – это просто номера шпилей (вместо номеров можно задавать произвольные идентификаторы шпилей).

Comments

Pingback from SICP по-русски » Blog Archive » Решение упражнения 2.42 из SICP
Date: February 3, 2008, 12:47 pm

[…] SICP по-русски Структура и интерпретация компьютерных программ: заметки и решения « Ханойские башни на Scheme […]

Comment from psv
Date: December 7, 2008, 12:06 am

мда а легенду о алмазных дисках и конце света не читали? и вместо null лучше ‘() писать.

Write a comment