하노이 타워는 수학 퍼즐입니다. 이 퍼즐에서는 모든 디스크를로드 / 폴 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
암호알고리즘
하노이 타워 문제의 알고리즘 부분으로 이동합니다.
- 디스크 수를 나타내는 정수 n을 초기화합니다.
- 소스, 대상 및 보조에 대해 3 개의 스택을 만듭니다. 마찬가지로 3 개의 변수를 'A'로, d를 'B'로, a를 'C'로 만듭니다.
- mod 2의 디스크 수가 0인지 확인하고 d를 임시 변수에 저장합니다. 그 후 d를 a로 업데이트하고 a를 임시 변수로 업데이트하십시오.
- 먼저 총 이동 횟수에 대한 변수를 만들고 (n * n) -1로 업데이트합니다.
- n에서 1로 이동하고 소스 스택의 현재 값을 푸시합니다.
- 1에서 총 이동으로 이동하고 현재 인덱스 모드 3이 1인지 확인하고 소스 및 대상 스택에서 상단을 팝합니다. 소스 스택의 팝된 상단이 INT_MIN과 같으면 팝된 대상의 상단을 소스로 푸시합니다.
- Else 대상 스택의 팝된 상단이 INT_MIN과 같으면 팝된 소스 스택의 상단을 대상 스택으로 푸시합니다.
- Else 소스 스택의 팝업 된 상단이 대상 스택의 팝업 된 상단보다 큰 경우 소스 스택의 상단을 모두 푸시하고 그렇지 않으면 대상 스택의 상단을 모두 푸시합니다. 그 후 순회를 인쇄하십시오.
- 마찬가지로 현재 인덱스 모드 3이 2인지 확인하고 소스 및 보조 스택에서 상단을 팝합니다. 소스 스택의 팝된 상단이 INT_MIN과 같으면 보조 스택의 팝된 상단을 소스 스택으로 푸시합니다.
- Else 보조 스택의 팝된 상단이 INT_MIN과 같으면 팝된 소스 스택의 상단을 보조 스택으로 푸시합니다.
- 그렇지 않으면 소스 스택의 튀어 나온 상단이 보조 스택의 튀어 나온 상단보다 크면 소스 스택의 두 상단을 모두 밀고 그렇지 않으면 보조 스택의 양쪽을 모두 밉니다. 그 후 순회를 인쇄하십시오.
- 마찬가지로 현재 인덱스 mod 3이 0인지 확인하고 보조 및 대상 스택에서 맨 위를 팝합니다. 보조 스택의 팝된 상단이 INT_MIN과 같으면 대상 스택의 팝된 상단을 보조 스택으로 푸시합니다.
- Else 대상 스택의 팝된 상단이 INT_MIN과 같으면 보조 스택의 팝된 상단을 대상 스택으로 푸시합니다.
- 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) 스택 공간을 사용했기 때문입니다.
참조 하노이 타워 구현을위한 반복적 인 방법.
