Введение в процедурное программирование. Управляющие инструкции

1. Программирование

Часть 3
Введение в процедурное программирование
Управляющие инструкции
1

2. 4. Процедурное программирование 4.1. Парадигмы программирования

Парадигма программирования — совокупность теорий,
стандартов и методов, используемых при разработке
программ.
Наиболее известные парадигмы программирования:
Процедурное программирование - парадигма программирования,
отражающая традиционную архитектуру компьютера - архитектуру Фон
Неймана. В соответствии с этой парадигмой программа
рассматривается как последовательность инструкций, задающих
процедуру решения задачи. Выполнение программы сводится к
последовательному выполнению инструкций с целью преобразования
исходного состояния памяти, то есть значений исходных данных, в
заключительное, то есть в результаты.
Объектно-ориентированное программирование - парадигма
программирования, основанная на представлении программы в виде
совокупности объектов, каждый из которых является экземпляром
определенного класса, а классы образуют иерархию наследования.
2

3. 4. Процедурное программирование 4.2. Принципы структурного программирования

Структурное программирование — методология
разработки программного обеспечения, предложенная в 70-х
года XX века Эдсгером Дейкстрой, разработанная и
дополненная Никласом Виртом, развитие парадигмы
процедурного программирования.
Цели структурного программирования:
Повышение эффективности и надежности программ
(разбиение на модули с дальнейшей независимой
оптимизацией модулей, простота тестирования и отладки)
Повышение производительности труда программиста
(обеспечение дисциплины программирования, улучшение
читабельности программ, повышение скорости
программирования и возможности коллективной
разработки программ)
3

4. 4. Структурное программирование 4.2. Принципы структурного программирования

Использование ограниченного числа управляющих
конструкций (структур):
следование (последовательное исполнение) – однократное
выполнение инструкцийй в том порядке, в котором они
записаны в тексте программы;
ветвление (выбор) – однократное выполнение одной из двух
или более инструкций, в зависимости от выполнения
некоторого заданного условия;
повторение (цикл) – многократное исполнение одной и той
же инструкции до тех пор, пока выполняется некоторое
заданное условие продолжения цикла.
В программе базовые конструкции могут быть вложены друг в
друга произвольным образом, но никаких других средств
управления последовательностью выполнения инструкций не
предусматривается.
4

5. 4. Структурное программирование 4.2. Принципы структурного программирования

Использование ограниченного числа управляющих
конструкций (структур):
Алгоритмические конструкции могут иметь только одну точку
входа и одну – выхода;
Инструкция goto не используется;
Не допускается излишняя вложенность алгоритмических
структур (не более 3-х уровней вложенности инструкции if)
Не используются языковые конструкции с неочевидной
семантикой и программистские «трюки»
5

6. 4. Структурное программирование 4.2. Принципы структурного программирования

Использование подпрограмм (процедур, функций) для
структурирования программ
Повторяющиеся фрагменты программы (либо не
повторяющиеся, но представляющие собой логически
целостные вычислительные блоки) оформляются в виде так
называемых подпрограмм (процедур или функций).
При выполнении размещаемой в программе инструкции вызова
подпрограммы (функции) выполняется эта подпрограмма, после
чего исполнение программы продолжается с инструкции,
следующей за командой вызова подпрограммы.
Каждая подпрограмма реализует только одну логическую
функцию
Подпрограмма (функция) имеет одну входную и выходную точку;
Размер подпрограммы не превышает 100 инструкций;
Число других подпрограмм, вызываемых подпрограммой, не
должно превышать 7.
6

7. 4. Структурное программирование 4.2. Принципы структурного программирования

Соблюдение специальных требований к оформлению
текстов программ
Каждая функция начинается с комментариев, объясняющих ее
назначение, назначение входных и выходных параметров,
содержащих перечень и назначение вызываемых ей функций,
номер версии и дата последней модификации;
В одной строке записывается не более одной инструкции (если
только группа инструкций не выполняет общее действие)
Если для записи одной инструкции требуется больше, чем
одна строка, все последующие строки записываются с
отступами
Тела инструкций цикла, ветвления, выбора записываются с
отступами
Идентификаторы всех объектов программы должны быть
смысловыми
Идентификаторы родственных объектов программы должны
начинаться с одинакового префикса
7

8. 4. Структурное программирование 4.2. Принципы структурного программирования

Пошаговая детализация при написании текста
программы
На первом шаге описывается общая схема работы в обозримой
линейной текстовой форме (т.е. с использованием очень
крупных понятий), причем это описание не является полностью
формализованным и ориентировано на восприятие его
человеком.
На каждом следующем шаге производится уточнение и
детализация одного из понятий, использованного (как правило,
неформализованно) в каком либо описании, разработанном на
одном из предыдущих шагов.
В результате такого шага создается описание выбранного
уточняемого понятия либо в терминах языка
программирования, либо в такой же форме, что и на первом
шаге с использованием новых уточняемых понятий.
8

9. 4. Структурное программирование 4.2. Принципы структурного программирования

Пошаговая детализация при написании текста
программы
Процесс детализации завершается, когда все уточняемые
понятия будут выражены в конечном счете на языке
программирования.
Последним шагом является получение текста программы на
языке программирования путем замены всех вхождений
уточняемых понятий заданными их описаниями и выражение
всех вхождений конструкций структурного программирования
средствами этого языка программирования.
9

10. 4. Структурное программирование 4.2. Принципы структурного программирования

Разработка программы методом «сверху вниз»
На первом этапе разрабатывается основная программа, в
которой вместо каждого связного логического фрагмента текста
вставляется вызов функции, которая будет выполнять этот
фрагмент.
Вместо настоящих, работающих функций, к программе
подключаются специально написанные функции - «заглушки»,
которые ничего не делают.
Полученная программа проверяется и отлаживается.
После того, как программист убедится, что функциивызываются
в правильной последовательности (то есть общая структура
программы верна), функции-заглушки последовательно
заменяются на реально работающие, причём разработка
каждой функции ведётся тем же методом, что и основной
программы.
10

