Início / coding / Perguntas / 79276350
Accepted
Muhab Joumaa
Asked: 2024-12-13 03:25:17 +0800 CST

Como definir um algoritmo de Markov normal (NMA) para trocar dois números ternários separados pelo símbolo "^"?

  • 772

Estou tentando escrever um algoritmo de Markov normal em um emulador para trocar dois números ternários separados pelo símbolo "^". Por exemplo, para a entrada "120^210", o resultado deve ser "210^120".

Eu tentei estas regras:

^0 -> 0@^
^1 -> 1@^
^2 -> 2@^
@^0 -> 0@^
@^1 -> 1@^
@^2 -> 2@^
@^ -> ^
^->@
@0 -> ^0
@1 -> ^1
@2 -> ^2
@ -> ^

Mas não funcionou corretamente; só recebo "120210^".

algorithm

1 respostas

  1. Best Answer

    Quando o ^símbolo se moveu para a extrema direita, e é substituído por @, então não há mais regras que se aplicam. Por exemplo, @0, @1, @2nunca ocorrerá, então as regras correspondentes nunca serão ativadas, e então isso @é substituído de volta para ^sem ter realizado nada.

    Eu sugeriria dividir a tarefa nestas fases:

    1. Transforme todos os dígitos do lado direito em letras (a, b e c)
    2. Mova todas as letras para a esquerda de todos os dígitos (restantes)
    3. Transforme as letras em dígitos novamente

    Você pode usar um marcador diferente para cada fase para saber "onde você está".

    Aqui está uma possível implementação em JavaScript do algoritmo de Markov, dado um conjunto de regras que aplicarão as fases acima:

    // Every rule consists of 3 parts: find, replace, is-terminating-rule
const rules = [
    // Map the right-side digits to letters
    ["^0", "a^", false],
    ["^1", "b^", false],
    ["^2", "c^", false],
    ["^",  "@",  false], // Mapping completed, go to next phase:
    // Move letters left of all digits
    ["0a", "a0", false],
    ["0b", "b0", false],
    ["0c", "c0", false],
    ["0@", "@0", false],
    ["1a", "a1", false],
    ["1b", "b1", false],
    ["1c", "c1", false],
    ["1@", "@1", false],
    ["2a", "a2", false],
    ["2b", "b2", false],
    ["2c", "c2", false],
    ["2@", "@2", false],
    ["@",  "<|", false], // Move completed, go to next phase:
    // Change letters back to digits
    ["a<", "<0", false],
    ["b<", "<1", false],
    ["c<", "<2", false],
    ["<",  "",   false], // Change back completed, go to last phase:
    // Terminating rule
    ["|",  "^",  true],
];

const result = applyRules("210^120", rules);
console.log("final:", result);

// Used Markov algorithm
function applyRules(str, rules) {
    for (let i = 0; i < 5000; i++) { // Avoid infinite loop
        const rule = rules.find(([find]) => str.includes(find)); 
        if (!rule) return str;
        const [find, replace, terminating] = rule;
        str = str.replace(find, replace);
        console.log(`apply rule "${find}"=>"${replace}", result="${str}"`);
        if (terminating) return str;
    }
}

    • 0

relate perguntas