Главная » Free Pascal » Ханойские башни Free Pascal

0

Одной из самых интересных рекурсивных программ является компьютерная модель игры "Ханойские  башни".  Придумал  эту  игру  французский  математик Э. Люка. На деревянной подставке были установлены три иглы, на первую из кото- рых было насажено несколько дисков разного диаметра (рис. 9.8).

Игла 1                              Игла 2                              Игла 3

Рис. 9.8. Игра "Ханойские башни"

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

Рекламная кампания, имевшая целью повышение уровня продаж, сообщала: "Игра является моделью пирамиды браминов, установленной в храме индийского города Бенарес. Настоящая пирамида состоит из 64 золотых дисков, насаженных на один из трех алмазных стержней. Брамины круглосуточно перекладывают дис- ки, чтобы переместить пирамиду с первого стержня на третий в соответствии с ука- занными выше правилами. За 1 секунду перемещается один диск. Когда пирамида будет полностью перемещена, наступит конец света". История умалчивает о том, как индийский храм перекочевал во Вьетнам.

Можно показать, что "конец света" должен был наступить через

264 -1 секунд

после начала миссии браминов. Доказательство этого факта выполняется по ин- дукции. На малом количестве дисков (n = 1, 2, 3) мы убеждаемся, что операция по переносу выполнима за 1, 3 и 7 шагов. Предполагая, что оценка верна для (n – 1)-го диска, т. е. требует ( 2n-1 -1 ) шагов, покажем, что она справедлива и для дисков. Проведем эту операцию в три этапа:

± перенесем верхние n – 1 дисков со стержня 1 на стержень 2, затратив шагов;

2n-1 -1

± перенесем самый большой диск со стержня 1 на стержень 3 за 1 шаг;

± перенесем – 1 дисков со стержня 2 на стержень 3, затратив 2n-1 -1 шагов; Общее число шагов, которое нам потребовалось, равно

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

Обозначим через MT (от англ. move tower) исходную задачу — MT(n,1,3). Очевидно, что она может быть сведена к решению трех подзадач меньшей размер- ности:

± MT(n-1,1,2) — перенос верхних n – 1 дисков со стержня 1 на стержень 2;

± MD(1,3) — перенос оставшегося диска со стержня 1 на стержень 3;

± MT(n-1,2,3) — перенос n – 1 диска со стержня 2 на стержень 3.

Эти соображения наводят на мысль, что для моделирования игры было бы по- лезно написать рекурсивную процедуру переноса башни MT(n, from_b, to_b, work_b), где:

± n — количество перемещаемых дисков;

± from_b — номер стержня, с которого диски перемещаются;

± to_b — номер стержня, на который перемещаются диски;

± work_b — номер стержня, используемого в качестве рабочего.

Очевидно, что процедура MT(n,i,j,k) сводится к выполнению трех следующих процедур:

MT(n-1,i,k,j); MD(i,j);

MT(n-1,k,j,i);

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

   Листинг 9 .1 5 .  Программа  Hanoj                                               

program Hanoj; var n:integer;

procedure MD(from_b,to_b:integer); begin

write(from_b,’->’,to_b,’   ‘); end;

procedure MT(n, from_b, to_b, work_b : integer); begin

if n>0 then begin

MT(n-1,from_b, work_b, to_b); MD(from_b, to_b);

MT(n-1, work_b, to_b, from_b);

end; end; begin

write(‘n = ‘); readln(n);

MT(n,1,2,3);

readln; end.

Результат ее работы по переносу 5 колец отображен на рис. 9.9.

Рис. 9.9. Перенос "Ханойской башни"

Источник: Кетков, Ю. Л., Свободное программное обеспечение. FREE PASCAL для студентов и школьников, Ю. Л. Кетков, А. Ю. Кетков. — СПб.: БХВ-Петербург, 2011. — 384 с.: ил. + CD-ROM — (ИиИКТ)

По теме:

  • Комментарии