Home » Forums » Python » Python in General

python: สามเหลี่ยมปาสคาล

Submitted by wd on 9 February, 2007 - 12:34

เขียน Recursive แบบโบราณครับ
ใช้เมธอด values ของ dictionaries ประกอบกับ list

def tri(x=1):
  if x==0:
    return [0]
  if x==1:
    return [1]
  if x==2:
    return [1,1]
  l={}
  l[0]=1
  l[x]=1
  last=tri(x-1)
  for i in range(x-2):
    l[i+1]=last[i]+last[i+1]
  return l.values()

def f(x,y):
  if x>y:
    return 0
  return tri(y)[x-1]

ผลลัพธ์

>>> tri(6)
[1, 5, 10, 10, 5, 1]
>>> f(6,2)
0
>>> f(2,6)
5
‹ for ... in ... : เอกสารไพธอนโปรแกรมมิ่ง ภาษาไทย ›
»
Submitted by veer on 9 February, 2007 - 16:41.
veer's picture

เขียนแบบ iterative แทน recursive จะออกเปล่า?

»
Submitted by sugree on 9 February, 2007 - 22:45.
sugree's picture

ลองเขียนแบบ Memoize บ้าง

class TriPas(dict):
    def __getitem__(self,key):
        if key in self:
            return self.get(key)
        col,row = key
        if col == 1 or col == row:
            self[key] = 1
        elif col > row:
            self[key] = 0
        else:
            self[key] = self[(col,row-1)]+self[(col-1,row-1)]
        return self.get(key)
 
h = TriPas()
print h[(2,5)]

แต่ถ้าเป็น Python 2.5 จะมี __missing__

class TriPas(dict):
    def __missing__(self,key):
        col,row = key
        if col == 1 or col == row:
            self[key] = 1
        elif col > row:
            self[key] = 0
        else:
            self[key] = self[(col,row-1)]+self[(col-1,row-1)]
        return self.get(key)
»
Submitted by veer on 10 February, 2007 - 01:52.
veer's picture

แบบไม่ recursive เขียนแล้วก็งงๆ ว่าถูกหรือเปล่า :-P

def _tri(x,y):
 
    a = [0 for i in range(x+2)]
    b = [0 for i in range(x+2)]
 
    for i in range(1, y + 1,1):
        if i <= x:
            b[1] = 1
            b[i] = 1
            for j in range(2, i, 1):
                b[j] = a[j] + a[j - 1]
        elif (y - i + 1) < x:
            for j in range(x - (y - i), x + 1, 1):
                b[j] = a[j] + a[j - 1]
        else:
            b[1] = 1
            for j in range(2, x + 1, 1):
                b[j] = a[j] + a[j - 1]
        t = b
        b = a
        a = t
    return a[x]
 
def tri(x,y):
    if x > y:
        return 0
    if x > ((y + 2) / 2):
        return _tri(y - x + 1, y)
    else:
        return _tri(x, y)
 
print tri(2,5)
»

ย้าย Codenone

ประกาศย้าย Codenone ไปใช้ Forum ของ Blognone แทนครับ ตามไปตั้งกระทู้ต่อได้ที่ Codenone Forum (รายละเอียดอ่านจากกระทู้ ย้าย Codenone ไปรวมกับ Blognone)

กระทู้เก่าๆ จะย้ายตามไปในภายหลัง ตอนนี้ปิดการโพสต์กระทู้ไว้ เหลือไว้เฉพาะอ้างอิงเท่านั้น