11. 4. Структурное программирование 4.2. Принципы структурного программирования

Разработка программы методом «сверху вниз»
Разработка заканчивается тогда, когда не останется ни одной
функции - «заглушки», которая не была бы удалена.
Такая последовательность гарантирует, что на каждом этапе
разработки программист одновременно имеет дело с
обозримым и понятным ему множеством фрагментов, и может
быть уверен, что общая структура всех более высоких уровней
программы верна.
При сопровождении и внесении изменений в программу
выясняется, в какие именно функции нужно внести изменения,
и они вносятся, не затрагивая части программы,
непосредственно не связанные с ними.
11

12. 4. Структурное программирование 4.3. Базовые управляющие структуры

Компоненты конструкций структурного программирования
true
S
Действие
простая инструкция используемого языка
программирования (инструкция присваивания,
ввода, вывода, обращения к процедуре и др.),
фрагмент программы, являющийся композицией
основных конструкций структурного
программирования.
Каждая из этих конструкций имеет по управлению
только один вход и один выход. Тем самым, и
обобщенный оператор имеет только один вход и
один выход.
P
false
Условие (предикат):
выражение,
результатом которого
может быть true или
false
В зависимости от
значения выражения в
программе может быть
выполнена передача
управления тому или
иному узлу обработки
12

13. 4. Структурное программирование 4.3. Базовые управляющие структуры

Следование (последовательное исполнение)
S1
Действие 1
S2
Действие 2
13

14. 4. Структурное программирование 4.3. Базовые управляющие структуры

Ветвление (выбор)
Решение
[true]
S1
[false]
S2
14

15. 4. Структурное программирование 4.3. Базовые управляющие структуры

Повторение
Слияние
Решение
[true]
[false]
S
15

16. 4. Структурное программирование 4.3. Базовые управляющие структуры

Диаграмма деятельности — диаграмма, на которой показано
разложение некоторой деятельности на её составные части.
Правила построения структурированных программ
1. Начать с простейшей диаграммы деятельности, состоящей из
одного действия
2. Каждое состояние действия может быть заменено двумя
последовательными состояниями действия
3. Каждое состояние действия может быть заменено любой
управляющей структурой
4. Правила 2 и 3 могут применяться любое число раз и в любой
последовательности
16

17. 4. Структурное программирование 4.3. Базовые управляющие структуры

Вложенные структуры
Правило 2
Состояние действия
17

18. 4. Структурное программирование 4.3. Базовые управляющие структуры

Вложенные структуры
Правило 2
Правило 3
Состояние действия
Состояние действия
18

19. 4. Структурное программирование 4.3. Базовые управляющие структуры

Вложенные структуры
Состояние действия
Состояние действия
Правило
3
Правило
2
Состояние
Состояние
действия
действия
19

20. 4. Структурное программирование 4.3. Базовые управляющие структуры

Вложенные структуры
Состояние действия
Состояние действия
Состояние действия
Состояние действия
Состояние
действия
20

21. 4. Структурное программирование 4.4. Ветвления

Условная инструкция if…else
[true]
S1
[false]
S2
if (Условие)
инструкция1;
else
инструкция2;
21

22. 4. Структурное программирование 4.3. Ветвления

Пример использования инструкции if…else
int main() // determines is the entered number greater than 100 or not
{
int x;
cout << "\nEnter a number: ";
cin >> x;
if( x > 100 )
cout << "That number is greater than 100\n";
else
cout << "That number is not greater than 100\n";
return 0;
}
22

23. 4. Структурное программирование 4.3. Базовые управляющие структуры

Инструкция if
[true]
[false]
S1
if (Условие)
инструкция;
23

24. 4. Структурное программирование 4.4. Ветвления

Пример использования инструкции if
int main() // determines is the entered number greater than 100
{
int x;
cout << "\nEnter a number: ";
cin >> x;
if( x > 100 )
cout << "That number is greater than 100\n";
return 0;
}
24

25. 4. Структурное программирование 4.3. Ветвления

Несколько инструкций в теле if
#include <stdafx.h>
#include <time.h>
using namespace std;
int main() //Guess a magic number
{
unsigned int guess = 0;
unsigned int magic = time (NULL); //returns number of sec. from 01/01/1970
magic &= 0x00000007; // generates pseudo random in [0-7]
cout << "Guess the magic number: "; cin >> guess;
if(guess == magic)
{
cout << endl << "** Right ** magic " ;
cout << magic << "==" << guess << " (guess}";
}
getch ();
return 0;
}
25

26. 4. Структурное программирование 4.3. Ветвления

Несколько инструкций в теле if…else
…
int main() // Guess a magic number (with message if guessing wasn’t success)
{
…
if (guess == magic)
{
cout << endl << "** Right ** magic " ;
cout << magic << "==" << guess << " (guess}";
}
else
{
cout << endl << "** Wrong ** magic ";
cout << magic << “!=" << guess << " (guess}";
}
…
}
26

27. 4. Структурное программирование 4.3. Ветвления

Вложенные инструкции if…else
…
int main() // more complicated program to guess a magic number
{
…
if (guess == magic)
{
cout << endl << "** Right ** magic " ;
cout << magic << "==" << guess << " (guess}";
}
else
{
cout << endl << "** Wrong ** ";
if (guess > magic) cout << " too high " ;
else cout << " too low " ;
}
…
}
27

28. 4. Структурное программирование 4.3. Ветвления

Вложенные инструкции: соответствие if и else
…
int main()
{
…
if (i)
{
if (j) инструкция 1;
if (k) инструкция 2;
else инструкция 3;
}
else инструкция 4;
…
}
28

29. 4. Структурное программирование 4.3. Ветвления

Вложенные инструкции: соответствие if и else
…
int main()
{
…
if (i)
{
if (j) инструкция 1;
if (k) инструкция 2;
else инструкция 3;
}
else инструкция 4;
…
}
Во вложенных условных
инструкциях раздел else всегда
связан с ближайшим
предшествующим инструкцияом if,
находящимся с ним в одном блоке и
не связанном с другим разделом
else.
29

