Korean, Edit

Hanoi Tower in C Language

Higher category : [C Language] C Language Index

1. Overview

2. Minimum Number of Moves

3. C Code

a. GitHub

1. Overview

⑴ Definition

The Hanoi Tower is a problem introduced by the French mathematician Lucas in 1883. It involves determining the minimum number of moves required to move n disks.

⑵ Legend

In a temple in Benares, India, there is a large dome that represents the center of the world. Inside the dome, three diamond needles are engraved on a bronze plate. The height of the needle is one cubit, and its thickness is no more than the body of a star. One of the needles is adorned with 64 golden disks. The largest disk is placed at the bottom, and the remaining disks are stacked smaller and smaller up to the top. This is the sacred Tower of Brahma. Following Brahma’s instructions, the monks climbed the altar day and night, moving the disks one by one to another needle according to the rules. It is said that when this task is completed, the tower will collapse and the world will come to an end.

2. Minimum Number of Moves

⑴ Overview

For example, if there are only two disks and you want to move them from pillar A to pillar C, you can move them as follows: A → B, A → C, B → C. Mathematicians have made various attempts to solve this problem and have found that the minimum number of moves is 2ⁿ-1.

⑵ Recursive relation

① Recursive formula: a_n+1 = 2a_n + 1

② Diagram to aid understanding the recursive formula

3. C Code

#include <stdio.h>
#include <stdlib.h>
/* This is an algorithm to solve the Hanoi Tower problem */
// Step 1. transfer (n-1)-th floor pyramid to other blank(A or B)
// Step 2. transfer the largest disk to C
// Step 3. repeat step 1 and step 2 (n is getting smaller)

void Hanoi(int n, char A, char B, char C){
	if(n == 1) printf("%c → %c\n", A, C);
	else{
		Hanoi(n-1, A, C, B);
		printf("%c → %c\n", A, C);
		Hanoi(n-1, B, A, C);
	}
}

int main(int argc, char *argv[]) {
	int n;
	scanf("%d", &n);
	Hanoi(n, 'A', 'B', 'C');
	return 0;
}

Input: 2016.02.08 19:39

Modified: 2022.09.08 13:24