, старший преподаватель кафедры математики и информационных технологий Педагогического института ТОГУ
Технологии программирования. Графическая модель алгоритма для демонстрации идей структурного программирования
Технологии программирования
Переход от машинно-зависимых языков и псевдокодов к языкам высокого уровня в 60-70-х г. г. ХХ века привел к развитию технологии структурного программирования. Наибольший вклад в теорию и практику структурного программирования внесли такие классики программирования, как Эдсгер Вибе Дейкстра, Никлаус Вирт, Дональд Эрвин Кнут, Андрей Петрович Ершов, Михаил Романович Шура-Бура.
Итальянские математики Коррадо Бом (англ. Corrado Bцhm) и Джузеппе Якопини (Giuseppe Jacopini, Джакопини – один из вариантов прочтения итальянской фамилии) в 1966 году [1] сформулировали Теорему структурного программирования, которая содержит следующее положение.
Теорема Бома-Якопини. Любой исполняемый алгоритм может быть преобразован к структурированному виду, то есть может быть представлен в виде композиции трех управляющих структур:
- последовательное выполнение, ветвление, цикл.
В дальнейшем Эдсгер Дейкстра в своей статье 1968 года [2, 4] продолжил продвижение идеи структурирования и жестко критиковал использование оператора передачи управления GOTO.
Перечислим основные принципы структурного программирования [6].
Принцип абстракции: позволяет разработчику рассматривать программу в нужный момент без лишней детализации. Детализация увеличивается при переходе от верхнего уровня абстракции к нижнему.
Принцип формальности: предполагает строгий методический подход к программированию, придает творческому процессу определенную строгость и дисциплину.
Принцип модульности. В соответствии с этим принципом программа разделяется на отдельные законченные фрагменты, модули, которые просты по управлению и допускают независимую отладку и тестирование. В результате отдельные ветви программы могут создаваться разными группами программистов.
Принцип иерархического упорядочения: взаимосвязь между частями программы должна носить иерархический, подчиненный характер. Это, кстати, следует и из принципа нисходящего проектирования.
Нисходящее проектирование строится на вышеперечисленных принципах. При нисходящем проектировании происходит анализ задачи с целью определения возможности разбиения ее на ряд подзадач. Затем каждая из полученных подзадач также анализируется для возможного разбиения на подзадачи. Процесс для очередной подзадачи заканчивается, когда подзадачу невозможно или нецелесообразно разбивать на подзадачи далее. Результат этого процесса, зафиксированный в графической форме, является основой для построения структурной схемы программы, которая показывает, во-первых, что делает вся программа в целом и ее отдельные части, а, во-вторых, отображает взаимосвязь подзадач друг с другом.
Таким образом, технологию структурного программирования можно определить как методологию разработки программного продукта, в основе которой лежит представление программы в виде иерархической структуры блоков. Методология структурной разработки программного обеспечения была признана «самой сильной формализацией 70-х годов».
Графическая модель алгоритма
Одной из наиболее крупных содержательных линий в школьном курсе информатики является фундаментальный раздел алгоритмизации. Традиционно при введении понятия алгоритма используется и графический способ описания алгоритма – блок-схемы. Язык блок-схем позволяет, в том числе, продемонстрировать учащимся основные идеи структурного программирования.
Блок-схема – это способ описания алгоритма, в котором отдельные шаги изображаются в виде графических блоков (геометрических фигур), соединенных направленными линиями, задающими последовательность выполнения шагов.
Значения графических блоков и правила построения схем регламентируются стандартом ГОСТ 19.701-90 «Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения» [3].
Рассмотрим основные графические блоки-символы:
Символ ПАРАЛЛЕЛОГРАММ отображает данные, позволяет изображать действие ввода/вывода значения переменной:
Символ ПРЯМОУГОЛЬНИК позволяет отобразить выполнение определенной операции или группы операций, приводящее к изменению значения:
Символ РОМБ отображает решение или функцию переключательного типа, имеющую один вход и ряд альтернативных выходов, один и только один из которых может быть активизирован после вычисления условий, определенных внутри этого символа. Соответствующие результаты вычисления могут быть записаны по соседству с линиями, отображающими эти пути:
Символ ПРЯМОУГОЛЬНИК С ПОЛЯМИ позволяет включить в схему алгоритма вызов подпрограммы (функции):
Символ ОВАЛ отображает на схеме выход во внешнюю среду (завершение алгоритма) и вход из внешней среды (начало алгоритма):
Двойной символ цикла:
Обе части символа имеют один и тот же идентификатор. Условия для инициализации, приращения, завершения и т. д. помещаются внутри символа в начале или в конце в зависимости от расположения операции, проверяющей условие.
Символ СОЕДИНИТЕЛЬ используется для обрыва линии и продолжения ее в другом месте. Соответствующие символы-соединители должны содержать одно и то же уникальное обозначение. Пример использования соединителя:
ЦОР «Конструктор алгоритмов»
Построение графической модели алгоритма может быть выполнено «от руки». Однако, предлагаем школьникам при выполнении заданий к предмету «Информатика» ХКЗФМШ использовать специальную программу «Конструктор алгоритмов».
Рассмотрим ЦОР [5] (цифровой образовательный ресурс) к учебнику «Информатика и ИКТ» для 9 класса авторского коллектива ( ), содержащий данную программу – «Конструктор алгоритмов».
Окно программы включает основное меню, рабочую область и панель инструментов, на которой можно выбирать символы-блоки для построения блок-схем алгоритмов.
Назначение программы определяется ее режимами работы:
- конструирование блок-схемы алгоритма, выполнение алгоритма по заданной блок-схеме, трассировка (пошаговое выполнение алгоритма) с отслеживанием значений данных, хранящихся в памяти.
Для знакомства с интерфейсом программы необходимо на странице Единой коллекции цифровых образовательных ресурсов (http://school-collection. edu. ru/) запустить презентации:
- «Методическое сопровождение к учебной программе "Конструктор алгоритмов". Демонстрация к теме: интерфейс программы» ресурс № 000, «Методическое сопровождение к учебной программе "Конструктор алгоритмов". Демонстрация к теме: режимы работы программы» ресурс № 000, «Методическое сопровождение к учебной программе "Конструктор алгоритмов". Демонстрация к теме: ввод и редактирование алгоритма» ресурс № 000.
Программа «Конструктор алгоритмов» представлена в виде исполняемого файла – ресурс № 000.
Примечание: в случае, если ЦОР не найден на сайте Единой коллекции цифровых образовательных ресурсов, запросите ссылку для скачивания данного ЦОР с Google. Диск по адресу электронной почты redko. *****@***com
Самостоятельная работа
Предлагаемые здесь задачи являются контрольной работой №1 2017-2018 учебного года для учащихся 7-9 классов. Решите эти задачи, запишите решения в отдельную (от физики и математики) тетрадь, либо сохраните все файлы в одном архиве, добавив в него также текстовый файл с информацией о вас:
- Фамилия, имя, класс, профиль класса (например: Голиков Василий, 9 кл., математический) Индекс, адрес места жительства, электронная почта (если есть), телефон (домашний или мобильный) Данные о школе (например: МБОУ №1 п. Бикин) Фамилия, И. О. учителя математики (например: учитель математики )
Рекомендуется решить не менее двух примеров из каждого блока и ответить на первый вопрос (теоретический).
Электронную версию решения можно отправить на адрес электронной почты
Задания:
Перечислите другие технологии программирования, отличные от структурного. Приведите примеры языков программирования, реализующих эти технологии (парадигмы). В программе «Конструктор алгоритмов» выполните построение алгоритмов для решения задач, представленных ниже. Проведите трассировку алгоритмов. Зафиксируйте в виде скриншота выполнение алгоритма для каждого набора входных данных, предложенных в задаче.Блок 1. Задачи линейной структуры
Заданы величины X, Y действительного типа. Написать программу для обмена значений величин. Использовать вспомогательные величины нельзя. Протестировать алгоритм для X=-3 и Y=8. Дано натуральное число Х. Вычислить Y = X5. Разрешается использовать только три операции умножения. Разработать схему алгоритма для решения этой задачи. Протестировать алгоритм для X=-2 и X=3. Дано натуральное число Х. Вычислить Y = 1 - 2X + 3X2 - 4X3. Разрешается использовать не более 8 арифметических операций. Допустимы: операции сложение, вычитание, умножение. Разработать схему алгоритма для решения этой задачи. Протестировать алгоритм для X=0, X=1, X=-2. Разработать схему алгоритма для вычисления расстояния между двумя точками с координатами (X1,Y1) и (X2,Y2). Доказать правильность работы алгоритма на трёх различных тестах. Треугольник задан длинами сторон А, В, С. Разработать схему алгоритма, определяющую, существует ли данный треугольник. Если треугольник существует, то установить значение флага F=1, иначе F=0. Для решения этой задачи использовать сложные логические условия. Протестировать алгоритм для следующих исходных данных:а) A=3, B=4, C=5
б) A=1, B=1, C=1
в) A=0, B=4, C=5
г) A=-3, B=6, C=5
д) A=2, B=1, C=8
Блок 2. Задачи на ветвление
Разработать схему алгоритма для отыскания max(min(a, b), min(c, d)), не используя сложные логические условия и вложенные ветвления. Числа a, b,c, d - целые. Протестировать алгоритм для следующих исходных данных:а) a=4 b=5 c=6 d=9
б) a=2 b=1 c=6 d=9
в) a=2 b=1 c=8 d=4
г) a=12 b=1 c=6 d=9
Точка А задана координатами X, Y. Разработать схему алгоритма, который устанавливает значение флага F=1, если точка принадлежит заштрихованной области (см. рисунок 1) и значение флага F=0 в противном случае. Вывести значение F. Протестировать алгоритм для точек (0,0), (1,0), (1.5,1), (-1,1.5), (-2,-1), (2,-1), (1,-1), (-1,1).
Рис. 1
Точка А задана координатами X, Y. Разработать схему алгоритма, который устанавливает значение флага F=1, если точка принадлежит заштрихованной области (см. рисунок 2) и значение флага F=0 в противном случае. Вывести значение F. Протестировать алгоритм для точек (0,0), (1.5,1), (2,1), (1,-1), (-0.5,-0.2), (-2,-1), (-1,-2), (-1,1), (-3, 1).
Рис.2
Точка А задана координатами X, Y. Разработать схему алгоритма, который устанавливает значение флага F=1, если точка принадлежит заштрихованной области (см. рисунок 3) и значение флага F=0 в противном случае. Вывести значение F. Протестировать алгоритм для точек (0,0), (2,2), (0.5,0.5), (0.5,-1.5), (-0.5,0.5), (-2,-1),(-1,-2), (-1,1), (2, 0).
Рис.3
Блок 3. Задачи циклической структуры
а) A=1000, B=1100
б) A=900, B=1000
в) A=600, B=1200
Разработать схему алгоритма для нахождения всех делителей натурального числа N. Протестировать алгоритм для N=10, N=75, N=99, N=13. Разработать схему алгоритма для вычисления N! (факториал числа N). Факториал вычисляется по формуле:N!=
Операцию вычисления факториала использовать нельзя!
Протестировать алгоритм для N=0, N=2 N=4.
