Структурное программирование конспект урока 11 класс

Обновлено: 07.07.2024

Сайт учителя информатики. Технологические карты уроков, Подготовка к ОГЭ и ЕГЭ, полезный материал и многое другое.

§ 9. Структурное программирование

Информатика. 11 класса. Босова Л.Л. Оглавление

На всех этапах подготовки к алгоритмизации задачи широко используется структурное представление алгоритма.

Cтруктурное программирование воплощает принципы системного подхода в процессе создания и эксплуатации программного обеспечения ЭВМ. В основу структурного программирования положены следующие достаточно простые положения:

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

Фундаментом структурного программирования является теорема о структурировании.

Эта теорема устанавливает, что, как бы сложна ни была задача, схема соответствующей программы всегда может быть представлена с использованием ограниченного числа элементарных управляющих структур.

Базовыми элементарными структурами являются структуры: следование, ветвление и повторение (цикл), любой алгоритм может быть реализован в виде композиции этих трех конструкций.

Первая (а) структура — тип последовательность (или просто последовательность), вторая (б) – структура выбора (ветвление), третья (в) – структура цикла с предусловием.

9.1. Общее представление о структурном программировании

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

Одна из таких технологий — структурное программирование — была разработана ещё в начале 70-х годов прошлого века и связана с именем выдающегося нидерландского ученого Эдсгера Дейкстры (1930-2002).

Структурное программирование — технология разработки программного обеспечения, в основе которой лежит представление программы в виде иерархической структуры логически целостных фрагментов (блоков).

Перечислим некоторые принципы структурного программирования.

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

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

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

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

Такая последовательность гарантирует, что на каждом этапе разработки программист будет иметь дело с обозримым и понятным ему множеством фрагментов, осознавая, что общая структура всех более высоких уровней программы верна.

Действия по вычислению длины отрезка представляют собой логически целостный фрагмент, который целесообразно оформить в виде вспомогательного алгоритма.

9.2. Вспомогательный алгоритм

Пусть ХА, ХВ, YA, YB, ХС, YC — координаты вершин треугольника ABC. Его периметр — сумма длин отрезков АВ, ВС и АС.

Из курса геометрии вам известна формула для вычисления длины отрезка АВ по координатам его концов (рис. 2.11):

Рис. 2.11. Отрезок АВ

Вспомогательный алгоритм — это алгоритм, целиком используемый в составе другого алгоритма.

На рисунке 2.12 представлены:

1) блок-схема алгоритма вычисления периметра треугольника, предполагающая вызов вспомогательного алгоритма Отрезок;
2) блок-схема вспомогательного алгоритма Отрезок.

При вызове вспомогательного алгоритма указываются его параметры (входные данные и результаты). Параметрами вспомогательного алгоритма Отрезок являются величины XI, Y1, Х2, Y2, D. Это формальные параметры, они используются при описании алгоритма. При конкретном обращении к вспомогательному алгоритму формальные параметры заменяются фактическими параметрами, т. е. именно теми величинами, для которых будет исполнен вспомогательный алгоритм. Типы, количество и порядок следования формальных и фактических параметров должны совпадать.

Рис. 2.12. Алгоритм вычисления периметра треугольника и вспомогательный алгоритм Отрезок

Команда вызова вспомогательного алгоритма исполняется следующим образом:

1) формальные входные данные вспомогательного алгоритма заменяются значениями фактических входных данных, указанных в команде вызова вспомогательного алгоритма;
2) для заданных входных данных исполняются команды вспомогательного алгоритма;
3) полученные результаты присваиваются переменным с именами фактических результатов;
4) осуществляется переход к следующей команде основного алгоритма.

Каким будет результат работы алгоритма при следующих исходных данных: ХА = 1, ХВ = 2, ХС = 3, YA = 1, YВ = 3, YC = 1.

9.3. Рекурсивные алгоритмы

Алгоритм называется рекурсивным, если на каком-либо шаге он прямо или косвенно обращается сам к себе.

Пример 2. Как известно, факториал натурального числа n определяется следующим образом: n! = 1 • 2 • 3 • … • n; 0! считается равным единице (0! = 1).

Иначе это можно записать так:

В определении факториала через рекурсию имеется условие n ? 1, при достижении которого вызов рекурсии прекращается.

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

Пример 3. Определим функцию S(n), вычисляющую сумму цифр в заданном натуральном числе n:

