Файл: А. Б. Шнейвайс основы программирования.pdf

1.2.11
СИ-операция последовательного вычисления
,
В [10, 6.2] эта операция названа близким родственником блока, посколь- ку позволяет связать несколько выражений в одно, не заводя блока:
#include
using namespace std;
int main(void)
{
int i=10, j;
// Результат:
i= (j=4, i+j); cout<<" i="<j="<//
i=14
j=4
i=
j=4, i+j ; cout<<" i="<j="<//
i= 4
j=4
cout<<" i+j="<//
i+j=8
return 0;
}
В этой программе в операторе присваивания i=(j=4,i+j) операторы j=4 и i+j заключены в круглые скобки. Операция ”
,
” выполняется до присваивания значения переменной i с результатом равным по опреде- лению значению оператора i+j из правой части, т.е. i=10+4=14.
Без круглых скобок i=j=4,i+j операция i+j тоже выполняется (прав- да, не совсем понятно зачем, так как из-за более высокого приоритета операции присваивания сначала j=4, а затем и i=4. Таким образом,
левая часть конструкции i=j=4,i+j, расположенная до запятой, отра- ботает полностью (т.е. слева от запятой не останется ни присваивания,ни имени приемщика суммы). Так что, выражение i=j=4,i+j синтаксиче- ски верно, но значение суммы i+j, которая всё-таки вычислиться, не будет присвоено никакой переменной.
Цель оператора
,
– обеспечить одновременное выполнение нескольких операторов, если по какой-то причине (например, по синтаксису языка)
допустим только один.
Например, в операторе цикла с параметром (for) в качестве парамет- ра цикла обычно используется одна переменная, для которой первым делом задается начальное значение, после чего ставится
;
, отделяющая шаг инициализации от условия продолжения цикла. Однако, нередки ситуации, когда в одном операторе for удобно использовать несколько аналогов параметра цикла. Рассмотрим примитивный вариант програм- мы, выясняющей, является ли строка перевертышем:
47

#include
#include
using namespace std;
int main(void)
{int i, j;
bool p, q;
char *s="пилвиноонивлип\0";
char *c="пилвиноенивлип\0";
for (i=0,j=13,p=true;(i<=j)&& (p=s[i]==s[j]);i++,j--);
if (p) cout<else cout<for (i=0,j=13,q=true;(i<=j)&& (q=c[i]==c[j]);i++,j--);
if (q) cout<else cout <return 0;
}
Если в этой программе после i=0 поставить
;
, то уже не сможем в заго- ловке цикла инициализировать j и p (или q). Ещё один пример:
#include
// В программе используются функции sumxy1 и sumxy2
using namespace std;
// соответственно c одним и двумя формальными типа int sumxy1(int);
// int аргументами. В качестве единственного факти- int sumxy2(int,int);
// ческого аргумента первой (sumxy1) подается выражение int main(void)
// (x,x+y). В контексте наличия круглых скобок запятая
{int x=100, y=200;
// между x и x+y трактуется cout<<" x + y
="<// последовательного вычисления cout<<" x + y
="<// с результатом: x + y = 300.
return 0; }
// В контексте вызова sumxy2
int sumxy1(int x)
// "запятая" толкуется как
{cout<<"sumxy1: x="<// обычный разделитель аргументов return x;}
// так, что через имя функции int sumxy2(int x, int y)
// при аргументах x=100 и y=200
{cout<<"sumxy2: x="<y="<// для возвращается результат:
return x+y;
// x + (x+y) = 400.
}
Вывод: использование операции последовательного вычис- ления требует неослабного внимания и высокой аккуратности,
поскольку позволяет (как видели из первого примера) легко получить синтаксически верную конструкцию, делающую со- всем не то, что имелось ввиду.
48

1.2.12
Приоритет операций
Название
Символ
Символ операции
С, C++
Примеч.
Ф-77 Ф>90
Примеч.
Обращение к
()
Слева
()
Cлева
1
функции направо направо
Выделение эле-
[]
– ” –
()
– ” –
мента массива
Выделение поля структурной
– ” –
– ” –
переменной
%
Выделение поля струк. перемен
–>
– ” –
=>
– ” –
ной по указате лю на ее начало
Возведение в pow(a,q) функция
**
СПРАВА
степень a q
налево
Логическое
!
Справа
.not.
Справа
2
отрицание налево налево
Поразрядное
∼
–”–
not(i)
Функция.
логическое НЕ
not(9)=6
Изменение знака
−
–”–
–
Справа налево
Инкремент
++
–”–
НЕТ
k=k+1
Декремент
−−
–”–
НЕТ
k=k-1
Определение ад- реса переменной
&
–”–
НЕТ
Обращение к па- мяти по значе-
∗
–”–
нию указателя
Преобразование
( имя )
–”–
Набор к типу типа функций
Определение sizeof
Справа размера в байтах налево
49

Название
Символ
Символ операции
С, C++
Примеч.
Ф-77 Ф>90
Примеч.
3
Умножение
*
Сл.напр.
*
Cл.напр.
Деление
/
– ” –
/
– ” –
Ост. от дел.
%
– ” –
mod(a,b)
Функция
4
Сложение
+
Сл.напр.
+
Сл.напр.
Вычитание
−
–”–
–
–”–
5
Сдвиг влево

–”–
ishf t(i, s)
s>=0
Функция
Сдвиг вправо

–”–
ishf t(i, s)
s<=0 6
Меньше
<
Сл.напр.
.lt.
<
Сл.напр.
≤
<=
–”–
.le.
<=
–”–
Больше
>
–”–
.gt.
>
–”–
≥
>=
–”–
.ge.
>=
–”–
7
Равно
==
Сл.напр.
.eq.
==
–”–
Не равно
! =
–”–
.ne. / =
–”–
8
Поразр.конъ.
&
Сл.напр.
iand(i, j)
Функция
9
Поразр.искл.
∧
Слева ieor(i, j)
Функция
ИЛИ
(xor)
направо
10
Поразр.дизъ.
|
Сл.напр.
ior(i, j)
Функция
11
Логическое И
&&
Сл.напр.
.and.
Сл.напр.
12
Логическое
||
Слева
.or.
Слева
ИЛИ
направо направо
Искл. лог. ИЛИ
НЕТ
.xor.
Эквив.
НЕТ
.eqv.
Неравн.
НЕТ
.neqv.
13
Условная
? :
Слева
НЕТ
операция направо
14
Присваивание
=
%=
Справа
=
Справа
+ =
− =
налево
НЕТ
налево
∗ =
/ =
–”–
НЕТ
= =
–”–
НЕТ
| =
& =
–”–
НЕТ
∧
=
–”–
НЕТ
15
Опер. запятая
,
Сл.напр.
НЕТ
50

Левая часть таблицы содержит перечень всех операций языка СИ в по- рядке убывания приоритета. Группы Cи-операций одинакового приори- тета разделены тонкой чертой. Справа даны соответствующие операции
(или функции) ФОРТРАНа. Правда, ФОРТРАН- и CИ-приоритеты не всегда совпадают.
Приоритет выполнения операций ФОРТРАНа:
1 2
3 4
5 6
7 8
** *
.lt. <
.eq. == .not. .and. .or.
.xor.
/
.le. <=
.ne. /=
.eqv.
.gt. >
.neqv.
.ge. >=
Видим, что операции отношения в ФОРТРАНе имеют более высокий приоритет чем любая из логических операций, в то время как в СИ опе- рация отрицания ! по приоритету выше любой операции отношения. По- этому, например, на ФОРТРАНе: (.not.0>1) есть true, но на СИ:
(!0>1) есть 0, то есть false (cм. последний оператор следующего приме- ра). Именно поэтому в сомнительных случаях не пренебрегаем скобками.
При использовании сложного булева выражения важно помнить, что его расчет прекращается, когда результат уже ясен, т.е. операнды после пер- вой булевой операции могут и не вычислятся: Обратимся к примеру:
#include
using namespace std;
int main(void)
{int i,j;
i=0;
j=5;
if((i++)&&(++j)) cout<<"
j="<cout<<" i="<j="<if((++i)&&(j++)) cout<<" i="<j="<cout<<"
(!0>1)="<<(!0 >1 )<cout<<" (!(0>1))="<<(!(0>1))<return 0; }
Результат работы этой программы:
// Почему нет вывода, соответствующего первому условному

// оператору программы?
i=1
j=5

// Почему не отработало (++j)?
i=2
j=6

// Почему отработало (j++)?
(!0>1)=0
(!(0>1))=1 51

Аналогичный результат получает и программа на ФОРТРАНе-77.
program tstbool0
implicit none interface function bfun(j) result(w); logical w; integer j; end function bfun end interface logical i
integer j i=.false.
j=5
if ( i.and.bfun(j) ) write(*,*) ’ i=’,i,’
j=’,j i=.true.;
write(*,*) ’ i=’,i,’
j=’,j if ( i.and.bfun(j) ) write(*,*) ’ i=’,i,’
j=’,j write(*,*) ’ .not. 0>1 =’,.not.0>1
write(*,*) ’ .not.(0>1)=’,.not.0>1
end program tstbool0
function bfun(j) result(w)
implicit none logical w integer j;
w=j<1000; j=j+1;
end function bfun

Правда, в ФОРТРАНе невозможна проверка (.not.0)>1. Почему?
i= T
j=
5
i= T
j=
6
.not. 0>1 = T
.not.(0>1)= T
52

1.3
О чем узнали из первой главы? (2-ой семестр)
1. О СИ-операциях инкремента ++ и декремента –.
2. О префиксной и постфиксной формах их использования.
3. Префиксная форма сначала использует текущее значение опе- ранда, а уж затем изменяет его значение.
4. Постфиксная форма, наоборот, – сначала изменяет текущее зна- чение своего операнда, а уж затем использует.
5. В СИ операция нахождения остатка от деления двух целых обо- значается символом %, а в ФОРТРАНе имеется похожая по сути встроенная функция mod, имя которой является родовым.
6. Операция присваивания в СИ не только пересылает значение,
но и понимает его как свой результат. Поэтому в СИ допустима,
например, запись a=b=c=d=5. В ФОРТРАНе оператор присваи- вания последним свойством не обладает.
7. О наличии в СИ комбинированной операции присваивания,
которой тоже нет в ФОРТРАНе.
8. Про СИ-операции сдвига

и

, которые С++ по контексту от- личает от операции направления в потоки ввода/вывода, и про соот- ветствующую одновременно им обеим ФОРТРАН-функцию ishift.
9. СИ-операция sizeof позволяет получить количество байт необходи- мое для размещения данного любого типа. Операндом этой опера- ции может быть и значение, и имя типа, и имя переменной. В совре- менном ФОРТРАНе для подобной цели можно использовать функ- ции kind, size и sizeof.
10. О поразрядных логических операциях СИ и о соответствующих им встроенных функциях современного ФОРТРАНа.
11. О явном и неявном преобразовании типов данных.
12. Приоритеты операций в ФОРТРАНе и СИ не всегда одинаковы. Лю- бая операция отношения ФОРТРАНа имеет более высокий приори- тет чем любая из логических операций. В СИ приоритет операции отрицания выше приоритета любой из операций отношения.
53

1.4
Первое домашнее задание (2-ой семестр)
1. Продемонстрировать в дисплейном классе работоспособность лек- ционных СИ- и ФОРТРАН-программ по теме «ВЫРАЖЕНИЯ и
ОПЕРАЦИИ»
( пункты:
• 1.2.3 — тернарная операция;
• 1.2.4 — операция присваивания;
• 1.2.5 — операция sizeof;
• 1.2.6 — операции сдвига;
• 1.2.7 — поразрядные логические операции.
).
2. Сдать преподавателю список вопросов по неясным моментам исход- ных СИ- и ФОРТРАН-текстов, рассмотренных в лекции.
3. Разработать C- и ФОРТРАН-функции подсчёта количества единиц в двоичном представлении целого неотрицательного числа.
4. Разработать (на ФОРТРАНе и С) наиболее оптимальный алгоритм
(в виде функции) решения предыдущей задачи.
5. Усовершенствовать функцию из предыдущего пункта так, чтобы она позволяла находить количество единиц в двоичном представле- нии любой допускаемой компилятором разновидности типа целого типа (т.е. -1, -2, -4, -8, -16).
54

2
Немного о рекурсии в программировании.
Рекурсия – определение какого–нибудь понятия через само это понятие.
Например, таким свойством обладает каждое из "бесконечной"череды изображений человека в настенном зеркале, если он держит в руках дру- гое зеркало, отражающее изображение первого. Каждое из изображений определяется через свое предыдущее отражение. Налицо свойство рекур- сивности.
Рекурсия часто используется в математических определениях (см., на- пример, [17]):
1. Натуральное число: Число – это аксиоматическое (т.е. принимае- мое без доказательства) понятие математики, используемое для от- ражения количественных соотношений. Интуитивно под натураль- ным числом понимаются числа, предназначенные для счёта.
Рекурсивное определение:
a) единица – натуральное число;
б) целое число, следующее за натуральным, есть натуральное.
2. n! :.
Нерекурсивное определение : n! = 1 · 2 · 3 · · · n .
Рекурсивное определение:
a) 0! = 1.
б) если n > 0, то n! = n · (n − 1)!.
3. Произведение двух натуральных чисел через сложение:
Нерекурсивный вариант: a · b = a + a + · · · + a
|
{z
}
b раз
=
b
X
i=1
a.
Рекурсивное определение:
a) a · 1 = a;
б) Если же b 6= 1, то a · b = a + a · (b − 1) .
55

