Transcript Pycon 2011

Question:
How many different ways are there to
climb a staircase with n steps (for
example, 100 steps) if you are allowed
to skip steps, but not more than one at a
time?
Explore by hand, look for a
pattern:
n = 1:
n = 2:
1
1+1
1+1+1
1+1+1+1
?
1 way
2
1+2
1+1+2
2+1
1+2+1
Too
much
work!
2 ways
n = 3:
n = 4:
2 +1+1
3 ways
4 ways?
2+2
5 ways!
n = 5:
Use a computer:
Generate all sequences of 1s and 2s of
length from 1 to n, and count the
sequences for which the sum of the
elements is equal to n.
Generate... – how?!
A better approach:
Model the situation in a different way
(isomorphism):
0
0
1
0
1
0
0
0 marks a step we step on;
1 marks a step we skip.
A valid path cannot have two
1s in a row, ends with a 0.
Problem restated: Count all sequences of 0s
and 1s of length n with no two 1s in a row
Binary number system
for x in range (2**n):
# Binary digits of x are used as a
# sequence of 0s and 1s of length n
Bitwise logical operators
if x & (x << 1) == 0: # If the binary representation of x
# has no two 1s in a row...
&
00010100010
00101000100
-----------------00000000000
&
00101100100
01011001000
-----------------00001000000
Final
program:
def countPaths(n):
""" Returns the number of sequences of 0s and 1s
of length n with no two 1s in a row """
count = 0
for x in range(2**n):
if x & (x << 1) == 0:
count += 1
return count
for n in range(101):
print(n+1, countPaths(n))
11
22
33
45
58
6 13
...
100 573147844013817084101
Fibonacci numbers!
The answer is 101th Fibonacci number!
There is an easier way to compute it, of course,
for example:
def fibonacciList (n):
"Returns the list of the first n Fibonacci numbers"
fibs = [1, 1]
while len(fibs) < n:
fibs.append (fibs[-1] + fibs[-2])
return fibs
print (fibonacciList (101))
[1, 1, 2, 3, 5, 8, 13, ...,
...
... 573147844013817084101]
Back to math:
Show mathematically that the number
of paths for n steps is the (n+1)th
Fibonacci number.
[email protected]