Содержание: История создания головоломки Легенда Алгоритм решения

Три стержня и диски разных диаметров, вначале все диски собраны на одном стержне так, что меньшие диски лежат на больших. Люка предлагал переложить все диски с первого стержня на третий, используя второй. Ханойские Башни это головоломка, которую в 1883 г. придумал французский математик Эдуард Люка.

Башни Брамы были созданы не иначе как при Сотворении мира, и с того времени жрецы в храме трудятся, перекладывая диски. Башни Брамы были созданы не иначе как при Сотворении мира, и с того времени жрецы в храме трудятся, перекладывая диски. 3 алмазных стержня и 64 золотых диска каждый меньший диск лежит на большем

или миллиардов лет. Если бы монахи, работая день и ночь, делали каждую секунду одно перемещение диска, их работа продолжалась бы 580 миллиардов лет. А сколько перемещений потребуется при перемещении трёх дисков? Число перемещений дисков, которые должны совершить монахи

За один раз можно перемещать только один диск; Больший диск нельзя располагать на меньшем диске; Любой диск можно укладывать либо на большее кольцо, либо на свободный стержень.

Два кольца переложить с первого на третий стержень Сколько команд имеет данный алгоритм?……………………… Первая команда Вторая команда Третья команда Ханой (2, 1, 3) Назовём этот алгоритм - Ханой (2, 1, 3) – алгоритм перемещения 2-х колец с 1-го стержня на 3.

Три кольца переложить с первого стержня на третий Сколько команд имеет данный алгоритм?………………………. Алгоритм Ханой всегда имеет конечное число команд, сколько бы ни было колец Перемещение башни из двух колец с 1-го стержня на второй Перемещение башни из двух колец со второго стержня на третий. Ханой (2, 1, 2) Ханой (2, 2, 3) Какое имя у данного алгоритма? Ханой (3, 1, 3)

За сколько команд переложили кольца в алгоритме П(2)? – Сколько раз мы вызывали алгоритм П(2) в алгоритме П(3)? - Выведем формулу вычисления количества команд в алгоритме перекладывания колец. П(3) = 2*П(2) +1 = 3 2 Введём обозначения: П(2) –перемещение 2-х колец П(3) – перемещение 3-х колец. 2 * = 7

Ханой (3, 1, 3) = Ханой (2, 1, 2) Переместить с 1 – 3 Ханой (2, 2, 3) Рекурсия – способ решения задачи, при котором одно из решений – это решение той же самой задачи. Рекурсивные вызовы отличаются друг от друга значениями параметров. А что произойдет, если удастся избавиться от этих параметров? Тогда рекурсивное решение запишется следующим образом: Построить башню = Построить башню Перенести диск с одного стержня на другой Построить башню.

Сколько команд перемещения будет в алгоритме П (4)? Запишите формулу и подсчитайте. П (4) = ? Запишите как будет выглядеть рекурсивный алгоритм? 2 * П (3) +1 = Ханой (4, 1, 3) = Ханой (3, 1, 2) Переместить с 1 – 3 Ханой (3, 2, 3) 2 * = 15

Число колец Число перемещений Перемещение (количество колец)23П(2) 37 П(3) = 2 * П(2) П(4) = 2 * П(3) П(5) = 2 * П(4) П(6) = 2 * П(5) П(7) = 2 * П(6) +1 Выполните головоломку за компьютером. Желаю добиться рекорда!

of_Hanoi.jpeghttp://ru.wikipedia.org/wiki/Файл:Tower_ of_Hanoi.jpeg of_Hanoi_4.gifhttp://ru.wikipedia.org/wiki/Файл:Tower_ of_Hanoi_4. gif /mathemat/stud2/index.asp.htmhttp:// /mathemat/stud2/index.asp.htm ?id=13221http:// ?id=13221