The Problem

There are 3 pegssource,auxillaryandtarget.ndisks of different sizes are given which can slide onto any peg . In the beginning all of the disks are in the source peg in the order of size with largest disk at the bottom and smallest disk at the top. We have to move all the disks from source peg to target peg such that in the end the target peg will have all the disks in the same order of size.

Rules:

1. Only one disk can be moved from one peg to another peg at a time

2. A larger disk cannot be placed on top of the smaller disk

C++ Program

#include <iostream> #include <cstdlib> static int moveCounter = 0; void towerOfHanoi(int ndisk, char source, char auxillary, char target) { if(ndisk == 1) { std::cout << "Move [" << ndisk << "] [" << source << "] to [" << target << "]" << std::endl; ++moveCounter; return; } //place ndisk - 1 disks from source to auxillary peg towerOfHanoi(ndisk - 1, source, target, auxillary); //place ndisk to target peg std::cout << "Move [" << ndisk << "] [" << source << "] to [" << target << "]" << std::endl; ++moveCounter; //place ndisk - 1 disks from auxillary to target peg towerOfHanoi(ndisk - 1, auxillary, source, target); } int main(int args, char *argv[]) { if(argv[1] == NULL) { std::cout << "ERROR: Insufficient Arguments\n"; std::cout << "Usage: ./a.out number_of_disks\n"; exit(-1); } int disks = atoi(argv[1]); char peg1 = 'A', peg2 = 'B', peg3 = 'C'; towerOfHanoi(disks, peg1, peg2, peg3); std::cout << "Total Moves = " << moveCounter << std::endl; }

Java Program

public class TowerOfHanoi { private static final char source = 'A'; private static final char auxillary = 'B'; private static final char target = 'C'; private static int moveCount = 0; public static void main(String args[]) { if(args.length < 1) { System.out.println("ERROR: Insufficient Arguments"); System.out.println("Usage: java TowerOfHanoi number_of_disks"); System.exit(-1); } int ndisk = Integer.parseInt(args[0]); towerOfHanoi(ndisk, source, auxillary, target); System.out.println("Total Moves = " + moveCount); } public static void towerOfHanoi(int ndisk, char source, char auxillary, char target) { if(ndisk == 1) { System.out.println("Move [" + ndisk + "] from [" + source + "] to [" + target + "]"); ++moveCount; return; } //move ndisk - 1 disks from source peg to auxillary peg towerOfHanoi(ndisk - 1, source, target, auxillary); System.out.println("Move [" + ndisk + "] from [" + source + "] to [" + target + "]"); ++moveCount; //move ndisk - 1 disks from auxillary peg to target peg towerOfHanoi(ndisk - 1, auxillary, source, target); } }

Time Complexity: Let the time required for n disks is T(n). There are 2 recursive call for n-1 disks and one constant time operation to move a disk fromsourcepeg totargetpeg . Let it be c. Therefore, T(n) = T(n-1) + c + T(n-1) T(n) = 2T(n-1) + c T(0) = k1 T(1) = 2T(0) + c1 = 2k1 + c1 T(2) = 2T(1) + c2 = 2(2T(0)) + c2 = 2(2k1 + c1) + c2 = 4k1 + 2c1 + c2 T(3) = 2T(2) + c3 = 2(4k1 + 2c1 + c2) + c3 = 8k1 + 4c1 + 2c2 + c3 Coefficient of k1 =2^{n}Time complexity is O(2^{n})

**Output**

pankaj@pankaj-ub:~/workspace/source/fun/cpp$ ./a.out 3 Move [1] [A] to [C] Move [2] [A] to [B] Move [1] [C] to [B] Move [3] [A] to [C] Move [1] [B] to [A] Move [2] [B] to [C] Move [1] [A] to [C] Total Moves = 7 pankaj@pankaj-ub:~/workspace/source/fun/cpp$ ./a.out 5 Move [1] [A] to [C] Move [2] [A] to [B] Move [1] [C] to [B] Move [3] [A] to [C] Move [1] [B] to [A] Move [2] [B] to [C] Move [1] [A] to [C] Move [4] [A] to [B] Move [1] [C] to [B] Move [2] [C] to [A] Move [1] [B] to [A] Move [3] [C] to [B] Move [1] [A] to [C] Move [2] [A] to [B] Move [1] [C] to [B] Move [5] [A] to [C] Move [1] [B] to [A] Move [2] [B] to [C] Move [1] [A] to [C] Move [3] [B] to [A] Move [1] [C] to [B] Move [2] [C] to [A] Move [1] [B] to [A] Move [4] [B] to [C] Move [1] [A] to [C] Move [2] [A] to [B] Move [1] [C] to [B] Move [3] [A] to [C] Move [1] [B] to [A] Move [2] [B] to [C] Move [1] [A] to [C] Total Moves = 31

## No comments :

## Post a Comment