Добавил:
kingracer
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз:
Предмет:
Файл:ФБТ БИ 2курс / global
.pys1 = input("First sequence: ")
s2 = input("Second sequence: ")
s1 = "_" + s1
s2 = "_" + s2
p = []
way = []
for i in s1:
stolbik = []
wayStolbik = []
for j in s2:
stolbik.append(0)
wayStolbik.append("")
p.append(stolbik)
way.append(wayStolbik)
for i in range(len(s1)):
p[i][0] = -2 * i
for j in range(len(s2)):
p[0][j] = -2 * j
for x in range(1, len(s1)):
for y in range(1, len(s2)):
left = p[x-1][y] - 2
up = p[x][y-1] - 2
if (s1[x] == s2[y]):
slog = 1
else:
slog = -1
diag = p[x-1][y-1] + slog
p[x][y] = max(left, up, diag)
if (p[x][y] == left):
way[x][y] = "l"
if (p[x][y] == up):
way[x][y] = "u"
if (p[x][y] == diag):
way[x][y] = "d"
res1 = ""
res2 = ""
x = len(s1)-1
y = len(s2)-1
while (way[x][y] != ""):
if (way[x][y] == "d"):
res1 = s1[x] + res1
res2 = s2[y] + res2
x = x - 1
y = y - 1
if (way[x][y] == "u"):
res1 = "_" + res1
res2 = s2[y] + res2
y = y - 1
if (way[x][y] == "l"):
res1 = s1[x] + res1
res2 = "_" + res2
x = x - 1
print("P matrix:")
for s in p:
print(s)
print("Resulting sequence 1: " + res1)
print("Resulting sequence 2: " + res2)
Соседние файлы в папке ФБТ БИ 2курс