Башня ханой. Ханойская башня на пальцах

Ханойская башня является одной из популярных головоломок XIX века . Даны три стержня, на один из которых нанизаны восемь колец, причём кольца отличаются размером и лежат меньшее на большем. Задача состоит в том, чтобы перенести пирамиду из восьми колец за наименьшее число ходов на другой стержень. За один раз разрешается переносить только одно кольцо, причём нельзя класть большее кольцо на меньшее.

Энциклопедичный YouTube

1 / 5
Эту игру придумал французский математик Эдуард Люка в 1883 году , её продавали как забавную игрушку. Первоначально она называлась «Профессор Клаус (Claus) из Колледжа Ли-Су-Стьян (Li-Sou-Stian)» , но вскоре обнаружилось, что таинственный профессор из несуществующего колледжа - не более чем анаграмма фамилии изобретателя игры, профессора Люка (Lucas) из колледжа Сен-Луи (Saint Louis).

Решение

Существует несколько подходов к решению, все они дают идентичные результаты.

Рекурсивное решение

Рекурсивно решаем задачу «перенести башню из n −1 диска на 2-й штырь». Затем переносим самый большой диск на 3-й штырь, и рекурсивно решаем задачу «перенеси башню из n −1 диска на 3-й штырь».
В информатике задачи, основанные на легенде о Ханойской башне, часто рассматривают в качестве примера использования рекурсивных алгоритмов и преобразования их к нерекурсивным.

«Треугольное» решение

Расположим штыри в виде треугольника. Начнём с самого маленького кольца и переложим его на любую отметку. В дальнейшем это кольцо нужно перемещать в том же направлении, что и при первом перекладывании. Затем перенесём какое-нибудь из оставшихся колец (такой ход единственный), после чего снова переложим самое маленькое кольцо и т. д. (Интересно заметить, что перенумеровав «кольца» по порядку, мы добьёмся неожиданного эффекта: чётные кольца будут перемещаться из одной вершины треугольника в другую в одном направлении, а нечётные - в противоположном направлении.)

Циклическое решение

Обозначим через «1-2» такое действие: переложить диск или с 1-го штыря на 2-й, или со 2-го на 1-й, в зависимости от того, где он меньше. Тогда, чтобы решить головоломку с чётным количеством дисков, надо многократно повторять действия: 1-2, 1-3, 2-3. Если число дисков нечётно - 1-3, 1-2, 2-3.

Применение кода Грея для решения

// Ханойские башни #include using namespace std ; void hanoi_towers (int quantity , int from , int to , int buf_peg ) //quantity-число колец, from-начальное положение колец(1-3),to-конечное положение колец(1-3) { //buf_peg - промежуточный колышек(1-3) if (quantity != 0 ) { hanoi_towers (quantity - 1 , from , buf_peg , to ); cout << from << " -> " << to << endl ; hanoi_towers (quantity - 1 , buf_peg , to , from ); } } int main () { setlocale (LC_ALL , "rus" ); int start_peg , destination_peg , buffer_peg , plate_quantity ; cout << "Номер первого столбика:" << endl ; cin >> start_peg ; cout << "Номер конечного столбика:" << endl ; cin >> destination_peg ; cout << "Номер промежуточного столбика:" << endl ; cin >> buffer_peg ; cout << "Количество дисков:" << endl ; cin >> plate_quantity ; hanoi_towers (plate_quantity , start_peg , destination_peg , buffer_peg ); return 0 ; }

Pascal :

program hanoibns (input , output ) ; var n : integer ; procedure tower (k : integer ; a , b , c : char ) ; begin if k > 1 then tower (k - 1 , a , c , b ) ; writeln ("from " , a , " to " , b ) ; if k > 1 then tower (k - 1 , c , b , a ) end ; begin read (n ) ; tower (n , "A" , "C" , "B" ) end .

Пример алгоритма решения на языке Python :

def Hanoi (n , A , C , B ): if n != 0 : Hanoi (n - 1 , A , B , C ) print "Move the plate from" , A , "to" , C Hanoi (n - 1 , B , C , A )

Пример алгоритма решения на языке Java :

public class Hanoi { public static void hanoiTowers (int quantity , int from , int to , int buf_peg ) { if (quantity != 0 ) { hanoiTowers (quantity - 1 , from , buf_peg , to ); System . out . println ("" + from + " -> " + to ); hanoiTowers (quantity - 1 , buf_peg , to , from ); } } public static void main (String args ) { int start_peg = 1 , destination_peg = 2 , buffer_peg = 3 , plate_quantity = 4 ; hanoiTowers (plate_quantity , start_peg , destination_peg , buffer_peg ); } }

Пример итеративного алгоритма решения на языке

#include #include void carryingOver (int , int , int ); main () { int number , countDisk , counter = 1 , count ; printf ("Введите количество дисков: " ); /* Ханойская башня */ scanf ("%d" , & number ); while (counter <= pow (2 , number ) - 1 ) { /* Запускаем цикл повторений */ if (counter % 2 != 0 ) { /* На нечетном ходу мы будем трогать только самый маленький диск */ printf ("%3d %d " , counter , 1 ); carryingOver (number , counter , 1 ); /* С помощью этой функции определяем для данного диска перемещение */ } else { /* Определяем диск который нужно переместить на четном ходу */ count = counter ; countDisk = 0 ; while (count % 2 == 0 ) { /* Диск который нужно переместить */ countDisk ++ ; /* будет числом деления номера хода на 2 без остатка */ count = count / 2 ; } printf ("%3d %d " , counter , countDisk + 1 ); carryingOver (number , counter , countDisk + 1 ); } counter ++ ; } return 0 ; } /* Функция определения перемещения дисков */ void carryingOver (int n , int i , int k ) { int t , axisX , axisY , axisZ ; if (n % 2 == 0 ) { /* Определяем порядок осей в зависимости от четности */ axisX = 1 ; /* и не четности количества дисков */ axisY = 2 ; axisZ = 3 ; } else { axisX = 1 ; axisY = 3 ; axisZ = 2 ; } /* Номер хода можно представить единственным образом */ /* как произведение некоего нечетного числа на степень двойки */ /* k будет номером диска который мы перемещаем */ t = ((i / pow (2 , k - 1 )) - 1 ) / 2 ; if (k % 2 != 0 ) { /* Определяем перемещение дисков для нечетного хода */ switch (t % 3 ) { /* Выбираем перемещение в зависимости от данного условия */ case 0 : printf ("%d -> %d \n " , axisX , axisY ); break ; case 1 : printf ("%d -> %d \n " , axisY , axisZ ); break ; case 2 : printf ("%d -> %d \n " , axisZ , axisX ); break ; } } else { /* Определяем перемещение дисков для чётного хода */ switch (t % 3 ) { case 0 : printf ("%d -> %d \n " , axisX , axisZ ); break ; case 1 : printf ("%d -> %d \n " , axisZ , axisY ); break ; case 2 : printf ("%d -> %d \n " , axisY , axisX ); break ; } } } Существуют программы визуализации решения этой головоломки.
Варианты

