Towers of hanoi in C++


/* The towers of Hanoi Demo Program
*
*
* printStacks() prints out the stacks
*
*
* */

#include <stdlib.h>

#include <iostream.h>

#define SIZE 4

// We have 3 stacks each of size SIZE
// To represent disks we represent them by numbers
// Hence 2 is a smaller disk than 4
// 0 indicates the absence of the disk
// The stacks are initialized in main
//
int stack[3][SIZE] ;

//Lets maintain a global variable to maintain the number of moves required

int numMoves = 0;

void moveDisk(int, int);
void printStacks();
void moveStack(int size, int start, int end , int temp);

/* This is the function you should write
* Assume that you have a function called moveDisk which moves the
* topmost disk from the start stack to the end stack
* You dont need to care about the implementation of moveDisk or
* printStacks
*/

void moveStack(int size, int start, int end , int temp){

if( size == 0) return ;// base case
//alternatively the base case could be if size ==1

int newTempStack = end;
// Move smaller stack from start to temp using the end  stack as a temp stack
moveStack(size-1, start, temp, newTempStack);

//Move the larger disk
moveDisk(start, end);

//Move the rest of the stack from temp to end stack using the start stack as the new temp
newTempStack = start;
moveStack(size-1, temp, end, newTempStack);

}

//Function to Move a disk from stack start to stack end

void moveDisk(int start, int end){
int i = 0;
while( stack[start][i] == 0 && i < SIZE ){
i = i+1 ; // Find the disk to be moved
}
if(i == SIZE) return ; // No disk to move !!!!
int startDisk = stack[start][i];
stack[start][i] = 0;
i =0;
while( stack[end][i] == 0 && i < SIZE ){
i = i+1 ; // Find the disk to be moved
}
stack[end][i-1] = startDisk;
printStacks();
numMoves +=1;
}

//Print the stacks ..
void printStacks(){
int s,j;
for(j = 0 ; j< SIZE ; j+=1){
for(s = 0; s < 3 ; s++){
if (stack[s][j]==0)
cout << ” \t”;
else if (stack[s][j]==1)
cout << “*\t”;
else if (stack[s][j]==2)
cout << “**\t”;
else if (stack[s][j]==3)
cout << “***\t”;
else if (stack[s][j]==4)
cout << “****\t”;
}
cout << “\n”;
}
cout << “****************************\n”;
}

int main(void){
//Initialize the arrays
for(int i = 0 ; i < SIZE ; i +=1){
stack[0][i] = i+1 ;
stack[1][i] = 0;
stack [2] [i] = 0;
}

cout << “****************************\n”;

printStacks();

cout << “****************************\n”;

moveStack(SIZE, 0 , 2 , 1);
cout << “\n\nThe number of moves required is :” << numMoves;

return 0;
}

Advertisements

2 Comments Add yours

  1. infact i got this piece of code on the net and made some modification to it, nothing is perfect dude..

    send me an improve version if u have, i can post it here under the actual one.. thanks!!

  2. selven says:

    😀 try using namespace and stl’s stack instead to be more CPP 😀

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s