Непейвода Н.Н., Скопин И.Н. Основания программирования

Подождите немного. Документ загружается.

7.2. ПОТОКОВАЯ ОБРАБОТКА

295

(функциональная генерация), либо с использованием рекуррентного соотно-

шения:

= a

i−1

∗ a.

Очевидно, что второй способ более эффективен. В данном случае он и более

нагляден из-за того, что нет нужды специально придумывать, как вычислять

степень. Более высокая эффективность рекуррентной генерации по сравне-

нию с функциональной связана с тем, что предшествующие элементы потока

так или иначе должны быть вычислены, и нерационально терять информа-

цию, полученную на предыдущих шагах цикла, если ее можно продуктивно

использовать.

Этот довод совершенно теряет силу, когда не требуется организовывать

поток. Так, если действие извлечения (или вычисления) очередного элемен-

та требует меньше ресурсов по сравнению с рекуррентным счетом, то потеря

прежней информации оправдана. К примеру, при больших i вычисление a

по

формуле exp(i ∗ln(a)) может осуществиться быстрее, чем при циклическом

накоплении результата. Разумеется, это верно только тогда, когда в алгорит-

мы вычисления функций exp и ln не заложена потоковая генерация, эффек-

тивность которой сопоставима с рекуррентным накопительным умножением

i−1

∗ a).

Конец примера 7.2.1.

Рекуррентная генерация очень полезна при решении задач суммирования

или другого накопительного вычисления, связанного с последовательностя-

ми.

Пример 7.2.2. Пусть требуется подсчитать сумму ряда:

S = 1 −

1 ∗ 2

−

1 ∗ 2 ∗ 3

+ ··· + (−1)

1 ∗ 2 ∗ ··· ∗ i

+ ··· .

Два варианта программы приведены в таблице 7.5. Главный недостаток пер-

вого алгоритма: функциональная генерация элементов суммируемого потока

приводит к повторному счету. На каждой итерации внешнего цикла во вну-

треннем цикле заново считаются составляющие членов ряда, предшествую-

щих искомому (генерация локального по отношению к задаче суммирования

потока троек чисел s

, u и f). Вместе с тем, рекуррентное соотношение:

= t

i−1

∗ (−1)

= t

i−1

∗

−a

296

ГЛАВА 7. ЦИКЛИЧЕСКИЕ ВЫЧИСЛЕНИЯ

Плохая программа Хорошая программа

/* Смысл переменных, которые не

прокомментированы см. в хоро-

шей программе

/* Суммирование */

#include <stdio.h>

#include <math.h>

. int main()

I = 0; t =

