cc 150: 스 택 을 사용 하여 한 노 타 를 실현 합 니 다.

재 귀적 해법 도 스 택 에 사 용 된 것 으로 재 귀적 으로 자신 을 호출 할 때마다 중간 상태 파 라 메 터 를 스 택 에 누 릅 니 다.그러나 이런 조작 은 모두 시스템 암시 적 으로 진행 되 기 때문에 너 는 그것 이 구체 적 으로 어떻게 창고 에서 나 오 는 지 에 관심 을 가 질 필요 가 없다.만약 우리 가 창고 자신 으로 이 과정 을 실현 하려 고 한다 면, 그 중의 세부 사항 을 고려 해 야 한다.
      그 다음 에 우 리 는 스 택 으로 재 귀 과정 에서 이런 상태 매개 변수 들 의 스 택 출 고 과정 을 명시 적 으로 실현 할 것 이다.우선, 우 리 는 작업 과정 에서 의 인 자 를 저장 하기 위해 데이터 구 조 를 정의 해 야 한다.

struct op{
    int begin, end;
    char src, bri, dst;
    op(){

    }
    op(int pbegin, int pend, int psrc, int pbri, int pdst):begin(pbegin), end(pend), src(psrc), bri(pbri), dst(pdst){

    }
};

     그 중에서 5 개의 매개 변 수 는 기둥 src 에 원반 이 있 고 레이 블 은 begin 에서 end 까지 src 에서 dst 로 이동 하 며 중간 에 기둥 bri 를 빌 릴 수 있 음 을 나타 낸다.end 는 재 귀 해법 중의 n, src, bri, dst 와 재 귀 해법 중의 대응 에 해당 한다.그런데 왜 begin 이라는 변 수 를 정의 해 야 합 니까?기둥 에 접시 가 하나 밖 에 남지 않 았 는 지 판단 하기 위해 서다.begin 이 end 와 같다 면 기둥 에 '마지막' 원반 만 남아 이동 할 수 있다 는 뜻 이다.물론 다른 불 변수 로 원반 만 남 았 는 지 여 부 를 표시 하 는 것 도 효과 가 같다.재 귀 방법 을 말 할 때 초기 상태 에서 최종 상태 까지 모두 다음 과 같은 몇 가지 상 태 를 거 쳐 야 한다 고 말 했다.

(1~n, 0, 0)
(n, 1~n-1, 0)
(0, 1~n-1, n)
(0, 0, 1~n)

    이 과정 들 은 우리 가 지금 스스로 창고 에서 출고 하여 처리 해 야 한다.창고 에 쌓 일 때 는 처리 하지 않 고, 창고 에서 나 갈 때 처리 하 다.따라서 스 택 을 쌓 을 때 는 실제 작업 해 야 할 절차 와 반대 되 어야 한다.처음에 우 리 는 최종 적 으로 완성 하고 자 하 는 임 무 를 보류 할 것 이다.이상 하 게 들 리 는데 사실은 스 택 에 매개 변 수 를 누 르 는 것 입 니 다.

stack<op> st;
st.push(op(1, n, src, bri, dst));

    이 매개 변 수 는 기둥 src 에 1 ~ n 개의 원반 이 있 으 며, dst 로 이동 하려 면 기둥 bri 를 빌 릴 수 있 음 을 나타 낸다.스 택 st 가 비어 있 지 않 을 때 스 택 에서 계속 나 옵 니 다. begin 과 end 가 같 지 않 을 때 세 개의 push 작업 (위의 네 가지 상태 에 대응 하고 인접 상 태 는 하나의 push 작업 에 대응 하여 상 태 를 변화 시 킵 니 다) 을 합 니 다. push 는 실제 작업 순서 와 반대 되 기 때문에 스 택 에서 나 올 때 순서 가 정확 합 니 다). 만약 에 begin 과 end 가 같 으 면 현재 문제 규모 의 '마지막' 이 남 습 니 다.이동 방안 을 직접 인쇄 하 는 원반 입 니 다. hanoi 코드 는 다음 과 같 습 니 다.

void hanoi(int n, char src, char bri, char dst){
    stack<op> st;
    op tmp;
    st.push(op(1, n, src, bri, dst));
    while(!st.empty()){
        tmp = st.top();
        st.pop();
        if(tmp.begin != tmp.end){
            st.push(op(tmp.begin, tmp.end-1, tmp.bri, tmp.src, tmp.dst));
            st.push(op(tmp.end, tmp.end, tmp.src, tmp.bri, tmp.dst));
            st.push(op(tmp.begin, tmp.end-1, tmp.src, tmp.dst, tmp.bri));
        }
        else{
            cout<<"Move disk "<<tmp.begin<<" from "<<tmp.src<<" to "<<tmp.dst<<endl;
        }

    }
}