You have three small poles and five hoops - XS, S, M, L, XL (as in extra small, small, medium, large and extra large). They are placed on pole 1 in order, with largest at the bottom.

You can move one hoop at a time, and the hoops you are not moving have to be on a pole. You also cannot place a hoop on top of a smaller one. How can you move the hoops so that they are in the same order as they are now, but on pole 3?

Here's a simple program in C++ to do the recursion, similar to Charlie's but it takes an input for each of the three poles (so you could call them A, B, and C or whatever) instead of hardcoding the numbering. Also, I made the output a separate function, so that if you wanted to diplay the output as the current state of the poles/hoops, perhaps using stacks to 'push' and 'pop' the hoops, you could do that. Mine right now just does the simple output anyway.

#include <iostream>


using namespace std;





void hanoi(int n, char src, char dst, char xtr);


void showMove(int n, char src, char dst);





void main() {


    int n;


    cout << \"Number of hoops: \";


    cin >> n;


    hanoi(n, 'A', 'B', 'C');


}





void hanoi(int n, char src, char dst, char xtr) {


    // when there's just one left, put it where you want it


    if (n==1) {


        move(n,src,dst);


        return;


    }


    // if there are more than 1, move all but last hoop to extra pole


    hanoi(n-1, src, xtr, dst);


    showMove(n,src,dst);


    // after moving last hoop, put extra hoops back onto it


    hanoi(n-1, xtr, dst, src);





}





void showMove(int n, char src, char dst) {


    cout << \"Move \" << n << \" from \" << src << \" to \" << dst << endl;


}



		

			

			

 			
			

				Posted by DJ
				on 2003-09-08 12:29:22