Данные в файле лежат в определенном порядке, то есть образуют последовательность.
В общем случае длина последовательности неизвестна, так как в ОС Линукс файл — это не только данные на диске, но и, например, данные, поступающие с какого-либо устройства.
Рассмотрим следующую задачу обработки данных, находящихся в файле. Количество данных неизвестно и может быть очень большим, так что их невозможно поместить в память. Мы можем прочитать данные только один раз и мы должны для прочитанных данных вычислять некую характеристику.
Получается, что сразу после считывания очередного элемента мы должны перевычислить эту нужную характеристику.
Вопрос. Как это сделать, если все предыдущие данные нам уже недоступны?
Ответ. Можно попробовать вычислить новое значение нужной характеристики, пользуясь старым ее значением и данными, прочитанными на последнем шаге.
Пример 1. Количество чисел в файле. Зная количество прочитанных чисел, всегда можно узнать новое количество прочитанных чисел после считывания очередного числа: достаточно прибавить 1 к старому.
Введем понятие индуктивной функции на последовательности.
Пусть:
1) X – произвольный алфавит, какое-то конечное или бесконечное множество, например, множество букв русского языка или множество действительных чисел;
2) Ω(X) или просто Ω – пространство всех конечных последовательностей над X, т.е. Ω = { x1x2...xn: n ∈ Z+, xi ∈ X ∀ i ∈ 1...n };
3) ∆ - пустая последовательность, не содержащая ни одного элемента;
4) Ωk(X), или просто Ωk, - пространство конечных последовательностей длины не менее k, т. е. Ωk = { x1x2...xn : n ⩾ k, xi ∈ X}; таким образом, Ω = Ω0 ⊃ Ω1 ⊃ Ω2 ⊃ …;
5) *: Ω*X → Ω – операция добавления (дописывания) элемента в конец последовательности, т.е. x1x2...xn * x = x1x2...xnx, ∆ * x = x и т.п.
Определение. Функция F: Ω → Y называется индуктивной, если F(ω * x) можно вычислить, зная F(ω) и x, т.е. если
∃ G: Y * X → Y: ∀ ω ∈ Ω, x ∈ X F(ω * x) = G(F(ω), x)
Примеры индуктивной функции:
1) Число элементов последовательности
2) Сумма элементов числовой последовательности
3) Максимальный элемент числовой последовательности
4) Число нулевых элементов числовой последовательности
Примеры неиндуктивных функций:
1) Число максимальных элементов числовой последовательности
Определение. Функция F: Ω → Y называется индуктивным расширением функции f: Ω → Yf, если
a) F индуктивна;
b) ∃ π: Y → Yf такое, что ∀ω∈Ω f(ω) = π(F(ω))
Пример индуктивного расширения.
Рассмотрим функцию «число максимальных элементов последовательности». Эта функция не индуктивна: для вычисления f(ω*x) надо знать максимальный элемент ω.
Рассмотрим новую функцию:
F: Ω → Z+ * R, F(ω) = (f(ω), max(ω)),
где max: Ω → R – функция, сопоставляющая каждой последовательности максимум ее элементов, max(∆) = -∞.
Зная f(ω), max(ω) и x, можно найти и f(ω, x), и max(ω*x), то есть F – индуктивная функция.
Очевидно также, что ∀ω∈Ω, зная F(ω), можно найти f(ω) – достаточно просто «забыть» max(ω).
Таким образом, F – индуктивное расширение f и f можно вычислить так:
P.встать в начало
y := 0; m := -∞
цикл ∀x∈непрочитанной части P выполнять
выбор
при x < m => ничего не делать
при x == m => y := y + 1
при x > m => y:=1; m:=x
конец выбора
конец цикла
ответ := y
Пример 2. Программа на языке C, вычисляющая количество максимальных чисел в файле.
#include <stdio.h>
int main(void) {
FILE *IN;
double x, xMax;
int nMax;
IN = fopen(“tmp.dat”, “r”);
if (IN == NULL) {
printf(“File not opened\n”);
return -1;
}
if (fscanf(IN, “%lf”, &xMax) != 1) {
fclose(IN);
printf(“File is empty\n”);
return -1;
}
nMax = 1;
while (fscanf(IN, “%lf”, &x) == 1) {
if (x > xMax) {
xMax = x;
nMax = 1;
}
else if (x < xMax); /* Пустой оператор «;» - ничего не делать */
else {
++nMax;
}
}
fclose(IN);
printf(“Number of max numbers: %d\n”, nMax);
return 0;
}
1. Кушниренко А.Г., Лебедев Г.В. Программирование для математиков: Учеб. пособие для вузов — М.: Наука. Гл.ред.физ.-мат.лит., 1988