Алгоритм вставки 1 штуки в несовершенную Ханойскую башню

Question

Я делаю программу для своей руки-робота, чтобы построить Ханойскую башню. Я получил алгоритм, работающий на стоящей башне (замена башни на другое место, используя только 3 местоположения).

Местоположения: A, B, C
Части: 5

Я бы хотел построить башню поэтапно (я положу часть на локацию C, а рука помещает её на / в башню на локацию A). Код работает, если текущий кусок идет сверху.

Вопрос: существует ли (рекурсивный) алгоритм для помещения части в башню, используя только 3 места (A - текущая башня, C - новая часть, B - пустая)?

РЕДАКТИРОВАТЬ: Я не пытаюсь построить башню в другом месте. Я прошу алгоритм, который мог бы поместить кусок на C в башню на A (скажем, башня 5-3-2-1, и я помещаю последний '4' кусок на C. Алгоритм должен поместить его вправильное место для этого, чтобы стать 5-4-3-2-1).

Answer 1

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

1. Определите, сколько фигур в стеке A меньше, чем в стеке C. Назовите этот номер k . Это может быть ноль, в этом случае вы можете просто переместить кусок из стека C в стек A за одну операцию. Если нет:

2. Полностью игнорируйте фигуры в стеке А, которые находятся ниже верхних k фигур. Выполните этот и следующие шаги, как будто они не существуют. Теперь используйте свой существующий алгоритм (чтобы полностью переместить стек в другое место), чтобы переместить верхние элементы k из стека A в положение B. Игнорируемые нами фигуры не участвуют в этом движении.

3. Затем переместите кусок из стека C в стек A. Теперь также игнорируйте этот кусок на следующем шаге. Таким образом, мы можем действовать так, как если бы стек А сейчас пуст.

4. Используйте ваш алгоритм снова, чтобы переместить стек В в местоположение А. Опять же, мы игнорируем фрагменты, которые уже находятся в месте А: онине двигайтесь во время этого шага.