반복적 인 하노이 타워


난이도 중급
자주 묻는 질문 MAQ
분열과 정복 스택

하노이 타워는 수학 퍼즐입니다. 이 퍼즐에서는 모든 디스크를로드 / 폴 A에서로드 / 폴 B로로드 / 폴 C를 사용하여 이동해야합니다. 디스크는 다음 위치에 배치되어야합니다. 오름차순 즉 상단에 가장 작은 것입니다. 한 극에서 다른 극으로 디스크를 전송하는 것은 두 가지 조건에서 작동합니다.

  • 여러 디스크의 전송은 허용되지 않습니다. 즉, 한 번에 하나의 디스크 만 이동할 수 있습니다.
  • 더 큰 디스크는 폴의 작은 디스크 위에 놓을 수 없습니다.

예를 들어 –

반복적 인 하노이 타워

하노이 타워 문제에서 우리는 1에서 n까지 크기의 디스크를 나타내는 디스크 수를 제공했습니다. 모든 단계를 인쇄하여 디스크를 시작 극에서 대상 극으로 이동합니다.

3
Move the disk 1 from A to B
Move the disk 2 from A to C
Move the disk 1 from B to C
Move the disk 3 from A to B
Move the disk 1 from C to A
Move the disk 2 from C to B
Move the disk 1 from A to B
1
Move the disk 1 from A to B

암호알고리즘

하노이 타워 문제의 알고리즘 부분으로 이동합니다.

  1. 디스크 수를 나타내는 정수 n을 초기화합니다.
  2. 소스, 대상 및 보조에 대해 3 개의 스택을 만듭니다. 마찬가지로 3 개의 변수를 'A'로, d를 'B'로, a를 'C'로 만듭니다.
  3. mod 2의 디스크 수가 0인지 확인하고 d를 임시 변수에 저장합니다. 그 후 d를 a로 업데이트하고 a를 임시 변수로 업데이트하십시오.
  4. 먼저 총 이동 횟수에 대한 변수를 만들고 (n * n) -1로 업데이트합니다.
  5. n에서 1로 이동하고 소스 스택의 현재 값을 푸시합니다.
  6. 1에서 총 이동으로 이동하고 현재 인덱스 모드 3이 1인지 확인하고 소스 및 대상 스택에서 상단을 팝합니다. 소스 스택의 팝된 상단이 INT_MIN과 같으면 팝된 대상의 상단을 소스로 푸시합니다.
  7. Else 대상 스택의 팝된 상단이 INT_MIN과 같으면 팝된 소스 스택의 상단을 대상 스택으로 푸시합니다.
  8. Else 소스 스택의 팝업 된 상단이 대상 스택의 팝업 된 상단보다 큰 경우 소스 스택의 상단을 모두 푸시하고 그렇지 않으면 대상 스택의 상단을 모두 푸시합니다. 그 후 순회를 인쇄하십시오.
  9. 마찬가지로 현재 인덱스 모드 3이 2인지 확인하고 소스 및 보조 스택에서 상단을 팝합니다. 소스 스택의 팝된 상단이 INT_MIN과 같으면 보조 스택의 팝된 상단을 소스 스택으로 푸시합니다.
  10. Else 보조 스택의 팝된 상단이 INT_MIN과 같으면 팝된 소스 스택의 상단을 보조 스택으로 푸시합니다.
  11. 그렇지 않으면 소스 스택의 튀어 나온 상단이 보조 스택의 튀어 나온 상단보다 크면 소스 스택의 두 상단을 모두 밀고 그렇지 않으면 보조 스택의 양쪽을 모두 밉니다. 그 후 순회를 인쇄하십시오.
  12. 마찬가지로 현재 인덱스 mod 3이 0인지 확인하고 보조 및 대상 스택에서 맨 위를 팝합니다. 보조 스택의 팝된 상단이 INT_MIN과 같으면 대상 스택의 팝된 상단을 보조 스택으로 푸시합니다.
  13. Else 대상 스택의 팝된 상단이 INT_MIN과 같으면 보조 스택의 팝된 상단을 대상 스택으로 푸시합니다.
  14. Else 보조 스택의 튀어 나온 상단이 대상 스택의 튀어 나온 상단보다 크면 보조 스택의 상단을 모두 밀고 그렇지 않으면 대상 스택에서 두 개를 모두 밉니다. 그 후 순회를 인쇄하십시오.

