54 楊輝三角的變形

題目描述

1

1 1 1

1 2 3 2 1

1 3 6 7 6 3 1

1 4 10 16 19 16 10 4 1

以上三角形的數陣，第一行隻有一個數1，以下每行的每個數，是恰好是它上面的數，左上角數到右上角的數，3個數之和（如果不存在某個數，認為該數就是0）。

求第n行第一個偶數出現的位置。如果沒有偶數，則輸出-1。例如輸入3,則輸出2，輸入4則輸出3。

輸入n(n <= 1000000000)

輸入描述:

輸入一個int整數

輸出描述:

輸出傳回的int值

示例1

輸入

4

輸出

3

思路：1.利用矩陣生成楊輝三角矩陣的變形，然後在最後一行查找

2.找規律

當n<3時，沒有偶數，輸出-1；

當n為奇數時，第一個偶數位置在第二，輸出2；

當n為偶數且能被4整除時，第一個偶數位置在第三，輸出3；

當n為偶數但不能被4整除時，偶數位置在第四，輸出4

def getIndex(n):
    matrix = [[0 for j in range(2 * n - 1)] for i in range(n)]#n行，每行2n-1個；清單為0
    matrix[0][n - 1] = 1#第一行中間的為1
    print(matrix)
    for i in range(1, n):
        for j in range(1, 2 * n - 2):
            matrix[i][j] = matrix[i - 1][j - 1] + matrix[i - 1][j] + matrix[i - 1][j + 1]
    matrix[n - 1][0] = 1#最後一行的首尾為0
    matrix[n - 1][2 * n - 2] = 1
    print(matrix)
    for k in range(2 * n - 2):#查找最後一行的每個元素
        if matrix[n - 1][k] % 2 == 0:
            return k + 1
    return -1

while True:
    try:
        n = int(input())
        print(getIndex(n))
    except:
        break
           

while True:
    try:
        n=int(input())
        if n==1 or n==2:
            print(-1)
        elif n%2==1:
            print (2)
        elif n%4==0:
            print (3)
        else:
            print (4)
    except:
        break
           

楊輝三角形列印

1.生成器

def triangles():
    L=[1]
    while True:
        yield L
        L=[1]+[(L[i]+L[i+1]) for i in range(len(L)-1)]+[1]
n=0
for i in triangles():
    print(i)
    n+=1
    if n==10:
        break
           

2.循環清單

def angles(n):
    l=[[1]]
    #清單l有n個子清單，切記不可通過l=[[1]]*n實作
    for i in range(n):
        l.append([1])
    #從l[1]開始    
    for i in range(1,n):
        for x in range(1,i):
            l[i].append(l[i-1][x-1]+l[i-1][x])
        l[i].append(1)
    for i in range(n):
        print(l[i])
 if __name__=='__main__':
    angles(10)