Императивное программирование – это исторически первая методология программирования, которой пользовался каждый программист, программирующий на любом из «массовых» языков программирования – Бейсик, Паскаль, Си. Она ориентирована на классическую фон Неймановскую модель, остававшуюся долгое время единственной аппаратной архитектурой. Методология императивного программирования характеризуется принципом последовательного изменения состояния вычислителя пошаговым образом.
Императивное программирование наиболее пригодно для решения задач, в которых последовательное исполнение каких-либо команд является естественным. Примером здесь может служить управление современными аппаратными средствами. Поскольку практически все современные компьютеры императивны, эта методология позволяет порождать достаточно эффективный исполняемый код.
Однако с ростом сложности задач программы становятся все более объёмными и менее читаемыми. Поэтому программирование и отладка больших программ, написанных исключительно на основе методологии императивного программирования, может затянуться на долгие годы.
Семинар 8. Метод заметающей прямой (Алгоритмы и структуры данных, часть 1)
Структурное программирование, являясь развитием императивной методологии, зиждется на двух основных принципах: последовательная декомпозиция алгоритма решения задачи и использование структурного кодирования. Идея структурного программирования заключается в том, что структура программы должна отражать структуру решаемой задачи, чтобы алгоритм решения был ясно виден из текста программы.
Последовательная декомпозиция алгоритма решения задачи представляет собой так называемое нисходящее проектирование («сверху вниз») и предполагает разложение общей функции обработки данных на более простые функциональные элементы, подзадачи, каждая из которых также разбивается на более детальные до тех пор, пока алгоритм решения всей задачи не будет реализован в терминах языка программирования.
Структурное кодирование заключается в использовании только трех основных управляющих алгоритмических конструкций, каждая из которых имеет по одному входу и выходу, и их суперпозиции. Оператор безусловного перехода (GOTO) в структурном программировании не используется, так как он порождает трудно отслеживаемые при отладке связи.
С целью уменьшения сложности разработки программного обеспечения в технологии структурного программирования вводится понятие подпрограммы (программы в программе) – набора операторов, выполняющих нужное действие и не зависящих от других частей программы. Подпрограммы бывают двух видов – процедуры и функции. Процедура выполняет группу операторов (над некоторыми операндами), а функция, кроме того, возвращает (то есть передаёт обратно) в точку вызова вычисленное значение определённого типа.
Данные передаются подпрограмме в виде параметров или аргументов. Параметры, которые указываются в тексте заголовка, называются формальными. Они нужны только для формального описания тела подпрограммы. При выполнении программы, в момент вызова подпрограммы, подставляются конкретные значения (или ссылки на значения – переменные) – фактические параметры (см., в котором происходит слияние двух строк » qwe » и » asd «). Приведём код подпрограмм (модуль «Пример6_ПроцедураФункция»), вызов которых используется в этом примере:
СТРУКТУРЫ — ТВОЯ ГЛАВНАЯ ОШИБКА
Sub proc1()
‘Вызов процедуры AcB с параметрами s, «qwe», «asd»
Call AсB(s, «qwe», «asd»)
End Sub
‘Объявление процедуры AсB с параметрами c$, a$, b$
Sub AсB(c$, a$, b$)
End Sub
‘Объявление функции AiB с параметрами a$, b$
Function AiB(a$, b$) As String
End Function
Sub proc2()
‘Вызов функции AiB с параметрами «qwe», «asd»
End Sub
При выполнении первой подпрограммы (proc1) в этом примере происходит вызов процедуры (AcB). При выполнении второй подпрограммы (proc2) происходит вызов функции (AiB).На рисунке 12.1 представлено окно сообщения с результатом выполнения процедуры слияния двух строк » qwe » и » asd «. Точно так же будет выглядеть окно с результатом вызова функции.
Рис. 12.1. Окно сообщения с результатом выполнения примера 6
Необходимость разработки больших программных систем привела к появлению модульного программирования. Это такой способ программирования, при котором вся программа (точнее, проект) разбивается на составные части, называемые модулями, причем каждый из них имеет свой контролируемый размер, четкое назначение и детально проработанный интерфейс с внешней средой. Единственная альтернатива модульности – монолитная программа, конечно же, может быть удобна только при решении достаточно простых задач.
Концепция модульного программирования является основой всех современных подходов к проектированию и реализации программных систем. В то же время суть ее проста и отражает широко известные научные и технические методы, заключающиеся в поиске и реализации некоторого базового набора элементов, комбинации которых дают решение всех задач из определенного круга.
С применением модульного программирования появляются возможности коллективной разработки программ как набора «независимых» частей, последовательного уменьшения сложности методом разбиения сложной задачи на более простые подзадачи и, наконец, возможности повторного использования созданного ранее кода, в том числе применение восходящего («снизу вверх») проектирования.
Если концепция структурного программирования предлагает некоторый универсальный алгоритмический базис, то модульное программирование состоит в разработке под конкретную задачу или круг задач (предметную область) собственного базиса в виде набора модулей, позволяющего наиболее эффективно по целому ряду критериев построить программный комплекс. Модули, входящие в базис, это целые программы (в отличие от «макрооператоров» структурного программирования – подпрограмм), решающие некоторые подзадачи и часто оформляемые в виде отдельных файлов, причём так называемые модули расширения, могут быть написаны на совершенно другом языке.
12.3 Рекурсивные алгоритмы *
Рекурсия – это одна из фундаментальных концепций в математике и программировании. Это одна из форм мышления, это мощное средство, позволяющее строить элегантные и выразительные алгоритмы. Объект называется рекурсивным, если он содержит сам себя или определен с помощью самого себя.
Если процедура р содержит явное обращение к самой себе, то она называется явно рекурсивной. Если процедура р содержит обращение к некоторой процедуре q, которая в свою очередь содержит прямое или косвенное обращение к р, то р называется косвенно рекурсивной.
Рекурсивная программа не может вызывать себя бесконечно, иначе она никогда не остановится, таким образом в программе (функции) должен присутствовать еще один важный элемент – так называемое терминальное условие, то есть условие при котором программа прекращает рекурсивный процесс.
Рекуррентность – это рекурсивное определение функции. Классический пример такого рода функций – факториал. Напомним, факториал нуля равен 1, а факториал натурального числа N определяется как произведение натуральных чисел от единицы до N, что выражается рекуррентной формулой: N!=N (N-1)!, для N>=1 и 0! = 1. То есть для определения факториала одного числа требуется знать или вычислить факториал другого, уменьшенного на единицу. А это, в свою очередь, может потребовать определения факториала ещё меньшего числа. И так далее, до единицы. Этому напрямую соответствует нижеследующая рекурсивная функция:
Function factorial(N As Integer) As Long
If N=0 Then factorial=1 Else factorial=N*factorial(N-1)
End Function
Многие алгоритмы можно легко реализовать с помощью рекурсивных программ, и многие разработчики алгоритмов предпочитают выражать алгоритмы рекурсивно. Но делать это нужно крайне осторожно. Например, вызов factorial(-1) приведет к бесконечному рекурсивному циклу (аварийная остановка, конечно, будет, связанная с переполнением стека или выходом значения аргумента за пределы диапазона). Поэтому перед вызовом данной функции нужно делать проверку условия неотрицательности аргумента.
Стоит также отметить, что не все языки допускают использование рекурсий. В таких случаях можно обойтись использованием обычных циклов. Например, ту же функцию факториал реализовать без использования рекурсии:
Function factorial(N As Integer) As Long
Источник: studopedia.ru
Утверждение структура программы должна отражать структуру решаемой задачи отражает идею
Тысячи правильных ответов на различные тесты
Тысячи проверенных ответов
Вопрос теста:
Утверждение – «структура программы должна отражать структуру решаемой задачи» – отражает идею
- алгоритмического программирования
- объектно-ориентированного программирования
- структурного программирования
- событийно-ориентированного программирования
- модульного программирования
1.3. Понятие о структурном программировании. Модульный принцип программирования. Принципы проектирования программ сверху вниз и снизу вверх. Подпрограммы
Основная идея структурного программирования состоит в том, что структура программы должна отражать структуру решаемой задачи, чтобы алгоритм был ясно виден из исходного текста программы. Следовательно, надо разбить программу на последовательность модулей, каждый из которых выполняет одно или несколько действий.
Требование к модулю – чтобы его выполнение начиналось с первой команды и заканчивалось последней. Модульность – это основная характеристика структурного программирования. А для этого надо иметь средства для создания программы не только с помощью трех основных алгоритмических конструкций, но и с помощью средств более точно отражающих конкретную структуру алгоритма.
С этой целью в программирование введено понятие вспомо- гательного алгоритма или подпрограммы – набора операторов, выполняющего заданные алгоритмические действия и не зависящего от других частей исходного кода. Программа разбивается на множество подпрограмм, каждая из которых выполняет одно из действий исходного кода. Комбинируя эти блоки, удается сформировать итоговый алгоритм уже не из операторов, а из законченных блоков. Обращаться к блокам надо по названиям ( именам подпрограмм), а название несет смысловую нагрузку. Например, в конкретном языке программирования запись Call Summa может означать означает обращение к подпро-
грамме с именем Summa , а Call – оператор вызова подпрограммы. При структурном подходе к составлению алгоритмов и программ используются три основных типа алгоритмов: условные, циклические алгоритмы и подпрограммы.
Структурированными считаются алгоритмы и программы, составленные с использованием только этих трех типов алгоритмов, при этом для записи циклов и условий должна использоваться ступенчатая за- пись . Например: Если a>b то Вывод «Первое число больше» Иначе Вывод «Второе число больше» Конец если Алгоритм считается неструктурированным, если нет ступенчатой записи или если при создании программы использован оператор безусловного перехода GoTo – переход к метке, т.е., структурное программирование – это программирование без GoTo . Основным принципом технологии структурного програм- мирования является нисходящее программирование — это про- граммирование с использованием подпрограмм, которое позволяет вести разработку приложения «сверху вниз», от более общих задач к более частным. При проектировании сверху вниз программа строится с помощью последовательных уточнений. Этот процесс начинается с самого общего утверждения об ее абстрактной функции, такого как «Оттранслировать программу в машинный код» или «Обработать команду пользователя» и продолжается путем последовательных шагов уточнения. На каждом шаге уровень абстракции получаемых элементов должен уменьшаться, каждая операция на нем разлагается на композицию одной или нескольких более простых операций. Такой подход обеспечивает хорошее соответствие проекта его начальной спецификации, но не всегда способствует его эффективному повторному использованию. Модули разрабатываются в ответ на отдельные возникающие подзадачи и, как пра-
вило, являются не более общими, чем к этому их вынуждает непосредственный контекст. Проектирование, имеющее в виду возможность повторного использования, подразумевает построение наиболее общих, по возможности, компонент, из которых затем составляются системы.
Этот процесс идет снизу вверх (сначала строятся объекты, лишь затем из них конструируется программа) и противоположен идее проектирования сверху вниз, требующей начинать с определения задачи и выводить ее решение путем последовательных уточнений. Вместо поиска самой верхней функции системы будут анализироваться типы входящих в нее объектов.
Проектирование системы будет продвигаться вперед путем последовательного улучшения понимания классов этих объектов. Это процесс построения снизу вверх устойчивых и расширяемых решений для отдельных частей задачи и сборки из них все более и более мощных блоков будет продолжаться до тех пор, пока не будет получен окончательный блок, доставляющий решение первоначальной задачи.
При этом можно надеяться, что оно не является единственно возможным: если правильно применять метод, то те же компоненты, собранные по-другому и, возможно, объединенные с другими, окажутся достаточно общими, чтобы получить в качестве побочного продукта также и решения каких-то новых задач. Таким образом, проектирование снизу вверх основано на объектах и приводит к концепциям объектно-ориентированного программирования (см. п. 1.4). Теперь рассмотрим подробнее механизм подпрограмм, являющийся основой как классического структурного, так и объ- ектно-ориентированного программирования. Кроме имени подпрограмма может иметь параметры , которые называются формальными . Если имя служит для того. чтобы уникальным образом идентифицировать подпрограмму, то формальные параметры, которые напоминают переменные математических функций, выполняют роль ее входных и выходных данных.
Формальные параметры должны быть выбраны таким образом, чтобы ими был исчерпан весь набор необходимых входных и выходных величин. Нередко один и тот же параметр может оказаться входным и выходным одновременно. Например, на вход такого алгоритма может быть подан массив для обработки, а на выходе он может предстать в измененном виде как выходной параметр. Рис. 11.
Подпрограмма Первый элемент блок-схемы на рис. 11, в отличие от ранее рассмотренных примеров, где этот блок имел наименование “Начало”, включает имя подпрограммы Warn и один формальный параметр с именем i . С помощью этого имени подпрограмма может быть вызвана из другой подпрограммы или главной программы. Из схемы видно, что если на вход подпрограммы Warn подать i=0 , то она в блоке 3 выдаст сообщение «Введите данные». При любом другом i будет выведено сообщение «Конец расчетов». Этим исчерпываются возможности подпрограммы Warn .
На рис. 12 дана схема головного алгоритма (первый блок имеет наименование «Начало»). Этот алгоритм в блоках 2 и 8 обращается к процедуре Warn . При этом фактические пара- метры — константы 0 и 1 – поочередно подставляются на место формального параметра i . Рис. 12. Головной алгоритм и вызов подпрограммы Обычно при обучении программированию различают подпрограммы двух видов: процедуры и функции . Процедуры оформляются как отдельные независимые части программного кода, просто выполняющие последовательность операторов. Например, процедура вычисления суммы двух чисел, обозна- ченных a и b, могла бы быть описана следующим образом: Процедура Summa (a,b) c = a + b
Вывод с Конец Summa Здесь Summa – это назначенное программистом имя под- программы-процедуры, а в скобках указаны формальные параметры a и b . Соответственно, обращение из главной программы к процедуре осуществляется по имени с перечнем в скобках фактических параметров, которые ей передаются, например, оператор Summa( x,y ) может означать вызов процедуры с передачей ей фактических параметров x и y , которые будут подставлены на место формальных параметров a и b соответственно, так что процедура найдет и напечатает значение x+y . Процедура всегда вызывается отдельным оператором. Функция , в отличие от процедуры, всегда имеет один выходной параметр, следовательно, если этот параметр – скалярный (не является массивом), функция может быть вызвана непо- средственно в процессе вычисления выражения и справа от зна- ка присваивания , например, выражение y:=max(sin(x),cos(x)) демонстрирует вызов трех функций – sin и cos для вычисления синуса и косинуса от величины x и затем функции max , которая найдет большее из этих двух значений.
Подпрограммы необходимы при составлении алгоритма решения сложной задачи, так как позволяют решать задачу «по частям» или коллективно. Кроме того, их применение уменьшает объем программы за счет неоднократного использования подпрограмм для выполнения повторяющихся расчетов. Приведем пример.
Пусть требуется составить на структурированном языке алгоритм вычисления периметра треугольника, если известны координаты его вершин (треугольник лежит на плоскости). Обозначим координаты вершин xA , yA , xB , yB , xC , yC и ввод их значений осуществим в главной программе. Пусть AB — расстояние между точками A и B , BC — между B и C , AC — между A и С , а Р – периметр. Периметр вычислим по известной форму-
Источник: studfile.net