скачать doc
2. ИНДУКТИВНЫЕ ФУНКЦИИ НА ПОСЛЕДОВАТЕЛЬНОСТЯХ 0 17 1
2.1. Последовательности и файлы 17 1
2.2. Индуктивные функции 20 4
2.3. Стационарные значения индуктивных функций 22 6
2.4. Индуктивные расширения функций 23 7
2.5. Примеры задач с индуктивными функциями 24 8
.
3. ИНДУКТИВНЫЕ ФУНКЦИИ НА ПОСЛЕДОВАТЕЛЬНОСТЯХ
3.1. Последовательности и файлы
Пусть X – произвольный алфавит (конечное множество). Рассмотрим последовательности символов из этого алфавита: x1 x2 … xn (xi X). Пустую последовательность обозначим . Пусть:
(X) или для краткости просто пространство всех конечных последовательностей над X, т. е.
(X) = {x1 x2 … xn: nN0, xi X i1..n},
при этом ;
k(X) или для краткости просто k пространство конечных последовательностей длины не менее k, т. е.
k(X) = {x1 x2 … xn: n k, nN0, xi X i1..n};
таким образом, = 0 1 2 ... .
Определим операцию postfix: X добавления элемента в конец последовательности, т. е. если = x1 x2 … xn, то postfix(, x) = x1 x2 … xn x , а postfix(, x) = x. Иногда эту операцию удобнее записывать в инфиксной форме, используя для нее специальный знак, например «*», т. е. postfix(, x) = * x. В этих обозначениях * x = x1 x2 … xn x и * x = x. Если k, то * x k + 1.
Тогда конструктивно последовательность можно определить так:
1) есть последовательность;
2) если последовательность, то и * x последовательность;
3) ничто другое (кроме пп.1 и 2) не есть последовательность.
Полезно дополнительно определить следующие операции над последовательностями:
first: 1 X, rest: 1 , prefix: X 1,
и если и = x1 x2 … xn, то
first() = x1, rest() = x2 … xn, prefix(first(), rest()) = .
Последовательный файл (или далее просто файл) из записей типа X (file of X) это реализация математического понятия последовательности с ограниченными способами доступа к элементам. Наглядная модель файла представлена на рис. 3.1. Положение ленты относительно головки чтения-записи определяется разбиением ее (ленты) на две части: левую L(F) и пра-
-
L(F)
R(F)
Начало ленты
Лента
Головка
чтения-записи
Метка
конца
файла
Рис. 3.1. Наглядная модель последовательного файла
вую R(F). Кроме того, файл может находиться в одном из трех режимов: неопределенном (n), чтения (r), записи (w). Таким образом, файл можно определить как упорядоченную тройку F = (L(F), R(F), St(F)), где индикатор режимов St(F) {n, r, w}. Состояние файла R(F) = идентифицируется предописанной функцией (предикатом) Eof(F): если R(F) = , то Eof(F) = true, иначе Eof(F) = false (рис. 3.2).
| F: | | | | | | | | | F: | | | | | |
| | | | | | | | | | | | | | | |
| | Eof(F) = false | | | | | Eof(F) = true | ||||||||
Рис. 3.2. Действие функции Eof(F)
Определим основные операции над файлами.
1. Установка режима записи: Rewrite(F). Семантика этой операции задается свойством {true} Rewrite(F) {Eof(F) & (L(F) = ) & (St(F) = w)} и иллюстрируется на рис. 3.3.
| F: | | | | | | | | | F: | | | | | |
| | | | | | | | | | | | | | | |
Рис. 3.3. Установка режима записи Rewrite(F): слева состояние до
операции, справа состояние после операции
2. Запись в файл: Write(F, x). Семантика этой операции (аналога postfix) задается свойством
{(St(F) = w) & Eof(F) & (L(F) = )}
Write(F, x);
{(St(F) = w) & Eof(F) & (L(F)= * x )}
и иллюстрируется на рис. 3. 4.
| F: | | | | | | | | | F: | | | | | |
| | | | | | | | | | | | | | | |
| x: | | | | | | x: | | | ||||||
| | | | | | | | Запись | |||||||
Рис. 3.4. Запись в файл Write(F, x): слева – состояние до операции,
справа – состояние после операции
3. Установка режима чтения: Reset(F). Семантика операции задается свойством {F = } Reset(F) {(L(F) = ) & (R(F) = ) & (St(F) = r)} и иллюстрируется на рис. 3.5.
| F: | | | | | | | | | F: | | | | | |
| | | | | | | | | | | | | | | |
Рис. 3.5. Установка режима чтения Reset(F): слева – состояние
до операции, справа – состояние после операции
| F: | | | | | | | | | F: | | | | | |
| | | | | | | | | | | | | | | |
| x: | | | | | | x: | | | ||||||
| | | | | | | | Чтение | |||||||
Рис. 3.6. Чтение из файла Read(F, x): слева – состояние до операции,
справа – состояние после операции
4. Чтение из файла: Read(F, x). Семантика этой операции задается свойством
{(St(F) = r) & not Eof(F) & (L(F) = ) & (R(F) = )}
Read(F, x)
{(St(F) = r) & (L(F) = *first()) & (R(F) = rest()) & (x = first())}
и иллюстрируется на рис. 3.6.
3.2. Индуктивные функции
Пусть в файле fint записана последовательность целых чисел (Z), требуется найти максимальное из них, т. е. Max(). Программа может быть написана из естественного соображения: читаем последовательность и для каждого очередного элемента x определяем максимальный элемент прочитанной части последовательности. Очевидно, что Max(*x) = max(Max(), x), где max(a, b) обозначает максимальное из двух чисел a и b. Доопределив Max() = , получаем фрагмент программы, вычисляющий Max():
var x, y: Integer; fint: file of Integer; …
Reset(fint); y := 32768; {y := }
while not Eof(fint) do
begin
Read(fint, x);
if x > y then y := x
end {while} {y = Max()}
Инвариантом цикла здесь является соотношение y = Max(L(fint)), а ограничивающей функцией Length(R(fint)).
Функции от последовательностей, подобные рассмотренной, встречаются часто и могут быть названы индуктивными [14], или марковскими [18].
Определение. Функция f: (X) Y называется индуктивной, если f(*x) можно вычислить, зная f() и x, т. е. если существует
G:Y X Y,
такая, что для всех (X), x X выполняется соотношение
f(*x) = G(f(), x).
Рассмотренный пример с Max() записывается в этих обозначениях следующим образом:
f() = Max(), X = Z, f: (Z) Z, G(y, x) = max(y, x).
Еще один пример индуктивной функции:
f = «число положительных элементов последовательности».
Здесь f: (Z) N0. Функция f() индуктивна. Действительно, для всех (Z), x Z имеем f(*x) = G(f(), x), f() = 0, где G: N0Z N0 и
y + 1, если x > 0,
G(y, x) =
y, если x 0.
Индуктивные функции удобно вычислять. Пусть известно значение f0 = f(). Тогда значение fn = f(n), где n = x1 x2 … xn , можно найти так:
1 = 0*x1, f1 = f(1) = G(f0, x1),
2 = 1*x2, f2 = f(2) = G(f1, x2),
…
n = n 1*xn, fn = f(n) = G(fn 1, xn).
Если математическая последовательность представлена в программе файлом fin типа file of X, то эти рекуррентные соотношения можно реализовать в виде следующего фрагмента программы.
| Фактически это схема программ, из которой конкретная программа может быть получена интерпретацией абстрактных типов X и Y, переменных x, y и y0, функции G(y, x). Эта схема имеет инвариант цикла y = f(L(fin)) и ограничивающую функцию Length(R(fin)). | Reset(fin); y := y0; {y0 = f()} while not Eof(fin) do begin Read(fin, x); y := G(y, x) end {while} |
Пример неиндуктивной функции:
f = «число максимальных элементов последовательности».
Пусть, например x R, тогда f: (R) N0. Очевидно, можно положить f() = 0 и записать
1, если x > Max(),
f(*x) = f() + 1, если x = Max(),
f(), если x < Max().
Поскольку для вычисления f(*x) необходимо кроме f() и x знать еще Max(), то функция f не является индуктивной.
Можно ввести формальный критерий индуктивности [14].
Утверждение. Функция f индуктивна тогда и только тогда, когда
, : (f() = f()) (f(*x) = f(*x))
для любого x X.
Для предыдущего примера = (0, 1, 0, 1), = (1, 2, 1, 2), f() = 2, f() = 2. При x = 1 получим f(*x) = 3 и f(*x) = 2, т. е. f(*x) f(*x), и, следовательно, f неиндуктивна.
3.3. Стационарные значения индуктивных функций
Пусть f: (X) Y индуктивная функция, т. е. существует G:Y X Y, такая, что для всех (X), x X выполняется соотношение f(*x) = G(f(), x).
Значение ysY называется стационарным, если ys = G(ys, x) для любого x X.
Пример. Пусть f = «среди элементов (Z) нет нулевых». Здесь f: (Z) Boolean и решение имеет вид f() = true, f(*x) = (f() & (x 0)). Ясно, что f() = false – стационарное значение, так как для любого b: Boolean имеем false & b = false. В этом случае программу можно записать с учетом стационарного значения:
| Reset(fin); y := true; {y = f()} while not Eof(fin) & y do begin Read(fin, x); y := (x 0) end {while} | Здесь оператор y := y & (x 0) заменен на y := (x 0), поскольку в условие продолжения цикла добавлен конъюнктивный член y. В общем случае схема вычисления индуктивной функции, имеющей стационарное значение, такова: |
Reset(fin);
y := y0; {y0 = f()}
while not Eof(fin) & (y стационарное значение) do
begin
Read(fin, x);
y := G*(y, x)
end {while}
Здесь G* либо совпадает с G, либо является ее сужением с учетом выполнения условия «y стационарное значение» в теле цикла.
3.4. Индуктивные расширения функций
Многие функции не являются индуктивными. Это значит, что информация, заключенная в f(), недостаточна для вычисления f(*x). Однако можно определить, какой именно информации не хватает, и попытаться ее получить. Тогда рассмотрим более сложную функцию, чем исходная, но она уже будет индуктивной.
Пример. Пусть f = «число максимальных элементов последовательности». Эта функция уже рассматривалась в 3.2 как пример неиндуктивной функции. В полученные рекуррентные соотношения
1, если x > Max(),
f(*x) = f() + 1, если x = Max(),
f(), если x < Max()
входит еще функция Max(). Если вычислять и ее значение, то на каждом шаге можно будет определять f(*x).
Пусть x R, тогда f: (R) N0. Введем в рассмотрение функцию Max: (R) R*, где R* = R { }, «» идеальный элемент, используемый как значение Max(). Добавляя к соотношению для f(*x) соотношение Max(*x) = max(Max(), x), можно написать следующую программу:
Reset(fin);
y := 0; {y = f()} z := ; {z = Max()}
while not Eof(fin) do
begin
Read(fint, x);
if x > z then begin z := x; y := 1 end
else {x Max()}
if x = z then y := y + 1 else {ничего}
end {while} {y = f() & z = Max()}
Обобщая этот пример, введем понятие индуктивного расширения.
Определение. Функция F: Y называется индуктивным расширением функции f: Yf, если
1) F – индуктивна,
2) h: Y Yf , такая, что для всех : f() = h(F()).
Условие 2 означает, что, зная F(), можно получить f().
3.5. Примеры задач с индуктивными функциями
Пример 1. Вычисление значения полинома, заданного последовательностью коэффициентов по убывающим степеням.
Пусть = x1 x2 … xn 1 xn и p(; t) = x1 t n 1 + x2 t n 2 + ... + xn 1 t + xn.
Рассмотрим f() = p(; t), тогда
f(*x) = x1 t n + x2 t n 1 + ... + xn 1 t2 + xn t + x =
= f() t + x. (3.1)
Из f(1) = x1 = f() t + x1 следует f() = 0 для всех t.
| Эти соотношения лежат в основе следующей программы вычисления значения полинома (t задано). Эту программу естественно назвать схемой Горнера. | Reset(fin); y :=0; {f()=0} while not Eof(fin) do begin Read(fin, x); y := y*t + x end {while} {y = p(; t)} |
Простым и показательным примером практического использования данной вычислительной схемы является чтение натурального числа z, представленного в текстовом файле записью в позиционной системе счисления с основанием q (2 q qmax), т. е. z = <x1 x2 ... xn 1 xn>q , где xi 0..(q 1) для i 1..n и x1 0. Очевидно, что z = x1 q n 1 + x2 q n 2 + ... + xn 1 q + xn и может быть вычислено по схеме Горнера:
| const q = 3; {2 q 10} var x: Char; z: Integer; y: Word; fin: Text; begin Assign(fin, 'Number.dat'); Reset(fin); y :=0; while not Eof(fin) do begin Read(fin, x); z := Ord(x) 48; y := y*q + z end {while}; WriteLn('прочитано число = ', y) end. |
Пример 2. Вычисление значения производной полинома, заданного последовательностью коэффициентов по убывающим степеням.
Можно рассмотреть f1() = pt(; t) как новую функцию и попытаться для неё решить задачу заново, а можно поступить иначе продифференцировать по t уже полученное рекуррентное соотношение (3.1):
[f(*x)]t = [f()]t t + f(),
т. е. f1(*x) = f1() t + f(). Функция f1 неиндуктивна, и следует рассмотреть индуктивное расширение F() = (f1() , f()):
F(*x) = ( f1() t + f(), f() t + x).
Из соотношений f1(1) = [x1]t = 0 = f1(0) t + f(0) = f1() t + 0 для всех t R следует f1() = 0. Тогда для вычисления F() имеем программу
Reset(fin);
y := 0; {f() = 0} y1 := 0; {f1() = 0}
while not Eof(fin) do
begin
Read(fin, x);
y1:= y1*t + y;
y := y*t + x
end {while} {y = f() & y1= f1()}
Полученную программу можно назвать схемой Горнера для вычисления значения производной многочлена.
Пример 3. Вычисление максимальной длины равнины (площадки) в заданной последовательности. Пусть задана последовательность = x1 x2 … xn 1 xn . Площадкой длины k называется отрезок (связная подпоследовательность) равных элементов, т. е. xi = xi + 1 = … = xi + k 1 (при этом либо i = 1, либо xi 1 xi , а также либо xi + k 1 xi + k, либо i + k 1 = n). Функция f = «длина самой длинной площадки в » неиндуктивна. Чтобы показать это, воспользуемся критерием индуктивности. Действительно, пусть
= (1, 1), = (2, 2), f() = 2, f() = 2.
При x = 1 получим f(*x) = 3 и f(*x) = 2, т. е. f(*x) f(*x) , и, следовательно, f неиндуктивна.
Рассмотрим индуктивное расширение:
F() = ( f(), last(), конкурент()),
где last() последний элемент последовательности, а конкурент() длина хвостовой площадки (только площадка, заканчивающаяся последним элементом, может конкурировать с текущим рекордом f()).
Запишем рекуррентные (индуктивные) соотношения:
f(*x) = max(f(), конкурент(*x)),
конкурент() + 1, если x = last(),
конкурент(*x) =
1, если x last(),
last(*x) = x.
Все эти функции на пустой последовательности можно доопределить согласованно с индуктивными соотношениями:
f() = 0, конкурент() = 0, last() = 0.
Тогда получаем программу
Reset(fin);
y := 0; {f() = 0}
z := 0; {z конкурент, z() = 0}
last :=0; {last() любой}
while not Eof(fin) do
begin
Read(fin, x);
if x = last then z := z + 1
else z := 1;
if z > y then y := z;
last := x
end {while}
Пример 4. Вычисление максимальной суммы элементов среди всех отрезков последовательности. Пусть задана последовательность = x1 x2 … xn 1 xn . Требуется вычислить
f() = «сумма элементов отрезка с максимальной суммой»,
где отрезок связная подпоследовательность последовательности .
Пусть S(k, m) = ik..m xi, где 1 k m n. Тогда
f() = max(S(k, m): 1 k m n).
Функция f – неиндуктивна. Действительно, по критерию индуктивности: пусть = (5, 1), = (1, 5), f() = 5, f() = 5, но при x = 1 получим f(*x) = 5 и f(*x) = 6, т. е. f(*x) f(*x), и, следовательно, f неиндуктивна.
Рассмотрим индуктивное расширение F() = ( f(), t()), где роль потенциального конкурента текущему рекорду f() при продолжении последовательности играет t() максимальная сумма среди отрезков, прилегающих к правому концу последовательности, т. е. t() = max(S(j, n): 1 j n).
Вычисление f и t можно проводить следующим образом:
f(*x) = max(f(), t(*x)),
t(*x) = max(x, x + t()),
t() = 0, f() = .
В результате получим программу
const MinInt = 32768; {}
var x, { очередной элемент последовательности }
y, { y = f() }
z: Integer; { z = t() }
fin: Text; { input file}
begin ...
Reset(fin); { L(fin) = }
y := MinInt; z := 0; { y = f(), z = t() }
{ inv: y = f(L(fin)) & z = t(L(fin)) }
{ bound: length(R(fin)) }
while not Eof(fin) do
begin
Read( fin, x );
if z > 0 then z := z + x else z := x;
if z > y then { обновить рекорд } y := z;
end { while }…
end.