Java Reference
In-Depth Information
PROGRAMMING EXAMPLE:
Fibonacci Number
So far, you have seen several examples of loops. Recall that in Java,
while
loops are
used when a certain statement(s) must be executed repeatedly until certain conditions
are met. The following program uses a
while
loop to find a Fibonacci number.
Consider the following sequence of numbers:
1, 1, 2, 3, 5, 8, 13, 21, 34, ....
Given the first two numbers of the sequence (say, a
1
and a
2
), the nth number a
n
, n
>¼
3,
of this sequence is given by:
a
n
¼
a
n-1
+ a
n-2
Thus:
a
3
¼
a
2
+ a
1
¼
1+1
¼
2,
a
4
¼
a
3
+ a
2
¼
2+1
¼
3,
and so on.
Such a sequence is called a Fibonacci sequence. In the preceding sequence, a
2
¼
1
and a
1
¼
1. However, given any first two numbers, using this process, you can
determine the nth number, a
n
, n
>¼
3, of the sequence. The number determined this
way is called the nth Fibonacci number. Suppose a
2
¼
6 and a
1
¼
3.
Then:
a
3
¼
a
2
+ a
1
¼
6+3
¼
9; a
4
¼
a
3
+ a
2
¼
9+6
¼
15.
Next, we write a program that determines the nth Fibonacci number given the first
two numbers.
5
The first two numbers of the Fibonacci sequence and the position of the desired
Fibonacci number in the Fibonacci sequence
Input:
Output:
The nth Fibonacci number
To find, say, the 10th Fibonacci number of a sequence, you must first find a
9
and a
8
,
which requires you to find a
7
and a
6
and so on. Therefore, to find a
10
, you must first
find a
3
, a
4
, a
5
,...,a
9
. This discussion translates into the following algorithm:
1. Get the first two Fibonacci numbers.
PROBLEM
ANALYSIS
AND
ALGORITHM
DESIGN
2. Get the position of the desired number in the Fibonacci sequence.
That is, get the position,
n
, of the number in the Fibonacci sequence.
Search WWH ::
Custom Search