Torres de Hanói

movimientos = 0


def hanoi(n, origen, destino, auxiliar, escribir):
    global movimientos
    if n == 0:
        return
    hanoi(n - 1, origen, auxiliar, destino, escribir)     # aparta los n − 1 de encima
    movimientos += 1
    if escribir:
        print(f"{movimientos}. disco {n}: {origen} → {destino}")
    hanoi(n - 1, auxiliar, destino, origen, escribir)     # y los vuelve a poner encima


hanoi(3, "A", "C", "B", True)
for n in (10, 16):
    movimientos = 0
    hanoi(n, "A", "C", "B", False)
    print(f"{n} discos: {movimientos} movimientos (2^{n} − 1 = {(1 << n) - 1})")

let movimientos = 0;

function hanoi(n, origen, destino, auxiliar, escribir) {
    if (n === 0) return;
    hanoi(n - 1, origen, auxiliar, destino, escribir);    // aparta los n − 1 de encima
    movimientos++;
    if (escribir) console.log(`${movimientos}. disco ${n}: ${origen} → ${destino}`);
    hanoi(n - 1, auxiliar, destino, origen, escribir);    // y los vuelve a poner encima
}

hanoi(3, "A", "C", "B", true);
for (const n of [10, 16]) {
    movimientos = 0;
    hanoi(n, "A", "C", "B", false);
    console.log(`${n} discos: ${movimientos} movimientos (2^${n} − 1 = ${(1 << n) - 1})`);
}

using System;

class Program {
    static int movimientos = 0;

