1 Тема 1.7. Алгоритмизация и программирование Информатика

2 Содержание Введение Принципы структурного программирования Принципы структурного программирования Модульная структура Алгоритмические конструкции

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

4 Введение Со временем появилась необходимость разбиения программ на фрагменты. Реализация - процедурная декомпозиция. Процедура реализовывала законченные фрагменты и могла использоваться не один раз. Это привело к развитию структурного программирования.

5 Принципы структурного программирования - основаны на модульной структуре программного продукта и типовых управляющих структурах алгоритмов обработки данных различных программных модулей Модуль – логически взаимосвязанная совокупность функциональных элементов, оформленных в виде отдельных законченных частей.

6 Модульная структура Предполагает модульный состав программы Модуль – подпрограмма, имеющая самостоятельное значение, решающая некоторую подзадачу. При модульном программировании сначала определяются состав и подчиненность функций, а потом – набор программных модулей, реализующих их.

7 Модульная структура Функции верхнего уровня обеспечиваются главным модулем, - он управляет выполнением нижестоящих функций, которым соответствуют подчиненные модули. ГЛАВНЫЙ МОДУЛЬ МОДУЛЬ 1 МОДУЛЬ 2 *** МОДУЛЬ N

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

9 Модуль 1 Ф1 Функционально-модульные структуры Модуль 1 реализует функцию Ф1 функция Ф2 реализуется последовательностью выполнения Модуля 2, модуля 1, модуля d Ф2 Модуль 2 Модуль 1 Модуль d

10 Функционально-модульные структуры Функция Ф7 реализуется с помощью иерархии модулей Ф7 Модуль 3 Модуль k Модуль d Модуль 4 Модуль 3 выполняет выбор на выполнение подчиненных модулей k,d,4

11 При реализации алгоритма учитывать, что: Каждый модуль вызывается на выполнение вышестоящим модулем и, закончив выполнение, возвращает управление вызвавшему его модулю Принятие основных решений в алгоритме выносится на возможно высший уровень Для использования одной и той же функции в разных местах алгоритма создается модуль, который вызывается как только нужно.

12 Принципы модульного программирования 1. Описание данных 2. Нисходящее проектирование 3. Модульное программирование 4. Разработка главной программы 5. Сборка программы Технологические этапы модульного программирования Модули реализуются с помощью управляющих структур алгоритмов

13 Алгоритмические конструкции Алгоритм - точное предписание, задающее правила преобразования исходных данных в искомый результат. Алгоритм – понятное и точное описание последовательности действий, строгое исполнение которых приводит к решению поставленной задачи за конечное число шагов. Алгоритмизация – процесс разработки алгоритма для решения задачи

14 Алгоритмизация предполагает: определенный набор команд и функций для решения задачи; один или несколько методов решения задачи; исходные данные; вид конечного результата; построение последовательности команд и функций из заданного набора в соответствии с выбранным методом решения задачи.

15 Свойства алгоритмов Дискретность Определенность Конечность Результативность Массовость Правильность

16 Для записи алгоритмов используются: Естественный язык (словесная запись) Формулы Псевдокод Синтаксические диаграммы Графический (язык блок-схем) Запись алгоритмов

17 Основные блоки НАЧАЛО КОНЕЦ Действия Условие ДА НЕТ ВВОД ВЫВОД Конструкции

18 Следование Действие 1 Действие 2 *** Действие N все действия выполняются однократно, в строгой последовательности одно за другим, как записаны.

19 Ветвление Действие 2Действие 1 Условие ДА НЕТ Выбор одного или другого набора действий в зависимости от результата сравнения по условию

20 Цикл Повторить? Действия ДА Выход из цикла содержит набор действий, которые повторяются в указанной последовательности несколько раз.

21 Пример Задача. Определить наибольший общий делитель (НОД) двух чисел Исходные данные. А и В – два произвольных целых числа, не равных 0. Словесная запись алгоритма. (Алгоритм Евклида) 1. Сравнить два числа. 2. Если они равны, то это число и есть НОД. Сообщить его и закончить алгоритм. 3. Если не равны, то вычесть из большего меньшее и запомнить результат вместо большего числа. 4. Повторять п.п. 2-4

22 А, В Блок-схема алгоритма Евклида НАЧАЛО В – А В А = В ? А > В ? А – В А НЕТ ДА КОНЕЦ А НЕТ ДА

23 Пример Определить, каковы значения а и b после выполнения алгоритма. 1 шаг: b=8, a=5 2 шаг: Результат сравнения – ДА; b=3; Возврат на условие 3 шаг: Очередное условие. Результат сравнения – НЕТ. Результат: a=6; b=6 ДА НЕТ начало b=: b-a Конец а

24 Основные этапы решения задачи на компьютере Постановка задачи Формализация (математическая постановка) Выбор (или разработка) метода решения Разработка алгоритма Составление программы Отладка программы Вычисление и обработка результатов

25 Программа – алгоритм, записанный на языке, реализуемом на компьютере – языке программирования ЯЗЫКИ ПРОГРАММИРОВАНИЯ ВЫСОКОГО УРОВНЯ НИЗКОГО УРОВНЯ

26 Процесс генерации программного кода НЕТ ДА Ввод исходного текста программы Компиляция Ошибки есть? Редактирование Вывод Exe-файла

27 Система программирования Компилятор Интегрированная среда разработчика Отладчик Средства оптимизации кода программ Набор библиотек (возможно с исходными текстами программ) Редактор связей Сервисные средства Справочная система

28 Отладка программы разработка тестового набора исходных данных; определение тестового набора результирующих данных; проведение тестирования программы; исправление обнаруженных ошибок; верификация программы для получения гарантий правильной работы на любом наборе исходных данных.

29 Выводы Структурное программирование – одна из основных технологий, использующихся в современном программирования В основе структурного программирования лежит модульная декомпозиция программы Модули строятся на основе управляющих структур алгоритмов.