С четырьмя и более стержнями
Хотя вариант с тремя стержнями имеет простое рекурсивное решение, оптимальное решение Ханойской башни с четырьмя стержнями долгое время являлось нерешённой проблемой.Очевидно, что для любого количества стержней существует алгоритм для нахождения оптимальных решений, достаточно представить головоломку в виде неориентированного графа, сопоставив размещениям дисков вершины, а ходам - рёбра, и использовать любой алгоритм поиска (например, поиск в ширину) для нахождения оптимального решения. Однако эффективной стратегии определения оптимального решения для большого числа дисков нет: количество ходов, необходимое для решения головоломки с 10 стержнями и 1000 дисками, остаётся неизвестным.Существует предположительно оптимальный алгоритм Фрейма - Стюарта, разработанный в 1941 году . Связанная гипотеза Фрейма - Стюарта утверждает, что алгоритм Фрейма - Стюарта всегда находит оптимальное решение. Оптимальность алгоритма Фрейма - Стюарта была экспериментально проверена вплоть до 30 дисков на 4 стержнях . В 2014 году было окончательно доказано, что для четырёх стержней Алгоритм Фрейма - Стюарта является оптимальным .Другие варианты решения Ханойской башни с четырьмя стержнями рассматриваются в обзорной статье Пола Стокмайера .
Алгоритм Фрейма - Стюарта
Алгоритм Фрейма - Стюарта, дающий оптимальное решение для четырёх и предположительно оптимальное решение для большего количества стержней, описывается следующим образом: Алгоритм может быть описан рекурсивно: На весь процесс требуется 2 T (k , r) + T (n − k , r − 1) {\displaystyle 2T(k,r)+T(n-k,r-1)} ходов. Значение k {\displaystyle k} выбирается таким образом, чтобы значение этого выражения было минимальным. Ханойская башня является одной из популярных головоломок XIX века . Даны три стержня, на один из которых нанизаны восемь колец, причем кольца отличаются размером и лежат меньшее на большем. Задача состоит в том, чтобы перенести пирамиду из восьми колец за наименьшее число ходов на другой стержень. За один раз разрешается переносить только одно кольцо, причём нельзя класть большее кольцо на меньшее.
История создания головоломки
Эту игру придумал французский математик Эдуард Люка в 1883 году , её продавали как забавную игрушку. Первоначально она называлась «Профессор Клаус (Claus) из Колледжа Ли-Су-Стьян (Li-Sou-Stian)» , но вскоре обнаружилось, что таинственный профессор из несуществующего колледжа - не более чем анаграмма фамилии изобретателя игры, профессора Люка (Lucas) из колледжа Сен-Луи (Saint Louis).
Решение
В информатике задачи, основанные на легенде о Ханойской башне, часто рассматривают в качестве примера использования рекурсивных алгоритмов и преобразования их к нерекурсивным.
«Треугольное» решение
Расположим штыри в виде треугольника. Начнём с самого маленького кольца и переложим его на любую отметку. В дальнейшем это кольцо нужно перемещать в том же направлении, что и при первом перекладывании. Затем перенесём какое-нибудь из оставшихся колец (такой ход единственный), после чего снова переложим самое маленькое кольцо и т. д. (Интересно заметить, что перенумеровав «кольца» по порядку, мы добьёмся неожиданного эффекта: чётные кольца будут перемещаться из одной вершины треугольника в другую в одном направлении, а нечётные - в противоположном направлении.)
Циклическое решение
Обозначим через «1-2» такое действие: переложить диск или с 1-го штыря на 2-й, или со 2-го на 1-й, в зависимости от того, где он меньше. Тогда, чтобы решить головоломку с нечётным количеством дисков, надо многократно повторять действия: 1-2, 1-3, 2-3. Если число дисков чётно - 1-3, 1-2, 2-3.
Применение кода Грея для решения
Код Грея , рефлексный двоичный код в двоичной системе счисления , в котором два соседних значения различаются только в одном двоичном разряде. Изначально код Грея предназначался для защиты от ложного срабатывания электромеханических переключателей. Сегодня коды Грея широко используются для упрощения выявления и исправления ошибок в системах связи, а также в формировании сигналов обратной связи в системах управления. Код получил имя исследователя лабораторий Bell Labs Фрэнка Грея. Он использовал этот код в своей импульсной системе связи, для чего был написан патент за номером 2632058.Коды Грея применяются в решении задачи о Ханойских башнях. Пусть N - количество дисков. Начнём с кода Грея длины N, состоящего из одних нулей (то есть G(0)), и будем двигаться по кодам Грея (от G(i) переходить к G(i+1)) . Поставим в соответствие каждому I-ому биту текущего кода Грея I-ый диск (причём самому младшему биту соответствует наименьший по размеру диск, а самому старшему биту - наибольший). Поскольку на каждом шаге изменяется ровно один бит, то мы можем понимать изменение бита I как перемещение I-го диска. Заметим, что для всех дисков, кроме наименьшего, на каждом шаге имеется ровно один вариант хода (за исключением стартовой и финальной позиций). Для наименьшего диска всегда имеется два варианта хода, однако имеется стратегия выбора хода, всегда приводящая к ответу: если N нечётно, то последовательность перемещений наименьшего диска имеет вид f->t->r->f->t->r->… (где f-стартовый стержень, t-финальный стержень, r-оставшийся стержень), а если N чётно, то f->r->t->f->r->t ->… Реализации алгоритма C++ : // Ханойские башни #include
using namespace std; void hanoi_towers(int quantity, int from, int to, int buf_peg) //quantity-число колец, from-начальное положение колец(1-3),to-конечное положение колец(1-3) { //buf_peg - промежуточный колышек(1-3) if (quantity != 0) { hanoi_towers(quantity-1, from, buf_peg, to); cout << from << " -> " << to << endl; hanoi_towers(quantity-1, buf_peg, to, from); } } int main() { setlocale(LC_ALL,"rus"); int start_peg, destination_peg, buffer_peg, plate_quantity; cout << "Номер первого столбика:" << endl; cin >> start_peg; cout << "Номер конечного столбика:" << endl; cin >> destination_peg; cout << "Номер промежуточного столбика:" << endl; cin >> buffer_peg; cout << "Количество дисков:" << endl; cin >> plate_quantity; hanoi_towers(plate_quantity, start_peg, destination_peg, buffer_peg); return 0; } Пример алгоритма решения на языке Pascal : program hanoibns(input,output); var n:integer; procedure tower(k:integer;a,b,c:char); begin if k>1 then tower(k-1,a,c,b); writeln("from ",a," to ",b); if k>1 then tower(k-1,c,b,a) end; begin read(n); tower(n,"A","C","B") end. Пример алгоритма решения на языке Python : def Hanoi(n, A, C, B): if n != 0: Hanoi(n - 1, A, B, C) print "Move the plate from", A, "to", C Hanoi(n - 1, B, C, A) Пример алгоритма решения на языке Java : public class Hanoi { public static void hanoiTowers(int quantity, int from, int to, int buf_peg) { if (quantity != 0) { hanoiTowers(quantity-1, from, buf_peg, to); System.out.println("" + from + " -> " + to); hanoiTowers(quantity-1, buf_peg, to, from); } } public static void main(String args) { int start_peg = 1, destination_peg = 2, buffer_peg = 3, plate_quantity = 4; hanoiTowers(plate_quantity, start_peg, destination_peg, buffer_peg); } } Пример итеративного алгоритма решения на языке #include
#include
void carryingOver(int, int, int); main() { int number, countDisk, counter = 1, count; printf("Введите количество дисков: "); /* Ханойская башня */ scanf("%d", &number); while (counter <= pow(2, number) - 1) { /* Запускаем цикл повторений */ if (counter % 2 != 0) { /* На нечетном ходу мы будем трогать только самый маленький диск */ printf("%3d %d ", counter, 1); carryingOver(number, counter, 1); /* С помощью этой функции определяем для данного диска перемещение */ } else { /* Определяем диск который нужно переместить на четном ходу */ count = counter; countDisk = 0; while (count % 2 == 0) { /* Диск который нужно переместить */ countDisk++; /* будет числом деления номера хода на 2 без остатка */ count = count / 2; } printf("%3d %d ", counter, countDisk + 1); carryingOver(number, counter, countDisk + 1); } counter++; } return 0; } /* Функция определения перемещения дисков */ void carryingOver(int n ,int i, int k) { int t, axisX, axisY, axisZ; if (n % 2 == 0) { /* Определяем порядок осей в зависимости от четности */ axisX = 1; /* и не четности количества дисков */ axisY = 2; axisZ = 3; } else { axisX = 1; axisY = 3; axisZ = 2; } /* Номер хода можно представить единственным образом */ /* как произведение некоего нечетного числа на степень двойки */ /* k будет номером диска который мы перемещаем */ t = ((i / pow(2, k - 1)) - 1) / 2; if (k % 2 != 0) { /* Определяем перемещение дисков для нечетного хода */ switch (t % 3) { /* Выбираем перемещение в зависимости от данного условия */ case 0: printf("%d -> %d\n", axisX, axisY); break; case 1: printf("%d -> %d\n", axisY, axisZ); break; case 2: printf("%d -> %d\n", axisZ, axisX); break; } } else { /* Определяем перемещение дисков для чётного хода */ switch (t % 3) { case 0: printf("%d -> %d\n", axisX, axisZ); break; case 1: printf("%d -> %d\n", axisZ, axisY); break; case 2: printf("%d -> %d\n", axisY, axisX); break; } } } Существуют программы визуализации решения этой головоломки.
Варианты

