Муниципальное образовательное учреждение «Гимназия 8» Выполнила: Каверзина Т.Н. Учитель информатики г.Рубцовск, Алтайский край 2009г. - презентация

1 Муниципальное образовательное учреждение «Гимназия 8» Выполнила: Каверзина Т.Н. Учитель информатики г.Рубцовск, Алтайский край 2009г.

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

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

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

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

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

7

8 Два кольца переложить с первого на третий стержень Сколько команд имеет данный алгоритм?……………………… Первая команда Вторая команда Третья команда

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

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

11 Ханой (3, 1, 3) = Ханой (2, 1, 2) Переместить с 1 – 3 Ханой (2, 2, 3) Рекурсия – способ решения задачи, при котором одно из решений – это решение той же самой задачи.

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

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

14 шня шня _Hanoi.jpeghttp://ru.wikipedia.org/wiki/Файл:Tower_of _Hanoi.jpeg