Задача
Ханойская башня и двоичная система счисления.Рассмотрим два процесса, каждый из которых состоит из 28- 1 шагов. Первый — это процесс решения головоломки ``Ханойская башня'' (смотри задачу1.42) при помощи оптимального алгоритма. Второй — это процесс прибавления единицы, который начинается с 0 и заканчивается числом 28- 1. Опишите связь между этими двумя процессами.
Решение
Решение задачи отсутствует
Ответ
Занумеруем диски в головоломкеХанойская башня'' числами от 0 до 7. При увеличении на 1 числа<i>n</i>, записанного в двоичной системе счисления,могут измениться цифры сразу в нескольких разрядах. Если среди всех изменившихся разрядов наибольший номер имеет<i>k</i>-й разряд, то это означает, что на<i>n</i>-ом шаге решения головоломки Ханойская
башня'' следует перемещать диск с номеромk.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь