Q:

Python program for Tower of Hanoi

belongs to collection: Python basic programs

mahmoud2506
Save to bookmark
|
2022-05-19
|
  300 
0

The problem is looking easy but it's not. The way we are going to tackle it is recursion. The problem is simple when you see it from recursion perspective.

Key: The number of steps required to shift the stack is exactly equal to the twice of steps for shifting the stack of one less disk(The largest one) plus one step.

    Consider the case of shifting one disk : T(1) = 1
    Consider the case of shifting two disk : T(2) = 2*T(1) + 1 = 3
    Consider the case of shifting three disk : T(3) = 2*T(2) + 1 = 7
    .
    .
    .
    . 
    T(n) = 2*T(n-1) + 1
Python programming, examples, Python programming examples,
login and add your own answer to this question

All Answers

mahmoud2506
2022-05-19
need an explanation for this answer? contact us directly to get an explanation for this answer

So here is the code:

def hanoi(x):
    if x == 1:
        return 1
    else:
        return 2*hanoi(x-1) + 1

x = int(input("ENTER THE NUMBER OF DISKS: "))

print('NUMBER OF STEPS: ', hanoi(x))

Output:

ENTER THE NUMBER OF DISKS: 5
NUMBER OF STEPS:  31

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

Python basic programs
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
Python program to find standard deviation... >>
<< Python program to find winner of the day...