ФБТ БИ 2курс / ПОСЛЕДНЯЯ
.docxЛабораторна робота №8
Мета роботи: визначити найоптимальніший метод вирівнювання двох послідовностей
Реалізація алгоритму:
s1 = input("Введіть першу послідовність: ")
s2 = input("Введіть другу послідовність: ")
#Глобальне
def _global(s1, s2):
p = []
way = []
for i in s1:
row = []
way_row = []
for j in s2:
row.append(0)
way_row.append("")
p.append(row)
way.append(way_row)
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"
x = len(s1) - 1
y = len(s2) - 1
res1 = res2 = ""
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
while x:
res1 = s1[x]+res1
res2 = " " + res1
x = x - 1
while y:
res1 = " " + res1
res2 = s2[y] + res2
y = y - 1
ret = [res1, res2]
return ret
#Локальне
def local(s1, s2):
p = []
way = []
for i in s1:
row = []
way_row = []
for j in s2:
row.append(0)
way_row.append("")
p.append(row)
way.append(way_row)
for y in range(len(s2)):
for x in range(len(s1)):
if (s1[x] == s2[y]):
p[x][y] = p[x-1][y-1] + 1
m = max([a for b in p for a in b])
for x in range(len(s1)):
for y in range(len(s2)):
if p[x][y] == m:
xmax = x
ymax = y
res1 = res2 = ""
while m:
res1 = s1[xmax] + res1
res2 = s2[ymax] + res2
xmax = xmax - 1
ymax = ymax - 1
m = m - 1
ret = [res1, res2]
return ret
#Псевдоглобальне
def pseudo(s1, s2):
s1 = "_" + s1
s2 = "_" + s2
p = []
for i in s1:
row = []
for j in s2:
row.append(0)
p.append(row)
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)
x = len(s1)-1
y = len(s2)-1
lastrow = []
lastcol = []
for i in range(len(s2)):
lastrow.append(p[x][i])
for j in range(len(s1)):
lastcol.append(p[j][y])
maxrow = max(lastrow)
maxcol = max(lastcol)
res1 = res2 = ""
for i in range(len(s2)):
if lastrow[i] == maxrow:
ymax = i
xmax = x
res1 = ""
res2 = ""
while xmax and ymax:
res1 = s1[xmax] + res1
res2 = s2[ymax] + res2
xmax = xmax - 1
ymax = ymax - 1
if ymax == 0:
while xmax:
res1 = s1[xmax] + res1
res2 = "_" + res2
xmax = xmax - 1
if xmax == 0:
while ymax:
res1 = "_" + res1
res2 = s2[ymax] + res2
ymax = ymax - 1
for j in range(len(s1)):
if lastcol[j] == maxcol:
ymax = y
xmax = j
res1 = ""
res2 = ""
while xmax and ymax:
res1 = s1[xmax] + res1
res2 = s2[ymax] + res2
xmax = xmax - 1
ymax = ymax - 1
if ymax == 0:
while xmax:
res1 = s1[xmax] + res1
res2 = "_" + res2
xmax = xmax - 1
if xmax == 0:
while ymax:
res1 = "_" + res1
res2 = s2[ymax] + res2
ymax = ymax - 1
ret = [res1, res2]
return ret
#Результат
result = [_global(s1, s2), local(s1, s2), pseudo(s1, s2)]
check = [0, 0, 0]
j = k = 0
for i in range(3):
while (j < len(result[i][0])) and (k < len(result[i][1])):
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]
seq2 = result[0][1]
inp = "глобальне вирівнювання"
elif z == check[1]:
seq1 = result[1][0]
seq2 = result[1][1]
inp = "локальне вирівнювання"
elif z == check[2]:
seq1 = result[2][0]
seq2 = result[2][1]
inp = "псевдоглобальне вирівнювання"
print("Результуюча послідовність 1: " + seq1)
print("Результуюча послідовність 2: " + seq2)
print("Вага: " + str(z))
print("Найоптимальніше " + inp)
Висновок: за допомогою програми, створеної у процесі виконання даної лабораторної роботи ми спростили задачу вибору найоптимальнішого методу вирівнювання двох посліідовностей.