lection.md

Король

Варианты выполнения: 1. Диагонально сверху вниз по одному элементу 2. По строке (На примере реализован второй вариант)

Что интересно - эту программу можно вычислять параллельно: вычислив один элемент можно уже вычислять элемент на следующей строке. Главное что вычисления на слеюдующей строке не обогнали строку выше нее. Пример можно объяснить строителями которые строят стену, а стену строят параллельно кладя кирпичи. Это уже вопросы параллельного программирования.

def printList(lst):
    for i in lst:
        print(i)

m = int(input(":"))
n = int(input(":"))

K = [[0]*m for i in range(n)]

for i in range(n):
    K[i][0] = 1

for j in range(m):
    K[0][j] = 1

for i in range(1, n):
    for j in range(1, m):
        K[i][j] = K[i-1][j-1] + K[i-1][j] + K[i][j-1]

printList(K)

Result:

[1, 1, 1, 1, 1]
[1, 3, 5, 7, 9]
[1, 5, 13, 25, 41]
[1, 7, 25, 63, 129]
[1, 9, 41, 129, 321]

Наибольшая общая подпоследовательность

def printList(lst):
    for i in lst:
        print(i)

A = [1, 2, 3, 5, 7, 8, 9]
B = [1, 1, 3, 7, 2, 8, 4]

n = len(A)
m = len(B)

F = [[0]*(m+1) for i in range(n+1)]

for i in range(1, n+1):
    for j in range(1, m+1):
        if (A[i-1] == B[j-1]):
            F[i][j] = F[i-1][j-1] + 1
        else:
            F[i][j] = max(F[i-1][j], F[i][j-1])

printList(F)

Result:

[0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 1, 1, 1, 1]
[0, 1, 1, 1, 1, 2, 2, 2]
[0, 1, 1, 2, 2, 2, 2, 2]
[0, 1, 1, 2, 2, 2, 2, 2]
[0, 1, 1, 2, 3, 3, 3, 3]
[0, 1, 1, 2, 3, 3, 4, 4]
[0, 1, 1, 2, 3, 3, 4, 4]

Наибольшая возрастающая последовательность

Не совсем уверен в правильности

def printList(lst):
    for i in lst:
        print(i)

A = [[5, 6], [1, 3], [8, 9], [10, 11]]

F = [0]*len(A)

for i in range(len(A)):
    for j in range(i):
        if A[j]<A[i] and F[j]>F[i]:
            F[i] = F[j]
    F[i] += 1

print(F)
print(max(F))

Result:

[1, 1, 2, 3]
3