当前位置：首页 > JavaScript

js实现汉诺塔移动过程

2026-01-31 11:55:25JavaScript

汉诺塔问题概述

汉诺塔（Tower of Hanoi）是一个经典的递归问题，目标是将一组盘子从起始柱移动到目标柱，遵循以下规则：

每次只能移动一个盘子。
每次移动时，将最上面的盘子移动到某一柱上。
任何时候大盘子不能放在小盘子上面。

递归实现

递归是解决汉诺塔问题的自然方法。通过将问题分解为子问题，逐步移动盘子。

function hanoi(n, source, target, auxiliary) {
    if (n === 1) {
        console.log(`Move disk 1 from ${source} to ${target}`);
        return;
    }
    hanoi(n - 1, source, auxiliary, target);
    console.log(`Move disk ${n} from ${source} to ${target}`);
    hanoi(n - 1, auxiliary, target, source);
}

// 示例：移动3个盘子，从柱子A到柱子C，借助柱子B
hanoi(3, 'A', 'C', 'B');

非递归实现（栈模拟）

使用栈模拟递归过程，避免递归调用栈过深的问题。

function hanoiIterative(n, source, target, auxiliary) {
    const stack = [];
    stack.push({ n, source, target, auxiliary });

    while (stack.length > 0) {
        const { n, source, target, auxiliary } = stack.pop();
        if (n === 1) {
            console.log(`Move disk 1 from ${source} to ${target}`);
        } else {
            stack.push({ n: n - 1, source: auxiliary, target, auxiliary: source });
            stack.push({ n: 1, source, target, auxiliary });
            stack.push({ n: n - 1, source, target: auxiliary, auxiliary: target });
        }
    }
}

// 示例：移动3个盘子
hanoiIterative(3, 'A', 'C', 'B');

可视化实现

结合HTML和CSS，动态展示汉诺塔移动过程。

<!DOCTYPE html>
<html>
<head>
    <style>
        .tower { display: inline-block; width: 20px; height: 200px; background: #ccc; margin: 0 50px; position: relative; }
        .disk { height: 20px; background: #f00; position: absolute; bottom: 0; border-radius: 10px; }
    </style>
</head>
<body>
    <div id="towers"></div>
    <script>
        function initTowers(n) {
            const towers = document.getElementById('towers');
            towers.innerHTML = '';
            for (let i = 0; i < 3; i++) {
                const tower = document.createElement('div');
                tower.className = 'tower';
                tower.id = `tower${i}`;
                towers.appendChild(tower);
            }
            for (let i = n; i >= 1; i--) {
                const disk = document.createElement('div');
                disk.className = 'disk';
                disk.id = `disk${i}`;
                disk.style.width = `${20 + i * 20}px`;
                disk.style.bottom = `${(n - i) * 20}px`;
                document.getElementById('tower0').appendChild(disk);
            }
        }

        function moveDisk(from, to, callback) {
            const disks = document.getElementById(`tower${from}`).children;
            const disk = disks[disks.length - 1];
            document.getElementById(`tower${to}`).appendChild(disk);
            setTimeout(callback, 500);
        }

        function hanoiVisual(n, source, target, auxiliary, callback) {
            if (n === 0) return callback();
            hanoiVisual(n - 1, source, auxiliary, target, () => {
                moveDisk(source, target, () => {
                    hanoiVisual(n - 1, auxiliary, target, source, callback);
                });
            });
        }

        initTowers(3);
        hanoiVisual(3, 0, 2, 1, () => console.log('Done!'));
    </script>
</body>
</html>