Непейвода Н.Н., Скопин И.Н. Основания программирования
Подождите немного. Документ загружается.
7.2. ПОТОКОВАЯ ОБРАБОТКА
315
#include <math.h>
int N,i,j,k;
int Prime;
int a[1000];
FILE *f;
int main(void) {
f = fopen("prime.txt","r"); //
fscanf(f,"%i:",&k); // Фрагмент, ответственный за
for (i=1;i<=k;i++) // инициализацию массива
a
fscanf(f,"%i",&a[i]); //
fclose(f); //
do {
printf("Write N:");
scanf ("%i",&N);
if (N<=0)
printf("If N <= 0 then there is no prime numbers\n");
else {
if (k>=N) i = a[N];
else {
i=a[k];
while (k<N) {
i+=2;
for (j=2,Prime=true; Prime && a[j]<=sqrt(i); j++)
Prime = i%a[j];
if (Prime) {
a[++k]=i;
printf("%i ", i);
}
}
}
printf("\nIf N = %i - %i\n", N, i);
}
scanf("%c",&N);
}
while (N != ’n’);
{ f = fopen("prime.txt","w"); //
fprintf(f,"%i:",k); // Фрагмент, ответственный за
for (i=1;i<=k;i++) // долговременное хранение
316
ГЛАВА 7. ЦИКЛИЧЕСКИЕ ВЫЧИСЛЕНИЯ
fprintf(f,"%i",a[i]); // полученных результатов
} //
fclose(f); //
return 0;
}
Как и раньше, в этой программе курсивом выделены добавления и измене-
ния текста предыдущей программы. Стоит отметить, что фрагмент, ответ-
ственный за долговременное хранение полученных результатов, может быть
улучшен, так как нет надобности перезаписи файла, когда он фактически не
меняется.
В программе
Prime_Numbers_4
получено отображение массива выявлен-
ных простых чисел на файл. В данном случае файл рассматривается не как
новая структура данных, а просто как способ быстрой инициализации без
необходимости каждый раз пересчитывать старые результаты (ведь никто не
пересчитывает первые несколько десятков знаков числа π).
Вообще говоря, файл также может являться и полноценной структурой
данных, активной единицей. Например, вместо считывания массива можно
заменить все операции обращения к нему операциями поиска в файле. Полу-
чится нечто вроде пополняемого списка простых чисел: либо находим и из-
влекаем нужное, либо добавляем новые простые числа. Это показывает, что
файл является одной из структур данных, естественно соответствующих
потоку. В данном случае файл, как и массив, является машинным предста-
влением предвычисленной функции, но результаты вычислений хранятся в
долговременной памяти.
Такой способ долговременного запоминания подходит для очень боль-
ших чисел, когда размеры используемого “списка” превосходят возможности
оперативной памяти или разрядность используемых типов данных. Кстати,
при таких условиях может оказаться, что имеет смысл вернуться к самой пер-
вой версии программы без запоминания, противопоставив большой объем
(избыточных) вычислений огромному количеству затрачиваемой памяти.
Итак, массивы и файлы являются структурами данных, естественно соот-
ветствующими потокам. А структура, которая теоретически адекватна пото-
ку — потенциально бесконечная последовательность данных — остается для
программ важным призраком, стоящим за частичными представлениями.
Пример 7.2.5. Задача об N максимальных числах.
Цель настоящего примера — продемонстрировать начинающему программи-
7.2. ПОТОКОВАЯ ОБРАБОТКА
317
сту многообразие вариантов решения даже довольно простой задачи. Ситу-
ация, когда разработчик программы вынужден делать выбор того или иного
пути задаваемых вычислений, внешне кажущихся равнозначными, являет-
ся весьма типичной. В то же время далеко не всегда можно сформулировать
ясные критерии такого выбора.
Когда в своей работе программисту приходится отдавать предпочтение
одним решениям перед другими, он, прежде всего, определяет условия функ-
ционирования данного фрагмента программы. Иными словами, он должен
выяснить, как сказывается эффективность фрагмента на пользовательских
характеристиках программы в целом. Из ответа на этот вопрос можно по-
нять:
a) следует ли экономить память;
b) оптимизировать ли время исполнения фрагмента;
c) нужно ли заботиться о компактности программы;
d) каковы требования к интерфейсу данного фрагмента и окружающей его
программной среды;
e) насколько критична наглядность программы в данном месте?
От правильности такой оценки зависит качество создаваемого программного
изделия
7
.
Хотелось бы, чтобы из приводимого ниже материала стало очевидным,
что рассуждения по поводу решаемой задачи могут оказаться не менее полез-
ными для выработки варианта, чем, к примеру, прямой подсчет скорости ра-
боты и занимаемой памяти. Они могут указать на путь, мимо которого легко
пройти при прямолинейном программировании. Даже если такой путь будет
отвергнут, польза от его рассмотрения в том, что он будет отвергнут моти-
вированно. Возможно, что после изменения ситуации
8
отвергнутый подход
окажется предпочтительнее.
И последнее предварительное замечание. Разработка программы — это
не только разработка ее алгоритма, но и, прежде всего, выбор наиболее под-
ходящих структур данных. У начинающего программиста в арсенале пока
7
Следует к тому же отметить, что опытный программист никогда не позволит себе не-
оправданных расходов ресурсов. Сравните с поведением, скажем, программного обеспече-
ния фирмы
Microsoft
, которое занимает все доступные ресурсы.
8
Часто задача динамически меняется в ходе ее решения.
318
ГЛАВА 7. ЦИКЛИЧЕСКИЕ ВЫЧИСЛЕНИЯ
мало вариантов, между которыми приходится выбирать типы переменных,
размещение их в памяти и др. Но даже в этом случае следует подходить к вы-
бору осознанно, чтобы приучить себя к соответствующей дисциплине. Зача-
стую именно выбор структуры данных программы диктует применение того
или иного алгоритма. В то же время процесс выбора далеко не так прямо-
линеен, как это может показаться на первый взгляд. Как правило, приходит-
ся делать множество итераций, прежде чем система из алгоритма и структур
данных станет реализуемой программой. Общего рецепта здесь нет, и можно
надеяться только на выработку ориентиров, совокупность которых в конеч-
ном итоге и определяет программистскую квалификацию разработчика.
Что же касается выбора языка и системы программирования, которые ис-
пользуются для решения задачи, то по важности это вопрос второго порядка.
Если на этот выбор программист повлиять не в состоянии, то ему придется
приспосабливаться к внешним условиям и независимо от предпочтений ра-
ботать с тем, что есть. Иными словами, квалифицированный программист
должен легко адаптироваться к любой среде программирования. Именно
по этой причине в данном разделе мы иллюстрируем разработку програм-
мы, используя не
С/С++
, как ранее, а
Pascal
(стандарт языка). Мы намеренно
опускаем объяснение некоторых конструкций (изучение их — предмет эле-
ментарного самообразования либо особого курса для тех,кто не умеет учить-
ся сам), считая, что их смысл может быть извлечен из контекста при чтении
программы. Впредь мы будем чередовать эти и другие языки, почти произ-
вольно выбирая один или другой, с тем, чтобы у читателя складывались не
стереотипы, а предпочтения.
Рассмотрим простую учебную задачу, которая затем будет обобщена с це-
лью иллюстрации возможных подходов к решению и к анализу вариантов.По
ходу изложения критикуются решения, принимаемые без анализа ситуации,
отмечаются типичные ошибки. Учебная цель примера — дать в простейшей,
модельной, ситуации наглядное представление о том:
a) как можно настраивать программу на условия применения?
b) какие вопросы целесообразно задавать себе при составлении программ?
c) какие мотивации принимаемых и отвергаемых решений обыкновенно со-
провождают развитие алгоритма?
Задача поиска максимального элемента потока чисел, символов или зна-
чений какого-либо другого типа, обладающего операцией отношения срав-
7.2. ПОТОКОВАЯ ОБРАБОТКА
319
нения значений, — классический пример, с которого часто начинают зна-
комиться с задачами на составление алгоритмов. В варианте для чисел она
формулируется следующим образом:
Пусть имеется вводимая последовательность чисел (для определенности, це-
лых, принадлежащих некоторому диапазону, например, от 1 до 1000), посту-
пающих на вход программы одно за другим, —
поток
. Требуется написать
программу, которая из входного потока выбирает и печатает самое большое
число.
Как чаще всего бывает на практике, задача поставлена не совсем точ-
но: не указывается, как формируется поток. Это означает, что постановщик
ее оставляет вопрос о формировании потока на рассмотрение разработчика
программы. Следовательно, мы в праве предложить свой метод. Для просто-
ты будем считать, что поток строится с помощью клавиатурного ввода чисел,
а признаком его конца является ввод числа, которое в указанный диапазон от
1 до 1000 не входит.
В качестве других вариантов формирования потока можно указать, на-
пример, на случайную генерацию чисел с заранее фиксированным (с помо-
щью клавиатурного ввода) количеством элементов потока или с нефиксиро-
ванным количеством элементов. Во втором случае следует предусмотреть,
каким способом генерация потока завершается. Допустимы различные вари-
анты завершения: порождение при генерации потока такого числа, которое в
указанный диапазон от 1 до 1000 не входит, прекращение генерации потока
при нажатии клавиши и др. При выборе случайной генерации целесообразно
позаботиться о том, чтобы пользователь программы был в состоянии просма-
тривать числа потока.
Мы выбрали самый простой метод формирования потока, чтобы не пе-
регружать последующее обсуждение деталями. Тем не менее, настоятельно
советуем читателю запрограммировать все упомянутые выше методы и срав-
нить их с разных точек зрения (простота программы,удобство использования
и др.).
Хотя решение поставленной задачи вы вполне можете выполнить само-
стоятельно (что настоятельно рекомендуется сделать в качестве упражне-
ния), для последующего анализа мы приведем его в виде программы
M11
:
Программа 7.2.6
program M11 (Input, Output);
var A, {
переменная для текущего максимума
}
X : Integer; {
переменная для текущего числа потока
}
320
ГЛАВА 7. ЦИКЛИЧЕСКИЕ ВЫЧИСЛЕНИЯ
begin
if not eof
then begin
{
1.1
} read ( A ); X := A;
while (X > 0) and (X < 1000) and not eof do
begin
read ( X );
{
1.2
} if A < X
then A := X {
текущий максимум надо сменить
}
end;
write ( A )
end;
end.
Приведенное решение не требует обсуждения. Стоит разве что упомянуть о
решении, в котором предварительно входной поток переписывается в мас-
сив. Оно никуда не годится (это типичная ошибка начинающего, неправиль-
но понимающего принцип деления задачи на подзадачи: сначала организо-
вать ввод — подзадача 1, а затем искать максимум — подзадача 2). Крити-
ка такого решения даже не в том, что массив в данном случае — это всегда
ограничение длины потока и дополнительный расход памяти; главное, что
оно предполагает двойной просмотр потока, тогда как решение подзадач це-
лесообразно совместить.
Интересна не сама по себе рассмотренная задача, а ее развитие и обобще-
ния, причем такие, решение которых можно получить из приведенного путем
последовательного уточнения, приспосабливания уже имеющейся “наработ-
ки” для новой задачи.
Предлагается обсудить следующее обобщение задачи:
Написать программу, которая из входного потока выбирает и печатает в по-
рядке возрастания
N
самых больших чисел, где
N
— константа. Если раз-
личных чисел потока меньше
N
, то печатать все найденные числа.
Ее решение — тоже цикл, оно также должно включать запоминание мак-
симумов, но не одного, а сразу нескольких. Таким образом, возникает массив
(будем именовать его
A
). Смена же максимума на новое значение реализует-
ся посредством замены элемента в
A
. Эта идея может быть реализована по-
разному.
Бросается в глаза то, исходное задание
A
(аналог строки 1.1. в программе
7.2. ПОТОКОВАЯ ОБРАБОТКА
321
М11
) можно описать как перепись (разумеется, без повторений) начала вход-
ного потока, а поиск убираемого элемента (см. строку 1.2) — с помощью
просмотра
A
и поиска в нем минимума. При переписи приходится ввести
индекс заполненности
A
(в дальнейшем он обозначается
L
), который растет,
когда место в
A
еще не исчерпано (L < N). Если N невелико, вопрос о це-
не разделения переписи без повторений и просмотра не возникает, и вполне
приемлемо решение, когда работа с
A
организуется прямо, циклом с провер-
ками каждого элемента массива:
Программа 7.2.7
program MN2(Input, Output);
const N = 5; {
значение N = 5 выбрано для определенности
}
var A : array [1..N] of Integer;{
переменная для текущих максимумов
}
X, {
переменная текущего числа из потока
}
L, {
индекс заполненности массива
A }
i : Integer; {
индекс для просмотра массива
A }
begin
if not eof
then
begin
L := 0;
while (L < N) and (X > 0) and (X < 1000) and not eof do
begin
read ( X ); i := 1;
while (i <= L) and (X <> A[i]) do i := i + 1;
if i > L
then { Х
в
A
не найден
}
begin L := L + 1; A[L] := X
end;
end; {
массив
A
заполнен
}
while (X > 0) and (X < 1000) and not eof do
begin
read ( X ); i := 1;
while (i <= L) and (X <= A[i]) do i := i + 1;
if i <= L {
удаляемый элемент имеется?
}
then A[i] := X
end;
for i := 1 to L do write ( A[i] )
322
ГЛАВА 7. ЦИКЛИЧЕСКИЕ ВЫЧИСЛЕНИЯ
end;
end.
Однако с ростом N эффективность программы будет падать из-за того, что
приходится просматривать все большее и большее количество чисел. Возни-
кает желание улучшить просмотр, а заодно и перепись. Это можно сделать
при специальной организации
A
: использовать упорядочивание при заполне-
нии.
Идея упорядочивания весьма продуктивна, а потому ее обсуждение будет
проведено специально. Здесь же хотелось бы оценить первоначальный план
с другой стороны: оправдана ли предварительная перепись? При вниматель-
ном рассмотрении становится ясно, что заполнение
A
можно программно со-
вместить с просмотром и поиском убираемого элемента. Для этого надо ис-
пользовать индекс заполненности
L
как границу просмотра. Программа
MN3
,
реализующая эту идею, приводится ниже.
Программа 7.2.8
program MN3(Input, Output);
const N = 5;
var A : array [1..N] of Integer;
X,
L,
i, j : Integer; {
индексы для просмотра массива
A }
begin
if not eof
then
begin
L := 0;
while (X > 0) and (X < 1000) and not eof do
begin
read ( X ); i := 1;
while (i <= L) and (X <= A[i]) do i := i + 1;
if i <= L
then
if X <> A[i] {
исключение повторений
}
then begin { A
должен быть модифицирован, найден
}
j := i + 1; {
кандидат на удаление
}
while (j <= L) and (X < A[j]) do
7.2. ПОТОКОВАЯ ОБРАБОТКА
323
{
проверка остатка массива
A.
Здесь используется то, что
}
{
при ложности первого условия второе не проверяется!
}
j := j+1;
if L < N then L := j; {
пополнение
}
A[j] := X; {
модификация
}
end
else {
кандидат на удаление в
A
не найден
}
if L < N {
нужно ли пополнение
A
?
}
then begin L := i; A[i] := X end;
end;
while (X > 0) and (X < 1000) do
begin
read ( X ); i := 1;
while (i <= L) and (X < A[i]) do i := i + 1;
if i <= L {
удаляемый элемент имеется?
}
then A[i] := X
end;
for i := 1 to L do write ( A[i] )
end;
end.
При росте N программа
MN2
все еще будет неэффективной из-за увеличения
накладных расходов на полный просмотр массива
A
. Как уже отмечалось,
это можно поправить за счет упорядочивания массива. Предварительно от-
метим, что формулировка решаемой задачи не совсем точна: она оставляет
свободу разработчику в выборе того, в какой последовательности надо вы-
водить полученные результаты. Если это безразлично, то решение вопроса,
использовать упорядочивание или нет, разработчик программы вправе моти-
вировать только логикой построения алгоритма и оценкой эффективности. В
противном случае, когда требуется вывести результат в том или ином поряд-
ке (для определенности — по возрастанию), необходимость упорядочивания
диктуется условием задачи. И тогда возможное решение, связанное с допол-
нительным упорядочиванием массива
A
после завершения работы с потоком,
становится совершенно неприемлемым: оно приведет к заведомой неэффек-
тивности программы.
Упорядочивание массива
A
при заполнении, кроме уже рассмотренного
пополнения числа элементов
A
, требует реализовать вставку
X
внутрь мас-
сива
A
в двух вариантах:
324
ГЛАВА 7. ЦИКЛИЧЕСКИЕ ВЫЧИСЛЕНИЯ
a) когда
A
не заполнен, и
b) когда
A
заполнен.
Вставка в конец незаполненного
A
есть частный случай первого варианта.
При принятой для рассматриваемой задачи стратегии хранения накапливае-
мых максимальных элементов потока с помощью массива, а не какой-либо
иной структуры данных, оба варианта требуют сдвига части массива (пере-
писи) для освобождения места под
X
. В будущем мы изучим структуры дан-
ных, использование которых позволит избежать такой переписи, и именно от
них можно ожидать существенного повышения эффективности программы.
Однако это уже будут другая стратегия и другие методы программирования,
обсуждение которых стоит отдельного разговора. В рассматриваемой ниже
программе
MN3
используется простейшее из упорядочиваний, связанное с
непосредственным заполнением массива из потока.
Для определенности применяется упорядочивание по возрастанию. Чи-
тателю предлагается самостоятельно разработать программу, в которой мас-
сив
A
упорядочивается по убыванию, и сравнить эффективность двух реше-
ний задачи (есть основания полагать, что качество второго решения окажется
несколько выше).
Если
i
— индекс такого элемента массива
A
, что
A
[
i
] <
X
и при
k
>
i
все
A
[
k
] >
X
, то
• в варианте (a) местоположение для размещения
X
в
A
определяется ин-
дексом i+1, требуемый сдвиг есть перепись
A[i+1]
, ...,
A[L]
в
A[i+2]
, ...,
A[L+1]
, а
L
увеличивается на единицу;
• в варианте (b) местоположение для размещения
X
в
A
определяется ин-
дексом
i
, требуемый сдвиг есть перепись
A[2]
, ...,
A[i]
в
A[1]
, ...,
A[i-1]
.
Комментария требует использование признака
incl
для проверки завершения
цикла поиска возможного местоположения
X
в
A
. Этот признак остается лож-
ным во всех случаях, когда ситуация, связанная с необходимостью модифи-
кации
A
остается неопределенной, т. е. когда требуется продолжить поиск
текущего
X
.
Еще одно замечание, касающееся приводимой ниже программы. Всегда
следует стремиться к тому, чтобы более ранние проверки как можно опреде-
леннее выявляли различные пути вычислений. Читателю предлагается опре-
делить, что порядок выполняемых проверок существенен.