Самостоятельно определите функцию К(n), которая возвращает количество цифр заданного натурального числа n.

Пример 4. Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:

Требуется выяснить, чему равно значение функции F(7). По условию, F(1) = F(2) = 1.

Подобные вычисления можно проводить в уме, а их результаты фиксировать в таблице:

Пример 5. Исполнитель Плюс имеет следующую систему команд:

1) прибавь 1;
2) прибавь 2;
3) прибавь 4.

С помощью первой из них исполнитель увеличивает число на экране на 1, с помощью второй — на 2, с помощью третьей — на 4. Программа для исполнителя Плюс — это последовательность команд. Выясним, сколько разных программ, преобразующих число 20 в число 30, можно составить для этого исполнителя.

Количество программ, с помощью которых можно получить некоторое число n, будем рассматривать как функцию К(n).

Запишем все соотношения, определяющие функцию К(n):

Заполним по этой формуле таблицу для всех значений n от 20 до 30:

Итак, существует 169 различных программ, с помощью которых исполнитель Плюс может преобразовать число 20 в 30.

Любой объект, который частично определяется через самого себя, называется рекурсивным. Нас окружает множество рекурсивных объектов. Приведём примеры только некоторых из них.

1. Матрёшка — русская деревянная игрушка в виде расписной куклы, внутри которой находятся подобные ей куклы меньшего размера.

2. Два зеркала, поставленные друг напротив друга, — в них образуются два коридора из затухающих отражений. Это, например, можно наблюдать в спальном железнодорожном вагоне.

9.4. Запись вспомогательных алгоритмов на языке Pascal

Запись вспомогательных алгоритмов в языках программирования осуществляется с помощью подпрограмм. В языке Pascal различают два вида подпрограмм: процедуры и функции.

Процедура — подпрограмма, имеющая произвольное количество входных и выходных данных.

Описание процедуры имеет вид:

procedure ( ; var: );

begin

end;

В заголовке процедуры после её имени приводится перечень формальных параметров и их типов. Для вызова процедуры достаточно указать её имя со списком фактических параметров. При этом между фактическими и формальными параметрами должно быть полное соответствие по количеству, порядку следования и типу.

Пример 6. Запишем на языке Pascal программу нахождения периметра треугольника, заданного координатами его вершин. Вспомогательный алгоритм оформим с помощью процедуры.

Выполните программу на компьютере.

Подумайте, каким образом можно модифицировать программу, чтобы вычислять с её помощью периметр n-угольника. Каким образом при решении этой задачи можно использовать массивы?

Функция — подпрограмма, имеющая единственный результат, записываемый в ячейку памяти, имя которой совпадает с именем функции.

Описание функции имеет вид:

В заголовке функции после её имени приводится описание входных данных — указывается перечень формальных параметров и их типов. Там же указывается тип самой функции, т. е. тип результата. В блоке функции обязательно должен присутствовать оператор

Для вызова функции достаточно указать её имя со списком фактических параметров в любом выражении, в условиях (после слов if, while, until) или в операторе write главной программы.

Пример 7. Запишем на языке Pascal программу нахождения периметра треугольника, заданного координатами его вершин. Вспомогательный алгоритм оформим с помощью функции.

Выполните программу на компьютере.

На основе этой программы напишите функцию, вычисляющую площадь треугольника по целочисленным координатам его вершин. Используйте эту функцию для вычисления площади n-угольника.

САМОЕ ГЛАВНОЕ

Основные принципы структурного программирования заключаются в том, что:

Вспомогательный алгоритм — это алгоритм, целиком используемый в составе другого алгоритма.

Алгоритм называется рекурсивным, если на каком-либо шаге он прямо или косвенно обращается сам к себе.

Вопросы и задания

1. В чём заключается сущность структурного программирования? Какие преимущества обеспечивает эта технология?

2. Какой алгоритм называется вспомогательным?

3. Вспомните, в чём состоит суть метода последовательного построения (уточнения) алгоритма. Как он называется иначе?

5. Дан прямоугольный параллелепипед, длины рёбер которого равны а, b и с.

Требуется определить периметр треугольника, образованного диагоналями его граней. Какой алгоритм целесообразно использовать при решении этой задачи в качестве вспомогательного?

6. Какой вспомогательный алгоритм называется рекурсивным? Что такое граничное условие и каково его назначение в рекурсивном алгоритме?

7. Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:

