Чтобы узнать, что такое Ханойская башня, либо поищите ее в Google, либо посмотрите на странице Википедии .

Ваш код должен быть в состоянии сделать 2 вещи, и они следующие:

• Принять пользовательский ввод, который определяет количество дисков в начальной точке Ханойской башни
• Создайте вывод в выбранном вами стиле (если это логично), чтобы показать решение головоломки с башней.

Примером логического вывода может быть следующий (с использованием запуска на 4 диска):

L1L2C1L1R-2R-1L1L2C1C-1R-2C1L1L2C1

Lпредставляет левый штифт, Cпредставляет центральный штифт и Rпредставляет правый штифт, а цифры показывают, как далеко диск перемещается по этому штифту и в каком направлении. Положительные числа представляют количество колышков, движущихся в направлении самого правого колышка (поскольку диски начинаются на крайнем левом колышке).

В правилах к башне Ханоя просты:

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

Диски начинаются с самого левого колышка, самый большой снизу, самый маленький сверху, естественно.

Шелуха , 5 байт

↑≠⁰İr

Попробуйте онлайн!
Каждый nиз выходных данных представляет собой перемещение диска nк следующему доступному штифту (циклический перенос).

объяснение

   İr   The ruler sequence [0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, ...]
↑       Take while...
 ≠⁰     ... not equal to the input.

Питон, 76 символов

def S(n,a,b):
 if n:S(n-1,a,6-a-b);print n,a,b;S(n-1,6-a-b,b)
S(input(),1,3)

Например, для N = 3 он возвращает:

1 1 3  (move disk 1 from peg 1 to peg 3)
2 1 2  (move disk 2 from peg 1 to peg 2)
1 3 2  (move disk 1 from peg 3 to peg 2)
3 1 3  ...
1 2 1
2 2 3
1 1 3

Perl - 54 символа

for(2..1<<<>){$_--;$x=$_&-$_;say(($_-$x)%3,($_+$x)%3)}

Запустите с perl -M5.010и введите количество дисков на стандартный ввод.

Выходной формат:

Одна строка на ход, первая цифра от колышка, вторая цифра от колышка (начиная с 0)

Пример:

02 -- move from peg 0 to peg 2
01
21
02
10
12
02

GolfScript ( 31 25 24 символов)

])~{{~3%}%.{)3%}%2,@++}*

Спасибо Ильмари Каронену за то, что он указал, что мои первоначальные trперестановки могут быть сокращены на 6 символов. Разложив их как произведение двух перестановок, мне удалось сохранить еще одну.

Обратите внимание, что факторинг 3%увеличивает длину на один символ:

])~{{~}%.{)}%2,@++}*{3%}%

У некоторых людей действительно сложные выходные форматы. Это выводит колышек, перемещенный из (пронумерованный 0, 1, 2), и колышек перемещается в. В спецификации не указано, к какому колышку двигаться, поэтому он перемещается к колышку 1.

Например

$ golfscript hanoi.gs <<<"3"
01021201202101

Perl, 75- 79 символов

Полностью украдя формат вывода Кита Рэндалла:

sub h{my($n,$p,$q)=@_;h($n,$p^$q^h($n,$p,$p^$q),$q*say"@_")if$n--}h pop,1,3

Вызвать с -M5.010за say.

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

SML, 63

fun f(0,_,_)=[]|f(n,s,t)=f(n-1,s,6-s-t)@[n,s,t]@f(n-1,6-s-t,t);

вызвать функцию f(n,s,t)с:

• количество дисков
• отправная точка
• Т цель

Баш (64 символа)

t(){ tr 2$1 $12 <<<$s;};for((i=$1;i--;))do s=`t 1`01`t 0`;done;t

Публикация этого, несмотря на то, что он в два раза длиннее GolfScript, потому что мне нравится повторное использование tв качестве echo $s.

Скала, 92 88 87 символов

def?(n:Int,a:Int,b:Int){if(n>0){?(n-1,a,a^b)
print(n,a,b);?(n-1,a^b,b)}};?(readInt,1,3)

Выходной формат

Скажите номер диска = 3 тогда,

(1,1,3)(2,1,2)(1,3,2)(3,1,3)(1,2,1)(2,2,3)(1,1,3) (disk number,from peg, to peg)
                                                   \---------------------------/       
                                                            Move 1              ... Move n

C 98 92 87 символов

Реализует самый тривиальный алгоритм.
Выходные данные имеют вид, в ab ab abкотором каждая пара означает «переместить верхний диск из колышка а в колышек б».
РЕДАКТИРОВАТЬ : теперь ходы закодированы в шестнадцатеричном формате - 0x12 означает переход от колышка 1 к колышку 2. Сохранены некоторые символы.
РЕДАКТИРОВАТЬ : читает число из стандартного ввода, а не параметр. Более короткие.
Пример:
% echo 3 | ./hanoi
13 12 32 13 21 23 13

n;
h(d){n--&&h(d^d%16*16,printf("%02x ",d,h(d^d/16))),n++;}
main(){scanf("%d",&n);h(19);}

Желе , 5 байт

2*Ṗọ2

Попробуйте онлайн!

0переместить наименьший диск на одну позицию вправо (при необходимости
1перенести обратно на начало) переместить второй наименьший диск в единственный другой допустимый столбец
2переместить третий наименьший диск в единственный другой допустимый столбец
и т. д.

