Tower of Hanoi Problem in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main goal of the Tower of Hanoi problem?

To move all disks from the source peg to the destination peg following the rules: only one disk can be moved at a time, and a larger disk cannot be placed on top of a smaller disk.

beginner

What are the three pegs called in the Tower of Hanoi problem?

Source peg (where disks start), Auxiliary peg (used for temporary storage), and Destination peg (where disks must be moved).

intermediate

Explain the recursive approach to solve the Tower of Hanoi problem.

Move n-1 disks from source to auxiliary peg, move the nth (largest) disk to destination peg, then move n-1 disks from auxiliary to destination peg recursively.

intermediate

What is the minimum number of moves required to solve the Tower of Hanoi problem with n disks?

The minimum number of moves is 2^n - 1, where n is the number of disks.

beginner

In C, what is the base case for the recursive Tower of Hanoi function?

When n (number of disks) is 1, move the disk directly from source to destination and return.

What is the first step in the recursive solution of Tower of Hanoi for n disks?

A Move n-1 disks from auxiliary to destination peg

B Move the largest disk from source to destination peg

C Move all disks directly to destination peg

D Move n-1 disks from source to auxiliary peg

The recursive solution starts by moving n-1 disks from the source peg to the auxiliary peg.

How many moves does it take to solve Tower of Hanoi with 3 disks?

A 7

B 5

C 9

D 3

Minimum moves = 2^3 - 1 = 7 moves.

Which peg is used as temporary storage in Tower of Hanoi?

A Source peg

B Destination peg

C Auxiliary peg

D None

The auxiliary peg is used as temporary storage to help move disks.

What condition must be followed when placing disks on pegs?

A Larger disk can be placed on smaller disk

B Only one disk can be moved at a time

C Smaller disk can be placed on larger disk

D Disks can be stacked in any order

Only one disk can be moved at a time, and a larger disk cannot be placed on a smaller disk.

What is the base case in the Tower of Hanoi recursive function?

A n = 1

B n = 2

C n = 0

D n = 3

When n = 1, move the disk directly and stop recursion.

Describe the steps to solve the Tower of Hanoi problem recursively for n disks.

Think about breaking the problem into smaller parts.

Explain why the minimum number of moves for Tower of Hanoi is 2^n - 1.

Consider how moves increase as disks increase.