Требуется выяснить, чему равно значение функции F(10).

8. Исполнитель Калькулятор имеет следующую систему команд:

1) прибавь 1;
2) умножь на 2.

С помощью первой из них исполнитель увеличивает число на экране на 2, с помощью второй — в 2 раза.

1) Выясните, сколько разных программ, преобразующих число 1 в число 20, можно составить для этого исполнителя.
2) Сколько среди них таких программ, у которых в качестве промежуточного результата обязательно получается число 15?
3) Сколько среди них таких программ, у которых в качестве промежуточного результата никогда не получается число 12?

9. Попробуйте найти рекурсивные синтаксические структуры:

10. Найдите информацию о таких геометрических фракталах, как Снежинка Коха, Т-квадрат, Н-фрактал, кривая Леви, Драконова ломаная.

11. Напишите программу вычисления значения функции F(n), рассмотренной в примере 4 этого параграфа. Вычислите с её помощью значение функции F(7).

12. Напишите программу вычисления

13. Дана программа:

Не выполняя программу на компьютере, выясните, что получится в результате работы этой программы.

Проверьте свой результат, выполнив программу на компьютере.

Дополнительные материалы к главе смотрите в авторской мастерской.

Перечень вопросов, рассматриваемых в теме: структурное программирование, подпрограммы, формальные параметры, фактические параметры, параметры-значения, параметры-переменные, процедуры, функции, рекурсия.

Глоссарий по теме: структурное программирование, подпрограммы, процедуры, функции, рекурсия.

Основная литература по теме урока:

Л. Л. Босова, А. Ю. Босова. Информатика. Базовый уровень: учебник для 11 класса. — М.: БИНОМ. Лаборатория знаний, 2017

Дополнительная литература по теме урока:

- И. Г. Семакин, Т. Ю. Шеина, Л. В. Шестакова Информатика и ИКТ. Профильный уровень: учебник для 11 класса. — М.: БИНОМ. Лаборатория знаний, 2012

- Андреева Е. В. Программирование — это так просто, программирование — это так сложно. Современный учебник программирования. — М.: МЦНМО, 2015

Теоретический материал для самостоятельного изучения

На одном из прошлых уроков мы упоминали теорему, суть которой заключается в том, что для любой логической задачи можно составить алгоритм, используя лишь три базовых структуры: следование, ветвление и повторение. Эта теорема является одним из ключевых положений структурного программирования, о котором мы с вами сегодня и будем говорить.

Основные принципы структурного программирования заключаются в том, что:

Давайте узнаем, что такое подпрограммы, какими они могут быть и как их использовать.

На прошлом уроке мы рассмотрели один из базовых алгоритмов обработки числовых данных — алгоритм нахождения НОД натуральных чисел.

Вернемся к нему для решения задачи нахождения НОД трех натуральных чисел a, b, c. Для решения воспользуемся следующим математическим фактом: если a, b, c — три натуральных числа, то НОД (a, b, c) = НОД (НОД (a, b), c). Иначе говоря, нужно найти НОД двух величин, а затем НОД полученного значения и третьего числа.

Аналогичным образом можно было решить задачу нахождения НОД четырех, пяти и т. д. чисел. Понятно, что при этом код программы увеличился бы за счет добавления однотипных блоков. А можно ли каким-либо образом сократить запись алгоритма? Давайте разберемся.

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

Подпрограммы подразделяются на процедуры (procedure) и функции (function).

Описание процедуры в Паскале имеет следующий формат:

Оформим в нашем примере в качестве процедуры подпрограмму нахождения НОД двух натуральных чисел.

Теперь разберемся, какая служебная информация находится в круглых скобка рядом с именем процедуры.

Подпрограмма реализует некоторый частный алгоритм, который вызывается в основной программе. Для реализации алгоритма подпрограмме могут понадобиться некоторые данные из основной программы. Обработав эти данные, подпрограмма возвращает результат основной программе, если в этом есть необходимость. Передавать информацию из основной программы в подпрограмму и наоборот мы можем только через переменные, которые носят специальное название — параметры. Именно они и указываются в круглых скобках рядом с именем процедуры.

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

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

Параметры-значения указываются так:

Чаще всего параметры-значения служат для работы с входной в процедуру информацией, а параметры-переменные — для работы с выходной информацией.

Вернемся к программе nod1. Наша процедура evklid должна получить на вход две переменные, найти для них НОД и передать его в основную программу. Получаем:

