Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
PerlMonks  

comment on

( #3333=superdoc: print w/replies, xml ) Need Help??
Blokhead,

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.

Elgon

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)


In reply to Re^2: Hanoi Challenge by Elgon
in thread Hanoi Challenge by tilly

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Are you posting in the right place? Check out Where do I post X? to know for sure.
  • Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
    <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
  • Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
  • Want more info? How to link or or How to display code and escape characters are good places to start.
Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (2)
As of 2021-12-03 23:32 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    R or B?



    Results (30 votes). Check out past polls.

    Notices?