Towers of Hanoi


Need help converting from recursion to iteration, no clue.  Please advise.  Del


/* iteration example:

#include <cstdio>
#include <ctime>

#define N   29
void hanoi(void) {

     int x, fr, to;
     unsigned int i, j;

     for(x = 1; x < (1 << N); x++) {

          i = (x|x-1) + 1; to = (i+i/3) &3;
          i = x& x-1; fr = (i+i/3) &3;
           
          for(i = x, j = 1; ; i >>= 1, j++) { if(i&1) break; }
          #ifdef AUSGABE
               printf( "move disk %i from %i to %i\n", j, fr, to );
                    fflush(NULL);
          #endif

              return;
     }    

}

int main (void) {

     clock_t t0, t1;
     t0=clock();
     hanoi();  
     t1=clock();
     printf("Time: %f s\n",(t1-t0)/(float)CLOCKS_PER_SEC);

       return 0;
      
}

*/

// recursive

#include <iostream>
#include <iomanip>

using namespace std;

void move(unsigned n, unsigned& moveNumber, char source, char destination, char spare);

int main() {

      const char PEG1 = 'A', PEG2 = 'B', PEG3 = 'C';

      unsigned moveNumber = 0;
      cout << "This program solves the Hanoi Towers puzzle.\n\n";
      cout << "Enter the number of disks. " << endl;

      int numDisks;
      cout << endl;

      move(numDisks, moveNumber, PEG1, PEG3, PEG2);

}

void move(unsigned n, unsigned& moveNumber, char source, char destination, char spare) {

      if(n == 1) {
            moveNumber++;
            cout << setw(3) << moveNumber << ". Move the top disk from " << source << " to " << destination << endl;

      }
      else {
            move(n - 1, moveNumber, source, spare, destination);
            move(1, moveNumber, source, destination, spare);
            move(n - 1, moveNumber, spare, destination, source);

      }

}
edelossantosAsked:
Who is Participating?
 
ozoCommented:
 char *disk[]={"A","B","C"};
  for( int i=1; i < (1 << n); i++){
    cout << setw(3) << i << ". Move the top disk from " << disk[(i&i-1)%3] << " to " << disk[((i|i-1)+1)%3] << endl;
  }
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.