Beefy Boxes and Bandwidth Generously Provided by pair Networks
"be consistent"

Re^2: Hanoi Challenge

by Elgon (Curate)
on Oct 22, 2004 at 19:50 UTC ( #401660=note: print w/ replies, xml ) Need Help??

in reply to Re: Hanoi Challenge
in thread Hanoi Challenge


A query; Surely it is possible only to solve the problem in exactly O(n) when there is one more peg than discs plus one. (It could be that I misunderstand the O(n), O(log n), O(n^2) notation...)

Example: In the quickest solution for three pegs and three discs, for example, the large disc moves once, the medium disc moves twice and the smallest disc moves four times.

Example 2: Where there are three rings and four pegs, each ring only moves twice.


UPDATE:Thanks to Thor for pointing out my error, below. As a general rule, I find that for n pegs and n discs the number of moves required is 2n + 1. If, however, there are n discs and n + 1 (or more) pegs, then 2n - 1 moves are required. Can someone with a better understanding of the formalisms tell me whether either of these is O(n) ???

It is better either to be silent, or to say things of more value than silence. Sooner throw a pearl at hazard than an idle or useless word; and do not say a little in many words, but a great deal in a few.

Pythagoras (582 BC - 507 BC)

Comment on Re^2: Hanoi Challenge
Replies are listed 'Best First'.
Re^3: Hanoi Challenge
by thor (Priest) on Oct 22, 2004 at 20:16 UTC
    Example 2: Where there are three rings and four pegs, each ring only moves twice.
    Does it? If we're trying to get ring C to peg 4
    A -> 1
    B -> 2
    C -> 4
    B -> 4
    A -> 4
    In the case of n disks and n+1 pegs, the last disk moves only once.


    Feel the white light, the light within
    Be your own disciple, fan the sparks of will
    For all of us waiting, your kingdom will come

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://401660]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (3)
As of 2016-02-09 01:46 GMT
Find Nodes?
    Voting Booth?

    How many photographs, souvenirs, artworks, trophies or other decorative objects are displayed in your home?

    Results (295 votes), past polls