PTA_데이터 구조 와 알고리즘7 - 17 한 노 타의 비 귀속 실현 (25 점)

스 택 을 통 해 한 노 타 워 의 문제 (n, a, b, c) 를 비 재 귀 (순환) 방식 으로 풀 고 N 개의 접 시 를 시작 기둥 (a 로 표시) 에서 기둥 (b 로 표시) 을 통 해 목표 기둥 (c 로 표시) 으로 이동 시 키 며 모든 이동 이 한 노 타 문제 의 요구 에 부합 하도록 확보한다.
입력 형식: 시작 기둥 의 디스크 수 를 정수 N 으로 입력 하 십시오.
출력 형식: 모든 작업 (이동) 이 한 줄 을 차지 하고 1 -> 2 의 형식 으로 출력 합 니 다.
입력 예시:

3

출력 예시:

a -> c
a -> b
c -> b
a -> c
b -> a
b -> c
a -> c

코드:

#include
#define MaxSize 100

typedef struct{//         
    int N;//  
    char A;//   
    char B;//   
    char C;//   
} ElementType;
typedef struct{//      
    ElementType Data[MaxSize];
    int Top;
}Stack;
void Push(Stack *PtrS, ElementType item);//  
ElementType Pop(Stack *PtrS);//  
void Hanoi(int n);//       

int main()
{
    int n;
    scanf("%d",&n);
    Hanoi(n);
    return 0;
}

void Hanoi(int n){
    ElementType P, toPush;//P            （       ）,toPush         （N-1 1，  N-1     ）
    Stack S;
    P.N = n; P.A = 'a'; P.B = 'b'; P.C = 'c';
    S.Top = -1;
    Push(&S, P);
    while(S.Top!=-1){
        P = Pop(&S);//        ，        ，        1     
        if(P.N==1) printf("%c -> %c
",P.A, P.C);//N 1         
        else{
            toPush.N = P.N - 1;
            toPush.A = P.B; toPush.B = P.A; toPush.C = P.C;//   2： N-1             
            Push(&S, toPush);//   2  
            toPush.N = 1;
            toPush.A = P.A; toPush.B = P.B; toPush.C = P.C;//   1      
            Push(&S, toPush);//           
            toPush.N = P.N - 1;
            toPush.A = P.A; toPush.B = P.C; toPush.C = P.B;//   1： N-1             
            Push(&S, toPush);//   1  
        }
    }
}

void Push(Stack *PtrS, ElementType item){
    PtrS->Data[++(PtrS->Top)] = item;
    return;
}
ElementType Pop(Stack *PtrS){
    PtrS->Top--;
    return(PtrS->Data[PtrS->Top+1]);
}