1 Глава 3 Структурное программирование

2 3.1 Введение 3.2 Алгоритмы 3.3 Псевдокод 3.4 Управляющие структуры 3.5 Структура выбора If 3.6 Структура выбора If/Else 3.7 Цикл While 3.8 Составление алгоритма: Пример 1 (Цикл со счетчиком) 3.9 Составление алгоритма (разработка сверху вниз): Пример 2 (Sentinel-Controlled Repetition) 3.10 Составление алгоритма (разработка сверху вниз) : Пример 3 (Nested Control Structures) 3.11 Оператор присваивания 3.12 Операторы инкремента и декремента

3 3.1Введение Перед тем как писать программу: Перед тем как писать программу: Необходимо глубоко изучить проблему (задачу) Необходимо глубоко изучить проблему (задачу) Аккуратно спланировать подход к решению Аккуратно спланировать подход к решению Во время написания: Во время написания: Пользуйтесь доступными кирпичами для сборки Пользуйтесь доступными кирпичами для сборки Пользуйтесь «хорошими» правилами и принципами Пользуйтесь «хорошими» правилами и принципами

4 3.2Алгоритмы Проблемы вычислений Проблемы вычислений Все решается выполнением серии действий в определенном порядке Все решается выполнением серии действий в определенном порядке Алгоритм: процедура определяющая Алгоритм: процедура определяющая Какие действия выполняются Какие действия выполняются Порядок в котором их надо исполнять Порядок в котором их надо исполнять Управление выполнением Управление выполнением Указывает порядок в котором операторы будут выполнены Указывает порядок в котором операторы будут выполнены

5 3.3Псевдокод Псевдокод Псевдокод Искусственный, неформальный язык, который помогает разрабатывать алгоритмы Искусственный, неформальный язык, который помогает разрабатывать алгоритмы Похож на обычный English Похож на обычный English Не обязательно исполняется на компьютере Не обязательно исполняется на компьютере Помогает продумать в деталях программу перед тем как написать Помогает продумать в деталях программу перед тем как написать Легко преобразовать в программу на C++ Легко преобразовать в программу на C++ Состоит только из исполняемых операторов Состоит только из исполняемых операторов

6 3.4Управляющие структуры Последовательное исполнение Последовательное исполнение Операторы выполняются в порядке записи Операторы выполняются в порядке записи Передача управления Передача управления Следующий исполняемый оператор не является следующим по порядку Следующий исполняемый оператор не является следующим по порядку Использование goto приводит к проблемам Использование goto приводит к проблемам

7 3.4Управляющие структуры Bohm и Jacopini Bohm и Jacopini Все программы можно написать в терминах 3 х управляющих структур Все программы можно написать в терминах 3 х управляющих структур Последовательные структуры: Встроено в C. Программы выполняются последовательно по умолчанию Последовательные структуры: Встроено в C. Программы выполняются последовательно по умолчанию Структуры выбора: C имеет три: if, if / else, и switch Структуры выбора: C имеет три: if, if / else, и switch Структуры повторения: C имеет три: while, do / while и for Структуры повторения: C имеет три: while, do / while и for

8 3.4Управляющие структуры Граф-схема Граф-схема Графическое представление алгоритма Графическое представление алгоритма Рисуется с помощью определенных объектов, соединенных стрелками (линии исполнения) Рисуется с помощью определенных объектов, соединенных стрелками (линии исполнения) Прямоугольник (Действие): Прямоугольник (Действие): Указывает на тип действие Указывает на тип действие Овал: Овал: Указывает на начало или конец программы или секции кода Указывает на начало или конец программы или секции кода

9 3.4Управляющие структуры Один-вход/один-выход Один-вход/один-выход Соединяет исходящую точку одной структуры с входящей точкой следующей (Стекирование) Соединяет исходящую точку одной структуры с входящей точкой следующей (Стекирование) Делает написание программы проще Делает написание программы проще

