- Practice storing and retrieving
NSNumber
values in a collection.
Programmers often utilize mathematical concepts, proofs, and algorithms to give themselves direction in writing an exercise. For this exercise, we're going to challenge ourselves to write a method that will calculate the Fibonacci Sequence to a specified length.
The Fibonacci Sequence is defined by the formula:
Fn = Fn-1 + Fn-2
with the accepted seed values as either:
F0 = 0,F1 = 1, or
F1 = 1, F2 = 1
and begins:
F0 | F1 | F2 | F3 | F4 | F5 | F6 | F7 | F8 | F9 | F10 | F11 | F12 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 | 144 |
What the above information means is that, following the two initial values (in our case, 0
and 1
), each number is the sum of the two numbers preceding it in the sequence. If 0
is the zeroeth number (Hint: remember that arrays start at index 0
), then the first number is 1
, the second number is 0 + 1 = 1
, the third 1 + 1 = 2
, the fourth 1 + 2 = 3
, the fifth 2 + 3 = 5
, and so on into infinity.
Don't get intimidated by the math! Whether or not you recall learning about the Fibonacci Sequence in high school or college math class—if you've ever seen a snail shell or a pine cone you're already familiar with it. One of the amazing aspects of the Fibonacci Sequence (and of much of mathematics as a whole) is how prevalent it can be found in nature. Snail shells follow the Fibonacci Spiral (a geometric representation of the number sequence), while pine cones and sun flowers display the shape of Vogel's model (which relies on numbers in the Fibonacci Sequence).
Take a moment now (or save it for a study break later) to read about the history of the Fibonacci Sequence (its oldest known anthropological roots are actually in Sanskrit prosidy in India dating as far back as 200 BC) and look at some nature photography detailing Fibonacci geometry. If you're interested in some numerology, Arthur Benjamin's TED Talk is a six-minute video detailing how the Fibonacci Spiral and the Golden Ratio (1.618033...) are derived from the sequence.
Open the ios-fibo-finder.xcworkspace
file.
-
Navigate to the
FISAppDelegate.h
header file. Declare one method calledarrayWithFibonacciSequenceToIndex:
which takes oneNSUInteger
argument calledindex
and returns anNSArray
. -
Navigate to the
FISAppDelegate.m
implementation file. Use autocomplete to define the method implementation to returnnil
so that the build will succeed. Run the tests with⌘
U
to see that they fail. -
Modify the implementation of
arrayWithFibonacciSequenceToIndex:
to create a newNSMutableArray
variable calledsequence
that also serves as thereturn
object. -
To build the sequence in the array, we're going to need a loop. Between creating the
sequence
array and returning it, declare afor
loop whose counter is limited byindex + 1
and increments by one. -
Since the sequence requires the two previous numbers to calculate the next one, we need to prime the sequence. To do this, we're going to need to manually pass in
@0
and@1
on the first two iterations of the loop. We can detect the iteration number by checkingi
against0
and1
respectively.
- Create an
if
statement that checks wheni
is equal to0
. If it is, call theaddObject:
method on thesequence
array with@0
submitted as the argument. - Chain an
else if
statement that checks wheni
is equal to1
. If it is, call theaddObject:
method on thesequence
array with@1
submitted as the argument. - If you wish to inspect your sequence, insert an
NSLog()
right before the return statement that prints thesequence
array to the console. - Run the tests with
⌘
U
to see that the first two tests pass.
- Now it's time to implement the algorithm. Chain an
else
statement to theif
andelse if
statements to set a default behavior for every iteration of the loop after the first two. In order to calculate the next fibonacci number in the sequence, we're going to need to:
- pull the previous two numbers out of the
sequence
array,
Hint: You can subscript an array with an operation, such asi-2
. - convert them from
NSNumber
s to integer primitives, - calculate the next fibonacci number in the sequence by the finding the sum of the two converted integers, and
- add the new fibonacci number to the
sequence
array.
Use the tests and NSLog()
ing to help you determine when your implementation is correct.