Структурное программирование языки программирования
информатика
Лекции
1. Введение
ИНФОРМАЦИЯ И ЕЕ РОЛЬ В СОВРЕМЕННОМ ОБЩЕСТВЕ.
ИНФОРМАТИКА- НАУКА, ИЗУЧАЮЩАЯ СПОСОБЫ АВТОМАТИЗИРОВАННОГО СОЗДАНИЯ, ХРАНЕНИЯ, ОБРАБОТКИ, ИСПОЛЬЗОВАНИЯ, ПЕРЕДАЧИ И ЗАЩИТЫ ИНФОРМАЦИИ.
ИНФОРМАЦИЯ – ЭТО НАБОР СИМВОЛОВ, ГРАФИЧЕСКИХ ОБРАЗОВ ИЛИ ЗВУКОВЫХ СИГНАЛОВ, НЕСУЩИХ ОПРЕДЕЛЕННУЮ СМЫСЛОВУЮ НАГРУЗКУ.
В развитых странах большинство работающих заняты не в сфере производства, а в той или иной степени занимаются обработкой информации. Поэтому философы называют нашу эпоху постиндустриальной. В 1983 году американский сенатор Г.Харт охарактеризовал этот процесс так: «Мы переходим от экономики, основанной на тяжелой промышленности, к экономике, которая все больше ориентируется на информацию, новейшую технику и технологию, средства связи и услуги..»
2. КРАТКАЯ ИСТОРИЯ РАЗВИТИЯ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ.
Вся история развития человеческого общества связана с накоплением и обменом информацией (наскальная живопись, письменность, библиотеки, почта, телефон, радио, счеты и механические арифмометры и др.). Коренной перелом в области технологии обработки информации начался после второй мировой войны.
В вычислительных машинах первого поколения основными элементами были электронные лампы. Эти машины занимали громадные залы, весили сотни тонн и расходовали сотни киловатт электроэнергии. Их быстродействие и надежность были низкими, а стоимость достигала 500-700 тысяч долларов.
Появление более мощных и дешевых ЭВМ второго поколения стало возможным благодаря изобретению в 1948 году полупроводниковых устройств- транзисторов. Главный недостаток машин первого и второго поколений заключался в том, что они собирались из большого числа компонент, соединяемых между собой. Точки соединения (пайки) являются самыми ненадежными местами в электронной технике, поэтому эти ЭВМ часто выходили из строя.
В ЭВМ третьего поколения (с середины 60-х годов ХХ века) стали использоваться интегральные микросхемы (чипы)- устройства, содержащие в себе тысячи транзисторов и других элементов, но изготовляемые как единое целое, без сварных или паяных соединений этих элементов между собой. Это привело не только к резкому увеличению надежности ЭВМ, но и к снижению размеров, энергопотребления и стоимости (до 50 тысяч долларов).
История ЭВМ четвертого поколения началась в 1970 году, когда ранее никому не известная американская фирма INTEL создала большую интегральную схему (БИС), содержащую в себе практически всю основную электронику компьютера. Цена одной такой схемы (микропроцессора) составляла всего несколько десятков долларов, что в итоге и привело к снижению цен на ЭВМ до уровня доступных широкому кругу пользователей.
СОВРЕМЕННЫЕ КОМПЬТЕРЫ- ЭТО ЭВМ ЧЕТВЕРТОГО ПОКОЛЕНИЯ, В КОТОРЫХ ИСПОЛЬЗУЮТСЯ БОЛЬШИЕ ИНТЕГРАЛЬНЫЕ СХЕМЫ.
6.ПРЕДСТАВЛЕНИЕ ИНФОРМАЦИИ В КОМПЬЮТЕРЕ И ЕЕ ОБЪЕМ.
ЛЮБОЕ СООБЩЕНИЕ НА ЛЮБОМ ЯЗЫКЕ СОСТОИТ ИЗ ПОСЛЕДОВАТЕЛЬНОСТИ СИМВОЛОВ- БУКВ, ЦИФР, ЗНАКОВ. Действительно, в каждом языке есть свой алфавит из определенного набора букв (например, в русском- 33 буквы, английском- 26, и т.д.). Из этих букв образуются слова, которые в свою очередь, вместе с цифрами и знаками препинания образуют предложения, в результате чего и создается текстовое сообщение. Не является исключением и язык на котором «говорит» компьютер, только набор букв в этом языке является минимально возможным.
В КОМПЬЮТЕРЕ ИСПОЛЬЗУЮТСЯ 2 СИМВОЛА- НОЛЬ И ЕДИНИЦА (0 и 1), АНАЛОГИЧНО ТОМУ, КАК В АЗБУКЕ МОРЗЕ ИСПОЛЬЗУЮТСЯ ТОЧКА И ТИРЕ. Действительно, закодировав привычные человеку символы (буквы, цифры, знаки) в виде нулей и единиц (или точек и тире), можно составить, передать и сохранить любое сообщение.
ЭТО СВЯЗАНО С ТЕМ, ЧТО ИНФОРМАЦИЮ, ПРЕДСТАВЛЕННУЮ В ТАКОМ ВИДЕ, ЛЕГКО ТЕХНИЧЕСКИ СМОДЕЛИРОВАТЬ, НАПРИМЕР, В ВИДЕ ЭЛЕКТРИЧЕСКИХ СИГНАЛОВ. Если в какой-то момент времени по проводнику идет ток, то по нему передается единица, если тока нет- ноль. Аналогично, если направление магнитного поля на каком-то участке поверхности магнитного диска одно- на этом участке записан ноль, другое- единица. Если определенный участок поверхности оптического диска отражает лазерный луч- на нем записан ноль, не отражает- единица.
ОБЪЕМ ИНФОРМАЦИИ, НЕОБХОДИМЫЙ ДЛЯ ЗАПОМИНАНИЯ ОДНОГО ИЗ ДВУХ СИМВОЛОВ-0 ИЛИ 1, НАЗЫВАЕТСЯ 1 БИТ (англ. binary digit- двоичная единица). 1 бит- минимально возможный объем информации. Он соответствует промежутку времени, в течение которого по проводнику передается или не передается электрический сигнал, участку поверхности магнитного диска, частицы которого намагничены в том или другом направлении, участку поверхности оптического диска, который отражает или не отражает лазерный луч, одному триггеру, находящемуся в одном из двух возможных состояний.
Итак, если у нас есть один бит, то с его помощью мы можем закодировать один из двух символов- либо 0, либо 1.
3 бита- 8 вариантов;
Продолжая дальше, получим:
4 бита- 16 вариантов,
7 бит- 128 вариантов,
8 бит- 256 вариантов,
9 бит- 512 вариантов,
10 бит- 1024 варианта,
В обычной жизни нам достаточно 150-160 стандартных символов (больших и маленьких русских и латинских букв, цифр, знаков препинания, арифметических действий и т.п.). Если каждому из них будет соответствовать свой код из нулей и единиц, то 7 бит для этого будет недостаточно (7 бит позволят закодировать только 128 различных символов), поэтому используют 8 бит.
ДЛЯ КОДИРОВАНИЯ ОДНОГО ПРИВЫЧНОГО ЧЕЛОВЕКУ СИМВОЛА В КОМПЬЮТЕРЕ ИСПОЛЬЗУЕТСЯ 8 БИТ, ЧТО ПОЗВОЛЯЕТ ЗАКОДИРОВАТЬ 256 РАЗЛИЧНЫХ СИМВОЛОВ.
СТАНДАРТНЫЙ НАБОР ИЗ 256 СИМВОЛОВ НАЗЫВАЕТСЯ ASCII ( произносится «аски», означает «Американский Стандартный Код для Обмена Информацией»- англ. American Standart Code for Information Interchange).
ОН ВКЛЮЧАЕТ В СЕБЯ БОЛЬШИЕ И МАЛЕНЬКИЕ РУССКИЕ И ЛАТИНСКИЕ БУКВЫ, ЦИФРЫ, ЗНАКИ ПРЕПИНАНИЯ И АРИФМЕТИЧЕСКИХ ДЕЙСТВИЙ И Т.П.
КАЖДОМУ СИМВОЛУ ASCII СООТВЕТСТВУЕТ 8-БИТОВЫЙ ДВОИЧНЫЙ КОД, НАПРИМЕР:
ОБЪЕМ ИНФОРМАЦИИ, НЕОБХОДИМЫЙ ДЛЯ ЗАПОМИНАНИЯ ОДНОГО СИМВОЛА ASCII НАЗЫВАЕТСЯ 1 БАЙТ.
Очевидно что, поскольку под один стандартный ASCII-символ отводится 8 бит,
Остальные единицы объема информации являются производными от байта:
1 КИЛОБАЙТ = 1024 БАЙТА И СООТВЕТСТВУЕТ ПРИМЕРНО ПОЛОВИНЕ СТРАНИЦЫ ТЕКСТА,
1 МЕГАБАЙТ = 1024 КИЛОБАЙТАМ И СООТВЕТСТВУЕТ ПРИМЕРНО 500 СТРАНИЦАМ ТЕКСТА,
1 ГИГАБАЙТ = 1024 МЕГАБАЙТАМ И СООТВЕТСТВУЕТ ПРИМЕРНО 2 КОМПЛЕКТАМ ЭНЦИКЛОПЕДИИ,
1 ТЕРАБАЙТ = 1024 ГИГАБАЙТАМ И СООТВЕТСТВУЕТ ПРИМЕРНО 2000 КОМПЛЕКТАМ ЭНЦИКЛОПЕДИИ.
СКОРОСТЬ ПЕРЕДАЧИ ИНФОРМАЦИИ ПО ЛИНИЯМ СВЯЗИ ИЗМЕРЯЕТСЯ В БОДАХ.
В частности, если говорят, что пропускная способность какого-то устройства составляет 28 Килобод, то это значит, что с его помощью можно передать по линии связи около 28 тысяч нулей и единиц за одну секунду.
7. СЖАТИЕ ИНФОРМАЦИИ НА ДИСКЕ
ИНФОРМАЦИЮ НА ДИСКЕ МОЖНО ОБРАБОТАТЬ С ПОМОЩЬЮ СПЕЦИАЛЬНЫХ ПРОГРАММ ТАКИМ ОБРАЗОМ, ЧТОБЫ ОНА ЗАНИМАЛА МЕНЬШИЙ ОБЪЕМ.
Сжатие информации используют, если объем носителя информации недостаточен для хранения требуемого объема информации или информацию надо послать по электронной почте
Программы, используемые при сжатии отдельных файлов называются архиваторами. Эти программы часто позволяют достичь степени сжатия информации в несколько раз.
«Забытые» парадигмы программирования
Получилось так, что те парадигмы, которые раньше потом и кровью пробивались в свет через орды приверженцев традиционных методов постепенно забываются. Эти парадигмы возникли на заре программирования и то, почему они возникали, какие преимущества они давали и почему используются до сих пор полезно знать любому разработчику.
Ладно. Введение это очень весело, но вы его все равно не читаете, так что кому интересно — добро пожаловать под кат!
Императивное программирование
Исторически сложилось так, что подавляющее большинство вычислительной техники, которую мы программируем имеет состояние и программируется инструкциями, поэтому первые языки программирования в основном были чисто императивными, т.е. не поддерживали никаких парадигм кроме императивной.
Это были машинные коды, языки ассемблера и ранние высокоуровневые языки, вроде Fortran.
Ключевые моменты:
В этой парадигме вычисления описываются в виде инструкций, шаг за шагом изменяющих состояние программы.
В низкоуровневых языках (таких как язык ассемблера) состоянием могут быть память, регистры и флаги, а инструкциями — те команды, что поддерживает целевой процессор.
В более высокоуровневых (таких как Си) состояние — это только память, инструкции могут быть сложнее и вызывать выделение и освобождение памяти в процессе своей работы.
В совсем высокоуровневых (таких как Python, если на нем программировать императивно) состояние ограничивается лишь переменными, а команды могут представлять собой комплексные операции, которые на ассемблере занимали бы сотни строк.
Основные понятия:
Порожденные понятия:
— Присваивание
— Переход
— Память
— Указатель
Языки поддерживающие данную парадигму:
Как основную:
— Языки ассемблера
— Fortran
— Algol
— Cobol
— Pascal
— C
— C++
— Ada
Как вспомогательную:
— Python
— Ruby
— Java
— C#
— PHP
— Haskell (через монады)
Стоит заметить, что большая часть современных языков в той или иной степени поддерживает императивное программирование. Даже на чистом функциональном языке Haskell можно писать императивно.
Структурное программирование
Структурное программирование — парадигма программирования (также часто встречающееся определение — методология разработки), которая была первым большим шагом в развитии программирования.
Основоположниками структурного программирования были такие знаменитые люди как Э. Дейкстра и Н. Вирт.
Языками-первопроходцами в этой парадигме были Fortran, Algol и B, позже их приемниками стали Pascal и C.
Ключевые моменты:
Эта парадигма вводит новые понятия, объединяющие часто используемые шаблоны написания императивного кода.
В структурном программировании мы по прежнему оперируем состоянием и инструкциями, однако вводится понятие составной инструкции (блока), инструкций ветвления и цикла.
Благодаря этим простым изменениям возможно отказаться от оператора goto в большинстве случаев, что упрощает код.
Иногда goto все-же делает код читабельнее, благодаря чему он до сих пор широко используется, несмотря на все заявления его противников.
Основные понятия:
— Блок
— Цикл
— Ветвление
Языки поддерживающие данную парадигму:
Как основную:
Как вспомогательную:
— C#
— Java
— Python
— Ruby
— JavaScript
Поддерживают частично:
— Некоторые макроассемблеры (через макросы)
Опять-же большая часть современных языков поддерживают структурную парадигму.
Процедурное программирование
Опять-же возрастающая сложность программного обеспечения заставила программистов искать другие способы описывать вычисления.
Собственно еще раз были введены дополнительные понятия, которые позволили по-новому взглянуть на программирование.
Этим понятием на этот раз была процедура.
В результате возникла новая методология написания программ, которая приветствуется и по сей день — исходная задача разбивается на меньшие (с помощью процедур) и это происходит до тех пор, пока решение всех конкретных процедур не окажется тривиальным.
Ключевые моменты:
Процедура — самостоятельный участок кода, который можно выполнить как одну инструкцию.
В современном программировании процедура может иметь несколько точек выхода (return в C-подобных языках), несколько точек входа (с помощью yield в Python или статических локальных переменных в C++), иметь аргументы, возвращать значение как результат своего выполнения, быть перегруженной по количеству или типу параметров и много чего еще.
Основные понятия:
Порожденные понятия:
— Вызов
— Аргументы
— Возврат
— Рекурсия
— Перегрузка
Языки поддерживающие данную парадигму:
Как основную:
— C
— C++
— Pascal
— Object Pascal
Как вспомогательную:
— C#
— Java
— Ruby
— Python
— JavaScript
Поддерживают частично:
— Ранний Basic
Стоит отметить, что несколько точек входа из всех этих языков поддерживаются только в Python.
Модульное программирование
Который раз увеличивающаяся сложность программ заставила разработчиков разделять свой код. На этот раз процедур было недостаточно и в этот раз было введено новое понятие — модуль.
Забегая вперед скажу, что модули тоже оказались неспособны сдержать с невероятной скоростью растущую сложность ПО и в последствии появились пакеты (это тоже модульное программирование), классы (это уже ООП), шаблоны (обобщенное программирование).
Программа описанная в стиле модульного программирования — это набор модулей. Что внутри, классы, императивный код или чистые функции — не важно.
Благодаря модулям впервые в программировании появилась серьезная инкапсуляция — возможно использовать какие-либо сущности внутри модуля, но не показывать их внешнему миру.
Ключевые моменты:
Модуль — это отдельная именованная сущность программы, которая объединяет в себе другие программные единицы, близкие по функциональности.
Например файл List.mod включающий в себя класс List
и функции для работы с ним — модуль.
Папка Geometry, содержащая модули Shape, Rectangle и Triangle — тоже модуль, хоть и некоторые языки разделяют понятие модуля и пакета (в таких языках пакет — набор модулей и/или набор других пакетов).
Модули можно импортировать (подключать), для того, чтобы использовать объявленные в них сущности.
Основные понятия:
Порожденные понятия:
Языки поддерживающие данную парадигму:
Как основную:
— Haskell
— Pascal
— Python
Как вспомогательную:
— Java
— C#
— ActionScript 3
Поддерживают частично:
— C/C++
В некоторых языках для модулей введены отдельные абстракции, в других же для реализации модулей можно использовать заголовочные файлы (в C/C++), пространства имен, статические классы и/или динамически подключаемые библиотеки.
Вместо заключения
В данной статье я не описал популярные сейчас объектно-ориентированное, обобщенное и функциональное программирование. Просто потому, что у меня есть свое, довольно радикальное мнение на этот счет и я не хотел разводить холивар. По крайней мере сейчас. Если тема окажется полезной для сообщества я планирую написать несколько статей, изложив основы каждой из этих парадигм подробно.
Также я ничего не написал про экзотические парадигмы, вроде автоматного, аппликативного, аспект/агент/компонент-ориентированного программирования. Я не хотел делать статью сильно большой и опять-же если тема будет востребована, я напишу и об этих парадигмах, возможно более подробно и с примерами кода.
Учитель информатики
Сайт учителя информатики. Технологические карты уроков, Подготовка к ОГЭ и ЕГЭ, программирование, полезный материал и многое другое.
Структурное программирование
§ 9. Структурное программирование
Информатика. 11 класса. Босова Л.Л. Оглавление
На всех этапах подготовки к алгоритмизации задачи широко используется структурное представление алгоритма.
Cтруктурное программирование воплощает принципы системного подхода в процессе создания и эксплуатации программного обеспечения ЭВМ. В основу структурного программирования положены следующие достаточно простые положения:
Структурное программирование иногда называют еще «программированием без GO TO». Рекомендуется избегать употребления оператора перехода всюду, где это возможно, но чтобы это не приводило к слишком громоздким структурированным программам.
К полезным случаям использования оператора перехода можно отнести выход из цикла или процедуры по особому условию, «досрочно» прекращающего работу данного цикла или данной процедуры, т.е. завершающего работу некоторой структурной единицы (обобщенного оператора) и тем самым лишь локально нарушающего структурированность программы.
Фундаментом структурного программирования является теорема о структурировании.
Эта теорема устанавливает, что, как бы сложна ни была задача, схема соответствующей программы всегда может быть представлена с использованием ограниченного числа элементарных управляющих структур.
Базовыми элементарными структурами являются структуры: следование, ветвление и повторение (цикл), любой алгоритм может быть реализован в виде композиции этих трех конструкций.
Первая (а) структура — тип последовательность (или просто последовательность), вторая (б) – структура выбора (ветвление), третья (в) – структура цикла с предусловием.
9.1. Общее представление о структурном программировании
Программирование как род занятий и сфера деятельности интенсивно развивается со второй половины прошлого века. За это время сложились определённые технологии, способствующие повышению производительности труда программистов, в том числе сокращению числа ошибок, упрощению отладки, модификации и сопровождения программного обеспечения. Особенно это важно при разработке больших и сложных программных комплексов, осуществляемой усилиями целых коллективов программистов.
Одна из таких технологий — структурное программирование — была разработана ещё в начале 70-х годов прошлого века и связана с именем выдающегося нидерландского ученого Эдсгера Дейкстры (1930-2002).
Структурное программирование — технология разработки программного обеспечения, в основе которой лежит представление программы в виде иерархической структуры логически целостных фрагментов (блоков).
Перечислим некоторые принципы структурного программирования.
1. Любая программа строится из трёх базовых управляющих конструкций: последовательность, ветвление, цикл.
2. В программе базовые управляющие конструкции могут быть вложены друг в друга произвольным образом.
3. Повторяющиеся фрагменты программы можно оформить в виде подпрограмм (процедур и функций). В виде подпрограмм можно оформить логически целостные фрагменты программы, даже если они не повторяются.
4. Все перечисленные конструкции должны иметь один вход и один выход.
5. Разработка программы ведётся пошагово, методом «сверху вниз».
О методе разработки алгоритма «сверху вниз» вы получили представление в курсе информатики основной школы. Напомним его ключевые моменты на примере разработки некоторой программы.
Сначала пишется короткий текст основной программы. В ней вместо каждого логически целостного фрагмента вставляется вызов подпрограммы, которая будет выполнять этот фрагмент. Вместо настоящих, работающих, подпрограмм в программу вставляются так называемые заглушки. Как правило, они удовлетворяют требованиям интерфейса заменяемого фрагмента, но не выполняют его функций.
На следующем шаге следует убедиться, что подпрограммы вызываются в правильной последовательности, т. е. верна общая структура программы.
После этого подпрограммы-заглушки последовательно заменяются на полнофункциональные, причём разработка каждой подпрограммы ведётся тем же методом, что и основной программы. На каждом этапе проверяется, что уже созданная программа правильно работает по отношению к подпрограммам более низкого уровня.
Разработка заканчивается тогда, когда ни на одном уровне не останется ни одной заглушки. Полученная программа проверяется и отлаживается.
Такая последовательность гарантирует, что на каждом этапе разработки программист будет иметь дело с обозримым и понятным ему множеством фрагментов, осознавая, что общая структура всех более высоких уровней программы верна.
Действия по вычислению длины отрезка представляют собой логически целостный фрагмент, который целесообразно оформить в виде вспомогательного алгоритма.
9.2. Вспомогательный алгоритм
Пример 1. Применим метод «сверху вниз» для разработки алгоритма нахождения периметра треугольника, заданного координатами своих вершин.
Пусть ХА, ХВ, 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).
Число, меньшее 20, при заданных начальных условиях и системе команд исполнителя Плюс получить невозможно. Следовательно, при n 20 может быть получено из чисел n — 1, n — 2 и n — 4 одной из трёх команд, входящих в систему команд исполнителя — «прибавь 1», «прибавь 2» и «прибавь 4» соответственно. При этом каждая программа получения из исходного числа чисел n-1, n-2 и n-4 удлинится на одну команду и будет приводить к числу n. Следовательно, К(n) = К(n — 1) + + К(n — 2) + К(n — 4).
Запишем все соотношения, определяющие функцию К(n):
Заполним по этой формуле таблицу для всех значений n от 20 до 30:
Итак, существует 169 различных программ, с помощью которых исполнитель Плюс может преобразовать число 20 в 30.
Любой объект, который частично определяется через самого себя, называется рекурсивным. Нас окружает множество рекурсивных объектов. Приведём примеры только некоторых из них.
1. Матрёшка — русская деревянная игрушка в виде расписной куклы, внутри которой находятся подобные ей куклы меньшего размера.
2. Два зеркала, поставленные друг напротив друга, — в них образуются два коридора из затухающих отражений. Это, например, можно наблюдать в спальном железнодорожном вагоне.
3. Примером рекурсивной структуры является замечательное стихотворение Р. Бернса «Дом, который построил Джек» в переводе С. Маршака.
4. Рекурсивную природу имеют геометрические фракталы. На рисунке представлено построение одного из геометрических фракталов — треугольника Серпинского. Чтобы его получить, нужно взять равносторонний треугольник с внутренней областью, провести в нём средние линии и «выкинуть» центральный из четырёх образовавшихся маленьких треугольников. Дальше эти же действия нужно повторить с каждым из оставшихся трёх треугольников, и т. д.
9.4. Запись вспомогательных алгоритмов на языке Pascal
Запись вспомогательных алгоритмов в языках программирования осуществляется с помощью подпрограмм. В языке Pascal различают два вида подпрограмм: процедуры и функции.
Процедура — подпрограмма, имеющая произвольное количество входных и выходных данных.
Описание процедуры имеет вид:
procedure ( ; var: );
begin
В заголовке процедуры после её имени приводится перечень формальных параметров и их типов. Для вызова процедуры достаточно указать её имя со списком фактических параметров. При этом между фактическими и формальными параметрами должно быть полное соответствие по количеству, порядку следования и типу.
Пример 6. Запишем на языке Pascal программу нахождения периметра треугольника, заданного координатами его вершин. Вспомогательный алгоритм оформим с помощью процедуры.
Выполните программу на компьютере.
Подумайте, каким образом можно модифицировать программу, чтобы вычислять с её помощью периметр n-угольника. Каким образом при решении этой задачи можно использовать массивы?
Функция — подпрограмма, имеющая единственный результат, записываемый в ячейку памяти, имя которой совпадает с именем функции.
Описание функции имеет вид:
В заголовке функции после её имени приводится описание входных данных — указывается перечень формальных параметров и их типов. Там же указывается тип самой функции, т. е. тип результата. В блоке функции обязательно должен присутствовать оператор
Для вызова функции достаточно указать её имя со списком фактических параметров в любом выражении, в условиях (после слов if, while, until) или в операторе write главной программы.
Пример 7. Запишем на языке Pascal программу нахождения периметра треугольника, заданного координатами его вершин. Вспомогательный алгоритм оформим с помощью функции.
Выполните программу на компьютере.
На основе этой программы напишите функцию, вычисляющую площадь треугольника по целочисленным координатам его вершин. Используйте эту функцию для вычисления площади n-угольника.
САМОЕ ГЛАВНОЕ
Структурное программирование — технология разработки программного обеспечения, в основе которой лежит представление программы в виде иерархической структуры логически целостных фрагментов (блоков).
Основные принципы структурного программирования заключаются в том, что:
1) любая программа строится из трёх базовых управляющих конструкций: последовательность, ветвление, цикл;
2) в программе базовые управляющие конструкции могут быть вложены друг в друга произвольным образом;
3) повторяющиеся фрагменты программы можно оформить в виде подпрограмм (процедур и функций). В виде подпрограмм можно оформить логически целостные фрагменты программы, даже если они не повторяются;
4) все перечисленные конструкции должны иметь один вход и один выход;
5) разработка программы ведётся пошагово, методом «сверху вниз».
Вспомогательный алгоритм — это алгоритм, целиком используемый в составе другого алгоритма.
Алгоритм называется рекурсивным, если на каком-либо шаге он прямо или косвенно обращается сам к себе.
Запись вспомогательных алгоритмов в языках программирования осуществляется с помощью подпрограмм. В языке Pascal различают два вида подпрограмм: процедуры и функции.
Вопросы и задания
1. В чём заключается сущность структурного программирования? Какие преимущества обеспечивает эта технология?
2. Какой алгоритм называется вспомогательным?
3. Вспомните, в чём состоит суть метода последовательного построения (уточнения) алгоритма. Как он называется иначе?
4. Опишите основные шаги разработки программы методом «сверху вниз».
5. Дан прямоугольный параллелепипед, длины рёбер которого равны а, b и с.
Требуется определить периметр треугольника, образованного диагоналями его граней. Какой алгоритм целесообразно использовать при решении этой задачи в качестве вспомогательного?
6. Какой вспомогательный алгоритм называется рекурсивным? Что такое граничное условие и каково его назначение в рекурсивном алгоритме?
7. Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
Требуется выяснить, чему равно значение функции F(10).
8. Исполнитель Калькулятор имеет следующую систему команд:
1) прибавь 1;
2) умножь на 2.
С помощью первой из них исполнитель увеличивает число на экране на 2, с помощью второй — в 2 раза.
1) Выясните, сколько разных программ, преобразующих число 1 в число 20, можно составить для этого исполнителя.
2) Сколько среди них таких программ, у которых в качестве промежуточного результата обязательно получается число 15?
3) Сколько среди них таких программ, у которых в качестве промежуточного результата никогда не получается число 12?
9. Попробуйте найти рекурсивные синтаксические структуры:
1) в поэме А. Блока «Двенадцать»;
2) в стихотворении М. Лермонтова «Сон»;
3) в романе М. Булгакова «Мастер и Маргарита»;
4) в фольклоре.
10. Найдите информацию о таких геометрических фракталах, как Снежинка Коха, Т-квадрат, Н-фрактал, кривая Леви, Драконова ломаная.
11. Напишите программу вычисления значения функции F(n), рассмотренной в примере 4 этого параграфа. Вычислите с её помощью значение функции F(7).
12. Напишите программу вычисления
Не выполняя программу на компьютере, выясните, что получится в результате работы этой программы.
Проверьте свой результат, выполнив программу на компьютере.
Дополнительные материалы к главе смотрите в авторской мастерской.