Ханойские башни Free Pascal.Одной из самых интересных рекурсивных программ является компьютерная модель игры "Ханойские башни". Придумал эту игру французский математик Э. Люка. На деревянной подставке были установлены три иглы, на первую из кото- рых было насажено несколько дисков разного диаметра (рис. 9.8). Игла 1 Игла 2 Игла 3. Рис. 9.8. Игра "Ханойские башни" Цель игры заключалась в переносе пирамиды дисков с первой иглы на третью. По правилам игры за один ход можно перенести один диск, перекладывая его на ту или иную иглу. Переносимый диск может ложиться только на диск большего диа- метра. Рекламная кампания, имевшая целью повышение уровня продаж, сообщала: "Игра является моделью пирамиды браминов, установленной в храме индийского города Бенарес. Настоящая пирамида состоит из 64 золотых дисков, насаженных на один из трех алмазных стержней. Брамины круглосуточно перекладывают дис- ки, чтобы переместить пирамиду с первого стержня на третий в соответствии с ука- занными выше правилами. За 1 секунду перемещается один диск. Когда пирамида будет полностью перемещена, наступит конец света". История умалчивает о том, как индийский храм перекочевал во Вьетнам. Можно показать, что "конец света" должен был наступить через. после начала миссии браминов. Доказательство этого факта выполняется по ин- дукции. На малом количестве дисков ( n = 1, 2, 3) мы убеждаемся, что операция по переносу выполнима за 1, 3 и 7 шагов. Предполагая, что оценка верна для ( n – 1)-го диска, т. е. требует ( 2 n -1 -1 ) шагов, покажем, что она справедлива и для n дисков. Проведем эту операцию в три этапа: ± перенесем верхние n – 1 дисков со стержня 1 на стержень 2, затратив шагов; ± перенесем самый большой диск со стержня 1 на стержень 3 за 1 шаг; ± перенесем n – 1 дисков со стержня 2 на стержень 3, затратив 2 n -1 -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) сводится к выполнению трех следующих процедур: При n ? 1 выполнение этой цепочки процедур должно быть завершено. В ре- зультате получается очень изящная программа, моделирующая работу браминов (листинг 9.15). Листинг 9 .1 5 . Программа Hanoj. program Hanoj; var n:integer; procedure MD(from_b,to_b:integer); begin. 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); Результат ее работы по переносу 5 колец отображен на рис. 9.9. Рис. 9.9. Перенос "Ханойской башни" Источник: Кетков, Ю. Л., Свободное программное обеспечение. FREE PASCAL для студентов и школьников, Ю. Л. Кетков, А. Ю. Кетков. — СПб.: БХВ-Петербург, 2011. — 384 с.: ил. + CD-ROM — (ИиИКТ)  Ханойские башни на паскале Ханойские башни на паскале С этим скачивают:
|