ТОИ-ИМ 1 Лесли Анна Робертсон в своей книге "Программирование – это просто. Пошаговый подход" предлагает выделять 7 основных этапов разработки программ: - презентация

1 ТОИ-ИМ 1 Лесли Анна Робертсон в своей книге "Программирование – это просто. Пошаговый подход" предлагает выделять 7 основных этапов разработки программ: Постановка задачи, План решения задачи, Разработка алгоритма по плану, Проверка правильности алгоритма, Перевод алгоритма на конкретный язык программирования, Запуск, отладка и тестирование программы на компьютере, Создание документации для программы. Последовательность разработки программ

2 ТОИ-ИМ 2 Рассмотрим подробнее эти 7 этапов: Постановка задачи Определение целей решения задачи, функций программы и обобщённой структуры алгоритма решения задачи. Многократное внимательное изучение и анализ текста задачи "до тех пор, пока полностью не будет осмыслено то, что требуется сделать". При анализе задачи необходимо выделить : действия по вводу данных и характеристики входных данных (количество, вид, назначение и др.), действия по выводу данных и характеристики выходных данных (количество, вид, назначение и др.), действия по обработке данных для получения выходных данных их входных. На этом этапе анализа составляется обобщённая функциональная схема алгоритма решения задачи: задача структурируется (разбивается на относительно независимые (слабо зависимые) части и описываются функции всей задачи и каждой обобщённой части задачи, а также действия по реализации каждой функции). В том случае, когда задача не описана в текстовом виде или нечётко сформулирована, надо в режиме диалога-интервью с заказчиком составить чёткое текстуальное (вербальное) описание задачи и согласовать его с заказчиком программы. Последовательность разработки программ

3 ТОИ-ИМ План решения задачи Детализация обобщённой функциональной структуры, определение этапов обработки. Первоначальный план решения задачи представляет собой грубый набросок, который затем детализируется, уточняется, перерабатывается. Обычно план решения включает в себя: Основную логику решения задачи, Основные этапы обработки данных, Основные подзадачи (если требуется разбиение на подзадачи), Пользовательский интерфейс (если есть), Основные переменные и структуры данных. Последовательность разработки программ

4 ТОИ-ИМ Разработка алгоритма по плану План решения развивается в алгоритм: совокупность отдельных действий и операций, которые полностью описывают решаемые задачи и порядок их решения (выполнения). Для того, что бы написать алгоритм и программу для ЭВМ надо: описать решаемую задачу в терминологии деятельности – определить основные действия (группы действий) по решению задачи, разбить задачу и подзадачи на совокупность действий, каждое действие разбить на отдельные операции, определить алгоритмы выполнения каждой операции, детализация действий: описание основных действий в действиях более низкого уровня,– выполняется до тех пор, пока каждый из шагов алгоритма не описывается как детальная операция: способ выполнения действия с учётом внешних условий (ситуации), определить последовательность/параллельность выполнения действий и операций либо механизмы (принципы и протоколы) взаимодействия отдельных подзадач в процессе решения задачи. Последовательность разработки программ

5 ТОИ-ИМ Проверка правильности алгоритма Цель проверки алгоритма "на бумаге" – заблаговременный поиск основных логических ошибок, пока их нетрудно обнаружить и исправить. Проверка правильно ли выполняет алгоритм задуманные действия и операции осуществляется следующим образом: Подготавливаются тестовые входные данные, "Вручную" рассчитываются выходные данные соответствующие тестовым входным данным, Программист на бумаге ("вручную") подставляет входные данные в алгоритм и проверяет изменение всех переменных алгоритма, имитируя работу программы и проверяя логику работы алгоритма, Выходные данные, полученные в результате имитации работ алгоритма, сравниваются с выходными данными рассчитанными вручную. Таким образом, обнаруживаются логические ошибки в работе алгоритма. Для проверки алгоритма "на бумаге" обычно используются проверочные таблицы, отображающие состояние переменных алгоритма (программы) на каждом шаге выполнения Перевод алгоритма на конкретный язык программирования Производится кодирование алгоритма на выбранном языке программирования с учётом особенностей этого языка. Последовательность разработки программ

