Вся прелесть музыки — в мелодии. (Йозеф Гайдн)
Теория
Музыкальное произведение — это последовательность аккордов, нот или других комбинаций звучаний инструмента. Обычно такие произведения имеют один мотив на участок произведения. В данной лабораторной работе требуется определить, можно ли поданный на вход отрывок произведения определить как участок (развитие) заданного изначально произведения.
Произведение
Для представления музыки будут использоваться буквенные обозначения нот C, D, E, F, G, A, B (До, Ре, Ми, Фа, Соль, Ля, Си++).
Диезные и бемольные звучания опустим. Произведением (мелодией, необязательно звучащей нормально) будет считаться
последовательность из нот. Например: GGCBAG. Однако произведение может делится на такты или подтемы. Для обозначения этого
будет использоваться дефис. Например: GGCBAG-FEF-FFAGFE-DAD.
Как определить соответствие отрывка или нет?
Перед определением соответствует или нет, требуется указать точность совпадения, под точностью подразумевается сколько нот нужно
для определения следующей ноты. Для точности 1 следующей нотой может быть любая, которая шла после неё в оригинальном произведении.
Рассмотрим на примере: GGCBAG-FEА-FFAGFE-DAD. Для того, чтоб поставить ноту А, предыдущей должна быть нота из множества {B, F, D, E}.
Увеличивая точность, мы получаем {CB, -D, FF, FE}. Данное множество показывает, что критерии для выбора усложняются.
Если еще раз увеличить, то там, где идет разделитель мелодии, следующей ноты не будет — {GCB, -FE, -FF, -D}. Вот мы и определили для ноты А с точностью 3 всевозможные варианты.
Конечно, есть и другие варианты определения нот, это на ваш выбор. Однако продолжим рассматривать данный вариант определения.
Для соответствия отрывка произведению - все составленные для нот в отрывке множества должны являться подмножествами множеств из оригинального произведения.
Например, если отрывок FE-GG и точность 2, то данный отрывок будет считаться правильным, а FEF нет.
Как составить алгоритм:
Для составления используйте аналогичный предыдущей лабораторной работе формат, однако если вы используете структуры, то опишите полноценно взаимодействие с ними, например, для добавления элемента в дерево требуется расписать последовательность перемещений к требуемому родительскому узлу, какую информацию добавляете и т.п.
Задача
1 часть Дано оригинальное произведение, отрывок и точность. Требуется определить, принадлежит ли данный отрывок к произведению (учитывая точность). Требуется расписать алгоритм, аналогичный тому, что в теории.
2 часть Дано оригинальное произведение и отрывок. Требуется определить максимальную возможную точность (точность при которой отрывок перестает быть отрывком).
3 часть Сгенерировать мелодию, основываясь на оригинальном произведении. Данная задача является дополнительной, однако может значительно повысить оценку.
Ограничения
Если в предыдущей лабораторной работе было запрещено использовать массивы или сложные функции, неописанные в задаче, то в данной работе главным ограничением является запрет на использование срезов и других строковых сравнений (кроме сравнения на равенство). Если хочется использовать функцию или метод, которые выглядят подозрительно и возможно запрещены - спрашивайте.
Тесты
CCCEEE-ECCCGCEECEGE CCECG-ECE-CCEECG True 1
ADDCDEDAD-DD-DCDAADED-DEDCAEDEEEDD-EADDA AEEDA-ACA-DEA False 1
BE-EEAAAE-AA-EB EEEAA False 2
DCGDBD-EEBBBBGGDG-D-DBDGBGEGBBEE DGEDB-DDD False 2
AAGGBBB-BABBAAABG BABBAA True 2
GBECECC EEECE-CEE-AEAGB False 2
ABAABBABABBA-BAEA-B BAABAB True 2
BGAAG-C-BGFBAACABGB-ACBGAF GACG-AGGFC False 3
CCBC-DBFCEDB CFDBE False 4
CG-EDGDDG-DGGCGEE DEDEGG-ECE False 2
ED-BBCDBEDCE-GBEGBBG-D-ECGDGBGEGC GBEDC True 2