30. 4. Структурное программирование 4.3. Ветвления

Цепочка инструкций if-else
…
int main()
{
…
if (Выражение) инструкция;
else
if (Выражение) инструкция;
else
if (Выражение) инструкция;
…
else инструкция;
…
}
30

31. 4. Структурное программирование 4.3. Ветвления

Цепочка инструкцияов if-else (другой формат записи)
…
int main()
{
…
if (Выражение)
инструкция;
else if (Выражение)
инструкция;
else if (Выражение)
инструкция;
…
else
инструкция;
…
}
31

32. 4. Структурное программирование 4.3. Ветвления

Цепочка инструкцияов if-else
…
int main() // another more complicated program to guess a magic number
{
…
if (guess == magic)
{
cout << endl << "** Right ** magic " ;
cout << magic << "==" << guess << " (guess}";
}
else if (guess > magic)
cout << “** Wrong ** too high " ;
else
cout << “** Wrong ** too low " ;
}
…
}
32

33. 4. Структурное программирование 4.3. Ветвления

Пример: анализ результатов тестирования
if (grade >=90) cout << “excellent”;
else
if (grade >=70) cout << “very good”;
else
if (grade >=50) cout << “good”;
else
if (grade >=15) cout << “poor”;
else
cout << “very bad”;
if (grade>=90) cout << “excellent”;
if (grade>=70 && grade<90) cout << “very good”;
if (grade>=50 && grade<70 ) cout << “good”;
if (grade >=15 && grade<50) cout << “poor”;
if (grade<15) cout << “very bad”;
33

34. 4. Структурное программирование 4.3. Ветвления

Демонстрация многовариантности использования if … else
Задача.
Даны три вещественных числа a, b, c.
Записать на языке С++ алгоритм нахождения
наименьшего из этих чисел
34

35. 4. Структурное программирование 4.3. Ветвления

Демонстрация многовариантности использования if … else
Алгоритм 1 (используем цепочку if –then-else)
if ((a <= b) && (a<=c)) min = a;
else if ((b <= c) && (b<=a)) min = b;
else if ((c<=b) && (c<=a)) min = c;
if ((a<=b) && (a<=c)) min = a;
else if ((b<=c) && (b<=a)) min = b;
else min=c;
if ((a<=b) && (a<=c)) min = a;
else if (b<=c) min = b;
else min = c;
35

36. 4. Структурное программирование 4.3. Ветвления

Демонстрация многовариантности использования if … else
Алгоритм 2 (простой и надежный)
min = a;
if (b < min) min = b;
if (c < min) min = c;
Алгоритм 3 (вложенные if… else)
if (a <= b)
if (a <= c) min = a;
else min = c;
else
if (b <=c ) min = b;
else min = c;
36

37. 4. Структурное программирование 4.3. Ветвления

Демонстрация многовариантности использования if … else
Алгоритм 1 (используем цепочку if –then-else)
if (a<=b) and (a<=c) then min = a;
else if (b<=c) then min = b;
else min = c;
Алгоритм 2 (простой и надежный)
min = a;
if (b < min) min = b;
if (c < min) min = c;
Алгоритм 3 (вложенные if… else)
?
if (a <= b)
if (a <= c) min = a;
else min = c;
else
if (b <=c ) min = b;
else min = c;
37

38. 4. Структурное программирование 4.3. Ветвления

Простейший анализ вычислительной сложности
алгоритмов
№
Сравнеалго- ний/присваритма иваний
a<b<c a<c<b b<c<a b<a<c c<b<a
c<a<b
1.
2,6/1
2/1
2/1
3/1
3/1
3/1
3/1
2.
2/1,8
2/1
2/1
2/2
2/3
2/2
2/2
3.
2/1
2/1
2/1
2/1
2/1
2/1
2/1
38

39. 4. Структурное программирование 4.3. Ветвления

Простейший анализ вычислительной сложности
алгоритмов
Примерное время выполнения операций (P-200), 10-9 с:
short
float
Сравнение
10
350
Присваивание
5
300
39

40. 4. Структурное программирование 4.3. Ветвления

Результат: законченная программа вычисления min (a,b,c)
int main() // Calculates min value of a,b,c
{
float a=0, b=0,c=0, min=0;
cout << "Enter a, b, c divided by blanks:";
cin >> a >> b >> c;
if (a <= b)
if (a <= c) min = a;
else min = c;
else
if (b <=c ) min = b;
else min = c;
cout << endl << "The minimum value is " << min;
getch ();
return 0;
}
40

41. 4. Структурное программирование 4.3. Ветвления

Тернарный условный оператор ?
Выражение1 ? Выражение2 : Выражение3;
вместо
x = 10;
[Выражение 1 true]
if (x > 9) y = 100;
else y = 200;
Вернуть
значение
можно
Выражения 2
x = 10;
y = x > 9 ? 100 : 200;
[Выражение 1 false]
Вернуть
значение
Выражения 3
41

42. 4. Структурное программирование 4.3. Ветвления

Тернарный условный оператор ?
#include <stdafx.h>
using namespace std;
int main() //Calculates square of float and sets it's sign to the result
{
float a = 0, sqr = 0;
cout << "Enter a:"; cin >> a;
sqr = a < 0 ? -a*a : a*a;
cout << endl << "The result is " << sqr;
getch ();
return 0;
}
42

43. 4. Структурное программирование 4.3. Ветвления

Полученное ранее решение задачи min (a,b,c)
с помощью if…else
int main() // Calculates min value of a,b,c
{
float a=0, b=0,c=0, min=0;
cout << "Enter a, b, c divided by blanks:";
cin >> a >> b >> c;
if (a <= b)
if (a <= c) min = a;
else min = c;
else if (b <=c ) min = b;
else min = c;
cout << endl << "The minimum value is " << min;
getch ();
return 0;
}
43