10 3.5Структура выбора if Структура выбора: Структура выбора: Используется для выбора альтернативных направлений действия Используется для выбора альтернативных направлений действия Псевдокод: Псевдокод: Если оценка студента больше или равна 3 Напечатать Прошел Если оценка студента больше или равна 3 Напечатать Прошел Если условие true, выполнить блок и перейти к оператору после структуры Если условие true, выполнить блок и перейти к оператору после структуры Если false, перейти к оператору после структуры Если false, перейти к оператору после структуры Корректная запись – проще читать Корректная запись – проще читать C игнорирует пробелы C игнорирует пробелы

11 3.5Структура выбора if Псевдокод данной структуры в C: Псевдокод данной структуры в C: if ( grade >= 3 ) printf( "Passed\n" ); Код на C очень похож на псевдокод Код на C очень похож на псевдокод Ромб (решение) Ромб (решение) Указывает на принятие решения Указывает на принятие решения Содержит выражение которое может быть true или false Содержит выражение которое может быть true или false Тестирует условие и выбирает нужный путь Тестирует условие и выбирает нужный путь

12 3.5Структура выбора if Структура if – с одной точкой входа Структура if – с одной точкой входа true false grade >= 3 print Passed Решение может быть по любому выражению. ноль - false Не ноль - true Пример: дает true

13 3.6Структура выбора if / else if if Блок работает только если условие true Блок работает только если условие true if / else if / else Указывает действие, выполняемое и для true и даже для false Указывает действие, выполняемое и для true и даже для false Псевдокод: Псевдокод: If student s grade is greater than or equal to 3 Print Passed If student s grade is greater than or equal to 3 Print Passed else Print Failed else Print Failed Обратите внимание на пробелы и отступы Обратите внимание на пробелы и отступы

14 3.6Структура выбора if / else Код на C : Код на C : if ( grade >= 3 ) printf( "Passed\n"); printf( "Passed\n");else printf( "Failed\n"); printf( "Failed\n"); Тернарный оператор условия ( ?: ) Тернарный оператор условия ( ?: ) Принимает три аргумента (условие, значение если true, значение если false ) Принимает три аргумента (условие, значение если true, значение если false )

15 3.6Структура выбора if / else Тернарный оператор условия ( ?: ) Тернарный оператор условия ( ?: ) Принимает три аргумента (условие, значение если true, значение если false ) Принимает три аргумента (условие, значение если true, значение если false ) Наш псевдокод будет таким: Наш псевдокод будет таким: printf( "%s\n", grade >= 3 ? "Passed" : "Failed" ); Или его можно записать так: Или его можно записать так: grade >= 3 ? printf( Passed\n ) : printf( Failed\n );

16 3.6Структура выбора if / else Граф структуры if / else Граф структуры if / else truefalse print Failedprint Passed grade >= 3

17 3.6Структура выбора if / else Вложенные структуры if / else Вложенные структуры if / else Тест множества условий if / else внутри структур if / else Тест множества условий if / else внутри структур if / else Если одно из условий встретилось, остальные пропускаются Если одно из условий встретилось, остальные пропускаются Глубокие вложения не используются на практике Глубокие вложения не используются на практике

18 3.6Структура выбора if / else Псевдокод для структуры if / else Псевдокод для структуры if / else If student s grade is greater than or equal to 5 Print A else If student s grade is greater than or equal to 4 Print B else If student s grade is greater than or equal to 3 Print C else If student s grade is greater than or equal to 2 Print D else Print F If student s grade is greater than or equal to 5 Print A else If student s grade is greater than or equal to 4 Print B else If student s grade is greater than or equal to 3 Print C else If student s grade is greater than or equal to 2 Print D else Print F

19 3.6Структура выбора if / else Составной оператор: Составной оператор: Набор операторов внутри пары скобок Набор операторов внутри пары скобок Пример: Пример: if ( grade >= 3 ) printf( "Passed.\n" ); printf( "Passed.\n" ); else { printf( "Failed.\n" ); printf( "Failed.\n" ); printf( "You must take this course again.\n" ); } printf( "You must take this course again.\n" ); } Без скобок оператор Без скобок оператор printf( "You must take this course again.\n" ); Будет выполнен автоматически

