edelossantos
asked on
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
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);
}
}
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.