Связь между головоломками

Задача с кольцами может быть решена с помощью такого же рекурсивного алгоритма.

Существует и простая итерационная процедура для ее решения, еще более очевидная, чем итерационное решение задачи о башне. Однако, чтобы не лишать читателя удовольствия, которое он испытает, решив задачу, мы не станем открывать секрета этого простого метода. Здесь практически невозможно дать какое-нибудь указание, не сказав ответа. Отметим лишь, что решение можно сформулировать в одном или двух предложениях, и оно не требует никакой формальной записи.

Удивительно, что эти задачи оказываются почти полностью идентичными. Это напоминает еще об одном контрасте, который часто наблюдается в математике вообше и в вычислительной математике в частности. Две задачи, внешне кажущиеся совершенно различными, при более детальном рассмотрении оказываются, по существу, одной и той же задачей!

Связь между двумя рассмотренными головоломками проявляется при анализе двух двоичных кодов и алгоритма перевода из одного кода в другой. Подобно тому как мы представляли шаги решения задачи о башне последовательными двоичными числами, введем двоичный код для представления задачи с кольцами: пусть I представляет кольцо, находящееся на петле, а 0 — соответственно кольцо, снятое с петли. Тогда задача с пятью кольцами может быть представлена пятиразрядной последовательностью 0 и 1, так что крайний левый разряд будет соответствовать кольцу, расположенному у рукоятки. Первые четыре конфигурации в задаче с кольцами, записанные в виде таких чисел, будут иметь следую

щий вид:

1   I I I 1 (все кольца надеты)

11110  (первое кольцо снято)

110 10 (первое и третье кольца сняты)

110 11 (третье кольцо снято)

На следующих двух шагах снимается второе, а затем первое кольцо. После этого снимается пятое кольцо. Затем первые три кольца снова одеваются на петлю, чтобы можно было снять четвертое кольцо. Чтобы удалить все пять колец, требуется 21 шаг. Последние четыре конфигурации в последовательности, ведущей к решению, таковы:

00 0 10 (второе кольцо надето)

0 00 11 (первое и второе кольца налеты)

0 00 0 1   (первое кольцо надето)

00 0 00 (ни одно кольцо не надето)

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

1.  Крайний правый разряд можно изменить (с 0 на 1 или с 1 на 0) в любой момент.

2.  Из остальных разрядов можно изменять лишь тот, который находится непосредственно слева от крайнего справа разряда, имеющего значение 1.

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

 

0 Коментариев

Вы можете быть первым =)

Оставить коментарий