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

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

6.2. ТАБЛИЧНОЕ ЗАДАНИЕ

285

6.2.3. Условные выражения

В языках

Algol-60

Алгол-68

Java

имеется очень удобная конструкция:

условные выражения. Условное выражение языка

имеет вид

(P?A:B)

где

— выражение, значение которого вычисляется в случае истинности

— в случае его ложности. Во всех других языках семантика условных вы-

ражений такая же.

Заметим, что в

Алголе-68

практически все операторы выдают значение

и могут использоваться в качестве составных частей выражений. Например,

допустимо выражение

i + if P then j+ := 1; F (j) else abs(k := bad; z := k) ﬁ.

В выражениях этого языка могут стоять даже разборы случаев типа case.

Дополнительной семантической функцией разделителя последовательно вы-

полняемых операторов “

;

” является забывание значения предшествующего

оператора.

Языки,в которых все операторы (а иногда и описания) вырабатывают зна-

чение, называются языками с концепцией значения. Такие языки хорошо со-

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

ковой архитектурой систем

Barroughs

Эльбрус

, где вырабатываемые зна-

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

ных значений, а также со старыми архитектурами, где был регистр (сумматор),

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

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

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

сочетается со структурным программированием. Но ее отсутствие в языках

Pascal

C/C++

вполне естественно. Причина этого — в типах данных.

Современное программирование немыслимо без определения новых ти-

пов и сложных структур данных. Соответственно, если рассматривать все

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

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

ставленного типа в данные типа, требуемого по контексту.

А соединение

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

возникающего в программе, категорию (в смысле алгебры) всех имеющихся типов данных.

286

ГЛАВА 6. РАЗВЕТВЛЕНИЕ ВЫЧИСЛЕНИЙ

концепции значения с анархией преобразований,царящей в

C/C++

,или с бес-

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

Pascal

привело бы к неисчислимым неприятностям. К концепции значения мы еще

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

Концепция приведения была корректно выделена лишь в

Алголе 68

. Она

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

простейших их вариаций (например, ссылок на такие значения), и только для

них. Перенос этой концепции на вновь определяемые типы данных прорабо-

тан не был.

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

рокий обиход. Она ориентирует язык на вычисления в собственном смысле

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

бы для любых задач, а не для некоторого их класса.

Задания для самопроверки

1. (Для языка

) Объясните, почему не стоит пользоваться непустыми

действиями после

case

без

break

, за исключением, быть может, по-

следнего из разобранных случаев, и только тогда, когда нет

default

Глава 7

Циклические вычисления

Понятие цикла появилось еще при изобретении программирования Ав-

густой Адой Лавлейс. Повторяющиеся вычисления не должны требовать по-

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

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

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

луй, характерным признаком структурного программирования. В этом стиле

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

другими стилями.

§ 7.1. МОТИВАЦИЯ ЦИКЛИЧЕСКИХ ВЫЧИСЛЕНИЙ

Начнем с рассмотрения примера.

Программа 7.1.1

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

#include <stdio.h>

#include <math.h>

определим коды возврата программы

#deﬁne OK 0

#deﬁne SYNTAX_ERROR -1

#deﬁne BAD_OPERATION -2

#deﬁne ZERO_DIVISION -3

int main()

287

288

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

