Data Structures 08 - Tower of Hanoi

Code

#include <stdio.h>

/**
 * Tower of Hanoi problem function.
 * @param paraN Number of disks
 * @param paraSource Starting peg
 * @param paraDestination Destination peg
 * @param paraTransit Transit peg
 */
void hanoi(int paraN, char paraSource, char paraDestination, char paraTransit) {
    // If there are no disks, do nothing
	if (paraN <= 0) {
		return;
	} else {
        // Move the top n-1 disks to the transit peg
		hanoi(paraN - 1, paraSource, paraTransit, paraDestination);
        // Move the remaining disk to the destination peg
		printf("%c -> %c \r\n", paraSource, paraDestination);
        // Then move the n-1 disks from the transit peg to the destination peg
		hanoi(paraN - 1, paraTransit, paraDestination, paraSource);
	}// Of if
}// Of hanoi

/**
 * Test the Tower of Hanoi function.
 */
void hanoiTest() {
    printf("---- hanoiTest begins. ----\r\n");

    // Test with 2 disks
	printf("2 plates\r\n");
	hanoi(2, 'A', 'B', 'C');

    // Test with 3 disks
	printf("3 plates\r\n");
	hanoi(3, 'A', 'B', 'C');

    printf("---- hanoiTest ends. ----\r\n");
}// Of hanoiTest

/**
 * Main function.
 */
void main() {
    // Run the Tower of Hanoi test
	hanoiTest();
}// Of main

Summary: This code is a simple solution to the Tower of Hanoi problem. The Tower of Hanoi problem is a classic recursive problem where the goal is to move a stack of disks of different sizes from one peg to another, with the constraint that only a smaller disk can be placed on top of a larger disk, and only one disk can be moved at a time.

• The hanoi function solves the problem recursively by breaking it down into smaller sub-problems until there are no more disks to move.
• The hanoiTest function tests the hanoi function, testing with 2 and 3 disks.
• The main function is the program entry point, calling the hanoiTest function to execute the test.

Analysis

Time complexity: O(2^n) Space complexity: O(n)

Running Result