ハノイの塔

Javaで解く。ポイントはコメントの通り

import java.util.Stack;

public class Hanoi {
    public static class Tower {
        final int n;
        final Stack<Disk> disks = new Stack<Disk>();

        public Tower(int n) {
            this.n = n;
        }

        @Override
        public String toString() {
            return "Tower" + n;
        }

        public void add(Disk d) {
            if (!disks.isEmpty() && disks.peek().size <= d.size) {
                throw new IllegalArgumentException(d + " is not placed on"
                        + disks.peek());
            }
            disks.push(d);
        }

        public void moveDisks(int i, Tower dest, Tower buf) {
            // bufを使って上からi番目までをdestへ移動
            if (i <= 0) {
                return;
            }

            // destを使ってi-1番目までをbufへ移動
            moveDisks(i - 1, buf, dest);
            // 残りをdestへ移動
            moveTopTo(dest);
            // bufのディスクを自身を使ってdestへ移動
            buf.moveDisks(i - 1, dest, this);
        }

        private void moveTopTo(Tower dest) {
            if (disks.isEmpty()) {
                throw new IllegalStateException("foo");
            }
            Disk top = disks.pop();
            dest.add(top);
            System.out.println("move " + top + " to " + dest);
        }
    }

    public static class Disk {
        final int size;

        public Disk(int size) {
            this.size = size;
        }

        @Override
        public String toString() {
            return "Disk" + size;
        }
    }

    public static void main(String[] args) {
        int n = 5;
        Tower[] towers = new Tower[3];
        for (int i = 0; i < 3; i++) {
            towers[i] = new Tower(i + 1);
        }
        for (int i = 0; i < n; i++) {
            towers[0].add(new Disk(n - i));
        }
        System.out.println("n = " + n);
        towers[0].moveDisks(n, towers[2], towers[1]);
    }
}

実行結果

n = 5
move Disk1 to Tower3
move Disk2 to Tower2
move Disk1 to Tower2
move Disk3 to Tower3
move Disk1 to Tower1
move Disk2 to Tower3
move Disk1 to Tower3
move Disk4 to Tower2
move Disk1 to Tower2
move Disk2 to Tower1
move Disk1 to Tower1
move Disk3 to Tower2
move Disk1 to Tower3
move Disk2 to Tower2
move Disk1 to Tower2
move Disk5 to Tower3
move Disk1 to Tower1
move Disk2 to Tower3
move Disk1 to Tower3
move Disk3 to Tower1
move Disk1 to Tower2
move Disk2 to Tower1
move Disk1 to Tower1
move Disk4 to Tower3
move Disk1 to Tower3
move Disk2 to Tower2
move Disk1 to Tower2
move Disk3 to Tower3
move Disk1 to Tower1
move Disk2 to Tower3
move Disk1 to Tower3