收集了杨辉三角形的若干种求法,所有方法用以下函数输出测试结果:
>>> def test(func, n, out=True): from time import time start = time() if not out: t=(func(n)) else: for i in range(1,n+1): print(f'Y({i:>2}) = {func(i)}') print(time()-start)
方法一:
>>> def Yh1(n): t=L=[1] while n-1: n-=1 t=L+[t[i]+t[i+1] for i in range(len(t)-1)]+L return t >>> test(Yh1,17) Y( 1) = [1] Y( 2) = [1, 1] Y( 3) = [1, 2, 1] Y( 4) = [1, 3, 3, 1] Y( 5) = [1, 4, 6, 4, 1] Y( 6) = [1, 5, 10, 10, 5, 1] Y( 7) = [1, 6, 15, 20, 15, 6, 1] Y( 8) = [1, 7, 21, 35, 35, 21, 7, 1] Y( 9) = [1, 8, 28, 56, 70, 56, 28, 8, 1] Y(10) = [1, 9, 36, 84, 126, 126, 84, 36, 9, 1] Y(11) = [1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1] Y(12) = [1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1] Y(13) = [1, 12, 66, 220, 495, 792, 924, 792, 495, 220, 66, 12, 1] Y(14) = [1, 13, 78, 286, 715, 1287, 1716, 1716, 1287, 715, 286, 78, 13, 1] Y(15) = [1, 14, 91, 364, 1001, 2002, 3003, 3432, 3003, 2002, 1001, 364, 91, 14, 1] Y(16) = [1, 15, 105, 455, 1365, 3003, 5005, 6435, 6435, 5005, 3003, 1365, 455, 105, 15, 1] Y(17) = [1, 16, 120, 560, 1820, 4368, 8008, 11440, 12870, 11440, 8008, 4368, 1820, 560, 120, 16, 1] 0.2859833240509033 >>> >>> test(Yh1,323,False) 0.015624284744262695 >>> test(Yh1,1000,False) 0.2491614818572998 >>> test(Yh1,2000,False) 1.452894926071167 >>> test(Yh1,3000,False) 4.124391317367554 >>>
方法二:
>>> def Yh2(n): t=[[1],[1,1]] i=0 while i+2<n: i+=1 t.append([1]+[t[i][j]+t[i][j-1] for j in range(1,len(t[i]))]+[1]) return t[n-1] >>> test(Yh2,17) Y( 1) = [1] Y( 2) = [1, 1] Y( 3) = [1, 2, 1] Y( 4) = [1, 3, 3, 1] Y( 5) = [1, 4, 6, 4, 1] Y( 6) = [1, 5, 10, 10, 5, 1] Y( 7) = [1, 6, 15, 20, 15, 6, 1] Y( 8) = [1, 7, 21, 35, 35, 21, 7, 1] Y( 9) = [1, 8, 28, 56, 70, 56, 28, 8, 1] Y(10) = [1, 9, 36, 84, 126, 126, 84, 36, 9, 1] Y(11) = [1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1] Y(12) = [1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1] Y(13) = [1, 12, 66, 220, 495, 792, 924, 792, 495, 220, 66, 12, 1] Y(14) = [1, 13, 78, 286, 715, 1287, 1716, 1716, 1287, 715, 286, 78, 13, 1] Y(15) = [1, 14, 91, 364, 1001, 2002, 3003, 3432, 3003, 2002, 1001, 364, 91, 14, 1] Y(16) = [1, 15, 105, 455, 1365, 3003, 5005, 6435, 6435, 5005, 3003, 1365, 455, 105, 15, 1] Y(17) = [1, 16, 120, 560, 1820, 4368, 8008, 11440, 12870, 11440, 8008, 4368, 1820, 560, 120, 16, 1] 0.29276371002197266 >>> >>> test(Yh2,1000,False) 0.3641676902770996 >>> test(Yh2,2000,False) 1.9820797443389893 >>> test(Yh2,3000,False) 5.548851013183594 >>>
方法三:
>>> def Yh3(n): t=[_*[1] for _ in range(1,n+1)] for i in range(2,n): for j in range(1,i): t[i][j]=t[i-1][j-1]+t[i-1][j] return t[n-1] >>> test(Yh3,17) Y( 1) = [1] Y( 2) = [1, 1] Y( 3) = [1, 2, 1] Y( 4) = [1, 3, 3, 1] Y( 5) = [1, 4, 6, 4, 1] Y( 6) = [1, 5, 10, 10, 5, 1] Y( 7) = [1, 6, 15, 20, 15, 6, 1] Y( 8) = [1, 7, 21, 35, 35, 21, 7, 1] Y( 9) = [1, 8, 28, 56, 70, 56, 28, 8, 1] Y(10) = [1, 9, 36, 84, 126, 126, 84, 36, 9, 1] Y(11) = [1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1] Y(12) = [1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1] Y(13) = [1, 12, 66, 220, 495, 792, 924, 792, 495, 220, 66, 12, 1] Y(14) = [1, 13, 78, 286, 715, 1287, 1716, 1716, 1287, 715, 286, 78, 13, 1] Y(15) = [1, 14, 91, 364, 1001, 2002, 3003, 3432, 3003, 2002, 1001, 364, 91, 14, 1] Y(16) = [1, 15, 105, 455, 1365, 3003, 5005, 6435, 6435, 5005, 3003, 1365, 455, 105, 15, 1] Y(17) = [1, 16, 120, 560, 1820, 4368, 8008, 11440, 12870, 11440, 8008, 4368, 1820, 560, 120, 16, 1] 0.2826821804046631 >>> >>> test(Yh3,1000,False) 0.4663882255554199 >>> test(Yh3,2000,False) 2.530691385269165 >>> test(Yh3,3000,False) 6.483311176300049 >>>
方法四:
>>> def Yh4(n): L=[1] while n-1: n -= 1 L.append(0) L = [L[i-1] + L[i] for i in range(len(L))] return L >>> test(Yh4,17) Y( 1) = [1] Y( 2) = [1, 1] Y( 3) = [1, 2, 1] Y( 4) = [1, 3, 3, 1] Y( 5) = [1, 4, 6, 4, 1] Y( 6) = [1, 5, 10, 10, 5, 1] Y( 7) = [1, 6, 15, 20, 15, 6, 1] Y( 8) = [1, 7, 21, 35, 35, 21, 7, 1] Y( 9) = [1, 8, 28, 56, 70, 56, 28, 8, 1] Y(10) = [1, 9, 36, 84, 126, 126, 84, 36, 9, 1] Y(11) = [1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1] Y(12) = [1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1] Y(13) = [1, 12, 66, 220, 495, 792, 924, 792, 495, 220, 66, 12, 1] Y(14) = [1, 13, 78, 286, 715, 1287, 1716, 1716, 1287, 715, 286, 78, 13, 1] Y(15) = [1, 14, 91, 364, 1001, 2002, 3003, 3432, 3003, 2002, 1001, 364, 91, 14, 1] Y(16) = [1, 15, 105, 455, 1365, 3003, 5005, 6435, 6435, 5005, 3003, 1365, 455, 105, 15, 1] Y(17) = [1, 16, 120, 560, 1820, 4368, 8008, 11440, 12870, 11440, 8008, 4368, 1820, 560, 120, 16, 1] 0.29657435417175293 >>> >>> test(Yh4,1000,False) 0.24535727500915527 >>> test(Yh4,2000,False) 1.377683162689209 >>> test(Yh4,3000,False) 3.977062702178955 >>>
方法五:
>>> def Yh5(n): L = [1] for i in range(1,n): L+=[0] L=[L[j]+k for j,k in enumerate(L[::-1])] return L >>> test(Yh5,17) Y( 1) = [1] Y( 2) = [1, 1] Y( 3) = [1, 2, 1] Y( 4) = [1, 3, 3, 1] Y( 5) = [1, 4, 6, 4, 1] Y( 6) = [1, 5, 10, 10, 5, 1] Y( 7) = [1, 6, 15, 20, 15, 6, 1] Y( 8) = [1, 7, 21, 35, 35, 21, 7, 1] Y( 9) = [1, 8, 28, 56, 70, 56, 28, 8, 1] Y(10) = [1, 9, 36, 84, 126, 126, 84, 36, 9, 1] Y(11) = [1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1] Y(12) = [1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1] Y(13) = [1, 12, 66, 220, 495, 792, 924, 792, 495, 220, 66, 12, 1] Y(14) = [1, 13, 78, 286, 715, 1287, 1716, 1716, 1287, 715, 286, 78, 13, 1] Y(15) = [1, 14, 91, 364, 1001, 2002, 3003, 3432, 3003, 2002, 1001, 364, 91, 14, 1] Y(16) = [1, 15, 105, 455, 1365, 3003, 5005, 6435, 6435, 5005, 3003, 1365, 455, 105, 15, 1] Y(17) = [1, 16, 120, 560, 1820, 4368, 8008, 11440, 12870, 11440, 8008, 4368, 1820, 560, 120, 16, 1] 0.2609119415283203 >>> >>> test(Yh5,1000,False) 0.2201399803161621 >>> test(Yh5,2000,False) 1.249098300933838 >>> test(Yh5,3000,False) 3.7358851432800293 >>>
方法六:
>>> def Yh6(n): L=[1] for _ in range(n-1): L=[sum(_) for _ in zip([0]+L,L+[0])] return L >>> test(Yh6,17) Y( 1) = [1] Y( 2) = [1, 1] Y( 3) = [1, 2, 1] Y( 4) = [1, 3, 3, 1] Y( 5) = [1, 4, 6, 4, 1] Y( 6) = [1, 5, 10, 10, 5, 1] Y( 7) = [1, 6, 15, 20, 15, 6, 1] Y( 8) = [1, 7, 21, 35, 35, 21, 7, 1] Y( 9) = [1, 8, 28, 56, 70, 56, 28, 8, 1] Y(10) = [1, 9, 36, 84, 126, 126, 84, 36, 9, 1] Y(11) = [1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1] Y(12) = [1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1] Y(13) = [1, 12, 66, 220, 495, 792, 924, 792, 495, 220, 66, 12, 1] Y(14) = [1, 13, 78, 286, 715, 1287, 1716, 1716, 1287, 715, 286, 78, 13, 1] Y(15) = [1, 14, 91, 364, 1001, 2002, 3003, 3432, 3003, 2002, 1001, 364, 91, 14, 1] Y(16) = [1, 15, 105, 455, 1365, 3003, 5005, 6435, 6435, 5005, 3003, 1365, 455, 105, 15, 1] Y(17) = [1, 16, 120, 560, 1820, 4368, 8008, 11440, 12870, 11440, 8008, 4368, 1820, 560, 120, 16, 1] 0.173600435256958 >>> test(Yh6,1000,False) 0.14240050315856934 >>> test(Yh6,2000,False) 0.5334012508392334 >>> test(Yh6,3000,False) 1.3280022144317627 >>>
递归法:
>>> def Yh(n): if n==1: return [1] t = Yh(n-1)+[0] return [sum(z) for z in zip(t,t[::-1])] ''' 或者: >>> def Yh(n): if n==1: return [1] t = Yh(n-1) return [1]+[t[i]+t[i+1] for i in range(len(t)-1)]+[1] ''' >>> test(Yh,17) Y( 1) = [1] Y( 2) = [1, 1] Y( 3) = [1, 2, 1] Y( 4) = [1, 3, 3, 1] Y( 5) = [1, 4, 6, 4, 1] Y( 6) = [1, 5, 10, 10, 5, 1] Y( 7) = [1, 6, 15, 20, 15, 6, 1] Y( 8) = [1, 7, 21, 35, 35, 21, 7, 1] Y( 9) = [1, 8, 28, 56, 70, 56, 28, 8, 1] Y(10) = [1, 9, 36, 84, 126, 126, 84, 36, 9, 1] Y(11) = [1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1] Y(12) = [1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1] Y(13) = [1, 12, 66, 220, 495, 792, 924, 792, 495, 220, 66, 12, 1] Y(14) = [1, 13, 78, 286, 715, 1287, 1716, 1716, 1287, 715, 286, 78, 13, 1] Y(15) = [1, 14, 91, 364, 1001, 2002, 3003, 3432, 3003, 2002, 1001, 364, 91, 14, 1] Y(16) = [1, 15, 105, 455, 1365, 3003, 5005, 6435, 6435, 5005, 3003, 1365, 455, 105, 15, 1] Y(17) = [1, 16, 120, 560, 1820, 4368, 8008, 11440, 12870, 11440, 8008, 4368, 1820, 560, 120, 16, 1] 0.3664591312408447 >>> test(Yh,1000,False) 0.4101085662841797 # test(Yh,1024,False) 超最大递归深度
组合公式法:
>>> def Combin(n,i): m,t=min(i,n-i),1 for j in range(0,m): t*=(n-j)/(m-j) return t >>> def Yh(n): return [round(Combin(n-1,i)) if n<1000 else Combin(n-1,i) for i in range(n)] >>> test(Yh,17) Y( 1) = [1] Y( 2) = [1, 1] Y( 3) = [1, 2, 1] Y( 4) = [1, 3, 3, 1] Y( 5) = [1, 4, 6, 4, 1] Y( 6) = [1, 5, 10, 10, 5, 1] Y( 7) = [1, 6, 15, 20, 15, 6, 1] Y( 8) = [1, 7, 21, 35, 35, 21, 7, 1] Y( 9) = [1, 8, 28, 56, 70, 56, 28, 8, 1] Y(10) = [1, 9, 36, 84, 126, 126, 84, 36, 9, 1] Y(11) = [1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1] Y(12) = [1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1] Y(13) = [1, 12, 66, 220, 495, 792, 924, 792, 495, 220, 66, 12, 1] Y(14) = [1, 13, 78, 286, 715, 1287, 1716, 1716, 1287, 715, 286, 78, 13, 1] Y(15) = [1, 14, 91, 364, 1001, 2002, 3003, 3432, 3003, 2002, 1001, 364, 91, 14, 1] Y(16) = [1, 15, 105, 455, 1365, 3003, 5005, 6435, 6435, 5005, 3003, 1365, 455, 105, 15, 1] Y(17) = [1, 16, 120, 560, 1820, 4368, 8008, 11440, 12870, 11440, 8008, 4368, 1820, 560, 120, 16, 1] 0.26958274841308594 >>> >>> test(Yh,1000,False) 0.05560708045959473 >>> test(Yh,2000,False) 0.2970747947692871 >>> test(Yh,3000,False) 0.7152261734008789 >>>
类方法:
class Yh(): def __init__(self,n=None): self.data = [1] if n!=None: self.data=Yh()*n def __repr__(self): return f'{self.data}' def __mul__(self,n): while n>1: n-=1 self.data.append(0) self.data=[i[0]+i[1] for i in zip(self.data,self.data[::-1])] return self.data __rmul__ = __mul__ def List(n): i=0 while i<n: i+=1 print(Yh(i)) >>> test(Yh,17) Y( 1) = [1] Y( 2) = [1, 1] Y( 3) = [1, 2, 1] Y( 4) = [1, 3, 3, 1] Y( 5) = [1, 4, 6, 4, 1] Y( 6) = [1, 5, 10, 10, 5, 1] Y( 7) = [1, 6, 15, 20, 15, 6, 1] Y( 8) = [1, 7, 21, 35, 35, 21, 7, 1] Y( 9) = [1, 8, 28, 56, 70, 56, 28, 8, 1] Y(10) = [1, 9, 36, 84, 126, 126, 84, 36, 9, 1] Y(11) = [1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1] Y(12) = [1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1] Y(13) = [1, 12, 66, 220, 495, 792, 924, 792, 495, 220, 66, 12, 1] Y(14) = [1, 13, 78, 286, 715, 1287, 1716, 1716, 1287, 715, 286, 78, 13, 1] Y(15) = [1, 14, 91, 364, 1001, 2002, 3003, 3432, 3003, 2002, 1001, 364, 91, 14, 1] Y(16) = [1, 15, 105, 455, 1365, 3003, 5005, 6435, 6435, 5005, 3003, 1365, 455, 105, 15, 1] Y(17) = [1, 16, 120, 560, 1820, 4368, 8008, 11440, 12870, 11440, 8008, 4368, 1820, 560, 120, 16, 1] 0.19911837577819824 >>> >>> test(Yh,1000,False) 0.2420802116394043 >>> test(Yh,2000,False) 1.3822360038757324 >>> test(Yh,3000,False) 4.064407110214233 >>> >>> # 副产品:除了像函数一样使用外,还能用乘法表示项数,也可以直接列表 >>> Yh(11) [1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1] >>> Yh()*12 [1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1] >>> 12*Yh() [1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1] >>> Yh.List(10) [1] [1, 1] [1, 2, 1] [1, 3, 3, 1] [1, 4, 6, 4, 1] [1, 5, 10, 10, 5, 1] [1, 6, 15, 20, 15, 6, 1] [1, 7, 21, 35, 35, 21, 7, 1] [1, 8, 28, 56, 70, 56, 28, 8, 1] [1, 9, 36, 84, 126, 126, 84, 36, 9, 1] >>>