Does the following seem right? (problem description in comments) What concerns me is that the number of instructions gets out of hand horribly fast--so either that's part of the learning experience for the exercise or else I'm not seeing a better solution ...
Code:/** @file * cf. Sedgewick-Wayne, Intro to Programming in Java, p. 283, ex. 2.3.25: * There are 2n discs of increasing size stored on 3 poles. * Initially all of the discs with odd size (1, 3, ... 2n-1) are piled * on the left pole from top to bottom in increasing order of size; * all of the discs with even size (2, 4, ..., 2n) are piled on the right * pole. This program should provide instructions for moving the odd * discs to the right pole and the even discs to the left pole, * obeying the same rules as for towers of Hanoi. * * My instructions (as in Sedgewick-Wayne) will view the towers as * a cyclic group, where tower 1 is to the right of tower 3 * @author Marshall Farrier * @date 6/7/10 */ #include <iostream> using std::cout; using std::endl; /** class towers of Hanoi @param n height @param move_to_left true iff instructions are to move the tower to the left */ void move_tower(int n, bool move_left); /** recursive function giving instructions for interleaving both towers into 1 correct tower on the empty peg function makes use of move_tower() function @param n height of each tower note that this is for a total of 2n discs @param odd_on_right true iff odd tower is to the right of the even tower (as is the case in the starting set up with odd on peg 1 and even on peg 3) */ void interleave(int n, bool odd_on_right); /** once the 2 towers are consolidated this function gives instructions for distributing the odd and even disks from a single tower @param n tower height @param odd_on_right whether the instructions should distribute the disks with the odd disks on the right side (true) or left side (false) of the originial tower */ void distribute(int n, bool odd_on_right); /** combines the above functions into instructions for swapping 2 towers */ void swap_towers(int n, bool odd_on_right = true); int main() { using std::cin; int height; cout << "Enter height for each tower: "; cin >> height; //distribute(2 * height, true); // distributes odd tower to right of orig // interleave(height, true); swap_towers(height, false); return 0; } void move_tower(int n, bool move_left) { // base case: n == 0 if (!n) return; move_tower(n - 1, !move_left); cout << n; if (move_left) cout << " left\n"; else cout << " right\n"; move_tower(n - 1, !move_left); } void interleave(int n, bool odd_on_right) { if (!n) return; // interleave for respective tower heights using n - 1 interleave(n - 1, odd_on_right); // move the tower just created onto the base disc of the odd tower move_tower(2 * n - 2, odd_on_right); // move disc 2n to the empty peg cout << 2 * n; if (odd_on_right) cout << " left\n"; else cout << " right\n"; // move the tower atop the biggest odd disk back to the empty peg move_tower(2 * n - 1, !odd_on_right); } void distribute(int n, bool odd_on_right) { // <= 0 at least prevents infinite loop in case of incorrect input for n (which is assumed to be even) if (n <= 0) return; // move the tower, except for bottom even disc, to // where we want the bottom odd disk // i.e., if odd_on_right (we want odd tower on the right) // move_tower should also have its move_left variable set to false move_tower(n - 1, !odd_on_right); // move the base disk onto the empty peg: cout << n; if (odd_on_right) cout << " left\n"; else cout << " right\n"; // move the n - 2 tower back to the empty peg move_tower(n - 2, odd_on_right); // run distribute() on n - 2 discs: distribute(n - 2, odd_on_right); } void swap_towers(int n, bool odd_on_right) { interleave(n, odd_on_right); distribute(2 * n, odd_on_right); }