С четырьмя и более стержнями
Хотя вариант с тремя стержнями имеет простое рекурсивное решение, оптимальное решение Ханойской башни с четырьмя стержнями долгое время являлось нерешённой проблемой.Очевидно, что для любого количества стержней существует алгоритм для нахождения оптимальных решений, достаточно представить головоломку в виде неориентированного графа, сопоставив размещениям дисков вершины, а ходам - рёбра, и использовать любой алгоритм поиска (например, поиск в ширину) для нахождения оптимального решения. Однако эффективной стратегии определения оптимального решения для большого числа дисков нет: количество ходов, необходимое для решения головоломки с 10 стержнями и 1000 дисками, остаётся неизвестным.Существует предположительно оптимальный алгоритм Фрейма - Стюарта, разработанный в 1941 году . Связанная гипотеза Фрейма - Стюарта утверждает, что алгоритм Фрейма - Стюарта всегда находит оптимальное решение. Оптимальность алгоритма Фрейма - Стюарта была экспериментально проверена вплоть до 30 дисков на 4 стержнях . В 2014 году было окончательно доказано, что для четырех стержней Алгоритм Фрейма - Стюарта является оптимальным .Другие варианты решения Ханойской башни с четырьмя стержнями рассматриваются в обзорной статье Пола Стокмайера .
Алгоритм Фрейма - Стюарта
Алгоритм Фрейма - Стюарта, дающий оптимальное решение для четырёх и предположительно оптимальное решение для большего количества стержней, описывается следующим образом:
- Пусть $n$ - количество дисков.
- Пусть $r$ - число стержней.
- Определим $T(n,r)$ как наименьшее число ходов, необходимое для переноса n дисков с использованием r стержней.
Алгоритм может быть описан рекурсивно:
1. Для некоторого $k$ , $1 \leq k < n$ , перенести верхние $k$ на стержень i , не являющийся ни начальным, ни конечным стержнем, затратив на это $T(k,r)$ ходов.
2. Не используя стержень i , содержащий теперь верхние $k$ дисков, перенести оставшиеся $n-k$ дисков на конечный стержень, используя только оставшиеся $r-1$ стержней и затратив на это $T(n-k,r-1)$ ходов.
3. Наконец, переместить верхние $k$ дисков на конечный стержень, затратив на это $T(k,r)$ ходов.
На весь процесс требуется $2T(k,r)+T(n-k,r-1)$ ходов. Значение $k$ выбирается таким образом, чтобы значение этого выражения было минимальным.

Легенды

Придуманная профессором Люка легенда гласит, что в Великом храме города Бенарес, под собором, отмечающим середину мира, находится бронзовый диск, на котором укреплены 3 алмазных стержня, высотой в один локоть и толщиной с пчелу. Давным-давно, в самом начале времён, монахи этого монастыря провинились перед богом Брахмой. Разгневанный Брахма воздвиг три высоких стержня и на один из них возложил 64 диска, сделанных из чистого золота. Причем так, что каждый меньший диск лежит на большем.
Как только все 64 диска будут переложены со стержня, на который Брахма сложил их при создании мира, на другой стержень, башня вместе с храмом обратятся в пыль и под громовые раскаты погибнет мир.
Количество перекладываний в зависимости от количества колец вычисляется по формуле $2^n-1$ .
Число перемещений дисков, которые должны совершить монахи, равно 18 446 744 073 709 551 615 . Если бы монахи, работая день и ночь, делали каждую секунду одно перемещение диска, их работа продолжалась бы 584 миллиарда лет .

В культуре

Напишите отзыв о статье "Ханойская башня"
Примечания