{

ﬂoat x, y, result;

char operation;

char p; //

для организации цикла

do {

printf(”Введите выражение для вычисления в виде \n”);

printf( ”<число><операция><число>:\n”);

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

if( 3 != scanf( "%f%c%f", &x, &operation, &y ) )

{

printf( ”Синтаксическая ошибка!\n”);

return SYNTAX_ERROR; /*

выход из программы с кодом ошибки

}

printf( ”Исходное выражение: %f %c %f\n”, x, operation, y );

switch( operation )

{

case ’+’:

result = x + y;

break;

case ’-’:

result = x - y;

break;

case ’*’: result = x * y;

break;

case ’/’:

if( y == 0.0 )

{

printf( ”Деление на ноль!\n”);

return ZERO_DIVISION;

}

result = x / y;

break;

default:

printf( ”BAD_OPERATION: %c\n”, operation );

return BAD_OPERATION;

}

7.1. МОТИВАЦИЯ ЦИКЛИЧЕСКИХ ВЫЧИСЛЕНИЙ

289

printf( ”result = %f\n”, result );

{

printf ("Следующее вычисление? (y/n) \n");

scanf ("%c", &p );

}

while ( ( p !=’y’) && ( p !=’n’) );

if ( p == ’n’ )

return 0; /*

нормальное завершение

}

while ( true );

}

Проанализируем эту программу.

1. Обрабатывается последовательность троек вида:

<число> <операция> <число>,

которая берется из потока входных данных. Это — одна из наиболее

типичных ситуаций циклической обработки. Очередные данные тре-

буют выполнения одного и того же блока программы. Блок программы

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

полняемый в ходе обработки данных в цикле, называется итерацией

цикла.

2. Используется “бесконечный”цикл,который организован как искусствен-

но прерываемая в нужные моменты (для завершения работы) последо-

вательность одинаковых действий.

3. Программа прекращает работу в случае получения специального значе-

ния некоторой переменной (

), а также при ошибке ввода или вычисле-

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

выполнение цикла, называется управляющей переменной цикла.

4. Появление цикла ставит новые задачи. Например, прекращение выпол-

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

вательской точки зрения: желательно сделать попытку нейтрализации

ошибки (например, с помощью предложения пользователю повторить

ввод). До введения цикла задача нейтрализации ошибок не возникала.

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

290

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

проверкой) приводят к выводу о том, что непосредственное примене-

ние функции

scanf

не годится. Чтобы нейтрализовать ошибки, можно

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

цию, а затем анализировать ее (подобно тому, как поступает типич-

ный транслятор), или же добиться аналогичного эффекта в ходе чтения

строки ввода.

5. Для организации цикла используется конструкция

do <оператор > while <выражение>

которая предполагает проверку необходимости завершения цикла по-

сле выполнения итерации — так называемый цикл с постусловием. В

таком цикле <выражение> рассматривается в качестве условия, истин-

ность которого предписывает продолжение выполнения цикла (пере-

ход к новой итерации), ложность — завершение цикла.

Для данного примера, в котором необходимость завершения или продолже-

ния выполнения цикла фактически определяется не на основе проверки вы-

ражения-условия, а в ходе итерационных действий, выбор вида цикла почти

безразличен. С тем же эффектом можно было использовать цикл с преду-

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

итерации:

while ( <выражение-условие> ) do <оператор>

где <выражение-условие>—<выражение>,вырабатывающее логическое зна-

чение.

Эти два вида цикла взаимозаменяемы. Цикл с предусловием эквивален-

тен условному оператору, у которого в качестве <Действия T> стоит цикл с

постусловием

while

<выражение-условие>

<оператор>

(<выражение-условие>)

<оператор>

while

<выражение-

условие

В данном примере с тем же эффектом, что и в предыдущем случае, можно

было использовать цикл

for

“

for

” “(” <инициализирующий оператор> <выражение-условие> “;”

<выражение пересчета> “)” <оператор>

где <инициализирующий оператор> — любой, в том числе и пустой, опе-

ратор, назначение которого — задание начальных значений переменных для

выполнения цикла,

7.1. МОТИВАЦИЯ ЦИКЛИЧЕСКИХ ВЫЧИСЛЕНИЙ

291

<выражение пересчета> — выражение, предназначенное для подготовки

новых значений для очередной итерации.

Цикл

for

эквивалентен следующему оператору:

{ <инициализирующий оператор>

while (

<выражение-условие>

) {

<оператор>

<выражение пересчета>;

} }

Вид заголовка цикла

for

для данного примера —

for (;;)

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

ражения пересчета не требуется.

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

ко что приведенных вычислений будут совпадать. Но стандарт оставляет от-

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

частности, фрагмент

while ( True )

согласно семантике, требует проверки истинности выражения

True

. Практи-

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

сленности такой проверки и удаляют ее из объектного кода, но гарантировать

этого нельзя. По этой причине для организации бесконечных циклов предпо-

чтительнее пользоваться конструкцией

for (;;)

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

граммирования и для облегчения оптимизации объектного кода.

Пример 7.1.1. Рассмотрим цикл на языке

C++

for ( int i = 0; i <= 10; i ++ )

<оператор>

Этот заголовок указывает, что переменная

вне цикла не может быть исполь-

зована — она создается для применения внутри оператора. Как следствие,

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

гистров, не заботясь о сохранении значения переменной после завершения

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

носит служебный,

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

тексту лишь нарушает понимание программы и препятствует неявной авто-

матической оптимизации.

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

292

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

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

Есть очень много типовых приемов программирования циклов, которые

могут быть объединены под общим названием потоковой обработки.Смысл

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

некоторой последовательности — потока, а саму работу цикла вместе с его

подготовкой и завершением — как выполнение следующих шагов:

a) ИНИЦИАЛИЗАЦИЯ — действия, готовящие обработку потока;

b) Проверка,не исчерпан ли поток. Обозначается в таблицах как ПОТОК НЕ

ИСЧЕРПАН. Производит вычисление условия, указывающего на необхо-

димость выполнения оператора цикла или на его прекращение;

c) ПОРОЖДЕНИЕ ОЧЕРЕДНОГО ЭЛЕМЕНТА — создание,выделение,чте-

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

мент для обработки;

d) ОБРАБОТКА ЭЛЕМЕНТА — действия, связанные с отдельным элемен-

том потока;

e) ЗАВЕРШЕНИЕ — действия, которые надлежит выполнить после оконча-

ния итераций.

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

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

таблицах, идущих ниже.

Схема Пример

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

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

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

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

цикл

while (i < N) {

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

ЭЛЕМЕНТ

I++;

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

S = S + I;

конец цикла

}

ЗАВЕРШЕНИЕ

printf(”Сумма %i чисел = %i \n”, i, S

);

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

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

293

Схема Пример

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

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

ВКЛЮЧАЮЩАЯ ГЕНЕРАЦИЮ

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

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

цикл

while (i <= N) {

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

S = S + A;

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

ЭЛЕМЕНТ

I++; A = I*I;

конец цикла

}

ЗАВЕРШЕНИЕ

printf(“Сумма квадратов %i

чисел = %i \n“, i, S

);

Разграничение порождения и об-

работки довольно условно.Напри-

мер,стоит ли считать

A=I*I;

частью

обработки? Здесь продемонстри-

рован вариант, где порождение и

обработка смешаны

S = 0; I = 1; A =0;

while (i <= N)

{ I++; S = S + A; A =

I*I;}

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

7.2.1. Порождение элементов потока

Способы порожения очередного элемента потока можно расклассифици-

ровать следующим образом:

a) независимая генерация, когда порождение никак не связано с алгоритмом

обработки. Характерный пример — использование вводимой последова-

тельности;

b) функциональная генерация,когда очередной элемент вычисляется как функ-

ция от его порядкового номера. Пример такой генерации —

I++; A = I*I;

c) рекуррентная генерация, когда очередной элемент вычисляется как функ-

ция от предыдущего (в более сложных случаях — от нескольких преды-

дущих элементов). Пример —

X = X / 10;

d) смешанная генерация, в которой сочетаются предыдущие виды генера-

ции.

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

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

294

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

Схема Пример

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

ЮЩАЯ ПОРОЖДЕНИЕ

printf("Input X:"); scanf("%i",&X);

цикл ОБРАБОТКА ЭЛЕМЕНТА

do printf ("%c", ’0’ + X % 10);

ПОРОЖДЕНИЕ

X = X / 10;

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

while ( X != 0 )

ЗАВЕРШЕНИЕ

printf("\n");

Распечатывается обращенная последовательность цифр числа. Поток — X,

X/10, (X/10)/10, ..., 0. Обработка — печать остатка от деления X на 10.

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

стусловием

Схема Пример

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

printf(”Продолжить? (y|n)\n”);

цикл ПОРОЖДЕНИЕ ЭЛЕМЕН-

do scanf ( "%c", c );

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

// ОБРАБОТКА ОТСУТСТВУЕТ

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

while (c != ’y’)||(c != ’n’)

ЗАВЕРШЕНИЕ

if ( c ==’n’ ) return 0;

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

постусловием

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

порождения на составляющие. Полезно сопоставить различные виды пото-

ковой обработки.

Независимая генерация (или независимая часть смешанной генерации)

привлекает к потоковой обработке данные, получаемые внешним образом по

отношению к самой обработке, и в этом смысле ее использование следует из

постановки задачи.

Функциональная генерация по сравнению с рекуррентной часто более на-

глядна. Однако при потоковой обработке она, как правило, менее эффектив-

на.

Пример 7.2.1. Пусть на каждой очередной итерации цикла нам требуется

очередная степень числа a. Получить ее можно либо с помощью формулы

= exp(i ∗ ln(a))