20 3.6Структура выбора if / else Блок: Блок: Составной оператор с определением Составной оператор с определением Синтаксическая ошибка Синтаксическая ошибка Ловится компилятором Ловится компилятором Логические ошибки: Логические ошибки: Оказывают влияние в процессе исполнения Оказывают влияние в процессе исполнения Не фатальные: программа работает, но некорректный вывод Не фатальные: программа работает, но некорректный вывод Фатальные: программа неожиданно останавливается Фатальные: программа неожиданно останавливается

21 3.7Структура повторения while Структура повторения Структура повторения Программист указывает действие, которое надо повторять, пока условие остается true Программист указывает действие, которое надо повторять, пока условие остается true Псевдокод: Псевдокод: While there are more items on my shopping list Purchase next item and cross it off my list Цикл while повторяется до тех пор пока условие не станет false Цикл while повторяется до тех пор пока условие не станет false

22 3.7Структура повторения while Пример: Пример: int product = 2; while ( product <= 1000 ) product = 2 * product; product <= 1000 product = 2 * product true false

23 3.8Разработка алгоритмов (Цикл со счетчиком) Цикл со счетчиком Цикл со счетчиком Цикл работает до те пор пока счетчик достигнет определенного значения Цикл работает до те пор пока счетчик достигнет определенного значения Известно количество повторов Известно количество повторов Пример: Класс студентов приняла викторину. Оценки за викторину (integers в диапазоне от 0 до 100). Пример: Класс студентов приняла викторину. Оценки за викторину (integers в диапазоне от 0 до 100). Необходимо определить средний результат Необходимо определить средний результат Псевдокод: Псевдокод: Set total to zero Set grade counter to one While grade counter is less than or equal to ten Input the next grade Add the grade into the total Add one to the grade counter Set the class average to the total divided by ten Print the class average

24 1. Инициализ ация переменны х 2. Цикл обработки 3. Печать результато в 1/* Fig. 3.6: fig03_06. c 2 Class average program with 3 counter-controlled repetition */ 4#include 5 6int main() 7{7{ 8 int counter, grade, total, average; 9 10 /* initialization phase */ 11 total = 0; 12 counter = 1; /* processing phase */ 15 while ( counter <= 10 ) { 16 printf( "Enter grade: " ); 17 scanf( "%d", &grade ); 18 total = total + grade; 19 counter = counter + 1; 20 } /* termination phase */ 23 average = total / 10; 24 printf( "Class average is %d\n", average ); return 0; /* indicate program ended successfully */ 27}

25 Результат Enter grade: 98 Enter grade: 76 Enter grade: 71 Enter grade: 87 Enter grade: 83 Enter grade: 90 Enter grade: 57 Enter grade: 79 Enter grade: 82 Enter grade: 94 Class average is 81

26 3.9Разработка алгоритмов сверху вниз, декомпозиция Появились проблемы: Появились проблемы: Разработать программу усреднения результата сдачи, при условии что количество вводимых данных каждый раз разное. Неизвестное число студентов Неизвестное число студентов Как узнать что программа закончилась? Как узнать что программа закончилась?

27 3.9Разработка алгоритмов сверху вниз, декомпозиция Используется ключевое значение Используется ключевое значение Также называется сигналом, пустышкой, или флагом Также называется сигналом, пустышкой, или флагом Указывает на конец ввода данных Указывает на конец ввода данных Цикл заканчивается когда пользователь ввел пустышку Цикл заканчивается когда пользователь ввел пустышку Пустышка не может быть обычным вводом (как например -1 в данном случае) Пустышка не может быть обычным вводом (как например -1 в данном случае)

