In Python: Pascal\'s Triangle http://en.wikipedia.org/wiki/Pascal%27s_triangle T

Question

In Python:

Pascal's Triangle

http://en.wikipedia.org/wiki/Pascal%27s_triangle

To construct Pascal's triangle, each number at a given (row, column) location can be computed by summing the two numbers above it. The numbers on the edges are always 1.

Write a function called pascal(row, col) that computes the number at the given (row, col) by using the formula above (in the Wikipedia page). It's a recursive function. The base case is when (row, col) corresponds to one of the edges. Otherwise, it sums the two values above.

Memoization

Make a new function called mpascal(row, col) that uses memoization to speed up the computation.

Explanation / Answer

a)

import math
x = int(input("Row:"))
y = int(input("column:"))
ans = math.factorial(x)/(math.factorial(y)*math.factorial(x-y))
print(int(ans))

b)

def pascal(r,c):
if(c==0 or c==r):
return 1
return pascal(r-1,c)+pascal(r-1,c-1)

c)

l=[]
def mpascal(r,c):
global l
if(c==0 or c==r):
return 1
if(l[r][c]!=0):
return l[r][c];
if(l[r-1][c-1]==0):
a1 = mpascal(r-1,c-1)
l[r-1][c-1]=a1;
else:
a1 = l[r-1][c-1]
if(l[r-1][c]==0):
a2 = mpascal(r-1,c)
l[r-1][c]=a2;
else:
a1 = l[r-1][c]
l[r][c]=a1+a2;
return a1+a2

r = int(input("Row:"))
c = int(input("column:"))
l = [0]*(r+1)
for i in range(r+1):
l[i]=[0]*(i+1)
print(mpascal(r,c))

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.