4. Определение алгоритма Евклида (поиск наибольшего общего делителя двух натуральных чисел):
Если a>=b, то если a%b==0, то
НОД(a,b)=b,
иначе
НОД(a,b)=НОД(b,a%b)
иначе НОД(a,b)=НОД(b,a)
Во всех четырех примерах определяемое в пунктах б) (натуральное чис- ло, понятие факториала, произведения двух целых и алгоритм поиска наибольшего общего делителя двух натуральных чисел) выражалось че- рез самого себя, то есть выбранное нами определение обладает свойством рекурсивности (так нам захотелось).
Рекурсия применима не только для определения алгоритмов, но и для определения структур данных. В реальной жизни многие явления схематически можно изобразить в виде структурной системы, части которой связаны отношениями включения и подчинения. Такие системы называются иерархическими, их части – узлами, связи между ними
– связями или ссылками.
Примеры иерархических структур: Вселенная (Метагалактика – га- лактика – звездное скопление – звезда – планетная система); государ- ство (республика – область – район – населенный пункт); завод (службы управления и обеспечения – цеха – участки); родословная (ее схематиче- ское изображение – генеалогическое дерево); армейское соединение (ди- визия – полк – батальон – рота – взвод – отделение).
В дискретной математике иерархическим структурам сопоставляются модельные математические понятия списка, дерева, графа.
Список может служить моделью очереди к врачу в поликлинике;
дерево – моделью родословной (генеалогическое дерево) или, например,
моделью очередности встреч спортсменов по олимпийской системе;
граф – моделью станций и путей сообщения метрополитена и т.д.
Элемент списка (узел,звено) состоит как минимум из двух частей:
одна – содержательная (например, фамилия больного);
вторая – связующая (каждый должен помнить, за кем занял очередь).
Рекурсия позволяет определять подобные иерархические структуры.
56