6 ТОИ-ИМ Запуск, отладка и тестирование программы на компьютере Суть отладки состоит в выполнении программы на компьютере и устранении синтаксических ошибок ЯП и логических ошибок алгоритма. Отладка – это поиск и исправление синтаксических (проявляются во время компиляции) и логических (проявляются во время выполнения) ошибок в программе. Тестирование – это проверка работы программы со специально составленными наборами входных данных (тестов) и сравнение полученных результатов с рассчитанными "вручную" в поисках возможных логических или семантических ошибок. Этот этап выполняется несколько раз пока не останется сомнений в правильности работы программы. Последовательность разработки программ

7 ТОИ-ИМ Создание документации для программы Документация программы должна включать, как минимум: комментарии в текстах всех программных модулей (комментарий- заголовок, комментарии ко всем типам данных, переменным и константам программы, комментарии к ключевым блокам кода программы); инструкцию по установке программы, описание программы для системных администраторов, руководство пользователя. Документирование – завершающий этап создания программы, но разработка документации начинается с началом постановки задачи. В процессе эксплуатации программы документация обычно дополняется описанием и изменений, вносимых в программу после её сдачи заказчику. Последовательность разработки программ

8 Базовые алгоритмические структуры ТОИ-ИМ В соответствии со структурной теоремой, изложенной в классической работе итальянцев Бома и Джакопини (1965 г.), алгоритм любой программы может быть построен на основе трёх базовых управляющих структур (конструкций): последовательность, выбор решения (разветвление по условию) и цикл. Последовательность Последовательная управляющая структура – это непосредственное выполнение одного действия (операции) за другим в порядке их записи сверху вниз. Выбор решения (разветвление по условию) Управляющая структура бинарное ветвление – это проверка условия и выбор одного из двух альтернативных действий; выбор осуществляется в зависимости от истинности (true) или ложности (false) проверяемого условия. Управляющая структура множественное ветвление – это вычисление какого- нибудь константного выражения и, в зависимости от вычисленного значения, выбор одного из множества альтернативных действий. Цикл Управляющая структура цикл – это выполнение повторяющейся последовательности действий (операций), повторение которых осуществляется до тех пор, пока выполняется заданное условие. Существует три разновидности циклов: Цикл с предусловием – условие проверяется в начале цикла, а затем выполняется тело цикла – действия (операции) входящие в цикл. Цикл с постусловием – проверка условия осуществляется в конце цикла, после того как будут выполнены действия (операции) входящие в тело цикла. Цикл с заданным количеством повторений – в заголовке цикла задаётся количество повторений (итераций) цикла: задаётся начальное и конечное значение счётчика итераций цикла и шаг приращения счётчика в каждой итерации. 8

9 Представление алгоритмов ТОИ-ИМ 9 Блок-схемы трёх базовых управляющих алгоритмических структур Последовательность Непосредственное выполнение одного действия за другим

10 Представление алгоритмов ТОИ-ИМ 10 Блок-схемы трёх базовых управляющих алгоритмических структур Выбор решения Проверка выполнения условия и выбор одного из альтернативных действий 1. Бинарный выбор – ветвление 2. Множественный выбор

11 Представление алгоритмов ТОИ-ИМ 11 Блок-схемы трёх базовых управляющих алгоритмических структур Цикл Организация повторяющихся действий в соответствии с заданным условием Цикл с параметром Общая схема цикла Тело цикла выполняется n раз Условие Действие i = 1 (1) n Тело цикла (оператор) Вход Выход нет да

