Question 8
Back to Exercise
Read the number of disks and solve the Tower of Hanoi recursively, printing only the total number of moves and the first five moves.
Solution
#include <iostream>
long long moves = 0;
void hanoi(int n, char from, char to, char via) {
if (n == 0) return;
hanoi(n - 1, from, via, to);
if (++moves <= 5) std::cout << "move " << moves << ": disk " << n << ' ' << from << "->" << to << '\n';
hanoi(n - 1, via, to, from);
}
int main() {
int n;
std::cin >> n;
hanoi(n, 'A', 'C', 'B');
std::cout << "total moves: " << moves << '\n';
return 0;
}
move 1: disk 1 A->B move 2: disk 2 A->C move 3: disk 1 B->C move 4: disk 3 A->B move 5: disk 1 C->A total moves: 15
The solution always takes 2n − 1 moves (15 for 4 disks). For an even number of disks the smallest disk first moves to the spare peg.
Discussion & Comments 0
Share your method, a shortcut, or ask about a step you didn't follow.
No comments yet. Be the first to share your solution!