1; {

S = t; a2 = a *

a; ﬂoat a; // параметр

while ( abs ( t ) > e )

{ ﬂoat a2; // квадрат параметра

++; ﬂoat t = 1; // член ряда

u = 1; // числите

ль ﬂoat S = 1; // сумма

f = 1; // знаменате

ль ﬂoat e; // точность

sn= 1; // переменная для знак

а int I = 0; // номер члена ряда

k = 1; // служебная

переменная printf( "Введите a и e:");

while ( k <= I )

{ scanf ( "%f %f", &a, &e );

sn = - sn; // знак

члена while ( abs ( t ) > e )

a2 = a *

a; {

u = u *

a2 I ++;

f = f /

k; t = - t * a2 / I;

/* Для повышения точности сче-

та вместо I!, которое при больших

I быстро дает переполнение, вы-

числяется 1/I!; что позволяет про-

суммировать большее число чле-

нов ряда

S = S + t;

++; }

} printf("\nСумма ряда = %f\n",S);

t=sn*u*f;S=S+t;}//конец внеш-

него цик

ла

return

(0);

. }

Таблица 7.5. Программа для суммирования ряда

7.2. ПОТОКОВАЯ ОБРАБОТКА

297

показывает, что формирование внутреннего потока (цикла) избыточно.

Конец примера 7.2.2.

Программа из таблицы 7.5 демонстрирует использование и других типовых

приемов программирования. Перечислим некоторые из них, связанные с ци-

клической обработкой:

1. объединение циклов: вместо логически последовательного выполнения

нескольких циклов задается, когда это возможно, цикл с общими вы-

числениями;

2. чистка цикла: вынесение из цикла вычислений, которые на всех ите-

рациях оказываются одинаковыми;

3. повышение точности за счет преобразования формул для вычислений.

4. знакопеременное суммирование. Существует две схемы: умножение на

−1 и использование знакового флага (

F =-F;

7.2.2. Фильтрация потока

Вообще говоря, использование рекуррентной генерации предпочтитель-

нее по сравнению с функциональной, однако далеко не всегда это возможно.

Пример 7.2.3. Пусть требуется напечатать N первых простых чисел (т. е.

делящихся нацело только на себя и на единицу). Функциональная генера-

ция для решения задачи неприменима, так как не существует просто опи-

сываемой функции, вычисляющей простое число по его номеру. Для реше-

ния данной задачи можно воспользоваться следующим приемом: во-первых,

заменить алгоритмически трудную генерацию последовательности простых

чисел генерацией охватывающего, включающего потока (мы будем генери-

ровать нечетные числа), и во-вторых, встроить в обработку фильтрацию: ис-

ключение составных чисел. В программе

Prime_Numbers_1

фильтрация за-

дается как локальная потоковая обработка, в ходе которой проверяется, де-

лится ли анализируемое число на какое-либо из предшествующих чисел.

Нужно помнить, что математические эквивалентные преобразования и изоморфизмы

структур являются важнейшим компонентом культуры программиста. Переход к эквива-

лентной формулировке в математике соответствует переходу к другому представлению дан-

ных либо действий в программировании. Выигрыш, получаемый за счет того, что приме-

няется лучшая математическая формулировка, часто в порядки раз превышает выигрыш от

оптимизации самой программы.

298

ГЛАВА 7. ЦИКЛИЧЕСКИЕ ВЫЧИСЛЕНИЯ

Программа 7.2.1

/* Prime_Numbers_1.

Распечатка первых N простых чисел

#include <stdio.h>

#include <math.h>

int main(void)

{

int N,i,j,k,Prime; /*

назначение определяемых переменных

описывается при их использовании

printf("Введите N:");

scanf("%i",&N);

/* ОБЩАЯ ЧАСТЬ ВЫВОДА РЕЗУЛЬТАТА */

if (N<=0)

printf("При N <= 0 простых чисел не существует");

else if(N==1)

printf("При N = 1 единственное простое число - 1");

else

{

printf("Последовательность первых %i простых чисел есть: ",N);

printf("1,2"); /*

Первые два простых числа выведены,

рассмотрены особые случаи и выведено

начало искомой последовательности

ОБРАБОТКА ПОТОКА НЕЧЕТНЫХ ЧИСЕЛ:

ИНИЦИАЛИЗАЦИЯ потока нечетных чисел:

i=1;

k=2; //

k — счетчик напечатанных простых чисел

while (k<N)

{

ГЕНЕРАЦИЯ очередного нечетного числа:

i+=2;

ФИЛЬТРАЦИЯ (проверка, является ли i простым)

оформлена как ОБРАБОТКА ЛОКАЛЬНОГО ПОТОКА

ИНИЦИАЛИЗАЦИЯ локального потока

j=3; /*

3 — это первое число, делимость

на которое надо проверять

Prime=1; //

переменная-индикатор делимости

7.2. ПОТОКОВАЯ ОБРАБОТКА

299

while (j<=sqrt(i) && Prime) {

достаточно проверять делимость не для всех j,

а лишь для тех, которые не превосходят

√

i — факт из теории чисел;

цикл проверки прекращается, когда

обнаружена делимость i на j

ОБРАБОТКА элемента локального потока

Prime=i%j;

ГЕНЕРАЦИЯ элемента локального потока

j+=2;

так как i нечетно, проверяется делимость

только на нечетные числа, поэтому локальный

поток строится только из нечетных чисел

}

ФИЛЬТРУЮЩЕЕ УСЛОВИЕ

if (Prime) {

ОБРАБОТКА потока простых чисел

(отфильтрованные нечетные)

k++;

printf(",%i",i);

}

} //

конец ОБРАБОТКИ ПОТОКА НЕЧЕТНЫХ ЧИСЕЛ

}

printf(".\n");

return 0;

}

В программе

Prime_Numbers_1

имеются избыточные вычисления. В частно-

сти, в цикле

while (j<=sqrt(i) && Prime)

{ Prime=i%j; j+=2; }

много излишних проверок — достаточно поверять делимость не на все j, не

превосходящие

√

i, а лишь на простые, т. е. на те, которые ранее уже были

найдены и напечатаны. Это — одно из многих обстоятельств, которое заста-

вляет нас писать программы, запоминающие не только те данные, которые

непосредственно нужны для следующего шага, но и историю вычислений.

300

ГЛАВА 7. ЦИКЛИЧЕСКИЕ ВЫЧИСЛЕНИЯ

Конец примера 7.2.3.

Использование фильтров, или фильтрованная обработка — это широко ис-

пользуемый в программировании типовой прием. Он применяется, когда не-

возможно или неудобно говорить о точном вычислении какой-либо обраба-

тываемой структуры данных (в приведенной программе — поток), но можно

построить объемлющую структуру и предложить условие отбраковки (фильтр),

которое выделяет требуемую для переработки информацию.

Общие схемы фильтрованной потоковой обработки можно получить из

схем простой обработки потока путем незначительной модификации: доба-

вления проверки некоторого условия. С формальной точки зрения, понятие

фильтрованной обработки потока избыточно: это частный случай простой

потоковой обработки, если проверка условия считается частью обработки

элемента. Цель введения фильтрованной обработки методическая — она по-

могает разбивать решаемую задачу на относительно более простые подзада-

чи. Это хорошо видно на примере программы

Prime_Numbers_1

Схема Пример

ИНИЦИАЛИЗАЦИЯ

printf("Введите

N:");scanf("%i",&N);S = I =

пока ПОТОК НЕ ИСЧЕРПАН

цикл

while (I < N) {

ПОРОЖДЕНИЕ ОЧЕРЕДНОГО

ЭЛЕМЕНТ

I++;

если ФИЛЬТРУЮЩЕЕ УСЛО-

ВИЕ

if ( I/10 % 2 ) // вторая

то ОБРАБОТКА ЭЛЕМЕНТА

S = S + I; // цифра

конец цикла

} // нечетная

ЗАВЕРШЕНИЕ

printf("Сумма = %i \n", S );

Таблица 7.6. Фильтрация. Инициализация не включает порождение

7.2.3. Потоки и данные

В структурном программировании операторы тесно связаны с обрабаты-

ваемыми данными,в частности,для каждого оператора имеются те типы дан-

ных, которые естественно использовать именно в связи с данным операто-

ром. Иногда эти типы данных явно включаются в языки программирования

7.2. ПОТОКОВАЯ ОБРАБОТКА

301

Схема Пример

ИНИЦИАЛИЗАЦИЯ, ВКЛЮЧА-

ЮЩАЯ ГЕНЕРАЦИЮ

printf("Введите N:");

scanf("%i",&N);S = 0; I = A =

пока ПОТОК НЕ ИСЧЕРПАН

цикл

while (I <= N) {

если ФИЛЬТРУЮЩЕЕ УСЛО-

ВИЕ

if ( I/10 % 2 )

то ОБРАБОТКА ЭЛЕМЕНТА

S = S + A;

ПОРОЖДЕНИЕ ОЧЕРЕДНОГО

ЭЛЕМЕНТ

I++; A = I*I;

конец цикла

}

ЗАВЕРШЕНИЕ

printf("Сумма = %i \n", S );

Таблица 7.7. Фильтрация. Инициализация включает порождение

и, соответственно, в программы (например, альтернативные структуры для

операторов выбора); иногда они не включаются в них вообще, оставаясь при-

зраками в чистом виде (например, счетчики шагов для циклов с пред- или

постусловием); иногда такие типы данных включаются частично и непосле-

довательно. Именно последний случай имеет место для потоков, и, в связи

с этим, мы в данном параграфе рассматриваем некоторые из типов данных,

которые могут представлять потоки в конкретных программах.

Иногда строгая потоковость препятствует эффективности (см., например,

программу

Prime_Numbers_1

, при обсуждении которой упоминалось о по-

вторном счете). Поток — это, прежде всего, локальная организация обра-

ботки: программа “забывает” о том, что делалось с предыдущими элемен-

тами потока. Естественно, что языки программирования предусматривают

возможность запоминать информацию о том, что уже происходило. Рассмо-

трим пример (еще одна модернизация программы 7.2.1

Prime_Numbers_1

показывающий, как можно ликвидировать повторный счет.

Программа

Prime_Numbers_1

производит лишний счет, когда пытается

проверить делимость числа на все нечетные числа из диапазона 2 6 i 6

√

. Легко видеть, что достаточно проверять делимость на уже вычислен-

ные простые числа. Чтобы не потерять их, нужна дополнительная память.

Таким образом, в рамках задачи о простых числах выделяется подзадача со-

хранения получаемой информации и ее использования. Для этой подзадачи,

302

ГЛАВА 7. ЦИКЛИЧЕСКИЕ ВЫЧИСЛЕНИЯ

Схема Пример

ИНИЦИАЛИЗАЦИЯ, ВКЛЮЧА-

ЮЩАЯ ГЕНЕРАЦИЮ

printf("Введите N:");

scanf("%i",&N);S = 0; I = A =

цикл если ФИЛЬТРУЮЩЕЕ

УС

ЛОВИЕ

do if ( I/10 % 2 )

то ОБРАБОТКА ЭЛЕМЕНТА

S = S + A;

ПОРОЖДЕНИЕ ОЧЕРЕДНОГО

ЭЛЕМЕНТ

I++; A = I*I;

пока ПОТОК НЕ ИСЧЕРПАН

while (I <= N);

ЗАВЕРШЕНИЕ

printf("Сумма = %i \n", S );

Таблица 7.8. Фильтрация. Инициализация включает порождение. Использу-

ется цикл с постусловием

как и для всех

задач, можно ставить следующие вопросы:

a) Какова цель решения? Для чего будет нужно полученное решение? При-

менительно к данной подзадаче: для чего нужно запоминать получаемые

простые числа?

b) Как будет использовано решение? Это включает анализ возможных вари-

антов применения конструируемой программы. Применительно к данной

подзадаче: как найденные и запомненные простые числа будут участво-

вать в процессе решения объемлющей задачи?

c) Как решается поставленная задача? Этот вопрос ставится последним,

только после уяснения ответов на два предыдущих. Для подзадачи о за-

поминании простых чисел вопрос конкретизируется следующим образом:

каковы способы хранения получаемых данных и их извлечения?

Цель решения в учебных задачах, как правило, формулируется достаточно

точно

(в задаче о простых числах — сокращение цикла проверки делимо-

сти). Что касается второго вопроса, то его решение может повлечь за со-

бой такие следствия, которые влияют на критерии оценки решения задачи.

Не только для программистских! Эти вопросы являются частью системного и логического

подхода к проблеме.

В реальной практике, как правило, она формулируется неточно и неполно, а в худшем

случае прямо ошибочно.

7.2. ПОТОКОВАЯ ОБРАБОТКА

303

Схема Пример

ИНИЦИАЛИЗАЦИЯ

printf("Введите N:");

scanf("%i",&N);S1 = 0; S2 = 0;

I =

пока ПОТОК НЕ ИСЧЕРПАН

цикл

while (I < N) {

ПОРОЖДЕНИЕ ОЧЕРЕДНОГО

ЭЛЕМЕНТ

I++;

если РАЗДЕЛЯЮЩЕЕ УСЛОВИЕ

if ( I % 2 )

то ОБРАБОТКА 1 ЭЛЕМЕНТА

S1 += I;

иначе ОБРАБОТКА 2 ЭЛЕМЕН-

else S2 += I;

конец цикла

}

ЗАВЕРШЕНИЕ

printf("Сумма 1 = %I, Сумма 2 = %I

\n", S1, S2

);

Таблица 7.9. Разделение обработки на два потока

Применительно к рассматриваемому случаю распечатки первых N простых

чисел, по-видимому, ничего принципиально нового за счет запоминания не

получить. Но если чуть изменить постановку исходной задачи и сформули-

ровать ее как распечатку N-ого простого числа, то сам способ запоминании

промежуточных результатов может повлиять на стратегию решения вообще.

Так, если говорить о долговременном запоминании, то конструируемая про-

грамма может рассматриваться с совершенно новых позиций:

• Расширение масштаба решаемой задачи. Для выявления простоты в

этом случае достаточно проверять делимость не на все числа, меньшие

проверяемого числа (пусть даже нечетные), а только на простые числа.

Ранее идея могла возникнуть лишь умозрительно, поскольку распеча-

тывание всех простых чисел с номерами, меньшими либо равными N,

количественно ограничивает задачу. Ее просто не имеет смысла решать

при таких N, при которых эффект сокращения проверок не будет ска-

зываться. Развитие идеи сокращения проверок за счет хранения данных

приводит к мысли о том, что можно обойтись вообще без деления, за-

менив его последовательным вычеркиванием составных чисел, как это

делается в решете Эратосфена;

• Замена вычисления извлечением значения. При многократном поиске

304

ГЛАВА 7. ЦИКЛИЧЕСКИЕ ВЫЧИСЛЕНИЯ

Схема Пример

ИНИЦИАЛИЗАЦИЯ

int ch; int Sd=0, Sl=0, S=0;

пока ПОТОК НЕ ИСЧЕРПАН

цикл

while ((ch=getchar())!=’\n’) {

//генерация вместе с проверк

ой

ПОРОЖДЕНИЕ ОЧЕРЕДНОГО

ЭЛЕМЕНТ

если РАЗДЕЛЯЮЩЕЕ УСЛОВИЕ

if (’0’<=ch && ch<=’9’)

то ОБРАБОТКА 1 ЭЛЕМЕНТА

Sd ++;

иначе если РАЗДЕЛЯЮЩЕЕ

УСЛОВИЕ

else if (’a’<=ch && ch<=’z’)

то ОБРАБОТКА 2 ЭЛЕМЕНТА

Sl ++;

иначе если РАЗДЕЛЯЮЩЕЕ

УСЛОВИЕ

...

иначе АЛЬТЕРНАТИВНАЯ ОБ-

РАБ

ОТКА

else S ++;

конец цикла

}

ЗАВЕРШЕНИЕ

printf ("Sd=%i, Sl=%i, S=%i,\n

Total=%i \n",Sd,Sl,S

,Sd+Sl+S);

Таблица 7.10. Разделение обработки на несколько потоков. Используются

условия