By the time you have completed this lab, you and your lab partner should be able to
If your partner is more than 5 minutes late, ask the TA to pair you with someone else for this week.
Decide which one of you will be the first pilot for this lab, and then log in to the pilot's account and create a directory called lab03 inside his/her cs8 folder. You will work in this account for the rest of the lab, but remember to switch often between pilot and navigator roles during the course of the lab.
Start IDLE. Then, select "File->New Window" and add a comment at the top of this new file like the following (with the proper substitutions of course):
# lab03.py # Your name(s), today's date # a factorial function and a Fibonacci function
Then, save it under the name lab03.py inside your lab03 directory.
(Exercise 2.12 from page 56 of the text). Together we will write a function called factorial that computes the product of the first N numbers, where N is a parameter. For example, factorial(4) is calculated as 1 * 2 * 3 * 4, so the function should return the value 24. We will assume N is greater than 0. Be sure to understand the purpose and meaning of each of the following instructions before you execute them.
# factorial - returns n factorial # assumes n is greater than or equal to 0
def factorial(n):
result = 1
for i in range(2, n+1): result = result * i
return result
Save and run the module. Then test the function a few times (in the Python shell window) by comparing its results to ones that you calculate manually. Here is one example run of our solution:
>>> factorial(5) 120
First switch roles between pilot and navigator if you did not already do that.
(Based on Exercise 2.14 from page 56 of the text). Write a function named fib to compute the Nth Fibonacci number where N is a parameter. Here is the required function header and an appropriate comment - type or copy/paste them into lab03.py at least one blank line below the end of the factorial function:
# fib - returns nth term of Fibonacci sequence: # 1, 1, 2, 3, 5, 8, ... So fib(6) = 8 def fib(n):
The first two numbers in the Fibonacci sequence are both 1. After that, every succeeding number is equal to the sum of the previous two numbers. Here are the first 10 numbers in the sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. So fib(9) is 34 and fib(10) is 55 - think about what is fib(11) ... 34 + 55 of course.
Test your function thoroughly to be sure it is correct. Verify that both fib(1) and fib(2) return 1, fib(3) returns 2, and so on. You may assume that N will always be greater than 0, but find out what the function returns for 0 or negative values too, and try to understand why it returns what it does in such cases.
Hint: Another way to write this is: fib(i) = fib(i-1) + fib(i-2). This does not mean that to calculate fib(i) you should call fib for both of the lower results. What this really means is that the result of this iteration is dependent on your result of the last iteration and the iteration before that. Storing those (two) partial results are the key to getting this algorithm correct.
Remember to let both partners think about this before diving in. Don't skip the design step, in which you work this out on paper before trying to write in Python.
IMPORTANT: you don't have to finish the next step (or even Step 4) to earn full credit.
Please begin and try to finish, but if you are running out of time before lab ends, then move on to Step 6 - the TA will check off your work as complete anyway. |
For Hw3, you did some research about the "golden ratio" - often denoted by the lower case Greek letter, phi (φ). We hope you noticed this ratio can be approximated by using the Fibonacci function. In particular, as the value of n increases, the value of the fraction F(n+1)/F(n) gets nearer and nearer to φ. Here F denotes the Fibonnaci function. In calculus, this relationship is expressed as a limit, as n approaches infinity:
Of course, it is not necessary to plug ∞ into the formula to approximate the ratio, let alone (∞ + 1)! Your job is:
Find the smallest value of n for which the ratio is within 1.0e-10 of this approximate value of φ: 1.6180339887. |
Devise a strategy using your fib function, and other things you've learned so far in CS 8. Things you should know:
>>> abs(-5.5) 5.5 >>> abs(1.05) 1.05
Execute your strategy until an appropriate answer is visible in the Python shell window.
If you did Step 5, be sure your evidence for completing it is clearly visible for the TA to inspect, and be prepared to answer questions about your approach to that step. If you did not finish Step 4, be ready to show evidence that you tried it and to answer any questions your TA might pose about your efforts. Also insure a copy of lab03.py is open, and that the module has been run since you last changed it. The TA may want to see you demonstrate its functions.
Get your TA's attention to inspect your work, and to record your lab completion. |
Don't leave early though ... see challenge problems below.
Step 6a. ONLY IF YOU RAN OUT OF TIME TO HAVE THE TA INSPECT YOUR WORK
In the unlikely event that you must complete this assignment at CSIL, then submit it with the turnin program - but do not turn it in if the TA already checked you off. You MUST have both your name and your partner's name in the file in order to receive credit. Remember that the original pilot needs to do this step, since that is whose account you have been using in Phelps 3525. Use the following command after you cd into your cs8/lab03 directory:
turnin Lab03@cs8c lab03.pyAfter answering the questions, be sure to wait for the message indicating success.
Optional Extra Challenge
Some expressions of the golden ratio in nature and elsewhere form a "golden spiral" - several examples are here. An approximation to such a spiral (known as a "Fibonacci spiral") can be constructed from a series of squares, appropriately arranged and in sizes that correspond to a Fibonacci sequence.
- Start a function named drawSpiral to draw a variable number of squares, where this variable is a parameter. Here is a drawing of the first 9 squares.
- The spiral is drawn by superimposing quarter-circles appropriately within each square. First write a helper function named quarterCircle, and then modify drawSpiral to call this function each time a square is drawn. Here is the result of our solution that shows both squares and spiral (note our quarter circles are drawn with pen size of 4).
- Change drawSpiral again by adding (Boolean) parameters that let the user choose to draw the squares, the spiral, or both. The function header from our solution is:
def drawSpiral(turt, width, n, spiral=False, squares=True):
width
is the number of pixels in one side of the smallest square,turt
is the turtle, andn
is the number of squares to draw. The parametersspiral
andsquares
have default values - just the squares are drawn by default. Here is a run of our solution showing just the spiral (invoked withspiral=True, squares=False
).
Prepared for Computer Science 8 by Diana Franklin and Michael Costanzo.