---
title: ハノイの塔
tags: []
categories: ["Programming", "Algorithm", "TowerOfHanoi"]
date: 2012-04-10T17:22:32Z
updated: 2011-04-10T17:22:32Z
---

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