• Рекурсивное определение списка:
а) Список – это либо пустая структура;
б) либо – элемент списка, указывающий на список из последующих элементов;
• Рекурсивное определение дерева:
а) дерево – это либо пустая структура;
б) либо – узел, связанный с конечным числом деревьев.
В обоих определениях налицо рекурсивность: понятие списка определя- ется через понятие списка; понятие дерева — через понятие дерева.
Если, например, сопоставить себе корень генеалогического дерева, то две дуги из корня приведут к матери и отцу, по две дуги от каждого из родителей приведут к бабушкам и дедушкам и так далее.
Во всех языках программирования есть понятие процедуры, которое сопоставляет алгоритму имя так, что, описав алгоритм один раз, полу- чаем возможность многократно вызывать его по имени.
Аналогично: во многих языках программирования можно из имею- щихся элементарных базовых типов строить более сложные структуры данных (массивы, структуры, динамические структуры; см. следующую тему “Немного о массивах, структурах и указателях”).
СИ, СИ++ и современный ФОРТРАН предоставляют возмож- ность использовать и рекурсивные функции, и рекурсивные структу- ры данных, то есть описывать алгоритм или структуру, используя внут- ри описания обращение (или ссылку) к самому описываемому объекту.
В ”древних” версиях ФОРТРАНа рекурсивные функции и подпро- граммы НЕ ДОПУСКАЛИСЬ. В частности, при вызове в главной про- грамме функции однократного интегрирования y=trap(f,a,b,n) (здесь f — процедура расчёта подынтегральной функции), в описание алгорит- ма f нельзя было включать вызов trap (что означало бы рекурсию) для расчёта интеграла, который мог бы присутствовать в подынтегральной функции. Приходилось описывать две функции (trap и trap1) однократ- ного интегрирования, совпадающие во всех деталях кроме имён функций
(и в главной программе, например, вызывать trap, а при расчёте подын- тегральной функции trap1).
57