Алгоритм

Мы можем увидеть решение проблемы Ханойских башен рекурсивно; чтобы переместить стопку размера п от A до B , переместить стопку размера п -1 от А до С , то диск размером п от A до B , а затем переместить стопку размера п -1 от B до C . Это создает шаблон следующей формы (в формате вывода, используемом этой программой):

0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2 …

Мы можем наблюдать, что эта последовательность A007814 в OEIS. Другое возможное определение последовательности: « k- й (основанный на 1) элемент последовательности - это число нулей в конце числа k, когда оно записано в двоичном виде». И это то, что программа здесь рассчитывает.

объяснение

Сначала рассчитаем количество ходов в решении, 2 ⁿ -1. Оказывается, 2*самое короткое время - вычислить один дополнительный ход и отбросить его позже, так что это 2, то есть степень чего-либо. (Единственный вход, который мы до сих пор использовали, это аргумент командной строки, поэтому он используется по умолчанию.)

Далее мы используем встроенную функцию Jelly для вычисления количества нулей в конце числа в базе b ; что - х . Как мы рассчитываем в двоичном виде, это так . Все, что нам нужно сделать, это применить эту встроенную функцию к числам от 1 до 2 ⁿ -1 включительно.ọbọ2

Есть два простых способа перебора диапазона чисел в Jelly, €и R, и мои предыдущие попытки решить эту проблему использовали один из них. Однако в этом случае можно пойти немного короче: Ṗкогда задано число в качестве входных данных, вы можете выполнить итерацию, которая останавливает один элемент (обычно Ṗэто встроенная функция, используемая для обработки всех элементов, кроме одного). Это именно то, что мы хотим в этом случае (потому что 2*генерирует слишком много элементов), поэтому использование его для ссылки 2*и ọ2в 2*Ṗọ2дает нам 5-байтовое решение проблемы.

Awk, 72 символа

function t(n,a,b){if(n){t(n-1,a,a^b);print n,a,b;t(n-1,a^b,b)}}t($0,1,3)

Выходной формат такой же, как у Кейта Рэндалла .

awk -f tower.awk <<< "3"    
1 1 1
2 1 1
1 1 1
3 1 3
1 1 1
2 1 3
1 1 3

Bash скрипт, 100 96 символов

t(){ [[ $1<1 ]] && return
t $(($1-1)) $2 $(($2^$3))
echo $@
t $(($1-1)) $(($2^$3)) $3
}
t $1 1 3

Выходной формат такой же, как у Кейта Рэндалла .

1 1 3
2 1 2
1 3 2
3 1 3
1 2 1
2 2 3
1 1 3

Редактировать : 4 комментария Петра сохранены .

J, 23 байта

решение двоичных чисел

2&(+/@:~:/\)@#:@i.@^~&2

Это решение использует метод двоичного подсчета, описанный в этом видео .

То есть я генерирую двоичные цифры от 1до 2^n, затем беру инфиксы длины 2 и сравниваю каждый бит с соответствующим битом предыдущего числа, и проверяю, являются ли они неравными. Количество неравных битов является выходом для этого хода.

Вывод, например, для 3 дисков, где самый маленький диск помечен как 1:

1 2 1 3 1 2 1

1 означает «переместить наименьший диск на один колышек вправо, при необходимости вернувшись к первому колышку»

nдля всех остальных n означает «переместить диск nна легальную привязку» (всегда будет ровно одна)

Попробуйте онлайн!

рекурсивное решение

((],[,])$:@<:)`]@.(1=])

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

Визуализация его в виде дерева также подчеркивает этот момент:

              4
             / \
            /   \
           /     \
          /       \
         /         \
        /           \
       /             \
      3               3      
     / \             / \    
    /   \           /   \
   /     \         /     \ 
  2       2       2       2  
 / \     / \     / \     / \
1   1   1   1   1   1   1   1

Попробуйте онлайн!

APL (Dyalog Classic) , 19 байтов

3|(-⍪0 1⍪2∘-)⍣⎕,⍨⍪⍬

Попробуйте онлайн!

вывод представляет собой 2-столбцовую матрицу целых чисел в {0,1,2} - от колышка до колышка

К (нгн / к) , 23 байта

{3!x{-x,(,0 2),1+x}/()}

Попробуйте онлайн!

R , 73 байта

Помещение R на карту. Вдохновленный [ответом Кита Рэндалла] [1] с упрощенным вводом, напечатайте только конец и начните колышек, чтобы сохранить 2 байта. Также 0-индексированные колышки.

f=function(n,s=0,e=2){if(n){f(n-1,s,3-s-e)
print(c(s,e))
f(n-1,3-s-e,e)}}

Попробуйте онлайн!

JavaScript (ES6), 45b

h=(n,f,a,t)=>n?h(--n,f,t,a)+f+t+h(n,a,f,t):''

например, вызов h(4, 'A', 'B', 'C')(переместите 4 диска из колышка A в колышек C, используя вспомогательный колышек B)

возврат 'ABACBCABCACBABACBCBACABCABACBC'(переместите диск из колышка A в колышек B, переместите диск из колышка A в колышек C, переместите диск из колышка B в колышек C и т. д.)