НОВОСТИ
29.10.2010
Открылся новый раздел "Тексты песен"!
14.12.2009
Открылся новый раздел "Праздники"!



Диски

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

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

Добавил: Катерина
Источник: Интернет


ЗеркалоНаписано 9 сентября 2009, в 19:05

Задача о Ханойской башне. Классическая задача, на которой обычно объясняется принцип рекурсии: для одного диска ответ очевиден: надо просто перенести этот диск с оси А на ось Б; чтобы перенести 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.



Ваше мнение (не более 1000 символов):
Автор:
На обсуждение?

Большая просьба:

  1. Сообщение писать по теме, которая обсуждается
  2. Сообщение должно быть информационным

Пожалуйста: при копировании загадки "Диски" с данного сайта, делайте ссылку на наш сайт или на автора (если имеется)


ВХОД НА САЙТ
 
регистрация  


ДРУЗЬЯ

Rating All.BY