2.1
Рекурсивные процедуры (простые примеры).
Процедура (функция или подпрограмма) называется рекурсивной, ес- ли ее описание явно или неявно содержит обращение к ней же самой.
2.1.1
Нерекурсивная и рекурсивная СИ-функции расчета n!
#include
//
Файл tstfactor.cpp using namespace std;
double factorn (int); double factorr1(int); double factorr2(int);
int main()
{int n;
double fn, fr1, fr2;
cout<<"введите n:"<>n; cout<<" n="<fn=factorn (n);
fr1=factorr1(n);
fr2=factorr2(n);
cout<<" nn!="<nr1!="<nr2!="<return 0;
}
double factorn(int n)
//
Файл factor.cpp
{ int i; double p;
// Нерекурсивная функция расчета n!
p=1; for (i=1;i<=n;i++) p*=i;
// Находит n! посредством оператора return p; }
// цикла.
double factorr1(int n)
// Рекурсивная функция расчета n!
{ if (n==0) return 1; else return n*factorr1(n-1); }
double factorr2(int n)
// Рекурсивная функция расчета n!
{ return(n==0 ? 1 : n*factorr2(n-1));}// (через тернарную операцию)
Нерекурсивная функция factorn(n) вызывается один раз и за счет внутреннего оператора цикла находит искомое произведение. Рекурсив- ная factorr1(n) в главной программе также вызывается один раз, опе- ратора цикла не содержит, но внутри своего тела вызывает сама себя до тех пор, пока не получит в качестве текущего аргумента 0. Каждый очередной рекурсивный вызов не только требует дополнительного вре- мени, но и захватывает новую ячейку памяти под формальный параметр n. Так что при расчете 3! из оперативной памяти будет зафрахтовано четыре дополнительные ячейки для хранения 3 (первый вызов), 2 (вто- рой вызов), 1 (третий вызов) и 0 (четвертый вызов). После завершения очередного вызова соответствующая зафрахтованная ячейка перейдет в ведение операционной системы.
введите n:
//
Результаты вызовов функций
3
//
factorn(n), factorr1(n) и factorr2(n) при n=3.
n=3
nn!=6
nr1!=6
nr2!=6 58