Java Program to Solve the Tower of Hanoi Problem

Отвечено с помощью: GPT-4o-mini отJava Q&A Hub

Вопрос:

Write a Java program for solving the Tower of Hanoi Problem.

Ответ:

Certainly! The Tower of Hanoi is a classic problem in computer science and mathematics. The objective is to move a stack of disks from one peg to another, following these rules:

  1. Only one disk can be moved at a time.
  2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty peg.
  3. No larger disk may be placed on top of a smaller disk.

Here is a simple Java program that solves the Tower of Hanoi problem using recursion:

public class TowerOfHanoi {

    // Recursive function to solve Tower of Hanoi
    public static void solveTowerOfHanoi(int n, char source, char target, char auxiliary) {
        // Base case: If there is only one disk, move it from source to target
        if (n == 1) {
            System.out.println("Move disk 1 from " + source + " to " + target);
            return;
        }
        
        // Move n-1 disks from source to auxiliary, using target as a temporary peg
        solveTowerOfHanoi(n - 1, source, auxiliary, target);
        
        // Move the nth disk from source to target
        System.out.println("Move disk " + n + " from " + source + " to " + target);
        
        // Move the n-1 disks from auxiliary to target, using source as a temporary peg
        solveTowerOfHanoi(n - 1, auxiliary, target, source);
    }

    public static void main(String[] args) {
        int numberOfDisks = 3; // You can change this value to test with different numbers of disks
        System.out.println("The sequence of moves involved in the Tower of Hanoi are:");
        solveTowerOfHanoi(numberOfDisks, 'A', 'C', 'B'); // A, B and C are names of rods
    }
}

Explanation:

  • The solveTowerOfHanoi method is a recursive function that takes four parameters:

    • n: the number of disks.
    • source: the peg from which disks are to be moved.
    • target: the peg to which disks are to be moved.
    • auxiliary: the peg used as a temporary holding area.
  • The base case of the recursion is when there is only one disk (n == 1), in which case it simply moves the disk from the source peg to the target peg.

  • For more than one disk, the function first moves n-1 disks from the source peg to the auxiliary peg, then moves the nth disk directly to the target peg, and finally moves the n-1 disks from the auxiliary peg to the target peg.

How to Run:

  1. Copy the code into a file named TowerOfHanoi.java.
  2. Compile the program using javac TowerOfHanoi.java.
  3. Run the program using java TowerOfHanoi.

You can change the value of numberOfDisks in the main method to test the solution with different numbers of disks.