LearnFrenzy
Sign in Take a free test

Functions and Default Arguments · Function Programs · Question 8

Tower of Hanoi: count and list the moves in C++ Solution, output & explanation

  • Program
  • Medium
  • 0 comments
  • Answer explained
  • Moderated community
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
main.cpp
#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;
}

Output Verified by compiling and running

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!

Post your comment

Comments appear after a quick review by our team.

Search LearnFrenzy

Esc

Quick links