Ссылки
- последовательность A007664 в OEIS
- Константин Кноп. . Элементы (22.10.2012).
Отрывок, характеризующий Ханойская башня
Подъезжая к лесной караулке, Денисов остановился, вглядываясь в лес. По лесу, между деревьев, большими легкими шагами шел на длинных ногах, с длинными мотающимися руками, человек в куртке, лаптях и казанской шляпе, с ружьем через плечо и топором за поясом. Увидав Денисова, человек этот поспешно швырнул что то в куст и, сняв с отвисшими полями мокрую шляпу, подошел к начальнику. Это был Тихон. Изрытое оспой и морщинами лицо его с маленькими узкими глазами сияло самодовольным весельем. Он, высоко подняв голову и как будто удерживаясь от смеха, уставился на Денисова.
– Ну где пг"опадал? – сказал Денисов.
– Где пропадал? За французами ходил, – смело и поспешно отвечал Тихон хриплым, но певучим басом.
– Зачем же ты днем полез? Скотина! Ну что ж, не взял?..
– Взять то взял, – сказал Тихон.
– Где ж он?
– Да я его взял сперва наперво на зорьке еще, – продолжал Тихон, переставляя пошире плоские, вывернутые в лаптях ноги, – да и свел в лес. Вижу, не ладен. Думаю, дай схожу, другого поаккуратнее какого возьму.
– Ишь, шельма, так и есть, – сказал Денисов эсаулу. – Зачем же ты этого не пг"ивел?
– Да что ж его водить то, – сердито и поспешно перебил Тихон, – не гожающий. Разве я не знаю, каких вам надо?
– Эка бестия!.. Ну?..
– Пошел за другим, – продолжал Тихон, – подполоз я таким манером в лес, да и лег. – Тихон неожиданно и гибко лег на брюхо, представляя в лицах, как он это сделал. – Один и навернись, – продолжал он. – Я его таким манером и сграбь. – Тихон быстро, легко вскочил. – Пойдем, говорю, к полковнику. Как загалдит. А их тут четверо. Бросились на меня с шпажками. Я на них таким манером топором: что вы, мол, Христос с вами, – вскрикнул Тихон, размахнув руками и грозно хмурясь, выставляя грудь.
– То то мы с горы видели, как ты стречка задавал через лужи то, – сказал эсаул, суживая свои блестящие глаза.
Пете очень хотелось смеяться, но он видел, что все удерживались от смеха. Он быстро переводил глаза с лица Тихона на лицо эсаула и Денисова, не понимая того, что все это значило.
– Ты дуг"ака то не представляй, – сказал Денисов, сердито покашливая. – Зачем пег"вого не пг"ивел?
Тихон стал чесать одной рукой спину, другой голову, и вдруг вся рожа его растянулась в сияющую глупую улыбку, открывшую недостаток зуба (за что он и прозван Щербатый). Денисов улыбнулся, и Петя залился веселым смехом, к которому присоединился и сам Тихон.
– Да что, совсем несправный, – сказал Тихон. – Одежонка плохенькая на нем, куда же его водить то. Да и грубиян, ваше благородие. Как же, говорит, я сам анаральский сын, не пойду, говорит.
– Экая скотина! – сказал Денисов. – Мне расспросить надо…
– Да я его спрашивал, – сказал Тихон. – Он говорит: плохо зн аком. Наших, говорит, и много, да всё плохие; только, говорит, одна названия. Ахнете, говорит, хорошенько, всех заберете, – заключил Тихон, весело и решительно взглянув в глаза Денисова.
– Вот я те всыплю сотню гог"ячих, ты и будешь дуг"ака то ког"чить, – сказал Денисов строго.
– Да что же серчать то, – сказал Тихон, – что ж, я не видал французов ваших? Вот дай позатемняет, я табе каких хошь, хоть троих приведу.
– Ну, поедем, – сказал Денисов, и до самой караулки он ехал, сердито нахмурившись и молча.
Тихон зашел сзади, и Петя слышал, как смеялись с ним и над ним казаки о каких то сапогах, которые он бросил в куст.
Когда прошел тот овладевший им смех при словах и улыбке Тихона, и Петя понял на мгновенье, что Тихон этот убил человека, ему сделалось неловко. Он оглянулся на пленного барабанщика, и что то кольнуло его в сердце. Но эта неловкость продолжалась только одно мгновенье. Он почувствовал необходимость повыше поднять голову, подбодриться и расспросить эсаула с значительным видом о завтрашнем предприятии, с тем чтобы не быть недостойным того общества, в котором он находился.
Посланный офицер встретил Денисова на дороге с известием, что Долохов сам сейчас приедет и что с его стороны все благополучно.
Денисов вдруг повеселел и подозвал к себе Петю.
– Ну, г"асскажи ты мне пг"о себя, – сказал он.
Петя при выезде из Москвы, оставив своих родных, присоединился к своему полку и скоро после этого был взят ординарцем к генералу, командовавшему большим отрядом. Со времени своего производства в офицеры, и в особенности с поступления в действующую армию, где он участвовал в Вяземском сражении, Петя находился в постоянно счастливо возбужденном состоянии радости на то, что он большой, и в постоянно восторженной поспешности не пропустить какого нибудь случая настоящего геройства. Он был очень счастлив тем, что он видел и испытал в армии, но вместе с тем ему все казалось, что там, где его нет, там то теперь и совершается самое настоящее, геройское. И он торопился поспеть туда, где его не было.
Когда 21 го октября его генерал выразил желание послать кого нибудь в отряд Денисова, Петя так жалостно просил, чтобы послать его, что генерал не мог отказать. Но, отправляя его, генерал, поминая безумный поступок Пети в Вяземском сражении, где Петя, вместо того чтобы ехать дорогой туда, куда он был послан, поскакал в цепь под огонь французов и выстрелил там два раза из своего пистолета, – отправляя его, генерал именно запретил Пете участвовать в каких бы то ни было действиях Денисова. От этого то Петя покраснел и смешался, когда Денисов спросил, можно ли ему остаться. До выезда на опушку леса Петя считал, что ему надобно, строго исполняя свой долг, сейчас же вернуться. Но когда он увидал французов, увидал Тихона, узнал, что в ночь непременно атакуют, он, с быстротою переходов молодых людей от одного взгляда к другому, решил сам с собою, что генерал его, которого он до сих пор очень уважал, – дрянь, немец, что Денисов герой, и эсаул герой, и что Тихон герой, и что ему было бы стыдно уехать от них в трудную минуту.
Уже смеркалось, когда Денисов с Петей и эсаулом подъехали к караулке. В полутьме виднелись лошади в седлах, казаки, гусары, прилаживавшие шалашики на поляне и (чтобы не видели дыма французы) разводившие красневший огонь в лесном овраге. В сенях маленькой избушки казак, засучив рукава, рубил баранину. В самой избе были три офицера из партии Денисова, устроивавшие стол из двери. Петя снял, отдав сушить, свое мокрое платье и тотчас принялся содействовать офицерам в устройстве обеденного стола.
Через десять минут был готов стол, покрытый салфеткой. На столе была водка, ром в фляжке, белый хлеб и жареная баранина с солью.
Сидя вместе с офицерами за столом и разрывая руками, по которым текло сало, жирную душистую баранину, Петя находился в восторженном детском состоянии нежной любви ко всем людям и вследствие того уверенности в такой же любви к себе других людей.
– Так что же вы думаете, Василий Федорович, – обратился он к Денисову, – ничего, что я с вами останусь на денек? – И, не дожидаясь ответа, он сам отвечал себе: – Ведь мне велено узнать, ну вот я и узнаю… Только вы меня пустите в самую… в главную. Мне не нужно наград… А мне хочется… – Петя стиснул зубы и оглянулся, подергивая кверху поднятой головой и размахивая рукой.
– В самую главную… – повторил Денисов, улыбаясь.
– Только уж, пожалуйста, мне дайте команду совсем, чтобы я командовал, – продолжал Петя, – ну что вам стоит? Ах, вам ножик? – обратился он к офицеру, хотевшему отрезать баранины. И он подал свой складной ножик.
Офицер похвалил ножик.
– Возьмите, пожалуйста, себе. У меня много таких… – покраснев, сказал Петя. – Батюшки! Я и забыл совсем, – вдруг вскрикнул он. – У меня изюм чудесный, знаете, такой, без косточек. У нас маркитант новый – и такие прекрасные вещи. Я купил десять фунтов. Я привык что нибудь сладкое. Хотите?.. – И Петя побежал в сени к своему казаку, принес торбы, в которых было фунтов пять изюму. – Кушайте, господа, кушайте.
– А то не нужно ли вам кофейник? – обратился он к эсаулу. – Я у нашего маркитанта купил, чудесный! У него прекрасные вещи. И он честный очень. Это главное. Я вам пришлю непременно. А может быть еще, у вас вышли, обились кремни, – ведь это бывает. Я взял с собою, у меня вот тут… – он показал на торбы, – сто кремней. Я очень дешево купил. Возьмите, пожалуйста, сколько нужно, а то и все… – И вдруг, испугавшись, не заврался ли он, Петя остановился и покраснел.
Он стал вспоминать, не сделал ли он еще каких нибудь глупостей. И, перебирая воспоминания нынешнего дня, воспоминание о французе барабанщике представилось ему. «Нам то отлично, а ему каково? Куда его дели? Покормили ли его? Не обидели ли?» – подумал он. Но заметив, что он заврался о кремнях, он теперь боялся.
«Спросить бы можно, – думал он, – да скажут: сам мальчик и мальчика пожалел. Я им покажу завтра, какой я мальчик! Стыдно будет, если я спрошу? – думал Петя. – Ну, да все равно!» – и тотчас же, покраснев и испуганно глядя на офицеров, не будет ли в их лицах насмешки, он сказал:
– А можно позвать этого мальчика, что взяли в плен? дать ему чего нибудь поесть… может…
– Да, жалкий мальчишка, – сказал Денисов, видимо, не найдя ничего стыдного в этом напоминании. – Позвать его сюда. Vincent Bosse его зовут. Позвать.
– Я позову, – сказал Петя.
– Позови, позови. Жалкий мальчишка, – повторил Денисов.
Петя стоял у двери, когда Денисов сказал это. Петя пролез между офицерами и близко подошел к Денисову.
– Позвольте вас поцеловать, голубчик, – сказал он. – Ах, как отлично! как хорошо! – И, поцеловав Денисова, он побежал на двор.
– Bosse! Vincent! – прокричал Петя, остановясь у двери.
– Вам кого, сударь, надо? – сказал голос из темноты. Петя отвечал, что того мальчика француза, которого взяли нынче.
– А! Весеннего? – сказал казак.
Имя его Vincent уже переделали: казаки – в Весеннего, а мужики и солдаты – в Висеню. В обеих переделках это напоминание о весне сходилось с представлением о молоденьком мальчике.
– Он там у костра грелся. Эй, Висеня! Висеня! Весенний! – послышались в темноте передающиеся голоса и смех.
– А мальчонок шустрый, – сказал гусар, стоявший подле Пети. – Мы его покормили давеча. Страсть голодный был!
В темноте послышались шаги и, шлепая босыми ногами по грязи, барабанщик подошел к двери.
– Ah, c"est vous! – сказал Петя. – Voulez vous manger? N"ayez pas peur, on ne vous fera pas de mal, – прибавил он, робко и ласково дотрогиваясь до его руки. – Entrez, entrez. [Ах, это вы! Хотите есть? Не бойтесь, вам ничего не сделают. Войдите, войдите.]
– Merci, monsieur, [Благодарю, господин.] – отвечал барабанщик дрожащим, почти детским голосом и стал обтирать о порог свои грязные ноги. Пете многое хотелось сказать барабанщику, но он не смел. Он, переминаясь, стоял подле него в сенях. Потом в темноте взял его за руку и пожал ее.
– Entrez, entrez, – повторил он только нежным шепотом.
«Ах, что бы мне ему сделать!» – проговорил сам с собою Петя и, отворив дверь, пропустил мимо себя мальчика.
Когда барабанщик вошел в избушку, Петя сел подальше от него, считая для себя унизительным обращать на него внимание. Он только ощупывал в кармане деньги и был в сомненье, не стыдно ли будет дать их барабанщику.
От барабанщика, которому по приказанию Денисова дали водки, баранины и которого Денисов велел одеть в русский кафтан, с тем, чтобы, не отсылая с пленными, оставить его при партии, внимание Пети было отвлечено приездом Долохова. Петя в армии слышал много рассказов про необычайные храбрость и жестокость Долохова с французами, и потому с тех пор, как Долохов вошел в избу, Петя, не спуская глаз, смотрел на него и все больше подбадривался, подергивая поднятой головой, с тем чтобы не быть недостойным даже и такого общества, как Долохов.
Наружность Долохова странно поразила Петю своей простотой.
Денисов одевался в чекмень, носил бороду и на груди образ Николая чудотворца и в манере говорить, во всех приемах выказывал особенность своего положения. Долохов же, напротив, прежде, в Москве, носивший персидский костюм, теперь имел вид самого чопорного гвардейского офицера. Лицо его было чисто выбрито, одет он был в гвардейский ваточный сюртук с Георгием в петлице и в прямо надетой простой фуражке. Он снял в углу мокрую бурку и, подойдя к Денисову, не здороваясь ни с кем, тотчас же стал расспрашивать о деле. Денисов рассказывал ему про замыслы, которые имели на их транспорт большие отряды, и про присылку Пети, и про то, как он отвечал обоим генералам. Потом Денисов рассказал все, что он знал про положение французского отряда.

