Практическая работа 6 ГДЗ Босова 9 класс 2017 (Информатика)

Рассмотрим вариант решения задания из учебника Босова 9 класс, Бином: 6. В основу эффективного решения головоломки «Ханойская башня» положен алгоритм, суть которого сводится к следующему: для перемещения башни, состоящей из п колец, с первого стержня на третий мы должны решить чуть более простую задачу — переместить на второй стержень башню, состоящую из n-1 кольца. После этого нижний диск с первого стержня перемещается на третий и повторно осуществляется перемещение башни из n-1 кольца, но уже со второго диска на третий. Таким образом, число ходов, необходимых для перемещения башни из п колец, равно удвоенному числу ходов, необходимых для перемещения башни из n-1 кольца, и ещё одному ходу. Используйте эту закономерность для вычисления числа ходов, необходимых для перемещения башни из 64 колец. Вычислите, сколько времени займёт такое перемещение, если считать, что на один ход требуется 1 секунда. *Цитирирование задания со ссылкой на учебник производится исключительно в учебных целях для лучшего понимания разбора решения задания. 9 bosova9 pract/6 938

Число ходов для башни из $$n$$ колец обозначим через $$T(n)$$. По условию:

$$T(n)=2T(n-1)+1$$

При одном кольце нужен один ход:

$$T(1)=1$$

Тогда последовательно получаем:

$$T(2)=2\cdot 1+1=3$$

$$T(3)=2\cdot 3+1=7$$

Значит, для $$n$$ колец выполняется формула:

$$T(n)=2^n-1$$

Для $$64$$ колец:

$$T(64)=2^{64}-1$$

$$2^{64}=18446744073709551616$$

Следовательно,

$$T(64)=18446744073709551615$$

Если на один ход требуется 1 секунда, то время перемещения равно:

$$18446744073709551615\ \text{с}$$

Переведём в годы:

$$1\ \text{год}=365\cdot 24\cdot 60\cdot 60=31536000\ \text{с}$$

$$\frac{18446744073709551615}{31536000}\approx 5{,}85\cdot 10^{11}\ \text{лет}$$

Ответ

$$18446744073709551615$$ ходов; время перемещения — $$18446744073709551615$$ секунд, то есть примерно $$5{,}85\cdot 10^{11}$$ лет.