12 Представление алгоритмов ТОИ-ИМ 12 Блок-схемы трёх базовых управляющих алгоритмических структур Цикл Цикл с постусловием Тело цикла обязательно выполниться хотя бы один раз Цикл с предусловием Тело цикла может не выполниться ни разу Условие Тело цикла (оператор) Вход Выход нет да Условие Тело цикла (оператор) Вход Выход

13 Представление алгоритмов ТОИ-ИМ Как раньше было описано, для представления алгоритма могут использоваться различные способы: вербальное описание, графическая схема, таблица решений, описание средствами алгоритмического языка программирования. Для дальнейшего изучения основ программирования будем использовать представление алгоритмов в виде псевдокода (вербального формализованного описания), в виде блок-схемы (графического описания в совмещённом виде: блок-схема (графическое описание), в графических элементах которой записаны действия/операции в псевдокоде (вербальном формализованном описании). А затем будем преобразовывать блок-схемы в программы на ЯП Pascal и С. Графические элементы и составление блок-схем были рассмотрены раньше, сейчас рассмотрим подробнее псевдокод. Псевдокод Формализация словесного описания в псевдокоде – выбор ключевых слов псевдокода, применяемых для описания алгоритмических операций – производится таким образом, чтобы обеспечить согласование этих ключевых слов с основными операциями компьютера и операциями алгоритмических языков высокого уровня. 13

14 Представление алгоритмов ТОИ-ИМ Псевдокод 14 Основные операции ЯП и ключевые слова псевдокода: Получение информации Для описания получения информации компьютером в псевдокоде будут использоваться глаголы: Прочитать – для чтения входных данных из файла или памяти компьютера; Получить – для чтения входных данных из буфера клавиатуры компьютера. Примеры команд (операций) в псевдокоде: Прочитать имя_ученика, number_1, item_2 Получить tax_code В этих примерах используется один глагол: Прочитать или Получить, - за которым следует одно или несколько существительных, указывающих какие именно входные данные должны быть введены в программу. Выдача информации Для того чтобы передать информацию из компьютера на внешнее устройство используются глаголы: Печатать – отправка выходных данных на принтер, Записать – запись выходных данных в файл, Вывести – вывод выходных данных на экран, Запросить – вывод на экран сообщения, требующего ответа пользователя. Примеры: Печатать "Программа завершена" Записать имя_заказчика в выходной файл Вывести total_tax Запросить ввод имени ученика (обычно за запросом следует команда Получить). Например: Запросить имя_ученика Получить имя_ученика Формат псевдокода позволяет добавлять свои собственные ключевые слова, это обязательно глаголы

15 Представление алгоритмов ТОИ-ИМ Псевдокод 15 Основные операции ЯП и ключевые слова псевдокода: Выполнение математических действий / операций Для осуществления математических действий в псевдокоде используются знаки математических операций и глаголы: + + Прибавить – операция сложения, - - Вычесть – операция вычитания, * * Умножить – операция умножения, / / Делить – операция деления, Для выражений используются также: Вычислить – операция вычисления математического или логического выражения, ( ) ( ) Круглые скобки – определение порядка вычисления выражения. Команды псевдокода могут использовать как глаголы, так и знаки операций: Прибавить number к total или total = total + number Примеры: Делить total на count =* Sales_tax = cost_price * 0.01 Вычислить С = (А – 32) * 5 / 9 Математические выражения в программах на компьютере и алгоритмах выполняются согласно стандартному математическому порядку действий: первыми вычисляются выражения заключённые в скобки, затем слева направо выполняются операции умножения и деления, а затем слева направо – операции сложения и вычитания. Результат вычисления математического выражения – число.

16 Представление алгоритмов ТОИ-ИМ Псевдокод 16 Основные операции ЯП и ключевые слова псевдокода: Выполнение логических действий / операций Для осуществления логических действий в псевдокоде используются знаки математических операций и глаголы или местоимения: ?= Сравнить – проверить равенство значений двух переменных, || ИЛИ – логическая операция "или", && И – логическая операция "и", > Больше – логическая операция "больше", >= Больше или равно – логическая операция "больше или равно", < Меньше – логическая операция "меньше", <= Меньше или равно – логическая операция "меньше или равно", <> Не равно – логическая операция "не равно". Примеры: Сравнить total и count total ?= count Вычислить (А >= Б || 32 < C) Результат вычисления логического выражения – Истинно или Ложно. Больше – логическая операция "больше", >= Больше или равно – логическая операция "больше или равно", < Меньше – логическая операция "меньше", <= Меньше или равно – логическая операция "меньше или равно", <> Не равно – логическая операция "не равно". Примеры: Сравнить total и count total ?= count Вычислить (А >= Б || 32 < C) Результат вычисления логического выражения – Истинно или Ложно.">

17 Представление алгоритмов ТОИ-ИМ Псевдокод 17 Основные операции ЯП и ключевые слова псевдокода: Присваивание значений переменным или ячейкам памяти Псевдокод для присваивания значений употребляется, когда необходимо: I. Установить исходное значение данных (переменных), используются глаголы Инициализировать – определить начальное значение переменной при её объявлении в алгоритме или программе, Установить – изменить текущее значение переменной. II. Присвоить переменной значение результата обработки данных, используются знак операции или глагол = Равно – операция присваивания переменной, расположенной слева от знака "равно", результата вычисления выражения, расположенного справа от знака "равно". III. Сохранить значения, которые предполагается использовать позже Сохранить – записать текущее значение изменяющейся переменной в другую переменную. Хранить – записать текущее значение переменной в другую переменную. Примеры: Инициализировать max в ноль Установить count в ноль total_price = cost_price + sales_tax Хранить CustNum в last_CustNum

18 18 ТОИ-ИМ Представление алгоритмов Выбор решения – вычисление условия (логического выражения) и выбор из одного из альтернативных действий Для описания этого действия в псевдокоде используется конструкция с ключевыми словами: ЕСЛИ, ТО, ИНАЧЕ, ЕСЛИ ВСЁ. Синтаксическая конструкция бинарного ветвления/выбора в псевдокоде: ЕСЛИ условие Р истинно УСЛОВИЕ – логическое выражение ТО Выполнение блока действий в случае истинности условия ИНАЧЕ Выполнение блока действий в случае ложности условия ЕСЛИ ВСЁ Пример: ЕСЛИ student_status равно part_time ТО Прибавить 1 к part_time_count ИНАЧЕ Прибавить 1 к full_time_count ЕСЛИ ВСЁ Псевдокод Основные операции ЯП и ключевые слова псевдокода:

19 Графическая схема алгоритма Старый пример Даны три разные числа A, B, C. Вывести их на печать в порядке убывания. ввести три числа A, B, C проверить A¬=B, A¬=C, C¬=B если: A>B то: max1=A, max2=B иначе: max1=B, max2=A если: max1>C то: если: max2>C то: max3=C иначе: max3=max2 max2=C иначе: max3=max2 max2=max1 max1=C вывести на печать max1, max2, max3 ДА НЕТ A>B Ввод A, B, C НЕТ max1=A max2=B max1=B max2=A max1>C max3=max2 max2=max1 max1=C НЕТ max2>C ДА max3=С Вывод max1, max2, max3 A=B, A=C, B=C НЕТ ДА введите разные числа max3=max2 max2=C ТОИ-ИМ 19

B, A<>C, C<>B ЕСЛИ A>B ТО max1=A, max2=B ИНАЧЕ max1=B, max2=A ЕСЛИ ВСЁ ЕСЛИ max1>C ТО ЕСЛИ max2>C ТО max3=C ИНАЧ" title="Представление алгоритмов ТОИ-ИМ 20 Блок-схема с псевдокодом Запросить " Введите три разные числа " Получить три числа A, B, C Сравнить A<>B, A<>C, C<>B ЕСЛИ A>B ТО max1=A, max2=B ИНАЧЕ max1=B, max2=A ЕСЛИ ВСЁ ЕСЛИ max1>C ТО ЕСЛИ max2>C ТО max3=C ИНАЧ" class="link_thumb"> 20 Представление алгоритмов ТОИ-ИМ 20 Блок-схема с псевдокодом Запросить " Введите три разные числа " Получить три числа A, B, C Сравнить A<>B, A<>C, C<>B ЕСЛИ A>B ТО max1=A, max2=B ИНАЧЕ max1=B, max2=A ЕСЛИ ВСЁ ЕСЛИ max1>C ТО ЕСЛИ max2>C ТО max3=C ИНАЧЕ max3=max2 max2=C ЕСЛИ ВСЁ ИНАЧЕ max3=max2 max2=max1 max1=C ЕСЛИ ВСЁ Вывести max1, max2, max3 Даны три разные числа A, B, C. Вывести их на печать в порядке убывания. ЕСЛИ A>B ИНАЧЕ max1=B max2=A max1=A max2=B ТО ЕСЛИ ВСЁ ТО ЕСЛИ max1>C max3=max2 max2=max1 max1=C ТО max3=C max3=max2 max2=C ИНАЧЕ ЕСЛИ max2>C ИНАЧЕ ЕСЛИ ВСЁ Вывести max1, max2, max3 Конец Получить A, B, C Начало Вывести "Введите три разные числа" Сравнить A=B, B=C, А=C Ввод трёх разных чисел и вывод их на печать в порядке убывания ДА НЕТ Вывести "Числа одинаковые!" Нарисовать блок-схему с псевдокодом B, A<>C, C<>B ЕСЛИ A>B ТО max1=A, max2=B ИНАЧЕ max1=B, max2=A ЕСЛИ ВСЁ ЕСЛИ max1>C ТО ЕСЛИ max2>C ТО max3=C ИНАЧ"> B, A<>C, C<>B ЕСЛИ A>B ТО max1=A, max2=B ИНАЧЕ max1=B, max2=A ЕСЛИ ВСЁ ЕСЛИ max1>C ТО ЕСЛИ max2>C ТО max3=C ИНАЧЕ max3=max2 max2=C ЕСЛИ ВСЁ ИНАЧЕ max3=max2 max2=max1 max1=C ЕСЛИ ВСЁ Вывести max1, max2, max3 Даны три разные числа A, B, C. Вывести их на печать в порядке убывания. ЕСЛИ A>B ИНАЧЕ max1=B max2=A max1=A max2=B ТО ЕСЛИ ВСЁ ТО ЕСЛИ max1>C max3=max2 max2=max1 max1=C ТО max3=C max3=max2 max2=C ИНАЧЕ ЕСЛИ max2>C ИНАЧЕ ЕСЛИ ВСЁ Вывести max1, max2, max3 Конец Получить A, B, C Начало Вывести "Введите три разные числа" Сравнить A=B, B=C, А=C Ввод трёх разных чисел и вывод их на печать в порядке убывания ДА НЕТ Вывести "Числа одинаковые!" Нарисовать блок-схему с псевдокодом"> B, A<>C, C<>B ЕСЛИ A>B ТО max1=A, max2=B ИНАЧЕ max1=B, max2=A ЕСЛИ ВСЁ ЕСЛИ max1>C ТО ЕСЛИ max2>C ТО max3=C ИНАЧ" title="Представление алгоритмов ТОИ-ИМ 20 Блок-схема с псевдокодом Запросить " Введите три разные числа " Получить три числа A, B, C Сравнить A<>B, A<>C, C<>B ЕСЛИ A>B ТО max1=A, max2=B ИНАЧЕ max1=B, max2=A ЕСЛИ ВСЁ ЕСЛИ max1>C ТО ЕСЛИ max2>C ТО max3=C ИНАЧ">