44. 4. Структурное программирование 4.3. Ветвления

Решение задачи min (a,b,c) с помощью условного оператора
int main() // Calculates min value of a,b,c using conditional operator
{
float a=0, b=0,c=0, min=0;
cout << "Enter a, b, c divided by blanks:";
cin >> a >> b >> c;
min = a<=b ? (a<=c ? a : c) : (b<=c ? b : c);
cout << endl << "The minimum value is " << min;
getch ();
return 0;
}
44

45. 4. Структурное программирование 4.3. Ветвления

Вызовы функций из условного оператора
#include <stdafx.h>
using namespace std;
int f1(int n);
int f2();
int f3 ();
int main() // Demonstrates functions' calls by the conditional operator
{
int t=0;
cout << "Enter a number: "; cin >> t;
// prints proper message:
t ? f1(t) + f2() : f3 (); // int t as boolean, ignore values to be return
getch ();
return 0;
}
45

46. 4. Структурное программирование 4.3. Ветвления

Вызовы функций из тернарного условного оператора
int f1(int n) // first message if non-zero number entered
{
cout << endl << n;
return 0;
}
int f2() // second message if non-zero number entered
{
cout <<" entered.\n";
return 0;
}
int f3() // message if zero entered
{
cout <<"\nZero entered.\n";
return 0;
}
46

47. 4. Структурное программирование 4.3. Ветвления

