Authors: | Tom Dunham |
---|---|
Date: | 2009-03-31 |
A programming language gives us three things:
>>> 256 256
>>> 137 + 349 486
>>> 5 * 99 495
>>> 10 / 5 2
You can combine expressions
>>> 21 + 35 + 12 + 7 75 >>> 3 * (2 * 4 + (3 + 5)) + ((10 - 7) + 6) 57
You give something a name by assigning it to that name.
>>> size = 2 >>> size 2 >>> size * 5 10
>>> size = size + 2 >>> size 4 >>> pi = 3.1415926535897931 >>> pi 3.1415926535897931
This is also called binding a name to a value.
Assignment is such a fundamental part of programming that there are a lot of different ways to describe what's going on here.
The expression size = 2 can be read:
Note also that the meaning of = to Python is not what you are familiar with from maths. In maths, = is a test for equality. In Python, = binds a name to a value; == is the test for equality.
We've now seen some of the elements of programming languages
>>> def square(x): ... return x * x
>>> square(2) 4 >>> square(2 + 4) 36
Now we can use square as a building block
>>> def sum_of_squares(x, y): ... return square(x) + square(y) ... >>> sum_of_squares(3, 4) 25
Allow us to choose
We can now define the absolute value function:
>>> def abs(x): ... if x < 0: ... return -x ... else: ... return x
See handout
Evaluate the following expressions in the interpreter (in the given order)
10
5 + 3 + 4
9 - 1
6 / 2
(2 * 4) + (4 - 6)
a = 3
b = a + 1
a + b + a * b
a == b
print b
print a
5 / 2
Is that the value you expected?
5.0 / 2
You see this behavior because Python implements "floor division" for integers (the result is rounded down to the nearest integer). This is unsurprising for people familiar with the C programming language, but quite a shock for most others.
Because of this unintuitive behavior, it's unusual to see the / operator applied to two integers (or two names bound to integer values). Normally, division is written:
x * 1.0 / y
And deliberate floor division is written:
x // y
What is wrong with this (Python) expression? 1 + 1 = 2
Write a function that takes two arguments and returns their mean.
Python supports a number of boolean operations, though the notation may not be what you are used to:
>>> 2 < 4 True >>> 4 >= pi > 2 True >>> not 2 == 1 True |
>>> 2 == 2 True >>> 2 != pi True |
Computers are very good at repetitive tasks. Python offers two main ways to repeat yourself.
What does this print?
def countdown(n): while n > 0: print n n = n-1 print "Blastoff!"
countdown(10)
For loops process sequences.
range is a function that returns a list (more on these later).
>>> range(1, 10) [1, 2, 3, 4, 5, 6, 7, 8, 9]
What does this print?
for i in range(0, 10): print i
Loops express iteration (repetition of a process). This can also be done through recursion
def countdown(x): if x == 0: print "Blastoff" else: print x countdown(x-1)
Calling a procedure recursively and using a loop are two different ways to express the same thing.
Wikipedia has a good explanation of recursion:
To understand recursion, one must recognize the distinction between a procedure and the running of a procedure. A procedure is a set of steps that are to be taken based on a set of rules. The running of a procedure involves actually following the rules and performing the steps.
http://en.wikipedia.org/wiki/Recursion#Recursion_in_plain_English
Often you can write the same loop in several ways.
We're going to write a function to calculate factorials using while loops, for loops and recursion.
n = 1 → n! = 1
n > 1 → n! = n(n-1)!
def fac_while(x): fac = 1 count = 1 while count <= x: fac = fac * count count = count + 1 return fac
def fact_for(n): fac = 1 for i in range(1, n+1): fac = fac * i return fac
def fac_r(n): if n == 1: return 1 else: return n * fac_r(n-1)
See handout
Do the first three exercises without using the computer, then check your answers.
What will this print?
a = 10 while a < 100: print "a"
When will the program in question 1 terminate?
What will the following program print?
The % operator in Python performs modulo division (return the remainder after integer division).
a = 2 while a % 9 != 0: if a % 3 == 0: print 0 if a % 7 == 0: print 7 a = a -1 a = a + 2
Fibonacci numbers
Leonardo of Pisa (aka Fibonacci) used this sequence of numbers in 1202 to model the population of rabbits.
Definition
f(0) == 0 f(1) == 1 f(n) == f(n-2) + f(n-1)
The first 20 elements of the Fibonacci sequence are
F0 |
F1 |
F2 |
F3 |
F4 |
F5 |
F6 |
F7 |
F8 |
F9 |
F10 |
F11 |
F12 |
F13 |
F14 |
F15 |
F16 |
F17 |
F18 |
F19 |
F20 |
0 |
1 |
1 |
2 |
3 |
5 |
8 |
13 |
21 |
34 |
55 |
89 |
144 |
233 |
377 |
610 |
987 |
1597 |
2584 |
4181 |
6765 |
(For more see: http://www.research.att.com/~njas/sequences/A000045)
Write functions to calculate fib(n) using
Square Roots by Newton's Method
Write a procedure sqrt that uses the Newton-Raphson method to approximate the square root of it's parameter (x).
The Newton-Raphson method states that a guess (y) of the root of x can be improved by averaging y and x/y.
One way to apply the method is as follows:
Hints
You'll probably want to use either a while loop or recursion. Either way, you'll need to test if you are close enough to the result, and you may want to write a function to do this. For our purposes, within 0.001 is good enough.
We defined some maths functions in the lectures and in previous exercises; you can use them here.
If you are trying to form a recursive solution, take note of the similarities between the recursive examples we have studied so far. Notice that they all contain an if with a test that chooses between a terminal case (which means that the instructions don't have to be repeated again), and the recursive case (which means the procedure will be repeated to bring us closer to the solution).
Once you've solved the problem using one approach, try the other one (so if you used a loop, try to solve the problem recursively). Try to look where you duplicate code, move that into functions, and call the functions rather than having it in the file twice.