Мелодии записаны строками нот, например "CDEFG". Общий мотив — самая длинная общая подпоследовательность: ноты идут в том же порядке, но не обязательно подряд. Допишите common_motif_length(a, b): функция заполняет таблицу и возвращает длину общего мотива. Пропуски помечены # TODO.
common_motif_length("CDEFGAB", "CEGBD") # 4: C E G B
common_motif_length("AAAA", "AA") # 2
common_motif_length("CDE", "FGA") # 0Заготовка задачи обновилась с тех пор, как вы сохранили свой код.
Сбросить редактор к заготовке? Ваш код будет удалён.
def common_motif_length(a: str, b: str) -> int:
"""Длина самой длинной общей подпоследовательности строк a и b."""
table = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
for i in range(1, len(a) + 1):
for j in range(1, len(b) + 1):
if a[i - 1] == b[j - 1]:
# TODO: ноты совпали
pass
else:
# TODO: ноты не совпали
pass
return table[len(a)][len(b)]Вывод обрезан: показаны первые строки.
def test_example():
"""CDEFGAB и CEGBD → 4"""
got = common_motif_length("CDEFGAB", "CEGBD")
assert got == 4, f"ожидалось 4, получено {got!r}"
def test_repeats():
"""AAAA и AA → 2"""
got = common_motif_length("AAAA", "AA")
assert got == 2, f"ожидалось 2, получено {got!r}"
def test_nothing_common():
"""Нет общих нот → 0"""
got = common_motif_length("CDE", "FGA")
assert got == 0, f"ожидалось 0, получено {got!r}"
def test_empty():
"""Пустая мелодия → 0"""
assert common_motif_length("", "CDE") == 0, "пустая a"
assert common_motif_length("CDE", "") == 0, "пустая b"
assert common_motif_length("", "") == 0, "обе пустые"
def test_identical():
"""Одинаковые мелодии → длина мелодии"""
got = common_motif_length("GABCD", "GABCD")
assert got == 5, f"ожидалось 5, получено {got!r}"
def test_not_contiguous():
"""Подпоследовательность не обязана идти подряд"""
got = common_motif_length("CXDXE", "CDE")
assert got == 3, f"ожидалось 3, получено {got!r}"
def test_symmetric():
"""Порядок аргументов не важен"""
a, b = "ABCBDAB", "BDCABA"
assert common_motif_length(a, b) == common_motif_length(b, a) == 4, "ожидалось 4 в обе стороны"Можно решать и в своём редакторе: «Скопировать с тестами» и запустите python3 melody_subsequence.py — тесты те же, результат покажет ✓ / ✗ и итог.
Ячейка table[i][j] — длина самой длинной общей подпоследовательности первых i нот a и первых j нот b.
Ноты совпали: значение по диагонали плюс 1 — table[i - 1][j - 1] + 1.
Не совпали: берём лучшее из двух соседей — max(table[i - 1][j], table[i][j - 1]).
def common_motif_length(a: str, b: str) -> int:
"""Длина самой длинной общей подпоследовательности строк a и b."""
table = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
for i in range(1, len(a) + 1):
for j in range(1, len(b) + 1):
if a[i - 1] == b[j - 1]:
table[i][j] = table[i - 1][j - 1] + 1
else:
table[i][j] = max(table[i - 1][j], table[i][j - 1])
return table[len(a)][len(b)]