28 3.9Разработка алгоритмов сверху вниз, декомпозиция Top-down, stepwise refinement Top-down, stepwise refinement Начинаем отображение на псевдокоде сверху: Начинаем отображение на псевдокоде сверху: Determine the class average for the quiz Делим на маленькие задачи и перечисляем их: Делим на маленькие задачи и перечисляем их: Initialize variables Input, sum and count the quiz grades Calculate and print the class average

29 3.9Разработка алгоритмов сверху вниз, декомпозиция Большинство программ имеет три фазы: Большинство программ имеет три фазы: Инициализация: инициализация переменных программы Инициализация: инициализация переменных программы Обработка: ввод данных и настройка переменных Обработка: ввод данных и настройка переменных Завершение: расчет и печать конечных результатов Завершение: расчет и печать конечных результатов

30 3.9Разработка алгоритмов сверху вниз, декомпозиция Разделяем фазу инициализации Initialize variables на: Разделяем фазу инициализации Initialize variables на: Initialize total to zero Initialize counter to zero Разделяем Input, sum and count the quiz grades на Разделяем Input, sum and count the quiz grades на Input the first grade (possibly the sentinel) While the user has not as yet entered the sentinel Add this grade into the running total Add one to the grade counter Input the next grade (possibly the sentinel)

31 3.9Разработка алгоритмов сверху вниз, декомпозиция Разделяем Calculate and print the class average на Разделяем Calculate and print the class average на If the counter is not equal to zero Set the average to the total divided by the counter Print the average else Print No grades were entered If the counter is not equal to zero Set the average to the total divided by the counter Print the average else Print No grades were entered

32 1. Инициализ ации переменны х 2. Ввод данных 2.1 Выполнить цикл 1/* Fig. 3.8: fig03_08. c 2 Class average program with 3 sentinel-controlled repetition */ 4#include 5 6int main() 7{7{ 8 float average; /* new data type */ 9 int counter, grade, total; /* initialization phase */ 12 total = 0; 13 counter = 0; /* processing phase */ 16 printf( "Enter grade, -1 to end: " ); 17 scanf( "%d", &grade ); while ( grade != -1 ) { 20 total = total + grade; 21 counter = counter + 1; 22 printf( "Enter grade, -1 to end: " ); 23 scanf( "%d", &grade ); 24 }

33 3. Расчет среднего 3.1 Печать результато в Результат /* termination phase */ 27 if ( counter != 0 ) { 28 average = ( float ) total / counter; 29 printf( "Class average is %.2f", average ); 30 } 31 else 32 printf( "No grades were entered\n" ); return 0; /* indicate program ended successfully */ 35} Enter grade, -1 to end: 75 Enter grade, -1 to end: 94 Enter grade, -1 to end: 97 Enter grade, -1 to end: 88 Enter grade, -1 to end: 70 Enter grade, -1 to end: 64 Enter grade, -1 to end: 83 Enter grade, -1 to end: 89 Enter grade, -1 to end: -1 Class average is 82.50

Вложенные управляемые структуры Проблема Проблема Институт составляет лист результатов теста ( 1 = pass, 2 = fail) для 10 студентов Институт составляет лист результатов теста ( 1 = pass, 2 = fail) для 10 студентов Пишем программу, анализирующую результат Пишем программу, анализирующую результат Если больше 8 студентов сдало, напечатать « Перевести курс" Если больше 8 студентов сдало, напечатать « Перевести курс"

Вложенные управляемые структуры Важно Важно Программа должна обработать 10 результатов теста Программа должна обработать 10 результатов теста Будем использовать цикл со счетчиком Будем использовать цикл со счетчиком Два счетчика Два счетчика Один для количества сдавших, другой для количества не сдавших Один для количества сдавших, другой для количества не сдавших Каждый результат теста это число 1 или 2 Каждый результат теста это число 1 или 2 Если число не 1, полагаем что это 2 Если число не 1, полагаем что это 2

Вложенные управляемые структуры Верхний уровень структуры Верхний уровень структуры Analyze exam results and decide if tuition should be raised Первое уточнение Первое уточнение Initialize variables Input the ten quiz grades and count passes and failures Print a summary of the exam results and decide if tuition should be raised Расширим Initialize variables до Расширим Initialize variables до Initialize passes to zero Initialize failures to zero Initialize student counter to one