    static void Hanoi(int n, char origen, char destino, char auxiliar, bool escribir) {
        if (n == 0) return;
        Hanoi(n - 1, origen, auxiliar, destino, escribir);    // aparta los n − 1 de encima
        movimientos++;
        if (escribir) Console.WriteLine(
quot;{movimientos}. disco {n}: {origen} → {destino}");
        Hanoi(n - 1, auxiliar, destino, origen, escribir);    // y los vuelve a poner encima
    }

    static void Main() {
        Hanoi(3, 'A', 'C', 'B', true);
        foreach (int n in new[] { 10, 16 }) {
            movimientos = 0;
            Hanoi(n, 'A', 'C', 'B', false);
            Console.WriteLine(
quot;{n} discos: {movimientos} movimientos (2^{n} − 1 = {(1 << n) - 1})");
        }
    }
}

<?php
$movimientos = 0;

function hanoi(int $n, string $origen, string $destino, string $auxiliar, bool $escribir): void {
    global $movimientos;
    if ($n == 0) return;
    hanoi($n - 1, $origen, $auxiliar, $destino, $escribir);   // aparta los n − 1 de encima
    $movimientos++;
    if ($escribir) echo "$movimientos. disco $n: $origen → $destino\n";
    hanoi($n - 1, $auxiliar, $destino, $origen, $escribir);   // y los vuelve a poner encima
}

hanoi(3, "A", "C", "B", true);
foreach ([10, 16] as $n) {
    $movimientos = 0;
    hanoi($n, "A", "C", "B", false);
    echo "$n discos: $movimientos movimientos (2^$n − 1 = " . ((1 << $n) - 1) . ")\n";
}

def iterativo(n):
    """Sin recursividad: en los movimientos impares el disco 1 avanza en círculo (A→C→B si n es impar,
    A→B→C si es par); en los pares se hace el único movimiento posible que no lo toca."""
    postes = [list(range(n, 0, -1)), [], []]          # el final de cada lista es el disco de arriba
    paso, chico = (1 if n % 2 == 0 else 2), 0         # chico: el poste donde está el disco 1
    movs = []
    for k in range(1, 1 << n):
        if k % 2 == 1:
            de, a = chico, (chico + paso) % 3
            chico = a
        else:
            x, y = (chico + 1) % 3, (chico + 2) % 3
            de_x = bool(postes[x]) and (not postes[y] or postes[x][-1] < postes[y][-1])
            de, a = (x, y) if de_x else (y, x)
        disco = postes[de].pop()
        postes[a].append(disco)
        movs.append(f"disco {disco}: {'ABC'[de]} → {'ABC'[a]}")
    return movs


def recursivo(n, o, d, x, movs):
    if n == 0:
        return
    recursivo(n - 1, o, x, d, movs)
    movs.append(f"disco {n}: {'ABC'[o]} → {'ABC'[d]}")
    recursivo(n - 1, x, d, o, movs)


for i, m in enumerate(iterativo(3), 1):
    print(f"{i}. {m}")
iguales = True
for n in range(1, 13):
    r = []
    recursivo(n, 0, 2, 1, r)
    if r != iterativo(n):
        iguales = False
print("Mismos movimientos que la versión recursiva para n = 1..12: " + ("sí" if iguales else "no"))

/** Sin recursividad: en los movimientos impares el disco 1 avanza en círculo (A→C→B si n es impar,
    A→B→C si es par); en los pares se hace el único movimiento posible que no lo toca. */
function iterativo(n) {
    const postes = [[], [], []];                      // el final de cada array es el disco de arriba
    for (let d = n; d >= 1; d--) postes[0].push(d);
    const paso = n % 2 === 0 ? 1 : 2;
    let chico = 0;                                    // chico: el poste donde está el disco 1
    const movs = [];
    for (let k = 1; k < (1 << n); k++) {
        let de, a;
        if (k % 2 === 1) {
            de = chico;
            a = (chico + paso) % 3;
            chico = a;
        } else {
            const x = (chico + 1) % 3, y = (chico + 2) % 3;
            const deX = postes[x].length > 0 && (postes[y].length === 0 || postes[x].at(-1) < postes[y].at(-1));
            de = deX ? x : y;
            a = deX ? y : x;
        }
        const disco = postes[de].pop();
        postes[a].push(disco);
        movs.push(`disco ${disco}: ${"ABC"[de]} → ${"ABC"[a]}`);
    }
    return movs;
}

function recursivo(n, o, d, x, movs) {
    if (n === 0) return;
    recursivo(n - 1, o, x, d, movs);
    movs.push(`disco ${n}: ${"ABC"[o]} → ${"ABC"[d]}`);
    recursivo(n - 1, x, d, o, movs);
}

iterativo(3).forEach((m, i) => console.log(`${i + 1}. ${m}`));
let iguales = true;
for (let n = 1; n <= 12; n++) {
    const r = [];
    recursivo(n, 0, 2, 1, r);
    if (r.join("|") !== iterativo(n).join("|")) iguales = false;
}
console.log("Mismos movimientos que la versión recursiva para n = 1..12: " + (iguales ? "sí" : "no"));

using System;
using System.Collections.Generic;
using System.Linq;

class Program {
    /// Sin recursividad: en los movimientos impares el disco 1 avanza en círculo (A→C→B si n es impar,
    /// A→B→C si es par); en los pares se hace el único movimiento posible que no lo toca.
    static List<string> Iterativo(int n) {
        var postes = new List<Stack<int>> { new(), new(), new() };
        for (int d = n; d >= 1; d--) postes[0].Push(d);
        int paso = n % 2 == 0 ? 1 : 2, chico = 0;           // chico: el poste donde está el disco 1
        var movs = new List<string>();
        for (int k = 1; k < (1 << n); k++) {
            int de, a;
            if (k % 2 == 1) {
                de = chico;
                a = (chico + paso) % 3;
                chico = a;
            } else {
                int x = (chico + 1) % 3, y = (chico + 2) % 3;
                bool deX = postes[x].Count > 0 && (postes[y].Count == 0 || postes[x].Peek() < postes[y].Peek());
                de = deX ? x : y;
                a = deX ? y : x;
            }
            int disco = postes[de].Pop();
            postes[a].Push(disco);
            movs.Add(
quot;disco {disco}: {"ABC"[de]} → {"ABC"[a]}");
        }
        return movs;
    }

    static void Recursivo(int n, int o, int d, int x, List<string> movs) {
        if (n == 0) return;
        Recursivo(n - 1, o, x, d, movs);
        movs.Add(
quot;disco {n}: {"ABC"[o]} → {"ABC"[d]}");
        Recursivo(n - 1, x, d, o, movs);
    }

    static void Main() {
        var it = Iterativo(3);
        for (int i = 0; i < it.Count; i++) Console.WriteLine(
quot;{i + 1}. {it[i]}");
        bool iguales = true;
        for (int n = 1; n <= 12; n++) {
            var r = new List<string>();
            Recursivo(n, 0, 2, 1, r);
            if (!r.SequenceEqual(Iterativo(n))) iguales = false;
        }
        Console.WriteLine("Mismos movimientos que la versión recursiva para n = 1..12: " + (iguales ? "sí" : "no"));
    }
}

<?php
/** Sin recursividad: en los movimientos impares el disco 1 avanza en círculo (A→C→B si n es impar,
    A→B→C si es par); en los pares se hace el único movimiento posible que no lo toca. */
function iterativo(int $n): array {
    $postes = [range($n, 1), [], []];                 // el final de cada array es el disco de arriba
    $paso = $n % 2 == 0 ? 1 : 2;
    $chico = 0;                                       // chico: el poste donde está el disco 1
    $movs = [];
    for ($k = 1; $k < (1 << $n); $k++) {
        if ($k % 2 == 1) {
            $de = $chico;
            $a = ($chico + $paso) % 3;
            $chico = $a;
        } else {
            $x = ($chico + 1) % 3;
            $y = ($chico + 2) % 3;
            $deX = count($postes[$x]) > 0 && (count($postes[$y]) == 0 || $postes[$x][count($postes[$x]) - 1] < $postes[$y][count($postes[$y]) - 1]);
            $de = $deX ? $x : $y;
            $a = $deX ? $y : $x;
        }
        $disco = array_pop($postes[$de]);
        $postes[$a][] = $disco;
        $movs[] = "disco $disco: " . "ABC"[$de] . " → " . "ABC"[$a];
    }
    return $movs;
}

function recursivo(int $n, int $o, int $d, int $x, array &$movs): void {
    if ($n == 0) return;
    recursivo($n - 1, $o, $x, $d, $movs);
    $movs[] = "disco $n: " . "ABC"[$o] . " → " . "ABC"[$d];
    recursivo($n - 1, $x, $d, $o, $movs);
}

foreach (iterativo(3) as $i => $m) echo ($i + 1) . ". $m\n";
$iguales = true;
for ($n = 1; $n <= 12; $n++) {
    $r = [];
    recursivo($n, 0, 2, 1, $r);
    if ($r !== iterativo($n)) $iguales = false;
}
echo "Mismos movimientos que la versión recursiva para n = 1..12: " . ($iguales ? "sí" : "no") . "\n";