Инструкция switch
[true]
Case 1
Действия
для 1
break
Действия
для 2
break
Действия
для n
break
[false]
[true]
Case 2
[false]
[true]
Case n
[false]
Default: действия
по умолчанию
switch (Выражение)
{
case константа1:
последовательность инструкций;
break;
case константа2:
последовательность инструкций;
break;
case константа3:
последовательность инструкций;
break;
.
.
.
default
последовательность инструкций;
47

48. 4. Структурное программирование 4.3. Ветвления

Инструкция switch: пример функции «простейшее меню»
void menu()
{
cout <<"1. Check Spelling\n” << "2. Correct Spelling Errors\n” <<"3. Display Errors\n”;
cout <<"Strike Any Other Key to Skip\n” << "
Enter your choice: “;
char ch = getchar(); // read the selection from the keyboard
switch (ch) {
case '1':
check_spelling(); break;
case '2':
correct_errors(); break;
case '3':
display_errors(); break;
default :
printf("No option selected");
}
}
48

49. 4. Структурное программирование 4.3. Ветвления

Инструкция switch: опускаем break
// Process a value of i
void inp_handler(int i)
{
int flag=-1;
switch(i) {
case 1: // These cases have common
case 2: // statement sequences.
case 3:
flag = 0; break;
case 4:
flag = 1;
case 5:
error(flag); break;
default:
process(i);
}
Рассмотрим
возможные
входные
значения i
}
49

50. 4. Структурное программирование 4.3. Ветвления

Инструкция switch: опускаем break
// Process a value of i
void inp_handler(int i)
{
int flag = -1;
switch(i) {
case 1: // These cases have common
case 2: // statement sequences.
case 3:
flag = 0; break;
case 4:
flag = 1;
case 5:
error(flag); break;
default:
process(i);
}
Если i == 1
или i == 2
или i == 3
}
50

51. 4. Структурное программирование 4.3. Ветвления

Инструкция switch: опускаем break
// Process a value of i
void inp_handler(int i)
{
int flag = -1;
Если i == 4
switch(i) {
case 1: // These cases have common
case 2: // statement sequences.
case 3:
flag = 0; break;
case 4:
flag = 1;
case 5:
error(flag); break; // with flag == 1
default:
process(i);
}
}
51

52. 4. Структурное программирование 4.3. Ветвления

Инструкция switch: опускаем break
// Process a value of i
void inp_handler(int i)
{
int flag = -1;
Если i == 5
switch(i) {
case 1: // These cases have common
case 2: // statement sequences.
case 3:
flag = 0; break;
case 4:
flag = 1;
case 5:
error(flag); break; // with flag == -1
default:
process(i);
}
}
52

53. 4. Структурное программирование 4.3. Ветвления

Инструкция switch: опускаем break
// Process a value of i
void inp_handler(int i)
{
int flag = -1;
switch(i) {
case 1: // These cases have common
case 2: // statement sequences.
case 3:
flag = 0; break;
case 4:
flag = 1;
case 5:
error(flag); break;
default:
process(i);
}
Если (i != 1) &
(i !=2) & (i !=3) &
(i !=4) & (i != 5)
}
53

54. 4. Структурное программирование 4.3. Ветвления

Заменяем switch на if …else
// Process a value of i
void inp_handler(int i)
{
int flag = -1;
if (i == 1 || i==2 || i==3) flag = 0;
else
{
if (i==4) flag = 1;
if (i==5||i==4) error(flag);
}
if (i<0 || i >5) process (i); // it’s not so easy to simulate the default branch in switch
}
54

55. 4. Структурное программирование 4.4. Повторение

Цикл «пока» или «while»
while (Условие)
инструкция;
[true]
[false]
S
• Тело цикла может не исполняться ни разу
• Требует инициализации переменных
условия до входа в цикл
while (Условие)
{
инструкция1;
инструкция2;
инструкция3;
…
}
55

56. 4. Структурное программирование 4.4. Повторение

Пример цикла while (вывод на экран ASCII кода клавиши)
#include <stdafx.h>
using namespace std;
int main() // Waiting for a char and displays it's ASCII code
{
char ch = 0; // inits var that condition contains
while (ch != 27) // while not Esc pressed
{
ch=_getch(); // changes var that condition contains
cout << ch << " = " << ch+0 << endl;
}
Мелкая шалость:
return 0;
неявное
}
преобразование к int
56

57. 4. Структурное программирование 4.4. Повторение

Пример цикла while: цикл не выполнится ни разу
#include <stdafx.h>
using namespace std;
int main() // Waiting for a char and displays it's ASCII code
{
char ch = 27; // inits var ch with 27 and the condition will be false !!!
while (ch != 27) // the body of the cycle can’t be executed
{
ch=_getch(); // changes var that condition contains
cout << ch << " = " << ch+0 << endl;
}
return 0;
}
57

58. 4. Структурное программирование 4.4. Повторение

Пример цикла while: иногда можно и не инициализировать…
#include <stdafx.h>
using namespace std;
int main() // Waiting for a char and displays it's ASCII code
{
char ch=27; // or simply char ch;
while ( (ch = getch ()) != 27) // the best way to enter ch
cout << ch << " = " << static_cast <int> (ch) << endl;
В отличие
о первой
версии
значение
Esc не
выведется
return 0;
}
устранили
мелкую
шалость
58

59. 4. Структурное программирование 4.4. Повторение

Задача: цикл while + стратегия пошаговой детализации
Постановка задачи
Методом последовательных приближений найти решение
уравнения x-cos(x)=0 с заданной точностью r.
Математическая модель .
Перепишем уравнение в виде x=f(x)
Выберем начальное приближение x0
Положим x1=f(x0);
x2=f(x1);
…
xn=f(xn-1)
Погрешность d = |xn-1-f(xn-1)| = |xn-1-xn|
Условие сходимости: |f'(x)|<1
59

60. 4. Структурное программирование 4.4. Повторение

Находим решение
уравнения x-cos(x)=0
60

61. 4. Структурное программирование 4.4. Повторение

Задать начальное значение x=x0, точность r
Уточнить решение методом последовательных
приближений
Вывести значение x
61

62. 4. Структурное программирование 4.4. Повторение

Задать начальное значение x=x0, точность r
Инициализировать текущую погрешность d=2*r
Выполнять, пока
текущая погрешность
d>r
[d>r]
Уточнение x
[d<r]
Вывести значение x
62

63. 4. Структурное программирование 4.4. Повторение

Задать начальное значение x=x0, точность r
Инициализировать текущую погрешность d=2*r
Выполнять, пока
текущая погрешность
d>r
[d>r]
[d<=r]
Вычислить y=cos(x)
Положить d=|x-y|
Положить x=y
Вывести значение x
63

64. 4. Структурное программирование 4.4. Повторение

Алгоритм на псевдокоде
Псевдокод – искусственный неформальный язык,
позволяющий однозначно трактовать описываемые на нем
действия.
Данные.
Заданная точность
float r
Текущая погрешность
float d
Текущее значение xn-1
float x
Текущее значение f(xn-1) float y
Алгоритм.
1. Задать x=x0, r
2. Уточнить решение методом последовательных приближений
3. Вывести значение x
64

65. 4. Структурное программирование 4.4. Повторение

Алгоритм на псевдокоде: уточнение
Данные.
Заданная точность
float r
Текущая погрешность
float d
Текущее значение xn-1
float x
Текущее значение f(xn-1) float y
Алгоритм.
1. Задать x=x0, r
2. Инициализировать d
3. Пока d>r выполнять
3.1. Вычислить y = cos(x)
Метод последовательных
3.2. Положить d = |x-y|
приближений
3.3. Положить x = y
4. Вывести значение x
65

66. 4. Структурное программирование 4.4. Повторение

Программа на С++: детализируем псевдокод
int main() // Solves nonlinear equation x=cos (x)
{
float x=0.f, r=1e-6f, y=0.f; //start value of x, precision, value of cos(x)
cout << "Enter start value of x : "; cin >> x;
cout << "Enter required precision : "; cin >> r;
Данные
1. Задать x=x0, r
float d = 2*r; //current precision
2. Инициализировать d
while (d > r)
{
y = cos(x);
3. 1. Вычислить y=cos(x)
3. Пока d>r выполнить
d = abs(x-y);
3. 2. Положить d = |x-y|
3. 3. Положить x=y
x = y;
}
cout << "The solution is x = " << x;
4. Вывести значение x
_getch();
return 0;
}
66

67. 4. Структурное программирование 4.4. Повторение

Программа на С++
int main() // Solves nonlinear equation x=cos (x)
{
float x=0.f, r=1e-6f, y=0.f; //start value of x, precision, value of cos(x)
cout << "Enter start value of x : "; cin >> x;
cout << "Enter required precision : "; cin >> r;
float d = 2*r; //current precision
while (d > r)
{
y = cos(x);
d = abs(x-y);
x = y;
}
cout << "The solution is x = " << x;
_getch();
return 0;
}
67

68. 4. Структурное программирование 4.4. Повторение

Программа на С++
int main() // Solves nonlinear equation x=cos (x)
{
float x=0.f, r=1e-6f, y=0.f; //start value of x, precision, value of cos(x)
cout << "Enter start value of x : "; cin >> x;
cout << "Enter required precision : "; cin >> r;
float d = 2*r; //current precision
while (d > r)
{
y = cos(x);
d = abs(x-y);
x = y;
}
cout << "The solution is x = " << x;
_getch();
return 0;
Опасность :
если величина r
сопоставима с
погрешностью чисел
float, то цикл никогда не
завершится !!!
}
68

69. 4. Структурное программирование 4.4. Повторение

Сопровождение
int main() // Solves nonlinear equation x=cos (x)
{
float x=0.f, r=1e-6f, y=0.f; //start value of x, precision, value of cos(x)
cout << "Enter start value of x : "; cin >> x;
cout << "Enter required precision : "; cin >> r;
if (r < 1e-6f) r=1e-6; // elementary input data checking
float d = 2*r; //current precision
while (d > r)
{
y = cos(x);
d = abs(x-y);
x = y;
}
cout << "The solution is x = " << x;
_getch();
return 0;
}
69

70. 4. Структурное программирование 4.2. Базовые управляющие структуры

Повторение (цикл «до тех пор» или «do while»)
do
инструкция;
while (Условие)
S
[true]
[false]
do
{
инструкция1;
инструкция2;
…
}
while (Условие)
• Тело цикла обязательно исполняется хотя бы один раз
• Не требует обязательной инициализации переменных
условия до входа в цикл
70

71. 4. Структурное программирование 4.4. Повторение

Задача: цикл do while + стратегия пошаговой детализации
(без изменений)
Постановка задачи
Методом последовательных приближений найти решение
уравнения x-cos(x)=0 с заданной точностью r.
Математическая модель .
Перепишем уравнение в виде x=f(x)
Выберем начальное приближение x0
Положим x1=f(x0);
x2=f(x1);
…
xn=f(xn-1)
Погрешность d = |xn-1-f(xn-1)| = |xn-1-xn|
Условие сходимости: |f'(x)|<1
71

72. 4. Структурное программирование 4.4. Повторение

Алгоритм на псевдокоде
(без изменений)
Данные.
Заданная точность
float r
Текущая погрешность
float d
Текущее значение xn-1
float x
Текущее значение f(xn-1) float y
Алгоритм.
1. Задать x=x0, r
2. Уточнить решение методом последовательных приближений
3. Вывести значение x
72

73. 4. Структурное программирование 4.4. Повторение

Алгоритм на псевдокоде: уточнение с циклом do-while
Данные.
Заданная точность
float r
Текущая погрешность
float d
Текущее значение xn-1
float x
Текущее значение f(xn-1) float y
Алгоритм.
Предварительная
инициализация d
1. Задать x=x0, r
не нужна !!!
2. Выполнять :
2.1. Вычислить y = cos(x)
2.2. Положить d = |x-y|
Метод последовательных
2.3. Положить x = y
приближений
пока d>r
4. Вывести значение x
73

74. 4. Структурное программирование 4.4. Повторение

Алгоритм на псевдокоде:
контроль величины точности с циклом do-while
Данные.
Заданная точность
float r
Текущая погрешность
float d
Текущее значение xn-1
float x
Здесь тоже
Текущее значение f(xn-1) float y
предварительная
Алгоритм.
инициализация r
1. Ввести x=x0
не обязательна
2. Выполнять : вводить r пока r < 10-6
3. Выполнять
3.1. Вычислить y = cos(x)
3.2. Положить d = |x-y|
3.3. Положить x = y
пока d>r
4. Вывести значение x
74

75. 4. Структурное программирование 4.4. Повторение

Программа на С++
int main() // Solves nonlinear equation x=cos (x)
{
float x=0.f, r=1e-6f, y=0.f, d=1.f;
cout << "Enter start value of x : "; cin >> x;
do
{ cout << "Enter required precision (not less than 1e-6): "; cin >> r; }
while (r < 1e-6f);
do
{
y = cos(x);
d=abs(x-y); x = y;
}
while (d > r);
cout << "The solution is x = " << x;
_getch();
return 0;
}
75

76. 4. Структурное программирование 4.4. Повторение

Задача:
нахождение суммы конечного числа членов ряда
Постановка задачи.
Найти значение суммы первых 10 членов ряда
n
1
S i
i 0 2
76

77. 4. Структурное программирование 4.4. Повторение

Алгоритм на псевдокоде
Данные.
Заданное число членов ряда unsigned short n
Сумма ряда float s
Счетчик unsigned short i
Алгоритм.
1. Задать число суммируемых членов n
2. Положить s = 0
3. Положить значение счетчика i = 0
4. Пока i <= n выполнять
4.1 s = s + 1/2i
4.2 увеличить значение счетчика i = i+1
3. Вывести значение s
77

78. 4. Структурное программирование 4.4. Повторение

Программа на С++
int main()
{
const unsigned short n=5; //number of terms
float s = 0.f;
unsigned short i = 0;
while (i <= n)
{
s=s+1.0/ pow(2.0,i); //pow calculates double raised to integer (math.h)
i++;
}
cout << "The sum is equal to " << s;
_getch();
return 0;
}
78

79. 4. Структурное программирование 4.4. Повторение

Программа на С++
int main()
{
const unsigned short n=5; //number of terms
float s = 0.f;
unsigned short i = 0; // initialization
while (i <= n)
// condition
{
s=s+1.0/ pow(2.0,i); //pow calculates double raised to integer (math.h)
i++;
// increment
}
cout << "The sum is equal to " << s;
_getch();
return 0;
}
79

80. 4. Структурное программирование 4.4. Повторение

Алгоритм на псевдокоде
Данные.
Заданное число членов ряда unsigned short n
Сумма ряда float s
Счетчик unsigned short i
Алгоритм.
1. Задать число суммируемых членов n
2. Положить s = 0
3. Положить значение счетчика i = 0
(Инициализация)
4. Пока i <= n выполнять
(Условие)
4.1 s = s + 1/2i
4.2 увеличить значение счетчика i = i+1 (Приращение)
3. Вывести значение s
80

81. 4. Структурное программирование 4.4. Повторение

Цикл со счетчиком
for (Инициализация; Условие; Приращение)
инструкция;
Инициа
лизация
[true]
[false]
S
Приращение
for (Инициализация; Условие; Приращение)
{
инструкция1;
инструкция2;
…
}
• Тело цикла может не исполняться ни разу
• Инициализация переменных условия обычно выполняется в
заголовке цикла
• Не следует изменять переменные условия в теле цикла
81

82. 4. Структурное программирование 4.4. Повторение

Алгоритм на псевдокоде
Данные.
Заданное число членов ряда unsigned short n
Сумма ряда float s
Счетчик unsigned short i
Алгоритм.
1. Задать число суммируемых членов n
2. Положить s = 0
3. Для всех i от 0 до n выполнять
3.1 s = s + 1/2i
4. Вывести значение s
82

83. 4. Структурное программирование 4.4. Повторение

Программа на С++
int main()
{
const unsigned short n=10; //number of terms
float s = 0.f;
for (unsigned short i=0; i <= n; i++)
// it’s a good style to declare i here
s = s + 1.0 / pow(2.0,i);
// i is visible and lives only into the loop body
cout << "The sum is equal to " << s;
_getch();
return 0;
}
83

84. 4. Структурное программирование 4.4. Повторение

Программа на С++
int main()
{
const unsigned short n=10; //number of terms
float s = 0.f;
for (unsigned short i=0; i <= n; i++)
s += 1.0 / pow(2.0,i);
// it’s the c-style
cout << "The sum is equal to " << s;
_getch();
return 0;
}
Время выполнения –
10,4 микросекунды
84

85. 4. Структурное программирование 4.4. Повторение

Оптимизация программы на С++
int main()
{
const unsigned short n=10; //number of terms
float s = 0.f;
unsigned int p=1; // we will optimize calculations into the loop body
for (unsigned short i=0 ; i <= n; i++)
{
s += 1.0 / p; p <<= 1;
// p=p*2
}
cout << "The sum is equal to " << s;
_getch();
return 0;
Время выполнения
}
–
7,2 микросекунды
85

86. 4. Структурное программирование 4.4. Повторение

Задача построения таблицы функции
вещественного аргумента
Постановка задачи.
Построить таблицу функции y=sin(x),
аргумент x изменяется от 0 до 1 с шагом 0.1
86

87. 4. Структурное программирование 4.4. Повторение

Алгоритм на псевдокоде
(если бы счетчик мог быть только целым)
Данные.
Число рассчитываемых значений +1 unsigned short n
Текущее значение аргумента double x
Текущее значение функции double y
Приращение аргумента double delta
Счетчик unsigned short i
Алгоритм.
1. Задать число значений n и приращение delta
2. Напечатать шапку таблицы
3. Для всех i от 0 до n выполнять
3.1 Положить x = delta*i
3.2 Вычислить y = sin(x)
3.3 Вывести значения x и y
87

88. 4. Структурное программирование 4.4. Повторение

Программа на С++
int main()
{
const unsigned short n=10; //number of terms
const double delta = 0.1f;
cout <<"
x
y" << endl;
cout <<"-----------------------" << endl;
for (unsigned short i=0 ; i <= n; i++)
{
double x = delta * i; //we don't need x and y outside the body
double y = sin (x);
cout << setw(8) << x << setw(15) << y << endl;
}
_getch();
return 0;
}
88

89. 4. Структурное программирование 4.4. Повторение

Модификация программы на С++
(руки оторвать!!!)
int main()
{
const unsigned short n=10; //number of terms
const double delta = 0.1;
cout <<"
x
y" << endl;
cout <<"-----------------------" << endl;
for (unsigned short i= -1 ; i++-n; )
// an idiot only can write such code
{
double x = delta * i;
double y = sin (x);
cout << setw(8) << x << setw(15) << y << endl;
}
_getch();
return 0;
}
89

90. 4. Структурное программирование 4.4. Повторение

Алгоритм на псевдокоде
(в С++ счетчик может быть не только целым)
Данные.
Начальное значение аргумента double x_beg
Конечное значение аргумента double x_end
Текущее значение аргумента double x
Текущее значение функции double y
Приращение аргумента double delta
Алгоритм.
1. Задать x_beg, x_end и delta
2. Напечатать шапку таблицы
3. Для всех x от x_beg до x_end с шагом delta выполнять
3.1 Вычислить y = sin(x)
3.2 Вывести значения x и y
90

91. 4. Структурное программирование 4.4. Повторение

Модификация программы на С++
(бесконечный цикл !!!)
int main()
{
const double x_beg = 0, x_end = 1, delta = 0.1;
cout <<"
x
y" << endl;
cout <<"-----------------------" << endl;
for (double x = x_beg ; x==x_end; x += delta )
{
double y = sin (x);
cout << setw(8) << x << setw(15) << y << endl;
}
_getch();
return 0;
}
91

92. 4. Структурное программирование 4.4. Повторение

Модификация программы на С++
int main()
{
const double x_beg = 0, x_end = 1, delta = 0.1;
cout <<"
x
y" << endl;
cout <<"-----------------------" << endl;
for (double x = x_beg ; x<=x_end+1e-10; x += delta ) // prec. is 1e-14
{
double y = sin (x);
cout << setw(8) << x << setw(15) << y << endl;
}
_getch();
return 0;
}
92

93. 4. Структурное программирование 4.4. Повторение

Цикл for с двумя счетчиками
int main() // Using multiple counters to show powers of 2
{
int i = 0, power = 0;
const int max = 10;
for(i = 0, power = 1; i <= max; i++, power += power)
cout << endl << setw(10) << i << setw(10) << power;
cout << endl;
return 0;
0
1
2
3
4
5
6
7
8
9
10
1
2
4
8
16
32
64
128
256
512
1024
}
Операция последовательного вычисления «запятая» может
применяться в разделах инициализации и вычисления
приращения. Ее применение в разделе условия бессмысленно
(возвращается в качестве условия последнее значение)
93

94. 4. Структурное программирование 4.4. Повторение

Циклы for без тела
int main() // Solves equation x=cos(x) : real perversion
{
float x =1; cout << "Enter start value of x : "; cin >> x;
for (float d=1, r=1e-5f, y=0 ; d>r ; y=cos(x), d=abs(y-x), x=y);
cout << x;
_getch();
return 0;
}
…
for (unsigned int i=0; i < 2000000; i++);
// time delay for 200000 loops
…
for (unsigned int t_beg=time(NULL); time(NULL) - t_beg != 10; );
// time delay for 10 sec. Perversion? May be…
…
for ( ; ; ); //endless loop
94

95. 4. Структурное программирование 4.4. Повторение

Сравнение циклов
while (Условие)
do
инструкция;
while (Условие);
for (Иниц-я; Условие; Приращ-ие)
инструкция;
Цикл «пока»
Цикл «до тех пор»
Цикл со счетчиком
Инициализация
переменных,
управляющих
условием цикла,
должна быть сделана
до его начала
Переменные,
управляющие условием
цикла, могут быть
проинициализированы
как до начала цикла, так
и в его теле
Начальная установка переменных
(счетчиков) цикла до заголовка обычно не
требуется и выполняется в первой части
заголовка цикла (инициализация)
условие выполнения
проверяется до входа
в цикл
условие выполнения
проверяется после
первого выполнения
тела цикла
условие выполнения проверяется до
входа в цикл
инструкция;
В теле цикла должны присутствовать
инструкции, изменяющие переменные условия,
чтобы цикл через некоторое число итераций
завершился
Изменение в теле цикла значений
переменных, стоящих в его заголовке
нежелательно
95

96. 4. Структурное программирование 4.4. Повторение

Сравнение циклов
while (Условие)
инструкция;
Цикл «пока»
do
инструкция;
while (Условие)
for (Иниц-я; Условие; Приращ-ие)
инструкция;
Цикл «до тех пор»
Цикл со счетчиком
Цикл работает, пока условие является истинным
Цикл завершается, когда условие становится
ложным
Количество итераций цикла обычно
определяется в заголовке значениями
нижней и верхней границ счетчика и шага
цикла (приращения)
Цикл может не
выполниться ни разу,
если исходное
значение условия при
входе в цикл ложно
Цикл может не выполниться ни разу, если
исходное значение условия при входе в
цикл ложно
Цикл обязательно
выполняется как
минимум один раз
Если в теле цикла требуется более одной инструкции, то необходимо использовать составную
инструкцию (операторные скобки) { }
96

97. 4. Структурное программирование 4.4. Повторение

Сравнение циклов
while (Условие)
do
инструкция;
while (Условие)
for (Иниц-я; Условие; Приращ-ие)
инструкция;
Цикл «до тех пор»
Цикл со счетчиком
инструкция;
Цикл «пока»
Обычно применяется когда:
• количество итераций
заранее неизвестно
• значения переменных,
определяющие
условие выполнения
известны до входа в
цикл
• тело цикла может не
исполняться ни разу
• количество итераций
заранее неизвестно
• значения переменных,
определяющие
условие выполнения
вычисляются в теле
цикла
• тело цикла должно
выполняться хотя бы
один раз
• количество итераций известно
заранее
• количество итераций задается
изменением переменной-счетчика от
начального значения до значения,
определяемого условием путем
приращения
• тело цикла может не исполняться ни
разу
97

98. 4. Структурное программирование 4.4. Повторение

Оператор break
инструкция заголовка цикла
{
инструкция1;
инструкция2;
break;
инструкция3;
инструкция4;
…
}
инструкция, следующая за циклом
98

99. 4. Структурное программирование 4.4. Повторение

Оператор break: стандартный прием использования
true
инструкция заголовка цикла
{
инструкция1;
инструкция2;
if (Условие_досрочного_выхода) break;
инструкция3;
инструкция4;
…
}
инструкция, следующая за циклом
99

100. 4. Структурное программирование 4.4. Повторение

Пример, где нужен оператор break
// calculates 1./x while x != 0
int main()
{
float x=1.f;
while (x != 0)
{
cin >> x;
cout << endl << x << " " << 1.0 / x; //division on zero when x == 0
}
return 0;
}
100

101. 4. Структурное программирование 4.4. Повторение

Пример использования оператора break
// calculates 1./x while x != 0
int main()
{
float x=0.; // the initialization is not required
while (true) // endless loop. Alternative is for ( ; ;);
{
cin >> x; if (x == 0) break;
cout << endl << x << " " << 1.0 / x;
}
return 0;
}
101

102. 4. Структурное программирование 4.4. Повторение

Оператор continue
инструкция while или for
{
инструкция1;
инструкция2;
continue;
инструкция3;
инструкция4;
…
}
инструкция do
{
инструкция1;
инструкция2;
continue;
инструкция3;
инструкция4;
…
}
while (Условие_цикла) ;
102

103. 4. Структурное программирование 4.4. Повторение

Оператор continue: стандартный прием использования
Инструкция while или for
инструкция do
{
{
инструкция1;
инструкция1;
инструкция2;
инструкция2;
true if (Условие_перехода) continue;
if
(Условие_перехода)
continue;
true
инструкция3;
инструкция3;
инструкция4;
инструкция4;
…
…
}
}
while (Условие_цикла) ;
103

104. 4. Структурное программирование 4.4. Повторение

Пример, где нужен инструкция continue
// calculates product of non-negative x excepting 0. Finish if x<0
int main()
{
float x=0.f, p=1.f;
do
{
cin >> x;
if (x == 0) continue;
if (x < 0) break;
p *= x;
}
while (true);
cout << endl << p;
_getch();
return 0;
}
104

105. 4. Структурное программирование 4.4. Повторение

Как обойтись без continue
инструкция while или for
{
инструкция1;
инструкция2;
true
if (!Условие_перехода)
{
инструкция3;
инструкция4;
…
}
}
инструкция do
{
инструкция1;
инструкция2;
true if (!Условие_перехода)
{
инструкция3;
инструкция4;
…
}
}
while (Условие_цикла) ;
105

106. 4. Структурное программирование 4.4. Повторение

Как обойтись без break
while (Условие_цикла && !Условие_досрочного_выхода)
{
инструкция1;
инструкция2;
true if (!Условие_досрочного_выхода)
{
инструкция3;
инструкция4;
…
}
}
инструкция, следующая за циклом
106

107. 4. Структурное программирование 4.4. Повторение

Как обойтись без break
for (…; Условие_цикла && !Условие_досрочного_выхода ; … )
{
инструкция1;
инструкция2;
true if (!Условие_досрочного_выхода)
{
инструкция3;
инструкция4;
…
}
}
инструкция, следующий за циклом
107

108. 4. Структурное программирование 4.4. Повторение

Как обойтись без break
do
{
инструкция1;
инструкция2;
true if (!Условие_досрочного_выхода)
{
инструкция3;
инструкция4;
…
}
}
while (Условие_цикла && !Условие_досрочного_выхода);
инструкция, следующая за циклом
108