Algorithms and Data Structures assignment: make a recursive program that prints Pascal's Triangles upside down. I found it impossible at the time, but I just gave it another shot and solved it in 5min. Yay. P.S Optimisation took one day though.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | #! /usr/bin/env python
"""
For a given number, prints Pascal's Triangle upside-down up to that line.
Takes advantage of the fact that the Triangle is symmetric.
Uses the combinatorics property of the Triangle:
For any NUMBER in position INDEX at row ROW:
NUMBER = C(ROW, INDEX)
A hash map stores the values of the combinatorics already calculated, so
the recursive function speeds up a little.
Prints everything alligned at first, but starts screwing up at about 13.
tn.pablo@gmail.com
03/09/07
"""
import sys
def comb(N, n, combs):
"""
Returns the value of C(N,n).
First the function looks it up in a dictionary and only calculates
if it isn't present, in which case it works recursively.
"""
try:
ans = combs[(N,n)]
except KeyError:
if n == 0: ans=1
elif n == 1: ans=N
else:
ans = (comb(N, n-1, combs) * (N-n+1) * 1/n)
combs[(N,n)] = ans
return ans
lines = int(sys.argv[1])
# stack that will contain the items of the row to be mirrored
mirror = []
# dictionary of combinatoric-value pairs
combs = {}
for row in range(lines, -1, -1):
# insert indentation
print ' ' * (lines - row),
# first half of the row
limit = (row//2)+1
for index in range(limit):
num = comb(row, index, combs)
if not((row%2 == 0) and (index == limit-1)): mirror.append(num)
print '%i ' % num,
# for the second half, mirror the first
while mirror: print '%i ' % mirror.pop(),
print
|
This program is 75.89 times as efficent as my previous attempt at it (without a couple of optimisations).
Tags: programs
Memoize. You could use a simple memoize (see e.g. http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52201 ). Something like:
calculate a row at a time. If you know you're calculating the whole triangle, you can do a row at a time. Of course, then there's really no point in using recursion:
response. It isn't exactly the triangle I calculate recursively, it's the combinatorics. Besides, the assignment required recursion. I liked your solution though, faster than mine for sure.
response. The assignment required recursion :( I liked your solution though, faster than mine for sure.
response. My first version was your code without the memory/dictionary. You can imagine how slow it was.
Did it say where it required recursion? Because you could certainly rewrite my for-loop recursively if necessary. (That is, have get_rows(n) call get_rows(n-1) and remove the loop.)
response. No, it didn't. I'll give your idea a try :)
Old thread, but pascal's triangle was a challenge on a forum I frequent today and this is what I came up with: