ЗАГАДКИ

Случайная загадка

ОБСУЖДЕНИЯ

Главная

Добавить Игру

Контакты

Диски

У вас детская пирамидка из 4 дисков.
Вам нужно перенести все диски с оси А на ось Б используя промежуточную вспомогательную ось В, руководствуясь 2 правилами: 1)за один ход можно переносить только один диск 2) нельзя на меньший диск класть больший. Сколько минимально ходов нужно сделать, что бы решить ее?
Подсказки:
Существует такая персидская легенда:
в Персии на вершине священной горы проходящей через земную ось расположен Храм Времени. На алтаре этого храма находится пирамида из изумрудной оси, на которой лежат 64 золотых диска. И жрецы храма сменяя друг друга без перерыва переносят диски с одной оси на другую, как в нашей задаче. По преданию, когда все диски будут перенесены, земля перестанет вращаться и наступит конец света.

Ответ: 15. 2 в степени n минус 1, где n- число дисков.
А насчет легенды - волноваться не следует. Согласно вышеуказанной формуле это печальное событие наступит лишь через примерно 900 миллиардов лет. - (наведите курсор)

Катерина

предыдущая  | "Диски" | следующая

Зеркало

09 Сен, 2009

Задача о Ханойской башне. Классическая задача, на которой обычно объясняется принцип рекурсии: для одного диска ответ очевиден: надо просто перенести этот диск с оси А на ось Б; чтобы перенести n дисков с оси А на ось Б через ось В, надо сначала перенести n-1 диск с оси А на ось В (используя ось Б, как вспомогательную), затем перенести самый большой диск с оси А на ось Б и затем снова перенести n-1 дисков уже с оси В на ось Б. Как видим, при увеличении числа дисков на 1, число ходов увеличивается примерно в два раза (точнее Sn=2Sn-1+1, где Sn - число ходов, требуемое для перемещения n дисков), т.е. получается практически экспоненциальная зависимость.

Вывести точную формулу несложно. Достаточно определить несколько первых членов этой последовательности:

S1=1
S2=1·2+1=3
S3=3·2+1=7
S4=7·2+1=15
...

и заметить, что получаются числа вида 2n-1. Теперь докажем эту формулу по индукции:

Для n=1 формула очевидно выполняется. Теперь, предположив, что она выполняется для n, докажем, что она будет выполняться и для n+1:

Sn+1=2Sn+1=2(2n-1)+1=2·2n-2·1+1=2n+1-1, что соответствует формуле для Sn+1.

Авторизируйтесь что бы добавить свой комментарий

ВХОД НА САЙТ

Войдите на сайт с помощью одной из социальных сетей

TOP 10

100 лучших..