반복적 인 하노이 타워를위한 C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;

struct Stack{  
    unsigned capacity;  
    int top;  
    int *array;  
};  
  
struct Stack* createStack(unsigned capacity){  
    struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));  
    stack -> capacity = capacity;  
    stack -> top = -1;  
    stack -> array = (int*) malloc(stack -> capacity * sizeof(int));  
    return stack;  
}  
  
int isFull(struct Stack* stack){  
    return (stack->top == stack->capacity - 1);  
}  
  
int isEmpty(struct Stack* stack){  
    return (stack->top == -1);  
}  
  
void push(struct Stack *stack, int item){  
    if(isFull(stack)){  
        return;  
    }    
    stack -> array[++stack -> top] = item;  
}  
  
int pop(struct Stack* stack){  
    if(isEmpty(stack)){  
        return INT_MIN; 
    }    
    return stack -> array[stack -> top--];  
}  
  
void moveDisk(char fromPeg, char toPeg, int disk){  
    cout<<"Move the disk "<<disk<<" from "<<fromPeg<<" to "<<toPeg<<endl;  
} 
  
void moveDisksBetweenTwoPoles(struct Stack *src, struct Stack *dest, char s, char d)  
{  
    int pole1TopDisk = pop(src);  
    int pole2TopDisk = pop(dest);  
  
    if (pole1TopDisk == INT_MIN){  
        push(src, pole2TopDisk);  
        moveDisk(d, s, pole2TopDisk);  
    }  
  
    else if(pole2TopDisk == INT_MIN){  
        push(dest, pole1TopDisk);  
        moveDisk(s, d, pole1TopDisk);  
    }  
  
    else if(pole1TopDisk > pole2TopDisk){  
        push(src, pole1TopDisk);  
        push(src, pole2TopDisk);  
        moveDisk(d, s, pole2TopDisk);  
    }  
  
    else{  
        push(dest, pole2TopDisk);  
        push(dest, pole1TopDisk);  
        moveDisk(s, d, pole1TopDisk);  
    }  
}  
  
void TowerOfHanoi(int num_of_disks, struct Stack *src, struct Stack *aux, struct Stack *dest){  
    int i, total_num_of_moves;  
    char s = 'A', d = 'B', a = 'C';  
  
    if(num_of_disks % 2 == 0){  
        char temp = d;  
        d = a;  
        a = temp;  
    }  
    total_num_of_moves = pow(2, num_of_disks) - 1;  
  
    for(i = num_of_disks; i >= 1; i--){  
        push(src, i);  
    }    
  
    for(i = 1; i <= total_num_of_moves; i++){  
        if(i % 3 == 1){  
            moveDisksBetweenTwoPoles(src, dest, s, d); 
        }
  
        else if(i % 3 == 2){  
            moveDisksBetweenTwoPoles(src, aux, s, a);
        }
  
        else if(i % 3 == 0){  
            moveDisksBetweenTwoPoles(aux, dest, a, d);  
        }
    }  
}  
  
int main(){  
    
    unsigned n = 3;  
  
    struct Stack *source, *destination, *auxiliary;  
  
    source = createStack(n);  
    auxiliary = createStack(n);  
    destination = createStack(n);  
  
    TowerOfHanoi(n, source, auxiliary, destination); 
    
    return 0;  
}
Move the disk 1 from A to B
Move the disk 2 from A to C
Move the disk 1 from B to C
Move the disk 3 from A to B
Move the disk 1 from C to A
Move the disk 2 from C to B
Move the disk 1 from A to B