Ханойская башня
Ханойская башня является одной из популярных головоломок XIX века . Даны три стержня, на один из которых нанизаны восемь колец, причем кольца отличаются размером и лежат меньшее на большем. Задача состоит в том, чтобы перенести пирамиду из восьми колец за наименьшее число ходов. За один раз разрешается переносить только одно кольцо, причём нельзя класть большее кольцо на меньшее.

История создания головоломки

Эту известную игру придумал французский математик Эдуард Люка , в 1883 году её продавали как забавную игрушку. Первоначально она называлась «Профессор Клаус (Claus) из Колледжа Ли-Су-Стьян (Li-Sou-Stian)» но вскоре обнаружилось, что таинственный профессор из несуществующего колледжа - не более чем анаграмма фамилии изобретателя игры - профессора Люка (Lucas) из колледжа Сен-Луи (Saint Louis).

Решение

Начнем с самого маленького кольца и переложим его на любую отметку. В дальнейшем это кольцо нужно перемещать в том же направлении, что и при первом перекладывании. Затем произведем единственно возможное перемещение оставшихся колец, после чего снова переложим самое маленькое кольцо и т. д. (Интересно заметить, что, перенумеровав «кольца» по порядку, мы добьёмся неожиданного эффекта: четные кольца будут перемещаться из одной вершины треугольника в другую в одном направлении, а нечётные - в противоположном направлении.)

Применение кода Грея для решения

Код Грея, рефлексный двоичный код в двоичной системе счисления , в котором два соседних значения различаются только в одном двоичном разряде. Изначально, код Грея предназначался для защиты от ложного срабатывания электромеханических переключателей. Сегодня коды Грея широко используются для упрощения выявления и исправления ошибок в системах связи, а также в формировании сигналов обратной связи в системах управления. Код получил имя исследователя лабораторий Bell Labs Фрэнка Грея. Он использовал этот код в своей импульсной системе связи, для чего был написан патент за номером 2632058.

Коды Грея применяются в решении задачи о Ханойских башнях. Пусть N - количество дисков. Начнём с кода Грея длины N, состоящего из одних нулей (то есть G(0)), и будем двигаться по кодам Грея (от G(i) переходить к G(i+1)) . Поставим в соответствие каждому I-ому биту текущего кода Грея I-ый диск (причём самому младшему биту соответствует наименьший по размеру диск, а самому старшему биту - наибольший). Поскольку на каждом шаге изменяется ровно один бит, то мы можем понимать изменение бита I как перемещение I-го диска. Заметим, что для всех дисков, кроме наименьшего, на каждом шаге имеется ровно один вариант хода (за исключением стартовой и финальной позиций). Для наименьшего диска всегда имеется два варианта хода, однако имеется стратегия выбора хода, всегда приводящая к ответу: если N нечётно, то последовательность перемещений наименьшего диска имеет вид f->t->r->f->t->r->… (где f-стартовый стержень, t-финальный стержень, r-оставшийся стержень), а если N чётно, то f->r->t->f->r->t ->…

Реализации алгоритма

C++ :

// Ханойские башни #include using namespace std; void hanoi_towers(int quantity, int from, int to, int buf_peg) //quantity-число колец, from-начальное положение колец(1-3),to-конечное положение колец(1-3) { //buf_peg - промежуточный колышек(1-3) if (quantity ! = 0 ) { hanoi_towers(quantity- 1 , from, buf_peg, to) ; cout << from << " -> " << to << endl; hanoi_towers(quantity- 1 , buf_peg, to, from) ; } } int main() { setlocale(LC_ALL,"rus" ) ; int start_peg, destination_peg, buffer_peg, plate_quantity; cout << "Номер первого столбика:" << endl; cin >> start_peg; cout << "Номер конечного столбика:" << endl; cin >> destination_peg; cout << "Номер промежуточного столбика:" << endl; cin >> buffer_peg; cout << "Количество дисков:" << endl; cin >> plate_quantity; hanoi_towers(plate_quantity, start_peg, destination_peg, buffer_peg) ; return 0 ; }

Пример алгоритма решения на языке Pascal :

Program hanoi- bns(input, output) ; var n: integer ; procedure tower(k: integer ; a, b, c: char ) ; begin if k>1 then tower(k- 1 , a, c, b) ; writeln ("from " , a, " to " , b) ; if k>1 then tower(k- 1 , c, b, a) end ; begin read (n) ; tower(n, "A" , "C" , "B" ) end .

Пример алгоритма решения на языке Python :

Def Hanoi(n, A, C, B) : if n != 0 : Hanoi(n - 1 , A, B, C) print "Move the plate from" , A, "to" , C Hanoi(n - 1 , B, C, A)

Пример итеративного алгоритма решения на языке