Вложенные управляемые структуры Заменяем Input the ten quiz grades and count passes and failures на Заменяем Input the ten quiz grades and count passes and failures на While student counter is less than or equal to ten Input the next exam result If the student passed Add one to passes else Add one to failures Add one to passes else Add one to failures Add one to student counter Заменяем Print a summary of the exam results and decide if tuition should be raised на Заменяем Print a summary of the exam results and decide if tuition should be raised на Print the number of passes Print the number of failures If more than eight students passed Print Raise tuition If more than eight students passed Print Raise tuition

38 1. Инициализ ация переменны х 2. Ввод данных и расчет успехов/не удач 3. Печать результато в 1/* Fig. 3.10: fig03_10. c 2 Analysis of examination results */ 3#include 4 5int main() 6{6{ 7 /* initializing variables in declarations */ 8 int passes = 0, failures = 0, student = 1, result; 9 10 /* process 10 students; counter-controlled loop */ 11 while ( student <= 10 ) { 12 printf( "Enter result ( 1=pass,2=fail ): " ); 13 scanf( "%d", &result ); if ( result == 1 ) /* if/else nested in while */ 16 passes = passes + 1; 17 else 18 failures = failures + 1; student = student + 1; 21 } printf( "Passed %d\n", passes ); 24 printf( "Failed %d\n", failures ); if ( passes > 8 ) 27 printf( "Raise tuition\n" ); return 0; /* successful termination */ 30}

39 Результат Enter Result (1=pass,2=fail): 1 Enter Result (1=pass,2=fail): 2 Enter Result (1=pass,2=fail): 1 Enter Result (1=pass,2=fail): 2 Enter Result (1=pass,2=fail): 1 Enter Result (1=pass,2=fail): 2 Passed 6 Failed 4

Оператор присваивания Оператор присваивания присваивает переменной значение выражения Оператор присваивания присваивает переменной значение выражения c = c + 3; Может быть записана как c += 3; Форма оператора Форма оператора variable = variable operator expression; variable = variable operator expression; Может быть записан Может быть записан variable operator= expression; variable operator= expression; Примеры: Примеры: d -= 4 (d = d - 4) d -= 4 (d = d - 4) e *= 5 (e = e * 5) e *= 5 (e = e * 5) f /= 3 (f = f / 3) f /= 3 (f = f / 3) g %= 9 (g = g % 9) g %= 9 (g = g % 9)

Операторы инкремента и декремента Оператор инкремента ( ++ ) Оператор инкремента ( ++ ) Может использоваться вместо c+=1 Может использоваться вместо c+=1 Оператор декремента ( -- ) Оператор декремента ( -- ) Может использоваться вместо c-=1 Может использоваться вместо c-=1

Операторы инкремента и декремента Пред инкремент Пред инкремент Оператор до переменной ( ++c или --c ) Оператор до переменной ( ++c или --c ) Переменная меняется до того как выражение будет рассчитано Переменная меняется до того как выражение будет рассчитано Пост инкремент Пост инкремент Оператор после переменной( c++ или c-- ) Оператор после переменной( c++ или c-- ) Выражение будет рассчитано до изменения переменной Выражение будет рассчитано до изменения переменной

Операторы инкремента и декремента Если c равен 5, тогда Если c равен 5, тогда printf( "%d", ++c ); Напечатает 6 Напечатает 6 printf( "%d", c++ ); Напечатает 5 Напечатает 5 В любом случае, c теперь равно 6 В любом случае, c теперь равно 6

Операторы инкремента и декремента Когда переменная не является выражение Когда переменная не является выражение Пред и пост инкрементирование дает тот же эффект Пред и пост инкрементирование дает тот же эффект++c; printf( %d, c ); Тоже самое что и Тоже самое что иc++; printf( %d, c );