Transcript Fibonacci

Fibonacci
Problem Solving and Thinking in
Engineering Programming
H. James de St. Germain
Understand the Problem
• The Fibonacci Series is of interest and
excitement to Mathematicians and
Scientists.
• The Series is:
– 0,1,1,2,3,5,8,13,21,34,55,89,…
• To calculate a Fibonacci Number simply
add the two previous numbers together.
• We always start with zero and one (0 and 1)
What is the Requirements
• High Level English Description (or
Pseudocode Version 1)
– Calculate and Display the first ‘X’ Fibonacci
Numbers
Really Understand the Problem
•
•
•
•
•
Start with 0 and 1 (by definition)
Start of sequence is:
0,1
Add these two together: 1
Expanded sequence is:
0,1,1
Add last two numbers together
– 1+1 = 2
• Expanded sequence is:
0,1,1,2
• Add last two numbers together
– 1+2 = 3
• Expanded sequence is:
0,1,1,2,3
Do it by Hand!
0  add the first number
1  to the second number
1  to get the next number
Now What?
Do it by Hand!
0
1  now add this number
1  to this number
2  to get the next number
Now What?
Do it by Hand!
0
1
1  now add this number
2  to this number
3  to get the next number
Now What?
Do it by Hand!
0
1
1
2  now add this number
3  to this number
5  to get the next number
Now What?
Do it by Hand!
0
1
1
2
3  now add this number
5  to this number
8  to get the next number
Now What?
What does the Program
need to know at Each step?
0
1
1
2
3  now add this number
5  to this number
8  to get the next number
1.
2.
3.
the previous number
the number before that
the current number
What happens at each step?
•
Pseudocode Version 2:
1. set the first number to 0
2. set the second number to 1
3. Add previous two numbers together to get current
number
4. repeat step 3 until done
•
Question:
– Are the “last two numbers” always the same?
Transform Repeat to While
1. Add previous two numbers together to get
current number
2. repeat step 1 until done
1. while not done
– Add previous two numbers together to get
current number
end
What informatino do we need to
“know” or “compute” at Each Step?
• 2nd Previous Number
• Previous Number
• Current Number
• We need VARIABLES to store each of
these
Create Variables for our Program
•
•
•
•
second_previous = 0;
previous = 1;
current_number = ????
current_number = second_previous + …
previous;
What happens at each step?
1. Add previous and 2nd previous numbers
to get the current Fibonacci number
2. Then update our “previous” variables to
contain the “new” previous numbers
– Question: Is the ordering of these two steps
important?
– Is the ordering of the two operations in step
2 important?
Which of these produces the
correct values in our variables?
• Now is it:
– current = second_previous + previous;
– previous = current;
– second_previous = previous;
• Or is it:
– current = second_previous + previous;
– second_previous = previous;
– previous = current;
Lets Confirm our Understanding:
previous = 1, second_previous=1;
• Case 1:
– current = second_previous + previous;
– % current is assigned the value 2
– previous = current;
– % previous is assigned the value 2
– second_previous = previous;
– % second_previous is assigned the value 2
Lets Confirm our Understanding:
previous = 1, second_previous=1;
Case 2:
– current = second_previous + previous;
– % current is assigned the value 2
– second_previous = previous;
– % 2nd previous is assigned the value 1
– previous = current;
– % previuos is assigned the value 2
Pseudocode ( 3rd Version)
1. print “0,1”:
2. set the first two values to 0 and 1
3. While we haven’t reached our goal
1. add these values to get the next (or current)
value
2. print the current value:
3. update the previous two values
Onward to Code
•
•
•
•
•
fprintf(“0, 1, “);
second_previous = 0
previous = 1
current = previous + second_previous;
fprintf(“%d, ”, current);
Sample Code
•
•
•
•
•
•
•
•
second_previous = 0
previous = 1
current = previous + second_previous;
fprintf(“%d, ”, current);
second_previous = previous;
previous = current;
current = previous + second_previous;
fprintf(“%d, ”, current);
Sample Code
•
•
•
•
•
•
•
•
•
•
•
•
second_previous = 0
previous = 1
current = previous + second_previous;
fprintf(“%d, ”, current);
second_previous = previous;
previous = current;
current = previous + second_previous;
fprintf(“%d, ”, current);
second_previous = previous;
previous = current;
current = previous + second_previous;
fprintf(“%d, ”, current);
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
Sample Code
second_previous = 0
previous = 1
current = previous + second_previous;
fprintf(“%d, ”, current);
second_previous = previous;
previous = current;
current = previous + second_previous;
fprintf(“%d, ”, current);
second_previous = previous;
previous = current;
current = previous + second_previous;
fprintf(“%d, ”, current);
second_previous = previous;
previous = current;
current = previous + second_previous;
fprintf(“%d, ”, current);
second_previous = previous;
previous = current;
current = previous + second_previous;
fprintf(“%d, ”, current);
second_previous = previous;
previous = current;
current = previous + second_previous;
fprintf(“%d, ”, current);
second_previous = previous;
previous = current;
current = previous + second_previous;
fprintf(“%d, ”, current);
Seems like the same old same old,
over and over and over
• This implies that we want a loop!
• Remember: A Loop lets the computer do
things over and over again so we don’t
have to!
• What loop to use?
– For loop or While loop?
– Give a valid reason to use either!
While Loop
• while ( current < some large number)
– Use a while loop because we want all
Fibonacci numbers less than some number
FOR loop
• for ith_fib_number = 3:1000
– Use a for loop because we want the first 1000
Fibonacci numbers
Pseudocode (4th version)
Very Close to Code
• Set second_previous to 0
• Set previous to 1
• Starting with 3, go until ‘X’ (by ones)
– Current value is set to second_previous +
previous
– Print current value
– Set second_previous to previous
– Set previous to current
Code
second_previous = 0;
previous = 1;
fprintf(‘%d %d ‘, second_previous, previous);
for I = 3:total_fib_numbers
current = second_previous + previous;
fprintf(‘%d ‘, current);
second_previous = previous;
previous = current;
end % the for loop
Thoughts
• Is the variable I used in the loop?
– Nope! Its just a place holder.
for I = 3:total_fib_numbers
current = second_previous + previous;
fprintf(‘%d ‘, current);
second_previous = previous;
previous = current;
end % the for loop
Thoughts
• Are we calculating anything?
– Sort of, but when the program is over, does
the computer have anything it can use?
• Nope
• How would we write code to save these
values?
– What data type?
Saving the values
• What would we do if we needed to save
the values instead of simply printing them
to the screen?
• Answer:
– Use an Array
– Note: now the variable I is important
New Code with Array
% Pre-allocate (save buckets for)
% enough space for all the numbers
fib_numbers = zeros(1,total_fib_numbers);
% Set up the first two fib numbers from memory
% (your memory)
fib_numbers(1) = 0;
fib_numbers(2) = 1;
New Code with Array
for i = 3:total_fib_numbers
fib_numbers(i) = fib_numbers(i-1) + …
fib_numbers(i-2);
end % for
% where did the previous and
% 2nd previous variables go?
What is wrong with this code?
fib_numbers = fib_numbers(i-1) + …
fib_numbers(i-2);
Corrected:
fib_numbers(i) = fib_numbers(i-1) + …
fib_numbers(i-2);
Notice the Update of the Array uses the “(i)” next to
the array variable
Let me Repeat!
• NEVER use:
array = 5 + 6;
• ALWAYS use:
array( position ) = 5 + 6;
You must always “index” into an array!
Function
• How would we turn this code into a
function?
– What are the inputs?
– What are the outputs?
Draw a Black Box
• You have 1 minutes to draw a black box
for this function
Function as Black Box
Input
Function
Output
Fibonacci as Black Box
Fibonacci
Numbers
Count
Fibonacci
Integer
Array of
Numbers
Compute the first “count” fibonacci
numbers
Comment Your Function
• You have 1 minute to write a brief
comment that would go at the top of your
.m file for the Fibonacci function
Function Comment
% array_of_fib_numbers = compute_fib(…
%
how_many)
%
% Author: H. James de St. Germain
% Date: Fall 2007
%
% This function produces an array of the
% first “how many” Fibonacci Numbers
Function Design Pattern
• You have one minute to write the function
design pattern for this function
Function Design Pattern
function result_array = compute_fib( how_many )
result_array(1) = 0;
end %function
Function Code
• From your memory and your notes write
out the code for this function.
• … you have 1 minute….
• Pseudocode:
– set up first two values in array
– loop updating the “current” value based on the
previous two values
Function Code
function result_array = compute_fib( count )
result_array(1) = 0;
result_array(2) = 1;
for counter = 3 : count
result_array(counter) = …
result_array(counter-1) + …
result_array(counter-2);
end %for loop
end % function
How many…
1.
semicolons (;s) in the function? Where?
function result_array = compute_fib( count )
result_array(1) = 0;
result_array(2) = 1;
for counter = 3 : count
result_array(counter) = …
result_array(counter-1) + …
result_array(counter-2);
end %for loop
end % function
How many…
1.
fprintfs and input statements?
function result_array = compute_fib( count )
result_array(1) = 0;
result_array(2) = 1;
for counter = 3 : count
result_array(counter) = …
result_array(counter-1) + …
result_array(counter-2);
end % for loop
end % function
NEVER…
• use fprintf in a function
– unless told that the function “communicates”
with the user of the program
• use input in a function
– unless told that the function “recieves” input
from the user of the program
How many…
1.
variables? (parameters, return variables, local
variables)
function result_array = compute_fib( count )
result_array(1) = 0;
result_array(2) = 1;
for counter = 3 : count
result_array(counter) = …
result_array(counter-1) + …
result_array(counter-2);
end % for loop
end % function
End Fibonacci
– Questions?