#include #include void carryingOver(int , int , int ) ; main() { int number, countDisk, counter = 1 , count; printf ("Введите количество дисков: " ) ; /* Ханойская башня */ scanf ("%d" , & number) ; while (counter <= pow (2 , number) - 1 ) { /* Запускаем цикл повторений */ if (counter % 2 != 0 ) { /* На нечетном ходу мы будем трогать только самый маленький диск */ printf ("%3d %d " , counter, 1 ) ; carryingOver(number, counter, 1 ) ; /* С помощью этой функции определяем для данного диска перемещение */ } else { /* Определяем диск который нужно переместить на четном ходу */ count = counter; countDisk = 0 ; while (count % 2 == 0 ) { /* Диск который нужно переместить */ countDisk++; /* будет числом деления номера хода на 2 без остатка */ count = count / 2 ; } printf ("%3d %d " , counter, countDisk + 1 ) ; carryingOver(number, counter, countDisk + 1 ) ; } counter++; } return 0 ; } /* Функция определения перемещения дисков */ void carryingOver(int n , int i, int k) { int t, axisX, axisY, axisZ; if (n % 2 == 0 ) { /* Определяем порядок осей в зависимости от четности */ axisX = 1 ; /* и не четности количества дисков */ axisY = 2 ; axisZ = 3 ; } else { axisX = 1 ; axisY = 3 ; axisZ = 2 ; } /* Номер хода можно представить единственным образом */ /* как произведение некоего нечетного числа на степень двойки */ /* k будет номером диска который мы перемещаем */ t = ((i / pow (2 , k - 1 ) ) - 1 ) / 2 ; if (k % 2 != 0 ) { /* Определяем перемещение дисков для нечетного хода */ switch (t % 3 ) { /* Выбираем перемещение в зависимости от данного условия */ case 0 : printf ("%d -> %d\n " , axisX, axisY) ; break ; case 1 : printf ("%d -> %d\n " , axisY, axisZ) ; break ; case 2 : printf ("%d -> %d\n " , axisZ, axisX) ; break ; } } else { /* Определяем перемещение дисков для чётного хода */ switch (t % 3 ) { case 0 : printf ("%d -> %d\n " , axisX, axisZ) ; break ; case 1 : printf ("%d -> %d\n " , axisZ, axisY) ; break ; case 2 : printf ("%d -> %d\n " , axisY, axisX) ; break ; } } }

Существуют программы визуализации решения этой головоломки.

Легенды

Легенда гласит, что в Великом храме города Бенарас, под собором, отмечающим середину мира, находится бронзовый диск, на котором укреплены 3 алмазных стержня, высотой в один локоть и толщиной с пчелу. Давным-давно, в самом начале времён, монахи этого монастыря провинились перед богом Брахмой. Разгневанный, Брахма воздвиг три высоких стержня и на один из них возложил 64 диска. Брахма поместил на один из стержней 64 диска из чистого золота, причем так, что каждый меньший диск лежит на большем.

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

Количество перекладываний в зависимости от количества колец вычисляется по формуле .

Число перемещений дисков, которые должны совершить монахи, равно 18 446 744 073 709 551 615 . Если бы монахи, работая день и ночь, делали каждую секунду одно перемещение диска, их работа продолжалась бы 584 миллиарда лет .

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

В культуре

В рассказе Эрика Фрэнка Рассела "Ваш ход" ("Quiz Game", в другом переводе "Игра на выживание") чтобы оттянуть время казни главный герой выбирает игру в Ханойскую башню с 64 дисками в качестве последней игры. Объявленные правила модифицированы для двух игроков - игроки должны перекладывать диски по одному за ход, победителем считается тот, кто сделает последний ход. Герой называет такую игру "арки-маларки" и клянётся, что "священнослужители Бенаресского храма" на Земле играют в эту игру.

Примечания

Ссылки

Wikimedia Foundation . 2010 .

Слет научных обществ учащихся образовательных организаций общего и

Дополнительного образования детей города Нижневартовска

В 2014 – 2015 учебном году

СЕКЦИЯ №5: Прикладная математика

Головоломки. Ханойская башня

Разуваев Данил Леонидович

Муниципальное бюджетное

школа №15» 5Б класс

Руководитель:

Павлова Ирина Сергеевна

Учитель математики

Муниципальное бюджетное

общеобразовательное учреждение «Средняя

школа №15»

г. Нижневартовск 2015 год

Разуваев Данил Леонидович

город Нижневартовск

«Средняя Школа №15»

5-Б класс

АННОТАЦИЯ

Головоломки всего мира уникальны тем, что тренируют память на цифры и увеличиваю математические способности. Когда мы размышляем над головоломкой, подбираем варианты решений, вспоминаем, активизируем логические мыслительные процессы, которые работают все быстрее и быстрее, тем самым мы увеличиваем наши мыслительные возможности.

Головоломки развивают пространственное, ассоциативное и аналитическое мышление. Прикольные тесты развивают смекалку, внимание, тренируют память и быстроту восприятия.

Ханойская башня является одной из популярных . Даны три стержня, на один из которых нанизаны восемь колец, причем кольца отличаются размером и лежат меньшее на большем. Задача состоит в том, чтобы перенести пирамиду из восьми колец за наименьшее число ходов на другой стержень. За один раз разрешается переносить только одно кольцо, причём нельзя класть большее кольцо на меньшее.

В данной работе представлен алгоритм игры "Ханойская башня", следуя которому можно решить головоломку даже школьнику. Результатом данного исследования является формула для нахождения минимального количества ходов для произвольного набора колец и модель игры для кабинета математики. Подтверждением достоверности выведенной формулы является видеоролик, на котором представлен алгоритм ходов игры для 9 колец.

Головоломки. Ханойская башня.

Разуваев Данил Леонидович

Ханты-Мансийский автономный округ-Югра (Тюменская область)

город Нижневартовск

Муниципальное бюджетное общеобразовательное учреждение

«Средняя Школа №15»

5-Б класс

ПЛАН ИССЛЕДОВАНИЯ

Головоломка - загадка, задача, требующая для своего решения догадливости и сообразительности. Разгадывать их очень интересно и познавательно. Различные виды задач и головоломок привлекают нас своей логикой и таинственностью. Поэтому я захотел сделать работу по этой теме. Решение головоломок - отличный способ проведения досуга, особенно семейного времяпровождения, ведь они развивают интеллект, сообразительность и креативность мышления. Правильно найденный ответ на заковыристое задание поднимает уровень самооценки, вселяет уверенность в собственных умственных способностях и просто повышает настроение. Поэтому разгадывание различных головоломок очень актуально в современном мире, т.к. в процессе работы над головоломкой развивается смекалка и умение мыслить неординарно. В се больше и больше требуется именно нестандартное мышление особенно в современном информационно-компьютеризированном мире. Разгадывая разные головоломки у меня возник вопрос : "Сколько ребят из нашего класса умеют разгадывать головоломки и знают ли они о такой игре как "Ханойская башня"? Заинтересовавшись данной проблемой, я решил узнать, а умеют ли разгадывать головоломки ребята нашего класса. Для этого я составил анкету, состоящую из 3 вопросов, и предложил ответить на них моим одноклассникам. (Приложение 1). По результатам проведенного опроса оказалось, что большинство ребят любят отгадывать головоломки, однако занимаются этим очень редко (Приложение 2, Диаграмма 1 -2). Также все ребята знают, что головоломки очень полезны и регулярное отгадывание их помогает развивать логику. Лишь 10 % ребят моего класса знают о такой игре, как "Ханойская башня" (Приложение 2. Диаграмма 3.) и абсолютно все хотели бы научиться в неё играть. (Приложение 2. Диаграмма 4.) Проанализировав полученные результаты моего анкетирования, я решил провести исследование на тему: «Головоломки. Ханойская башня.» и ответить на следующие вопросы :

Кто и когда придумал первые головоломки?

Для чего они нужны?

Как и когда появилась логическая игра "Ханойская башня" и получиться ли у меня научиться в неё играть?

Есть ли какая - то закономерность ходов в игре "Ханойская башня"?

Поэтому гипотеза моего исследования заключается в следующем: " В игре "Ханойская башня" существует алгоритм ходов, по которому можно играть в неё с любым количеством колец."

Цель моего исследования: смастерить модель игры - головоломки "Ханойская башня" для кабинета математики, научиться играть в игру - головоломку "Ханойская башня" и попытаться вывести формулу для расчета ходов для произвольного количества колец.

Задачи исследования :
Методы исследования:
СОДЕРЖАНИЕ

Введение............................................................................................................................ 6

1. Теоретическая часть.....................................................................................................7

1.1. Головоломки - гимнастика ума........................................................................7

1.2. История создания игры «Ханойская башня»..................................................8

2. Практическая часть......................................................................................................9

2.1 Правила игры "Ханойская башня"...................................................................9

2.2. Выведение формулы для расчета ходов.........................................................9

Заключение.......................................................................................................................14

Список литературы..........................................................................................................15

Приложение......................................................................................................................16

Головоломки. Ханойская башня.

Разуваев Данил Леонидович

