Пусть M -- некоторое множество. Функция f, аргументами которой являются последовательности элементов множества M, а значениями -- элементы некоторого множества N, называется индуктивной, если ее значение на последовательности можно восстановить по ее значению на последовательности и по x[n], то есть если существует функция , для которой
Схема алгоритма вычисления индуктивной функции:
k := 0; f := f0; {инвариант: f - значение функции на <x[1],...,x[k]>} while k<>n do begin | k := k + 1; | f := F (f, x[k]); end;
Здесь f0 -- значение функции на пустой последовательности (последовательности длины 0). Если функция f определена только на непустых последовательностях, то первая строка заменяется на
Если функция f не является индуктивной, полезно искать ее индуктивное расширение -- такую индуктивную функцию g, значения которой определяют значения f (это значит, что существует такая функция t, что при всех ). Можно доказать, что среди всех индуктивных расширений существует минимальное расширение F (минимальность означает, что для любого индуктивного расширения g значения F определяются значениями g).
1.3.1. Указать индуктивные расширения для следующих
функций:
(а) среднее арифметическое последовательности вещественных чисел;
(б) число элементов последовательности целых чисел, равных ее максимальному элементу;
(в) второй по величине элемент последовательности целых чисел (тот, который будет вторым, если переставить члены в неубывающем порядке);
(г) максимальное число идущих подряд одинаковых элементов;
(д) максимальная длина монотонного (неубывающего или невозрастающего) участка из идущих подряд элементов в последовательности целых чисел;
(е) число групп из единиц, разделенных нулями (в последовательности нулей и единиц).
Решение:(а) сумма всех членов последовательности; длина;
(б) число элементов, равных максимальному; значение максимального;
(в) наибольший элемент последовательности; второй по величине элемент;
(г) максимальное число идущих подряд одинаковых элементов; число идущих подряд одинаковых элементов в конце последовательности; последний элемент последовательности;
(д) максимальная длина монотонного участка; максимальная длина неубывающего участка в конце последовательности; максимальная длина невозрастающего участка в конце последовательности; последний член последовательности;
(е) число групп из единиц, последний член.
1.3.2 (Сообщил Д.В. Варсанофьев) Даны две последовательности целых чисел
и .Выяснить, является ли вторая последовательность
подпоследовательностью первой, то есть можно ли из первой
вычеркнуть некоторые члены так, чтобы осталась вторая. Число
действий порядка .
Вариант 1. Будем сводить задачу к задаче меньшего размера.
n1:=n; k1:=k; {инвариант: искомый ответ <=> возможность из x[1]..x[n1] получить y[1]..y[k1] } while (n1 > 0) and (k1 > 0) do begin | if x[n1] = y[k1] then begin | | n1 := n1 - 1; | | k1 := k1 - 1; | end else begin | | n1 := n1 - 1; | end; end; {n1 = 0 или k1 = 0; если k1 = 0, то ответ - да, если k1<>0 (и n1 = 0), то ответ - нет} answer := (k1 = 0);
Мы использовали то, что если и -- подпоследовательность , то -- подпоследовательность .
Вариант 2. Функция
[максимальное
k1, для которого есть
подпоследовательность
] индуктивна.
1.3.3. Даны две последовательности
целых чисел. Найти максимальную длину
последовательности, являющейся подпоследовательностью обеих
последовательностей. Количество операций порядка .
1.3.4. (из книги Д. Гриса) Дана последовательность целых чисел
. Найти максимальную длину ее
возрастающей подпоследовательности (число действий порядка
).
n1 := 1; k := 1; u[1] := x[1]; {инвариант: k и u соответствуют данному выше описанию} while n1 <> n do begin | n1 := n1 + 1; | ... | {i - наибольшее из тех чисел отрезка 1..k, для кото- | рых u[i] < x[n1]; если таких нет, то i=0 } | if i = k then begin | | k := k + 1; | | u[k+1] := x[n1]; | end else begin {i < k, u[i] < x[n1] <= u[i+1] } | | u[i+1] := x[n1]; | end; end;Фрагмент ... использует идею двоичного поиска; в инварианте условно полагаем u[0] равным минус бесконечности, а u[k+1] -- плюс бесконечности. Наша цель: .
i:=0; j:=k+1; {u[i] < x[n1] <= u[j], j > i} while (j - i) <> 1 do begin | s := i + (j-i) div 2; {i < s < j} | if x[n1] <= u[s] then begin | | j := s; | end else begin {u[s] < x[n1]} | | i := s; | end; end; {u[i] < x[n1] <= u[j], j-i = 1}`
Замечание. Более простое (но не минимальное) индуктивное расширение получится, если для каждого i хранить максимальную длину возрастающей подпоследовательности, оканчивающейся на x[i]. Это расширение приводит к алгоритму с числом действий порядка .
1.3.5. Какие изменения нужно внести в решение предыдущей
задачи, если надо искать максимальную неубывающую
последовательность?