Лабораторна робота №8

Мета роботи: визначити найоптимальніший метод вирівнювання двох

послідовностей
Реалізація алгоритму:
s1 = input("Введіть першу slog = 1
послідовність: ")
else:
s2 = input("Введіть другу
slog = -1
послідовність: ")
diag = p[x-1][y-1] + slog
#Глобальне
p[x][y] = max(left, up, diag)
def _global(s1, s2):
if (p[x][y] == left):
p = []
way[x][y] = "l"
way = []
if (p[x][y] == up):
for i in s1:
way[x][y] = "u"
row = []
if (p[x][y] == diag):
way_row = []
way[x][y] = "d"
for j in s2:
x = len(s1) - 1
row.append(0)
y = len(s2) - 1
way_row.append("")
res1 = res2 = ""
p.append(row)
while (way[x][y] != ""):
way.append(way_row)
if (way[x][y] == "d"):
for i in range(len(s1)):
res1 = s1[x] + res1
p[i][0] = -2 * i
res2 = s2[y] + res2
for j in range(len(s2)):
x=x-1
p[0][j] = -2 * j
y=y-1
for x in range(1, len(s1)):
if (way[x][y] == "u"):
for y in range(1, len(s2)):
res1 = "_" + res1
left = p[x-1][y] - 2
res2 = s2[y] + res2
up = p[x][y-1] - 2
y=y-1
if (s1[x] == s2[y]):
 if (way[x][y] == "l"): if (s1[x] == s2[y]):
res1 = s1[x] + res1 p[x][y] = p[x-1][y-1] + 1
res2 = "_" + res2 m = max([a for b in p for a in b])
x=x-1 for x in range(len(s1)):
while x: for y in range(len(s2)):
res1 = s1[x]+res1 if p[x][y] == m:
res2 = " " + res1 xmax = x
x=x-1 ymax = y
while y: res1 = res2 = ""
res1 = " " + res1 while m:
res2 = s2[y] + res2 res1 = s1[xmax] + res1
y=y-1 res2 = s2[ymax] + res2
ret = [res1, res2] xmax = xmax - 1
return ret ymax = ymax - 1
#Локальне m=m-1
def local(s1, s2): ret = [res1, res2]
p = [] return ret
way = [] #Псевдоглобальне
for i in s1: def pseudo(s1, s2):
row = [] s1 = "_" + s1
way_row = [] s2 = "_" + s2
for j in s2: p = []
row.append(0) for i in s1:
way_row.append("") row = []
p.append(row) for j in s2:
way.append(way_row) row.append(0)
for y in range(len(s2)): p.append(row)
for x in range(len(s1)): for x in range(1, len(s1)):
 for y in range(1, len(s2)): res2 = s2[ymax] + res2
left = p[x-1][y] - 2 xmax = xmax - 1
up = p[x][y-1] - 2 ymax = ymax - 1
if s1[x] == s2[y]: if ymax == 0:
slog = 1 while xmax:
else: res1 = s1[xmax] + res1
slog = -1 res2 = "_" + res2
diag = p[x-1][y-1] + slog xmax = xmax - 1
p[x][y] = max(left, up, diag) if xmax == 0:
x = len(s1)-1 while ymax:
y = len(s2)-1 res1 = "_" + res1
lastrow = [] res2 = s2[ymax] + res2
lastcol = [] ymax = ymax - 1
for i in range(len(s2)): for j in range(len(s1)):
lastrow.append(p[x][i]) if lastcol[j] == maxcol:
for j in range(len(s1)): ymax = y
lastcol.append(p[j][y]) xmax = j
maxrow = max(lastrow) res1 = ""
maxcol = max(lastcol) res2 = ""
res1 = res2 = "" while xmax and ymax:
for i in range(len(s2)): res1 = s1[xmax] + res1
if lastrow[i] == maxrow: res2 = s2[ymax] + res2
ymax = i xmax = xmax - 1
xmax = x ymax = ymax - 1
res1 = "" if ymax == 0:
res2 = "" while xmax:
while xmax and ymax: res1 = s1[xmax] + res1
res1 = s1[xmax] + res1 res2 = "_" + res2
 xmax = xmax - 1 seq2 = result[0][1]
if xmax == 0: inp = "глобальне вирівнювання"
while ymax: elif z == check[1]:
res1 = "_" + res1 seq1 = result[1][0]
res2 = s2[ymax] + res2 seq2 = result[1][1]
ymax = ymax - 1 inp = "локальне вирівнювання"
ret = [res1, res2] elif z == check[2]:
return ret seq1 = result[2][0]
#Результат seq2 = result[2][1]
result = [_global(s1, s2), local(s1, s2), inp = "псевдоглобальне
pseudo(s1, s2)] вирівнювання"
check = [0, 0, 0] print("Результуюча послідовність 1: "
+ seq1)
j=k=0
print("Результуюча послідовність 2: "
for i in range(3):
+ seq2)
while (j < len(result[i][0])) and (k <
print("Вага: " + str(z))
len(result[i][1])):
print("Найоптимальніше " + inp)
if result[i][0][j] == result[i][1][k]:
check[i] += 1
else:
if (result[i][0][j] == "_") or
(result[i][1][k] == "_"):
check[i] -= 1
else:
check[i] -= 2
j += 1
k += 1
z = max(check[0], check[1], check[2])
if z == check[0]:
seq1 = result[0][0]
Висновок: за допомогою програми, створеної у процесі виконання даної
лабораторної роботи ми спростили задачу вибору найоптимальнішого методу
вирівнювання двох посліідовностей.