Эзотерический язык с 5 операторами

Question

Мне нужно реализовать язык Brainfuck как (?) Язык

Есть 5 команд для языка.

Первоначально,

int x=1; в начале выполнения алгоритма

Каждая команда делает следующее на языке Си.

"+": х + = 1;

"-": х- = 1;

">": x = x * 2;

"<": x = x / 2;

"!": printf ("% c", x);

Ввод - это последовательность символов с кодами ascii от 0 до 127.

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

Обратите внимание, что длина вывода должна быть сведена к минимуму.

Например

вход: ABC

Вывод: >>>>>>+!+!+!

объяснение: ASCII код для ABC 65 66 67 восприимчиво

x=1, так что x удваивается 6 раз, чтобы получить 64. Затем увеличивается и печатается 3 раза, чтобы напечатать все ABC.

Это минимально по сравнению с увеличением х 64 раз, чтобы добраться до х =65

Мне нужно реализовать этот язык.

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

Например, когда x=8 и нужно перейти к 12, уменьшите x в два раза, а затем умножьте на 2 быстрее, чем добавьте 4 раза. Решение для алгоритма становится очень сложным, когда числа становятся достаточно большими.

Я думаю о рекурсии, может быть, чтобы найти путь? для минимального количества команд.

Любые намеки или есть название этого эзотерического языка, к которому я могу обратиться?

Answer 1

Один способ найти минимальное количество шагов, чтобы перейти от одного значения x другой использует модифицированный алгоритм Дейкстры.

Это сводится к ведению списка номеров для исследования, который будет инициализирован для вашего стартового номера. Когда вы исследуете номер, вы делаете все возможные шаги, т.е. +, -, > а также <, отслеживая результат (и как вы туда попали), пока не дойдете до пункта назначения.

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