Lab4

Problem 1: The Towers of Hanoi

There are three towers (labeled ‘A’, ‘B’ and ‘C’), and a number of disks (say, n) of different sizes¬† which can slide onto any tower. The puzzle starts with the disks in a neat stack in ascending order of size on one tower (labeled ‘A’), the smallest at the top, thus making a conical shape.

The objective of the puzzle is to move the entire stack to another tower (labeled ‘B’), obeying the following rules:

  • Only one disk may be moved at a time.
  • Each move consists of taking the upper disk from one of the towers and sliding it onto another tower, on top of the other disks that may already be present on that tower.
  • No disk may be placed on top of a smaller disk.

With three disks, the puzzle can be solved in seven moves.

Write a recursive program that takes in “n” as input and prints out the steps to solve this puzzle.

Starter file:

Copy the starter file from here:

/comp/15/public_html/labs/lab4/towers_of_hanoi/problem/

Sample output:

Number of discs: 3

Steps to move 3 discs from A to B
Move disc from A to B
Move disc from A to C
Move disc from B to C
Move disc from A to B
Move disc from C to A
Move disc from C to B
Move disc from A to B

Solution:

The solution files are here.


Problem 2: Permutations of n unique alphabets taking r alphabets at a time

Write a recursive program that takes in “n”, “r” and the alphabets to be permuted as input, and prints out the permutations.

Starter file:

Copy the starter file from here:

/comp/15/public_html/labs/lab4/permutations/problem/

Sample output:

Number of chars (n): 3
Alphabets: abc
Number of alphabets in the permutations (r): 2
Permutations of abc taking 2 alphabets at a time.
ab
ac
ba
bc
ca
cb

Solution:

The solution files are here.