Larger disks cannot be placed on smaller sized discs.
Below is an illustration of how to solve the Tower of Hanoi problem with 3 discs.
The problem of Hanoi Tower (Tower of Hanoi) with disk number n can be solved with the minimum number of steps of 2 n −1
. Therefore, in the case of 3 discs, the Tower of Hanoi problem can be solved after 2 3 −1 = 7
steps.
To write an algorithm for the Tower of Hanoi math game, we first need to learn how to solve the problem with the number of disks of 1 and 2. We assign 3 columns with the following names:
cotNguon : the original column contains the disk
cotDich : column to move the disks to
CentralGian : intermediate columns have the purpose of mediating during disk movement
If there is only 1 disk, we only need to move from cotNguon to cotDich.
If there are 2 discs:
First we move the top disk (the smallest disk) to the MiddleGian.
Then we move the disk at the bottom (larger disk) to cotDich.
And finally move the smallest disk from the Chinese version to cotDich.
From these two algorithms, we will have an algorithm for the Tower of Hanoi problem for 3 or more discs. We divide the disk stack into two parts: the largest (the nth disk) is the first and (n-1) the other is the second.
Our goal is to move the nth disk from cotNguon to cotDich and then put all the remaining (n-1) disks on it. Now we can imagine how to solve the problem based on recursion according to the following steps:
Bước 1 : Di chuyển n-1 đĩa từ cotNguon tới cotTrungGian Bước 2 : Di chuyển đĩa thứ n từ cotNguon tới cotDich Bước 3 : Di chuyển n-1 đĩa từ cotTrungGian về cotDich
The recursive algorithm for the Tower of Hanoi problem is:
B ắ t đầ u gi ả i thu ậ t Th á p H à n ộ i Hanoi ( disk , cotNguon , cotDich , cotTrungGian ) IF disk == 0 , th ì di chuy ể n đĩ a t ừ cotNguon t ớ i cotDich ELSE Hanoi ( disk - 1 , cotNguon , cotTrungGian , cotDich ) // Bước 1 di chuy ể n đĩ a t ừ cotNguon t ớ i cotDich // Bước 2 Hanoi ( disk - 1 , cotTrungGian , cotDich , cotNguon ) // Bước 3 K ế t th ú c IF K ế t th ú c gi ả i thu ậ t
According to Tutorialspoint
Previous article: Basic concepts of recursion
Next lesson: Fibonacci sequence in data structure and algorithm