C The Tower of Hanoi Program
The Tower of Hanoi is a classic problem in computer science and mathematics that demonstrates recursion. It involves moving a stack of disks from one peg to another, following specific rules. The problem consists of three pegs and a number of disks of different sizes that can slide onto any peg. The challenge is to move the entire stack to another peg, adhering to the following rules:
- Only one disk can be moved at a time.
- 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.
- No disk may be placed on top of a smaller disk.
Recursive Approach to the Tower of Hanoi
The recursive approach to solving the Tower of Hanoi problem involves the following steps:
- Move the top disks from the source peg to the auxiliary peg.
- Move the nth disk from the source peg to the destination peg.
- Move the disks from the auxiliary peg to the destination peg.
Implementation of Tower of Hanoi in C
Here's a simple implementation of the Tower of Hanoi program in C:
Explanation of the Program
Header Files:
#include <stdio.h>
: This header file is included for standard input and output functions.
Function Declaration:
void towerOfHanoi(int n, char source, char destination, char auxiliary)
: This function takes the number of disks (n
) and the names of the source, destination, and auxiliary pegs as arguments.
Base Case:
- The base case checks if there is only one disk (
n == 1
). If so, it moves that disk from the source peg to the destination peg and returns.
- The base case checks if there is only one disk (
Recursive Steps:
- The function first moves disks from the source peg to the auxiliary peg using the destination peg as an intermediary.
- Next, it moves the nth disk from the source peg to the destination peg.
- Finally, it moves the disks from the auxiliary peg to the destination peg, using the source peg as an auxiliary.
Main Function:
- The program starts by prompting the user to enter the number of disks.
- It uses
scanf()
to read the input value.
Calling the Function:
- The
towerOfHanoi()
function is called with the user-defined number of disks and the names of the pegs (A for source, C for destination, and B for auxiliary).
- The
How to Run the Program
Compile the Code: Use a C compiler like
gcc
to compile the code.Execute the Program:
Input Data: Enter the number of disks when prompted.
Example Input/Output
Input:
Output:
Conclusion
The Tower of Hanoi program in C illustrates the use of recursion to solve a classic problem. It effectively demonstrates how a complex problem can be broken down into simpler subproblems, each of which can be solved using the same approach. This recursive technique is a fundamental concept in computer science and is widely applicable to various problems.