SandCastleIcon.png 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

External links

Example

Cookies help us deliver our services. By using our services, you agree to our use of cookies.