|
This article has links to websites or programs not trusted by Scratch or hosted by Wikipedia. Remember to stay safe while using the internet, as we cannot guarantee the safety of other websites. |
The Fibonacci sequence is a sequence of numbers. The first to numbers in the sequence are both 1. All other numbers in the sequence are equal to the sum of the two numbers before them. It was first described by Leonardo of Pisa, nicknamed Fibonacci, in his book Liber abbaci.
Creating a Fibonacci Number Generator
Using the definition of the sequence, a script can be created to find it's nth number:
when gf clicked delete all of [sequence v] add (1) to [sequence v] add (1) to [sequence v] repeat ((n) - (2)) //we repeat this loop two times less than n because there are two numbers in the sequence already set [last v] to (item (length of [sequence v]) of [sequence v]) set [2nd last v] to (item ((length of [sequence v]) - (1)) of [sequence v]) add ((last) + (2nd last)) to [sequence v] wait (1) secs // any number end set [nth number v] to (item (length of [sequence v]) of [sequence v])
Looking at the script, one can see that the only numbers relevant to finding the next number in the sequence are the previous two numbers, so it is unnecessary to store the entire sequence. Here is a more elegant approach that takes this fact into account:
when gf clicked set [last v] to (1) set [2nd last v] to (1) repeat (n) set [next v] to ((last) + (2nd last)) set [last v] to (next) set [2nd last v] to (last) wait (1) secs // any number end set [nth number v] to (2nd last)
Recursive Approach
Using custom blocks, the previous approach can be written in a recursive style:
when gf clicked fibbonaci (1) (1) (n) define fibbonaci (last) (2nd last) (n) if <(n) > (1)> then fibbonaci ((last) + (2nd last)) (last) ((n) - (1)) wait (1) secs // any number else set [nth number v] to (2nd last) end
