Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid
 
PerlMonks  

Re: Explain Fibonacci one-liner ??

by JavaFan (Canon)
on May 10, 2010 at 15:47 UTC ( [id://839248]=note: print w/replies, xml ) Need Help??


in reply to Explain Fibonacci one-liner ??

Main loop initializes $= each time to 1, and creates a string of sizes 0, 1, 2, ... 10. This string is matched against the regexp.

Note that the pattern does not match (due to the trailing ^), so basically what's happening that $= counts the number of times the regexp engine will backtrack. We can simplify the pattern a little:

/^(1|11)*^/
(the capture and backref of the anchor are just there to confuse the optimizer). So, what the pattern is counting how many times it can partition a string into 1 and 2 character substrings. Let's call this number F(n), for a string of size n. The pattern says "either match '1' or match '11'; then recurse with the rest". How many times can we do that? F(n+1) + F(n+2). So, we derive:
F(n) = F(n+1) + F(n+2)
Hmmm. That's exactly the definition of the Fibonacci series (except for the initial condition).

Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others wandering the Monastery: (9)
As of 2024-03-28 10:13 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found