Modeling the maximum number of moves in Tower of Hanoi problem. What would be the recursive algorithm for solving the Tower of Hanoi problem (with n disks and 3 pegs) in maximal number of moves (i.e. going through all possible disks/pegs combinations).

Kayley Dickson

Kayley Dickson

Answered question

2022-11-06

Modeling the maximum number of moves in Tower of Hanoi problem
What would be the recursive algorithm for solving the Tower of Hanoi problem (with n disks and 3 pegs) in maximal number of moves (i.e. going through all possible disks/pegs combinations).

Answer & Explanation

smeachtaczm

smeachtaczm

Beginner2022-11-07Added 14 answers

Step 1
In the initial position there are three towers, that I will call A,B,C, and assume the problem we want to solve recursively is:
Problem: Move all disks located in tower X to tower Y (for X , Y { A , B , C } and X Y).
The recursive solution is as follows:
- For n = 1 disks: move the disk from X to Y.
- For n = k + 1 disks:
1. Use the solution for k disks to move the first k disks from tower X to the tower Z, namely the only tower in the set {A,B,C}∖{X,Y}.
2. Move the ( k + 1 )-th disk to tower Y.
3. Use the solution for k disks to move the first k disks from tower Z to tower Y.
With this, the number of moves is recursively defined as:
{ M 1 = 1 M k + 1 = 2 M k + 1
which have the following general formula:
M n = 1 + 2 + + 2 n 1 = 2 n 1

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?