Ханты-Мансийский автономный округ-Югра (Тюменская область)

город Нижневартовск

Муниципальное бюджетное общеобразовательное учреждение

«Средняя Школа №15»

5- Б класс

ВВЕДЕНИЕ

Величие человека - в его способности мыслить.

Б. Паскаль

В наше рациональное время многие искренне полагают, что кроссворды, пасьянсы, шашки и прочие игры – всего лишь эффективное средство «убить» время, и больше от них толку никакого. Но последние исследования учёных опровергают это. Оказывается, «бесполезные игрушки» способны защитить от болезни Альцгеймера. Результаты исследования, представленные в Копенгагене на международной конференции Ассоциации Альцгеймера, свидетельствуют, что игры, стимулирующие мозговую деятельность, могут способствовать сохранности уязвимых структур мозга и когнитивных функций. Люди, которые коротают время с помощью игр, стимулирующих мыслительные процессы, показывают лучшие результаты в тестах на память, способность к обучению и восприятию информации – утверждают исследователи.

Игра "Ханойская башня" - это очень интересная и красивая головоломка. Кажется, что существует она тысячи лет. Но на самом деле она была придумана в 1883 году. Суть головоломки и алгоритм ее сборки и составляют предмет данной работы.

1. Теоретическая часть.

1.1. Головоломки - гимнастика ума.

Математические головоломки, это различные, запутанные задания с подвохом. Как правило на логику и смекалку, с определенными условиями решения, к примеру: " Нужно соединить нарисованные девять точек четырьмя прямыми линиями не отрывая ручки от листа бумаги. " (Рис. I .)

Рис .I .

Первые головоломки – разгадывание игры слов, собирание замысловатых конструкций – появились ещё в III веке до нашей эры. Большей частью они основывались на умозаключениях и математических расчётах. То же касалось и настольных игр для двух и более участников, в которых уже был задействован дух соревнования. Эти занятия обучали, развивали интуицию и логическое мышление, учили терпению и последовательности. Сегодня предметы «гимнастики для ума» становятся широко востребованными в деловой сфере и просто в повседневной жизни. Первые головоломки были громоздки и небезопасны в использовании, особенно, если это игра для детей. Их даже отказывались экспортировать на Запад, что явилось одной из причин запоздалой популярности головоломки.

Самая знаменитая головоломка мира была изобретена в 1974 году венгерским скульптором и профессором архитектуры Эрно Рубиком. По одной из версий кубик Рубика изначально создавался как учебное пособие. При помощи него Рубик пытался втолковать воспитанникам основы математической теории групп. В начале изобретение представляло собой набор из 27 деревянных кубиков с разноцветными гранями (всего 27 х 6=156 цветных граней). В современном виде кубик Рубика появился лишь в 1980 году. Тогда же кубик сменил прозвище с «магического куба» на «кубик Рубика» . Новое прозвище прижилось, и только в Венгрии, Португалии и Германии головоломку по-прежнему называют «магический куб» . Выделились и китайцы, отвергнувшие оба варианта названия. У них игра называется «венгерский куб» . Только за два дебютных года по всему миру было реализовано более 100 млн. фирменных кубиков. И еще в полтора раза больше подделок. Первые головоломки Puzzle появились еще в XVIII столетии, когда некий изобретатель наклеил географическую карту на деревянную доску и разрезал ее.

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

Британские ученые доказали, что разгадывание кроссвордов и тому подобная активность "омолаживает" мозг. Учеными доказано, что решение логических задачек улучшает кровообращение в мозге, то есть действует подобно физическим упражнениям. Люди старше 65, регулярно сидящие за кроссвордами и ребусами, реже страдают ухудшением памяти и болезнью Альцгеймера, заявили британские нейрофизиологи.

1.2. История создания игры «Ханойская башня»

"Ханойская башня" является одной из популярных головоломок XIX века.

Эту игру придумал французский математик Эдуард Люка (Рис. II .), в 1883 году, её продавали как забавную игрушку. Первоначально она называлась «Профессор Клаус из Колледжа Ли Су Цян », но вскоре обнаружилось, что таинственный профессор из несуществующего колледжа - не более чем анаграмма фамилии изобретателя игры, профессора Люка из колледжа Сен-Луи.

Рис .II .

Эдуард Люка
Легенда гласит, что в Великом храме города Бенарас, под собором, отмечающим середину мира, находится бронзовый диск, на котором укреплены 3 алмазных стержня, высотой в один локоть и толщиной с пчелу. Давным-давно, в самом начале времён, монахи этого монастыря провинились перед богом Брахмой. Разгневанный, Брахма воздвиг три высоких стержня и на один из них возложил 64 диска, сделанных из чистого золота. Причем так, что каждый меньший диск лежит на большем.
Как только все 64 диска будут переложены со стержня, на который Брахма сложил их при создании мира, на другой стержень, башня вместе с храмом обратятся в пыль и под громовые раскаты погибнет мир.

Легенда о Храме Варанаси была придумана Люка, чтобы заинтересовать публику.

Количество перекладываний в зависимости от количества колец вычисляется по формуле.

Число перемещений дисков, которые должны совершить монахи, равно 18 446 744 073 709 551 615. Если бы монахи, работая день и ночь, делали каждую секунду одно перемещение диска, их работа продолжалась бы 584 миллиарда лет.

А с каким количеством дисков башня считается классической? Или нет такого понятия? Я думаю, что 10. По крайней мене столько дисков было нарисовано на оригинальной коробке Лукаса. (Рис. III .)

Рис. III .

Игра "Ханойская башня"

2. Практическая часть

2.1. Правила игры "Ханойская башня".

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

Игра заключается в том, чтобы передвинуть диски с одного стержня на другой, не нарушая следующие правила:
Когда дисков совсем немного, игра кажется лёгкой. Но с увеличением количества дисков растёт и количество шагов, которые надо предпринять, чтобы диски перенести, а вместе с этим усложняется сама игра.

Во сколько шагов решается головоломка?

2.2. Выведение формулы для расчета ходов.

Я решил узнать, как увеличивается количество ходов от количества колец. Для этого я смастерил модель игры - головоломки "Ханойская башня" из подручных материалов (в моем случае это кольца пирамиды, нанизанные на стержень). (Приложение 3. Фото.1-4.)

Исследование №1 ( с одним кольцом).

Переместить его на любой из стержней можно одним движением. Всего 1 шаг.

Схема игры.

Исследование №2 ( с двумя кольцами).

1. Перемещаем маленькое кольцо на стержень В;

2.Перемещаем большое кольцо на стержень С;

3.Переносим маленькое кольцо на стержень С.

Всего 3 шага.

Схема игры.

Исследование №3 ( с тремя кольцами).

Решение заключается в следующей последовательности шагов:

1.Перемещаем маленькое кольцо на стержень С;

2. Перемещаем среднее кольцо на стержень В;

3. Переносим маленькое кольцо на стержень В;

4. Переносим большое кольцо на стержень С;

5. Перемещаем маленькое кольцо на стержень А;

6. Перемещаем среднее кольцо на стержень С;

7. Переносим маленькое кольцо на стержень С.

Как видим количество шагов увеличится. Всего 7 шагов.

Схема игры.

Я заметил что, процесс делится на три части. Сначала переносится башня из двух колец со стержня А на стержень В. Затем перемещается большое кольцо со стержня А на стержень С. И в итоге со стержня В на стержень С переносится башенка из двух колец. Чтобы передвинуть башню из двух колец, мне необходимо было 3 шага, а для перемещения башни из трёх колец мне потребовалось 3+1+3=7 шагов.

Ч тобы перенести башню из четырех колец с первого стержня на третий, я действовал по следующему алгоритму:

1) перенести башню из трех верхних колец с первого стержня на второй (7 ходов);
2) самое большое кольцо перенести с первого стержня на третий (1 ход);
3) перенести башню из трех колец со второго стержня на третий (7 ходов).

