こちらは「Pascal’s Triangle 2」のPythonによる解答例となっております。この問題は、パスカルの三角形を生成する問題です。
問題
正の整数 numRows が与えられた場合、パスカルの三角形の最初の numRows 行を返します。
- 1 <= numRows <= 30
解法
この問題は、二重ループを用いた1つのアプローチがあります。アルゴリズムの概要を以下に述べます。
- numRows分の二次元配列を作成します。
- 一次元目には、1がnumRows個入ったリストを格納します。
- 二次元目以降には、直前の行の隣り合う2つの要素を足したものを格納します。
Pythonコード
以下のコードが、「Pascal’s Triangle」を解くためのPythonプログラムとなります。
### Function ##################################################################
def solve(num=0):
solver = Solution().getRow
if 1 <= num <= Input().input: id_LIST = [num]
else: id_LIST = [id+1 for id in range(Input().input)]
for id in id_LIST:
data = Input(id)
ans = solver(data.rowIndex)
result = "OK" if ans==data.ans else "NG"
print(f"[{str(id).zfill(3)}] {result}")
### Class #####################################################################
import math
class Solution(object):
# def getRow(self, rowIndex):
# """
# :type rowIndex: int
# :rtype: List[int]
# """
# ### row0: 1
# ### row1: 1 1
# ### row2: 1 2 1
# ### row3: 1 3 3 1
# ### row4: 1 4 6 4 1
# ### row5: 1 5 10 10 5 1
# ### row6: 1 6 15 20 15 1
# numRows = rowIndex + 1
# pascal = [1] * numRows
# for i in range(numRows):
# for j in reversed(range(1,i)): pascal[j] = pascal[j-1] + pascal[j]
# return pascal
def comb(self, n, k):
if n == k or k == 0: return 1
else: return math.factorial(n) // ( math.factorial(k) * math.factorial(n-k) )
def getRow(self, rowIndex):
"""
:type rowIndex: int
:rtype: List[int]
"""
### row0: 1
### row1: 1 1
### row2: 1 2 1
### row3: 1 3 3 1
### row4: 1 4 6 4 1
### row5: 1 5 10 10 5 1
### row6: 1 6 15 20 15 1
### (x+y)**1 = 1x + 1y
### (x+y)**2 = 1x**2 + 2xy + 1y**2
### (x+y)**1 = 1x**3 + 3x**2y + 3xy**2 + 1y**3
### nCk = n!/k!(n-k)!
### row2:
### 2C0: 2!/(0!*(2-0)!) = 2/1*2 = 1
### 2C1: 2!/(1!*(2-1)!) = 2/1*1 = 2
### 2C2: 2!/(2!*(2-2)!) = 2/2*1 = 1
return [ self.comb(rowIndex,i) for i in range(0, rowIndex+1) ]
#==============================================================================
class Input:
def __init__(self, num=0):
if num == 1:
self.rowIndex = 3
self.ans = [1,3,3,1]
elif num == 2:
self.rowIndex = 0
self.ans = [1]
elif num == 3:
self.rowIndex = 1
self.ans = [1,1]
else:
self.input = 3
### Main ######################################################################
if __name__ == "__main__":
solve()
###############################################################################