### Tower of hanoi Iterative

Do you all got idea how to write the tower of hanoi in iterative ?
 12345678910111213141516171819202122232425262728 #include #include #include int main() { constexpr std::size_t NPEGS = 3U ; const char peg[NPEGS] = { 'A', 'B', 'C' } ; constexpr std::size_t MAX = std::numeric_limits::digits ; std::size_t ndisks ; std::cout << "ndisks ( 1 - " << MAX << ")? " ; std::cin >> ndisks ; if( ndisks > 0 && ndisks < MAX ) { const std::uintmax_t num_moves = ( 1U << ndisks ) - 1 ; // 2^n - 1 std::cout << ndisks << " disks, " << num_moves << " moves\n" ; // see: http://en.wikipedia.org/wiki/Tower_of_Hanoi#Binary_solution for( std::uintmax_t nmove = 1 ; nmove <= num_moves ; ++nmove ) { const auto from = ( nmove & (nmove-1) ) % NPEGS ; const auto to = ( ( nmove | (nmove-1) ) + 1 ) % NPEGS ; std::cout << nmove << ". from " << peg[from] << " to " << peg[to] << '\n' ; } } }

http://ideone.com/3kDnZi
the solution is restrict for 3 disks only.If let say it contains 100 disks..this solution is not suitable. Do u have more idea?Means when i key in 4 disks,the output will be result to the second peg but not the last peg..
Last edited on
> If let say it contains 100 disks..this solution is not suitable.

Repeat: // see http://en.wikipedia.org/wiki/Tower_of_Hanoi#Binary_solution

If you had bothered to read it, you would have got to:
 Although the three-peg version has a simple recursive solution as outlined above, the optimal solution for the Tower of Hanoi problem with four pegs (called Reve's puzzle), let alone more pegs, is still an open problem.
http://en.wikipedia.org/wiki/Tower_of_Hanoi#With_four_pegs_and_beyond
But izit can use the even and odd number to solve this problem ?any idea of this?
The minimum number of moves required is 2N - 1 where N is the number of disks. With 16 disks, we would need to print out 65,535 moves. Theoretically, a program can be written (using a large integer library) for any number of disks; in practice, assuming that one line can be printed in one nanosecond, printing out all the moves for 32 disks would take about 136 years.

> But izit can use the even and odd number to solve this problem ?any idea of this?

If you mean that, with three pegs, at the end we want all the disks to be on the last peg (peg C), yes. We have to take into account whether the number of disks is even or odd.

 123456789101112131415161718192021222324252627282930313233 #include #include #include #include int main() { constexpr std::size_t NPEGS = 3U ; char peg[NPEGS] = { 'A', 'B', 'C' } ; constexpr std::size_t MAX = std::numeric_limits::digits ; std::size_t ndisks ; std::cout << "ndisks ( 1 - " << MAX << ")? " ; std::cin >> ndisks ; if( ndisks > 0 && ndisks < MAX ) { // we want all disks to end up on peg C; so // if the number of disks is even, swap moves to peg B and peg C if( ndisks%2 == 0 ) std::swap( peg[1], peg[2] ) ; const std::uintmax_t num_moves = ( 1U << ndisks ) - 1 ; // 2^n - 1 std::cout << ndisks << " disks, " << num_moves << " moves\n" ; // see: http://en.wikipedia.org/wiki/Tower_of_Hanoi#Binary_solution for( std::uintmax_t nmove = 1 ; nmove <= num_moves ; ++nmove ) { const auto from = ( nmove & (nmove-1) ) % NPEGS ; const auto to = ( ( nmove | (nmove-1) ) + 1 ) % NPEGS ; std::cout << nmove << ". from " << peg[from] << " to " << peg[to] << '\n' ; } } }
Topic archived. No new replies allowed.