Теперь рассмотрим другой вариант программы, решающий ту же задачу. В ней используется процедура без параметров.

Чтобы разобраться в этом примере, введем одно важное понятие — область действия описания.

Областью действия описания любого программного объекта (переменной, типа, константы и т. д.) является тот блок, на который это описание распространяется. Если данный блок вложен в другой (подпрограмма), то присутствующие во вложенном блоке описания являются локальными. Они действуют только в пределах внутреннего блока. Описания же, расположенные во внешнем блоке, называются глобальными по отношению к внутреннему блоку. Если глобально описанный объект используется во внутреннем блоке, то на него распространяется внешнее (глобальное) описание.

В программе nod2 переменные x, y, nod1 являются локальными внутри процедуры; переменные a, b, c — глобальные. Однако внутри процедуры переменные a, b, c не используются. Связь между внешним блоком и процедурой осуществляется через параметры.

В программе nod2 все переменные являются глобальными. В процедуре evklid нет ни одной локальной переменной. Здесь обмен значениями между основной программой и процедурой осуществляется через глобальные переменные.

Теперь выясним, что такое подпрограмма-функция. Обычно функция используется в том случае, когда результатом работы подпрограммы должна быть скалярная (простая) величина. Тип результата называется типом функции.

Формат описания функции следующий:

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

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

Сравнивая приведенные выше программы, можно сделать вывод, что программа nod4 имеет определенные преимущества перед другими. Функция позволяет получить результат путем выполнения одного оператора присваивания. Здесь также демонстрируется возможность того, что фактическим параметром при обращении к функции может быть эта же функция.

Среди всевозможных подпрограмм особый интерес представляют так называемые рекурсивные подпрограммы.

Рекурсивная подпрограмма (функция, процедура) — подпрограмма, содержащая в своем описании вызов самой себя.

Пример 1. Как известно, факториал натурального числа определяется следующим образом:

Иначе это можно записать так:

F(n)=F(n–1) · n при n > 1.

В определении факториала через рекурсию имеется условие n ≤ 1, при достижении которого вызов рекурсии прекращается. Такое условие (оно называется граничным) в рекурсивном определении должно присутствовать обязательно!

Пример 2. Алгоритм вычисления функции F(n), где n — натуральное число, задан следующими соотношениями:

F(n)=F(n–1) +3· F(n–2) при n > 2.

Требуется выяснить, чему равно значение функции F(7).

По условию, F(1) = F(2) = 1.

F(3) = F(2) + 3 · F(1) = 1 + 3 · 1 = 4.

F(4) = F(3) + 3 · F(2) = 4 + 3 · 1 = 7.

F(5) = F(4) + 3 · F(3) = 7 + 3 · 4 = 19.

F(6) = F(5) + 3 · F(4) = 19 + 3 · 7 = 40.

F(7) = F(6) + 3 · F(5) = 40 + 3 · 19 = 97.

Подобные вычисления можно проводить в уме, а их результаты фиксировать в таблице:

И в завершение вспомним задачу вычисления НОД и модифицируем с использованием рекурсивной функции.

Для учеников 1-11 классов и дошкольников
Бесплатные сертификаты учителям и участникам

Урок № 63

Дата: 15 .01

Тема: Структурное программирование. Решение задач ЕГЭ.

Тип урока: комбинированный урок

Обучающие : повторить основные приемы программирования алгоритмов с ветвлением на Паскале;

Развивающие : развивать способности анализировать и обобщать учебный материал; развивать способности формализации, элементов системного мышления;

Воспитательные: воспитывать информационную компетентность, интерес к изучаемому предмету.

Проверка домашнего задания

Актуализация опорных знаний

Объяснение нового материала

Подведение итогов урока

Организационный момент.

Приветствие. Проверка присутствующих.

Проверка домашнего задания.

Проверка наличия, обсуждение.

Актуализация опорных знаний.

Объяснение нового материала.

Задача № 1: Ввести число. Если оно неотрицательно, вычесть из него 50, в противном случае прибавить к нему 100. (Написать программу, начертить блок-схему).

Задача № 2: Ввести 2 числа. Если их произведение отрицательно, умножить его на –2 и вывести на экран, в противном случае увеличить его в 1,5 раза и вывести на экран. (Написать программу, начертить блок-схему).

Задача № 3: Ввести число. Если оно четное, разделить его на 4, если нечетное - умножить на 5.