Всего на перенос потребовалось 15 ходов. Сначала три верхних я переместил на стержень В, затем большое кольцо – с А на С, и в конце оставшиеся три кольца со стержня В на С. Здесь у меня получилось 7+1+7=15 шагов. Аналогично, я сосчитал число ходов, необходимых для переноса башни из пяти колец:
15 + 1 + 15 = 2 15 + 1 = 31, а потом проверил это на практике.

Для башни из 6 колец я получил 2 31 + 1 = 63 и т. д. И так по нарастающей. Для десяти колец необходимо как минимум 1023 шага, а для шестидесяти четырёх – 18 446 744 073 709 551 615 шагов.

Таким образом я вывел алгоритм (формулу) для определения количества ходов, в зависимости от количества колец. Получилась следующая закономерность: при увеличении количества колец на 1 (n +1) количество ходов увеличивается в 2 раза +1 ход (x *2+1). Таким образом, зная количество ходов для 8 колец, можно вычислить количество ходов для 9 колец.

X (9)=255*2+1=511

Количество ходов для 9 колец я проверил опытным путём и получил такое же количество ходов как и по формуле. Сама последовательность ходов при перекладывании пирамиды из 9 колец, представлена в видеоролике, прилагающемся к работе.

Результаты, полученные опытным путём, представлены в таблице 2.1.

Таблица 2.1.

Количество колец ( n)

Количество ходов ( x)

= 2n - 1

Но полученная формула удобна только в том случае, когда нам известно количество ходов для n колец, а найти необходимо для n +1 кольца. В других случаях её использование невозможно. Поэтому я задумался над выведением другой формулы.

Математическая формула, описывающая эту операцию, выглядит так:

2 n -1, где n -количество колец.

Проверяя для 9 колец, я получил 2 9 -1=512-1=511

Для решения этой "Ханойской башни" мне потребовалось 511 шагов.
Минимальное количество шагов, которое необходимо выполнить, чтобы решить головоломку с любым количеством колец показано в таблице 2.2. 6
ЗАКЛЮЧЕНИЕ

В результате работы над проектом я смастерил из подручных материалов игру - головоломку "Ханойская башня", научился в неё играть и вывел формулы для определения количества ходов, зависящих от количества колец в данной игре. Через решение данной головоломки на практике сначала для одного кольца, потом для двух, трёх и т.д. мне удалось подтвердить выдвинутую гипотезу и установить, что
Данное исследование может пригодиться для занятий на факультативах по математике по разгадыванию головоломок и решению логических задач, тем самым развивать у ребят усидчивость, навыки решения логических задач и настойчивость, расширит кругозор учащихся и заинтересует их к дальнейшим разгадываниям логических задач и головоломок. Модель игры "Ханойская башня", которую мне удалось создать, находится в кабинете математики и в неё можно играть всем учащимся на переменах.

Мозгу человека свойственна пытливость и тяга к самосовершенствованию. Не случайно многие проявляют интерес к разгадыванию кроссвордов, сканвордов и прочих головоломок связанных с использованием и накоплением собственно словарного запаса. Во время раздумывания над головоломкой наше серое вещество работает на полную катушку и мобилизует все силы. Это приводит к тому, что происходит оценка предыдущего опыта, анализ ошибок и выработка стратегий на будущее, как это было показано в моём исследовании при решении головоломки "Ханойская башня" в зависимости от количества колец. Я испытал великолепную тренировку ума и своих мыслительных способностей. Таким образом, логические головоломки – это способ не только приятного, а еще и полезного времяпровождения.

СПИСОК ЛИТЕРАТУРЫ
Приложение 1.

Анкета
__________
_____________________________________________________________ __________
_____________________________________________________________ __________
_____________________________________________________________ ___________

Приложение 2.

Диаграмма 1.

Диаграмма 2.

Диаграмма 3.

Диаграмма 4.

Приложение 3.

(фото.2.)

(фото.4.)

(фото.3.)

(фото.1.)

Для того, чтобы переложить всю пирамиду, надо сначала переложить все, что выше самого большого диска, с первого на вспомогательный стержень, потом переложить это самое большой диск с первого на третий стержень, а потом переложить оставшуюся пирамиду со второго на третий стержень, пользуясь первым стержнем, как вспомогательным.
/* данная процедура переносит N дисков со стержня A на стержень C пользуясь B как вспомогательным, соблюдая правила */ процедура "Перенести" (A, B, C, N) начало если N=1 // Если диск всего один, то надо его перенести напрямую то снять диск со стержня A и положить на стержень C; возврат из процедуры; иначе // Переносим все диски, кроме самого большога со стежня // A на стержень B Перенести (A,C,B,N-1); // Переносим самый большой диск со стержня A на стержень C снять диск со стержня A и положить на стержень C; // Переносим все диски со стержня B на стержень C поверх // самого большого диска Перенести (B,A,C,N-1); возврат из процедуры; конец если; конец процедуры "Перенести";
Всего получается 2 N-1 перекладываний.
Нерекурсивный метод

Стержню, на котором диски находятся в начале, дадим номер 0; стержню, на который их надо перенести - номер 2; и, соответственно, оставшемуся стержню - номер 1.
Пусть всего дисков N. Занумеруем диски в порядке увеличения радиуса числами 0,1,2,...,N-1.
Как известно, задача решается за 2 N-1 ходов. Занумеруем ходы числами 1,2,...,2 N-1 .
Любое натуральное число i единственным образом представимо в виде i=(2t+1)*2 k , где t и k - целые (т.е. как произведение нечетного числа на некоторую степень двойки). Так вот, на i-ом ходе переносится диск номер k со стержня номер ((-1) N-k *t mod 3) на стержень номер ((-1) N-k *(t+1) mod 3).
Пример для N=4.
Ход k(диск) t Со_стержня Hа_стержень Стержни |)!" 1 0 0 0 1 |)! " 2 1 0 0 2 |) " ! 3 0 1 1 2 |) !" 4 2 0 0 1 |) !" 5 0 2 2 0 |") ! 6 1 1 2 1 |")! 7 0 3 0 1 |)!" 8 3 0 0 1)!" | 9 0 4 1 2)! |" 10 1 2 1 0 !) |" 11 0 5 2 0 !") | 12 2 1 1 2 !" |) 13 0 6 0 1 ! " |) 14 1 3 0 2 " |)! 15 0 7 1 2 |)!"
если пpедставить что стержни, на котоpые одеваются диски, pасположены в yглах pавностоpоннего тpеyгольника, то самый маленький диск каждым нечетным ходом движется по (или пpотив, это от пеpвоначального кол-ва дисков зависит) часовой стpелки.
Все четные ходы опpеделяются однозначно. Какой диск меньше - тот и перекладывать (иначе противоречит условию). Т.к. тpогать диск 0 нельзя и класть больший на меньший тоже нельзя.
Отметим две закономерности:
1. Hа каждом нечетном ходy происходит перенос наименьшего диска.
2. Hаименьший диск всегда переносится циклически: либо A-B-C-A-B-C-... (в слyчае четного количества дисков), либо A-C-B-A-C-B-... (в слyчае нечетного).
А посемy полyчаем алгоритм:
1. Определяем число дисков, откyда находим как бyдет перемещаться наименьший диск (данный шаг делается в начале, притом один раз).

2. Смотрим номер хода: если нечетный - переносим наименьший диск в направлении, определенном в п.1. если четный - то возможный ход один единственный - берем наименьший из двyх верхних дисков и переносим его.

Можно написать немного по другому:
Для N от 1 до 2 k-1 выполнять
1. В двоичном представлении N найти самый правый ненулевой разряд. Обозначим номер этого разряда t.

2. Обозначим номер стержня, на котором находится диск t через i. Переместить диск t со стержня i на стержень (i+(-1) t) mod 3.

Кстати, по номеру хода легко можно восстановить положение дисков на стержнях: после i-ого хода диск номер j находится на стержне номер (-1) n-j *((i div 2 j)-(i div 2 j+1)) mod 3.