Towers of Hanoi using Recursion Multiple choice Questions and Answers (MCQs)
Click on any option to know the CORRECT ANSWERS
What is the objective of tower of hanoi puzzle?
To move all disks to some other rod by following rules
To divide the disks equally among the three rods by following rules
To move all disks to some other rod in random order
To divide the disks equally among three rods in random order
Question 1 Explanation:
Objective of tower of hanoi problem is to move all disks to some other rod by following the following rules-1) Only one disk can be moved at a time. 2) Disk can only be moved if it is the uppermost disk of the stack. 3) No disk should be placed over a smaller disk.
Which of the following is NOT a rule of tower of hanoi puzzle?
No disk should be placed over a smaller disk
Disk can only be moved if it is the uppermost disk of the stack
No disk should be placed over a larger disk
Only one disk can be moved at a time
Question 2 Explanation:
The rule is to not put a disk over a smaller one. Putting a smaller disk over larger one is allowed.
The time complexity of the solution tower of hanoi problem using recursion is .....
O(n log n)
Question 3 Explanation:
Time complexity of the problem can be found out by solving the recurrence relation: T(n)=2T(n-1)+c. Result of this relation is found to be equal to 2n. It can be solved using substitution.
Recurrence equation formed for the tower of hanoi problem is given by .....
T(n) = 2T(n-1)+n
T(n) = 2T(n/2)+c
T(n) = 2T(n-1)+c
T(n) = 2T(n/2)+n
Question 4 Explanation:
As there are 2 recursive calls to n-1 disks and one constant time operation so the recurrence relation will be given by T(n) = 2T(n-1)+c.
Minimum number of moves required to solve a tower of hanoi problem with n disks is .....
Question 5 Explanation:
Minimum number of moves can be calculated by solving the recurrence relation - T(n)=2T(n-1)+c. Alternatively we can observe the pattern formed by the series of number of moves 1, 3, 7, 15.....Either way it turn out to be equal to 2n-1.
There are 5 questions to complete.