Unit 4.8 The Fibonnacci Number Problem

PROG

To compute the nth Fibonnacci number.

Fn = Fn-1 + Fn-2

PED

To learn how to keep track of the previous value in a do loop.

DO LOOP INVARIANT

The nth Fibonnacci Number is in MostRecent
n-1st Fibonnacci Number is in NextMostRecent
N contains n


Unit 4.8 The Fibonnacci Number Problem

Click here to view Unit 4.8 Pascal program.

All our do-loop examples only did something with a current number. We never had reason to do something with the number generated or read in just before it. Our example is designed to deal those situations where we need to keep track of the two or three most recently processed numbers. Other times, this is useful in programs that write reports. There is a list of data for each customer, e.g., several orders. Each data line contains the customer number and information about the specific part ordered. We need to tell when the customer changes to print out the total for each customer.

This technique is also needed when doing singly-linked lists, a topic you will see in CS202 and CS350, required courses for the CS Major.

We need two variables, one for the most recent number and the other for the previous number. At the end of the do-loop, we need to adjust these two variables. We also need another variable to contain the new number in the series, as it is generated. Note the precise order of the assignment statements and operations in the do loop. It is very critical and slight errors lead to difficult-to-find bugs.

Set Previous Number variable to the first number in the series
Set Most Recent Number variable to the second number in the series
while(we have not processed all the data)
process the current pair of numbers
compute or obtain the next number in the series
Set Previous Number to Most Recent Number
Set Most Recent Number to the next number-- computed above
end;

Now, we look at our example which involves computing the Fibonnacci number. The Fibonnacci numbers are defined such that each number is the sum of the preceeding numbers. The first number and the second number are both arbitrarily defined to be equal to one. At the w in the while, Fi is stored in the variable MostRecent and NextMostRecent contains Fi-1. Then line 15 sets Next to the value of Fi+1. After line 16, NextMostRecent will contain Fi. Then, we set MostRecent to Fi+1 in line 17. We adjust i in line 17.

Recall that our do-loop invariant is:

The nth Fibonnacci Number is in MostRecent
n-1st Fibonnacci Number is in NextMostRecent
N contains n


Check 1: that the do loop invariant and the condition being true implies that executing the statements leaves the do loop invariant true

We saw earlier that after line 17 is executed, we had the following quantities in the variables:

NextMostRecent: Fi
MostRecent: Fi+1

When i is incremented by one, then these would contain (by substitution):

NextMostRecent: Fi-1
MostRecent: Fi

which is the do loop invariant.

Check 2: that the do loop invariant and the condition not being true implies the POSTCONDITION for the loop does what its supposed to

From the do loop invariant, we have that MostRecent contains the ith Fibonnacci number. When the condition, i<>N is not true that means i=N. Thus MostRecent contains the Nth Fibonnacci number which is printed out in line 21.

Check 3: that the do loop invariant is initially true.

When i=2, Then MostRecent should contain F2 and NextMostRecent should contain F1. These are defined to be one and one and are set in lines 12 and 13.

Check 4: that executing the statements once makes progress towards the goal. Since each read statement removes a number from the file and advances us toward the end of what must be a finite set, then the statement makes progress.

Each time through the loop, we increment i and compute a new Fibonnacci number.