Задача № 4: Ввести рост человека. Вывести на экран “ВЫСОКИЙ”, если его рост превышает 180 см, и “НЕ ОЧЕНЬ ВЫСОКИЙ” в противном случае.

Задача № 5: Составить программу, которая спрашивает возраст человека и, если ему 18 лет и больше, сообщает “Замечательно. Вы уже можете водить автомобиль”, а в противном случае – “К сожалению, водить автомобиль Вам рановато”.

Задача № 1: Составить программу вычисления значений функции для любого х по желанию пользователя:

Задача № 2: Вовочка, любитель стрелять из рогатки, 7 раз попадал в милицию. Ввести с клавиатуры целое положительное число – № попадания. Определить результат: ,6,7 – милиционеры вставляли новое стекло, 4,5 – новое стекло вставлял папа Вовочки,1,2 , 3 – стекло не разбилось.

Задача № 3: Вводятся три значения ускорения свободного падения. Программа должна проверить, есть ли среди них ускорение свободного падения.

Задача № 4: Составить программу, которая запрашивает ввод температуры тела человека и определяет, здоров он или болен (здоров при 36

Задача №1: Человек вводит в компьютер число. Если оно находится в интервале от 28 до 30, то нужно напечатать текст ПОПАЛ, если оно больше 30 — то ПЕРЕЛЁТ, если оно меньше 28, то НЕДОЛЁТ.

Задача № 2: Ввести с клавиатуры трёхзначное число. Определить, является ли оно палиндромом (т.е. одинаково читается справа налево и слева направо). Например, числа 121, 343 – палиндромы.

Задача № 3: Ввести с клавиатуры двузначное число. Определить, делится ли оно на сумму своих цифр.

Задача № 5: Составить алгоритм решения линейного уравнения ax + b = 0. Учесть все возможные случаи в зависимости от исходных данных (одно решение, бесконечно много решений, нет решений).

Методы обучения объяснительно-иллюстративный, исследовательский, практический, дифференцированный

Оборудование и программное обеспечение:

компьютер;
проектор;
операционная система;
язык программирования Паскаль.

Организационный момент.
Актуализация знаний
Обобщение материала
Выступление учеников с разработанными программами
Контроль знаний
Подведение итогов урока. Домашнее задание.

1. Организационный момент

2. Актуализация начальных знаний учащихся.

- Понятие циклический алгоритм мы знаем. Давайте вспомним, что мы понимали под понятием цикла?
- Давайте вспомним, что характерно для циклического алгоритма? (Команды, входящие в цикл выполняются несколько раз).
- Приведите примеры циклических алгоритмов. ( “Бутерброды на весь класс”, “Сложение чисел”, “Произведение нескольких чисел”, и др.).
- Какие вы знаете способы записи алгоритмов? (словесная запись, словесно-формульная запись, запись в виде блок-схемы, на языке программирования).
- Сегодня Вы в своих выступлениях представите программы в которых используются циклические алгоритмы с операторами языка Паскаль While, For, Repeat.

3. Обобщение материала.

Цикл - процесс многократного повторения каких-либо действий .

При разработке программы циклической структуры выделяют следующие понятия:

параметр (переменная цикла) – величина, с изменением значения которой связано многократное выполнение цикла;
начальное и конечное значения параметра цикла;
шаг цикла - значение, но которое изменяется параметр цикла при каждом повторении;
Действия, повторяющиеся в цикле, называются телом цикла .

Цикл организуют по определенным правилам. Цикл состоит из следующих блоков:

подготовки цикла;
тела цикла;
условия продолжения цикла.

В подготовку цикла входят действия, связанные с заданием исходных значений для параметра цикла.

В тело цикла входят многократно повторяющиеся действия для вычисления искомых величин и подготовка следующего значения параметра цикла.

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

Язык Паскаль имеет три оператора, с помощью которых можно организовать циклическую структуру.

Цикл с предусловием “Пока”.
Цикл с постусловием “До”.
Цикл с параметром “Для”.

Обратите внимание на слайды. (далее учитель поясняет содержание слайдов) (Презентация)

Какие выводы вы можете сделать? (Можно использовать любой оператор цикла. Есть ограничения в использовании цикла For (шаг изменения параметра цикла должен быть 1 или -1. Если не известно сколько раз будет выполняться цикл, то используем While или Repeat)

Читайте также: