1

I need to implement a Brainfuck language like(?) language

There are 5 commands for the language.

Initially,

int x=1; at start of the execution of the algorithm

Each command does the following in C language.

"+": x+=1;

"-": x-=1;

">": x= x*2;

"<" : x= x/2;

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

Input is a sequence of characters that have ASCII codes between 0 to 127.

output should be a sequence of the commands above so that the program prints the same sequence of characters as the input

Note that the length of the output should be minimized.

For example

input: ABC

Output: >>>>>>+!+!+!

explanation: ASCII code for A B C are 65 66 67 receptively

x=1 so x is doubled 6 times to get to 64. Then increment and print 3 times to print all ABC.

This is minimal compared to increasing x 64 times to get to x=65

I need to implement this language.

But I am stuck on thinking up an algorithm that finds the sequence of commands when moving onto the next character in the input.

For instance, when x=8 and needs to move to 12, decrease x twice then multiplying by 2 is faster than adding 4 times. The decision for the algorithm gets very complicated when numbers get large enough.

I am thinking about recursion maybe to find the path? for minimum number of commands.

Any hints or is there a name of this esoteric language that I can refer to?

4

1 回答 1

1

找到从一个值x到另一个值的最小步数的一种方法是使用修改后的 Dijkstra 算法。

归结为维护要探索的数字列表，该列表将初始化为您的起始数字。当您探索一个数字时，您会采取所有可能的步骤，即+、和-，跟踪结果（以及您如何到达那里），直到您到达目的地。><

这将找到从您的起始号码到目的地号码的路径，并且保证是最短的。

于 2017-05-08T15:37:46.237 回答