반복적 인 하노이 타워를위한 자바 프로그램

class Iterative_TOH{ 
    
    class Stack{ 
        int capacity; 
        int top; 
        int array[]; 
    } 
      
    Stack createStack(int capacity){ 
        Stack stack=new Stack(); 
        stack.capacity = capacity; 
        stack.top = -1; 
        stack.array = new int[capacity]; 
        return stack; 
    } 
      
    boolean isFull(Stack stack){ 
        return (stack.top == stack.capacity - 1); 
    } 
      
    boolean isEmpty(Stack stack){ 
        return (stack.top == -1); 
    } 
      
    void push(Stack stack,int item){ 
        if(isFull(stack)){
            return; 
        }    
        stack.array[++stack.top] = item; 
    } 
      
    int pop(Stack stack){ 
        if(isEmpty(stack)) {
            return Integer.MIN_VALUE; 
        }    
        return stack.array[stack.top--]; 
    } 
      
    void moveDisksBetweenTwoPoles(Stack src, Stack dest, char s, char d){ 
        int pole1TopDisk = pop(src); 
        int pole2TopDisk = pop(dest); 
  
        if (pole1TopDisk == Integer.MIN_VALUE){ 
            push(src, pole2TopDisk); 
            moveDisk(d, s, pole2TopDisk); 
        } 
        else if (pole2TopDisk == Integer.MIN_VALUE){ 
            push(dest, pole1TopDisk); 
            moveDisk(s, d, pole1TopDisk); 
        } 
        else if (pole1TopDisk > pole2TopDisk){ 
            push(src, pole1TopDisk); 
            push(src, pole2TopDisk); 
            moveDisk(d, s, pole2TopDisk); 
        } 
        else{ 
            push(dest, pole2TopDisk); 
            push(dest, pole1TopDisk); 
            moveDisk(s, d, pole1TopDisk); 
        } 
    } 
      
    void moveDisk(char fromPeg, char toPeg, int disk){ 
        System.out.println("Move the disk "+disk + " from "+fromPeg+" to "+toPeg); 
    } 
      
    void TowerOfHanoi(int num_of_disks, Stack src, Stack aux, Stack dest){ 
        int i, total_num_of_moves; 
        char s = 'A', d = 'B', a = 'C'; 
       
        if(num_of_disks % 2 == 0){ 
            char temp = d; 
            d = a; 
            a  = temp; 
        } 
        total_num_of_moves = (int) (Math.pow(2, num_of_disks) - 1); 
       
        for(i = num_of_disks; i >= 1; i--){ 
            push(src, i); 
        }
       
        for(i = 1; i <= total_num_of_moves; i++){ 
            if (i % 3 == 1){ 
                moveDisksBetweenTwoPoles(src, dest, s, d); 
            }
       
            else if(i % 3 == 2){ 
                moveDisksBetweenTwoPoles(src, aux, s, a); 
            }
            
            else if(i % 3 == 0){ 
                moveDisksBetweenTwoPoles(aux, dest, a, d);
            }    
        } 
    } 
      
    public static void main(String[] args){ 
          
        int n = 3; 
          
        Iterative_TOH ob = new Iterative_TOH(); 
        Stack source, destination, auxiliary; 
          
        source = ob.createStack(n); 
        destination = ob.createStack(n); 
        auxiliary = ob.createStack(n); 
          
        ob.TowerOfHanoi(n, source, auxiliary, destination); 
    } 
}
Move the disk 1 from A to B 
Move the disk 2 from A to C 
Move the disk 1 from B to C 
Move the disk 3 from A to B
Move the disk 1 from C to A 
Move the disk 2 from C to B 
Move the disk 1 from A to B

반복적 인 하노이 타워의 복잡성 분석

시간 복잡성 : O (2n) 여기서 n은 하노이 타워 문제의 디스크 수입니다.

보조 공간 : O (n) 스택 공간을 사용했기 때문입니다.

참조 하노이 타워 구현을위한 반복적 인 방법.