towers of Hanoi variation

This is a discussion on towers of Hanoi variation within the C++ Programming forums, part of the General Programming Boards category; Does the following seem right? (problem description in comments) What concerns me is that the number of instructions gets out ...

  1. #1
    Registered User
    Join Date
    May 2009
    Posts
    242

    towers of Hanoi variation

    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);
    }

  2. #2
    Registered User
    Join Date
    May 2009
    Posts
    242
    P.S.: The approach in Sedgewick-Wayne is to generate instructions of the form "3 left" or "2 right" for moving the disc of size n in the appropriate direction.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. towers of hanoi - what is wrong with this code?
    By kanesoban in forum C Programming
    Replies: 4
    Last Post: 09-17-2007, 01:20 PM
  2. Towers of Hanoi (need help)
    By Loudan in forum C++ Programming
    Replies: 3
    Last Post: 01-30-2006, 09:17 PM
  3. towers of hanoi problem
    By aik_21 in forum C Programming
    Replies: 1
    Last Post: 10-02-2004, 01:34 PM
  4. Towers of Hanoi
    By cyberCLoWn in forum C++ Programming
    Replies: 6
    Last Post: 01-15-2004, 03:28 PM
  5. Towers of Hanoi
    By janehung in forum C Programming
    Replies: 12
    Last Post: 01-07-2002, 05:40 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21