Одно перекладывание Ханойских башен
Здесь мы рассмотрим классическую задачу о Ханойских башнях. В ней имеются три стержня и набор круглых дисков. Пусть количество дисков равно n. Диски имеют разный размер, никакие два из которых не имеют одинаковый радиус. Основное правило состоит в том, что запрещено класть больший диск на меньший. Пронумеруем диски с 1 (наименьший) до n (наибольший), стержни будем именовать A, B и C. Изначально все диски расположены на стержне A. Цель задачи состоит в перенесении их на стержень C, последовательно перекладывая их один за одним, никогда не кладя больший диск на меньший. Существует хорошо известное решение, которое рекурсивно перемещает n–1 диск с A на B, потом перемещает один диск с A на C, после чего рекурсивно перемещает n – 1 диск с B на C.
Псевдокод рекурсивного решения задачи о Ханойских башнях имеет вид:
move(num_disks, from_post, spare_post, to_post)
if (num_disks == 0)
return
move(num_disks – 1, from_post, to_post, spare_post)
print ("Move disk ", num_disks, " from ", from_post, " to ", to_post)
move(num_disks – 1, spare_post, from_post, to_post)
В этой задаче необходимо определить k-тое перекладывание по заданным k и n.
Входные данные
Каждая строка содержит два целых числа k и n. В конце входных данных расположена строка из двух нулей. Входные значения корректны, k и n - положительные целые числа, k меньше 2^n, поэтому k-тое перекладывание существует, n не более 60, поэтому ответ помещается в 64-битовый целочисленный тип.
Выходные данные
Вывести требуемое k-тое перекладывание, совершенное алгоритмом. Формат вывода должен быть следующим: "Case", один пробел, номер теста, двоеточие, один пробел, и ответ для текущего теста в формате: номер диска, имя стержня from_post и имя стержня to_post, разделяя их одним пробелом. Пробелы в конце строки не выводить.