최고 엔지니어의 꿈을 향해서

Hanoi Tower Problem

2008.11.15 19:04 : 분류없음

///////////////////////////////////////////////////////////////////////
public class Frame {
    private int n;
    private String from, to, spare;

    public Frame (int n, String from, String to, String spare) {
        this.n = n;
        this.from = from;
        this.to = to;
        this.spare = spare;
    }

    public int getN () { return n; }
   
    public String getFrom () { return from; }

    public String getTo () { return to; }

    public String getSpare () { return spare; }
}

///////////////////////////////////////////////////////////////////////
/////////////////////////////Hanoi Version 1///////////////////////////
// 하노이 버젼에서는 레지스터라이징을 사용하지 않았기 때문에, 함수 호출시 스택을 넘겨준다.
// 버젼 1은 여전히 재귀 함수를 쓰고는 있지만, 잘보면 Tail recursion or Tail call이다.
// 이것을 version2에서는 iteration버젼으로 바꾸었다.

import java.util.Stack;

public class Hanoi {

    public static void main (String[] args) {
        move(3,"start","end","spare");
    }

    public static void move (int n, String from, String to, String spare) {
        moveCps(n, from, to, spare, new Stack<Frame>());
    }

    public static void moveCps (int n, String from, String to, String spare, Stack<Frame> k) {
        while (n > 0) {
            Frame f = new Frame(n,from,to,spare);
            n = n-1;
            String temp = to;
            to = spare;
            spare = temp;
            k.push(f);
        }
        applyK(k);
    }

    public static void applyK (Stack<Frame> k) {
        if (k.empty()) return;
       
        Frame f = k.pop();
        System.out.printf("move from %s to %s%n", f.getFrom(), f.getTo());
        moveCps(f.getN()-1, f.getSpare(), f.getTo(), f.getFrom(), k);
    }
   
}
///////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

import java.util.Stack;

public class Hanoi2 {

    public static void main (String[] args) {
        move(4,"start","end","spare");
    }

    public static void move (int n, String from, String to, String spare) {
        moveCps(n, from, to, spare, new Stack<Frame>());
    }

    public static void moveCps (int n, String from, String to, String spare, Stack<Frame> k) {
        while (n > 0 || !k.empty()) {
            if (n > 0) {
                Frame f = new Frame(n,from,to,spare);
                n = n-1;
                String temp = to;
                to = spare;
                spare = temp;
                k.push(f);
            }
            else {
                Frame f = k.pop();
                System.out.printf("move from %s to %s%n", f.getFrom(), f.getTo());
                n = f.getN() - 1;
                from = f.getSpare();
                to = f.getTo();
                spare = f.getFrom();
            }
        }
    }

}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
아시다 시피, 위의 코드는 밑에 글에서 설명한데로 Scheme 코드를 거쳐 CPS한 후에 탄생되었다.
근데 내가 Hanoi scheme코드를 side effect있는 버젼(including printf(....))으로 시작했기 때문에, 결과값을 자료구조에 저장안하고, 걍 중간 중간 출력하는것을 볼수 있다...

Posted by 정해권 Trackback 0 Comment 0


티스토리 툴바