Структуры данных и алгоритмы (1021739), страница 44
Текст из файла (страница 44)
1) + 2 с начальным значением А(1, 1) = А(А(0, 1), 0) = .А(1, О) = 2. Отсюда следует, что А(х, 1) = 2х для всехх > 1. Другими словами, А(х, 1) — это "умножение на 2". Аналогично, для у = 2 их > 1 получим А(х, 2) = А(А(х - 1, 2), 1) = 2А(х -1,2) и АЦ1, 2) = А(А(0, 2), 1) =А(1, 1) = 2. Таким образом, А(х, 2) = 2х.
Подобным образом можно показать, чтоА(х, 3) = 22 2 ("этажерка" из х двоек). В свою очередь А(х, 4) растет так быстро, чтоэтот рост нельзя показать с помощью обычной математической записи.Функцию Аккермана одной переменной можно также определить какА(х) — А(х, х). Тогда функция а(л) является псевдообратной к функции А(х). Точнее,174ГЛАВА 5. СПЕЦИАЛЬНЫЕ МЕТОДЫ ПРЕДСТАВЛЕНИЯ МНОЖЕСТВо(п) равна наименьшему х такому, что п < А(х). Например, А(1) = 2, поэтому о(1) =а(2) = 1. Аналогично, А(2) = 4, отсюда следует, что а(3) = а(4) = 2.
Далее, А(3) = 8,поэтому а(5) = ... = а(8) = 3.Может показаться, что ос(и) растет хоть и медленно, но все-таки заметно. Однакоуже А(4) — это последовательное возведение числа 2 во вторую степень 65 536 раз(т.е. "этажерка" из 65 536 двоек). Поскольку log(A(4)) является "этажеркой" из65 535 двоек, то мы не можем даже точно прочитать значение А(4) или определить,какова разрядность этого числа. Поэтому <х(л) < 4 для всех "обозримых" целых п.
Итем не менее о(п), в принципе, может достигать значений 5, 6, 7, ..., более того, а(л)невообразимо медленно, но все-таки стремится к бесконечности.5.6. АТД с операторами MERGE и SPLITПусть S — множество, элементы которого упорядочены посредством отношения "<". Оператор разбиения SPLIT(S, Si, S2, х) разделяет множество S на два множества: Si = {а | а е S и а < х} и S2 = {а \ а е S и а > х]. Множество S после разбиения не определено (если не оговорено, что оно принимает значение Si или S2). Можно привести много различных ситуаций, когда необходимо разделить множествопутем сравнения всех его элементов с одним заданным значением. Одна из таких ситуаций рассмотрена ниже.Задача наибольшей общей подпоследовательностиПодпоследовательность последовательности х получается в результате удалениянескольких элементов (не обязательно соседних) из последовательности х.
Имея двепоследовательности х и у, наибольшая общая подпоследовательность (НОП) определяется как самая длинная последовательность, являющаяся подпоследовательностьюкак х, так и у.Например, для последовательностей 1, 2, 3, 2, 4, 1, 2 и 2, 4, 3, 1, 2, 1 НОП составляет подпоследовательность 2, 3, 2, 1, как показано на рис. 5.14. В этом примересуществуют и другие НОП, в частности 2, 3, 1, 2, но нет ни одной общей подпоследовательности длиной 5.•Рис.
5.14. Наибольшая общаяподпоследовательностьСуществует команда UNIX diff, которая, сравнивая файлы строка за строкой, находит наибольшую общую подпоследовательность, при этом рассматривая каждуюстроку файла как отдельный элемент подпоследовательности (т.е. здесь целая строкаявляется аналогом целых чисел из примера рис. 5.14). После выполнения командыdiff строки, не вошедшие в НОП, могут быть удалены, изменены или перемещены изодного файла в другой. Например, если оба файла являются версиями одной и тойже программы, выполненными с разницей в несколько дней, то оператор diff, скореевсего, найдет расхождения в этих версиях.Существуют различные способы решения задачи НОП, которые требуют выполненияпорядка О(п2) шагов для последовательностей длиной п.
Команда diff использует дифференцированную стратегию, которая работает хорошо, если файлы не имеют слишкомбольших повторений в строках. Например, в программах обычно много повторяющихсястрок "begin" и "end", но другие строки не должны повторяться также часто.5.6. АТД С ОПЕРАТОРАМИ MERGE И SPLIT175Алгоритм, использующий команду diff для поиска НОП, можно применить в эффективной реализации множеств с операторами MERGE и SPLIT. В этом случае время выполнения алгоритма поиска НОП составит О(р logra), где п — максимальноечисло строк в файле, ар — число пар позиций с совпадающими строками, когда одна позиция из одного файла, а другая из другого.
Например, для последовательностей из рис. 5.14 число р равно 12. Две единицы в каждой последовательности образуют 4 пары, три двойки в верхней последовательности и две в нижней дадут 6 пар,а тройки и четверки — еще 2 пары. В самом худшем случае р может иметь порядок' га2, тогда алгоритм поиска НОП будет выполняться за время О(га2 logn). На практикер обычно близко к и, поэтому можно ожидать время выполнения порядка О(п logn).Перед началом описания алгоритма предположим, что есть две строки(последовательности) элементов А = a\a2...an и В = bib2...bm, для которых ищетсяНОП. Первым шагом алгоритма будет составление для каждого элемента а спискапозиций строки А, на которых стоит этот элемент.
Таким способом определяетсямножество PLACES(a) = { i \ a = at }. Для вычисления множеств PLACES(a) можносоздать отображение из множества элементов в заголовки списков позиций. При использовании хеш-таблиц можно вычислить множества PLACES(a) в среднем за О(п)"шагов", где "шаг" — это действия, выполняемые при обработке одного элемента.Время, затрачиваемое на выполнение одного "шага", будет константой, если элемент,например, является символом или числом. Но если элементы в последовательностяхА та В являются текстовыми строками, то время выполнения "шага" будет зависетьот средней длины текстовых строк.Имея построенные множества PLACES(a) для каждого элемента а последовательности А, можно приступать непосредственно к нахождению НОП.
Упрощая изложение материала, мы покажем только, как определить длину НОП, оставляя в качестве упражнения построение конкретных НОП. Алгоритм будет по очереди просматривать все bj, где jпробегает значения 1, 2, ..., т. После обработки очередного Ь} мы должны для каждогоi от 0 до и знать длину НОП для последовательностей a tо( и blt ..., bj.Значения позиции группируются в множества Sk (k = О, 1, .... л), состоящие извсех целых чисел (позиций) i таких, что существует НОП длины k для последовательностей ai, ..., а,- и &J, ..., bj.
Отметим, St всегда являются множествами последовательных целых чисел и для любого k числа в St+1 больше, чем в S/,.Пример 5.8. Вернемся к последовательностям рис. 5.14, и пусть j= 5. Очевидно,что множество S0 состоит только из 0 (т.е. никакой элемент из первой последовательности не сравнивается с первыми пятью элементами (24312) из второй последовательности, поэтому НОП имеет длину 0). Если мы возьмем первый элемент из первой последовательности и сравним его с пятью элементами 24312 второй последовательности, то получим НОП длины 1. Если возьмем первые два элемента 12 изпервой последовательности, то получим НОП длины 2. Но первые три элемента 123при сравнении с элементами 24312 все равно дадут НОП длины 2.
Продолжая этотпроцесс, получим S0 = {0}, Sl = {!}, S2 = {2, 3}, S3 = {4, 5, 6} и S4 = {7}. ППредположим, что мы имеем множества Sk для (j - 1)-й позиции второй последовательности и теперь хотим изменить их для позиции j. Рассмотрим множествоPLACES(by). Для каждого г из PLACES(fy) определим, можно ли построить какуюлибо НОП путем добавления совпадения аг с bj к ранее построенным НОП дляaia r _i и bi, ..., bj.
Если оба числа г - 1 и г входят в множество SA, тогда все числа s, s > г из S4 перейдут в множество Sv+1 при добавлении Ь/. Это следует из того,что если есть k совпадений между подпоследовательностями а1( ..., о,._! и u l f ..., 6y_ltто добавление совпадения между аг и bj увеличит общее число совпадений наединицу. Таким образом, для преобразования множеств S/, и St+i следует выполнить такие действия.1.Применить оператор FIND(r) для нахождения множества St.2.Если FIND(r - 1) * St, тогда при добавлении совпадения 6, и аг новые НОП не образуют, множества Sj и, SA+1 не изменяются, и надо пропустить следующие шаги.176ГЛАВА 5. СПЕЦИАЛЬНЫЕ МЕТОДЫ ПРЕДСТАВЛЕНИЯ МНОЖЕСТВ3.Если FIND(r - 1) = Sk, то применяется оператор SPLIT(St, St, S\, r) для отделения от множества S» тех чисел, которые больше или равны г.4.
Для перемещения "отделенных" элементов в множество S^+i применяется оператор MERGE(S't, St+1, Sm).Следует первыми рассмотреть большие позиции из множества PLACES(fy). Чтобыувидеть, почему надо это делать, предположим, например, что множество PLACES(fy)содержит числа 7 и 9 и до ввода в рассмотрение элемента bt имеем S3 = {6, 7, 8, 9} иS4 = {10, 11}.Если мы сначала рассмотрим позицию 7 перед позицией 9, то множество S3 надобудет разбить на множества S3 = {6} и S'3 = {7, 8, 9}, затем преобразовать множествоS4: S4 = {7, 8, 9, 10, 11}.
Если затем рассмотреть позицию 9, то множество S4 разбиваем на множества S4 = {7, 8} и S'4 = {9, 10, 11}, последнее множество сливается смножеством S5. Таким образом, позиция 9 переместилась из множества S3 в множество S5 только при рассмотрении одного элемента из второй последовательности, чтоневозможно. Это означает, что в созданную НОП длины 5 включены совпадения bj ис а7, и с а9 одновременно, что является безусловной ошибкой.В листинге 5.15 показан эскиз алгоритма построения множеств S* при прохождении по элементам второй последовательности.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
