1. Любая программа представляет собой иерархическую структуру, построенную из трёх типов базовых конструкций.
2. Повторяющиеся фрагменты программы могут оформляться в виде подпрограмм.
3. Разработка программы ведётся пошагово, методом «сверху вниз».
Рассмотрим эти положения более подробно.
Работа Бома и Джакопини показала, что все программы могут быть написаны с использованием всего трёх управляющих структур, названных структура следования, структура выбора и структура повторения.
Любая программа представляет собой иерархическую структуру, построенную из трёх типов базовых конструкций:
· структура следования — однократное выполнение операций в том порядке, в котором они записаны в тексте программы;
· структура выбора — однократное выполнение одной из двух или более операций, в зависимости от выполнения некоторого заданного условия;
· структура повторения — многократное исполнение одной и той же операции до тех пор, пока выполняется некоторое заданное условие.
Выжить в Дубае: 1 выпуск
Структура следования встроена в C++. Пока не указано иное, компьютер выполняет операторы C++ один за другим в той последовательности, в которой они записаны.
C++ обеспечивает три типа структур выбора альтернатив:
· Структура выбора if выполняет некоторое действие, если проверяемое условие истинно, или пропускает его, если условие ложно. Она также называется структура с единственным выбором, поскольку она выбирает или игнорирует единственное действие.
· Структура выбора if/else выполняет одно действие, если условие истинно, и выполняет другое действие, если оно ложно. Она также называется структура с двойным выбором, поскольку осуществляет выбор между двумя различными действиями.
· Структура выбора switch выполняет одно из множества действий в зависимости от значения проверяемого выражения. Она также называется структура с множественным выбором, поскольку осуществляет выбор среди множества различных действий.
Посмотреть, как правильно нарисовать switch.
C++ обеспечивает три типа структур повторения, называемых:
· Структура повторения while выполняет действие, пока проверяемое условие истинно.
· Структура повторения do/while похожа на структуру повторения while. Сперва выполняется действие, а затем проверяется условие. Действия выполняется до тех пор, пока условие истинно.
· Структура повторения for позволяет выполнить заданное действие для всех значений параметра.
И это всё. C++ имеет только семь управляющих структур: следование, три типа выбора и три типа повторения. Любая программа на C++ формируется из такого количества комбинаций каждого типа управляющих структур, которое нужно для осуществления соответствующего алгоритма.
Как и структура следования, каждая управляющая структура на схеме содержит два символа малых окружностей: один – для точки входа и один – для точки выхода. Подобные управляющие структуры с одним входом и одним выходом облегчают построение программы – управляющие структуры связываются друг с другом соединением токи выхода одной из них с точкой входа другой. Это называется последовательным расположением управляющих структур.
Учимся программировать. Конструкции программы.
В дальнейшем мы выясним, что помимо рассмотренного есть только один путь соединения управляющих структур – их вложение. Таким образом, любая программа на C++, которую вы будете создавать, может быть построена всего на семи типах управляющих структур, соединённых всего двумя способами.
Источник: studopedia.su
1. Базовые конструкции структурного программирования
В теории программирования доказано, что программу для решения задачи любой сложности можно составить только из трех структур, называемых следованием, ветвлением и циклом. Этот результат установлен Боймом и Якопини в 1966 году путем доказательства того, что любую программу можно преобразовать в эквивалентную, состоящую только из этих структур и их комбинаций. Следование, ветвление и цикл называют базовыми конструкциями структурного программирования.
Следованием называется конструкция, представляющая собой последовательное выполнение двух или более операторов (простых или составных)(рис.1.1).
Ветвление задает выполнение либо одного, либо другого оператора в зависимости от выполнения какого-либо условия (рис1.2).
Если условие выполняется, то а = -а, иначе а = b.
Цикл задает многократное выполнение оператора 1, пока выполняется условие (рис.1.3).
Особенностью базовых конструкций является то, что любая из них имеет только один вход и один выход, поэтому конструкции могут вкладываться друг в друга произвольным образом, например, цикл может содержать следование из двух ветвлений, каждое из которых включает вложенные циклы.
Целью использования базовых конструкций является получение программы простой структуры. Такую программу легко читать, отлаживать и при необходимости вносить в нее изменения.
В большинстве языков высокого уровня существует несколько реализаций базовых конструкций. В C++ есть три вида циклов и два вида ветвлений (на два и на произвольное количество направлений). Они введены для удобства программирования, и в каждом случае надо выбирать наиболее подходящие средства.
Оператор «выражение»
Любое выражение, завершающееся точкой с запятой, рассматривается как оператор, выполнение которого заключается в вычислении выражения. Частным случаем выражения является пустой оператор;(он используется, когда по синтаксису оператор требуется, а по смыслу – нет). Примеры:
i++; // выполняется операция инкремента
а* = b + с; // выполняется умножение с присваиванием
fun( i, k); // выполняется вызов функции
Источник: h-l-l.ru
Базовые алгоритмические конструкции
Различают три базовые алгоритмические структуры: следование, ветвление, повторение.
Структура следованиесостоит из двух команд с указанной очередностью их выполнения и имеет вид:
Такую структуру ещё называют линейным вычислительным процессом, в котором этапы вычислений выполняются в линейной последовательности и каждый этап выполняется только один раз. На схеме блоки размещаются сверху вниз в порядке их выполнения. Для таких процессов характерно, что направление вычислений не зависит от исходных данных или промежуточных результатов. В виде блок-схемы линейный вычислительный процесс можно представить следующим образом:
Структура типа ветвление в полной форме состоит из некоторого условия, проверяемого на истинность при выполнении структуры, команды, выполняемой при выполнении проверяемого условия, и команды, выполняемой при невыполнении условия.
В виде блок-схемы разветвляющийся вычислительный процесс можно представить следующим образом. Разветвляющийся вычислительный процесс– это процесс, который реализуется по одному из нескольких заранее предусмотренных направлений в зависимости от выполнения некоторого условия. Каждое отдельное направление вычислений называется ветвью вычислений. В каждом конкретном случае процесс реализуется только по одной ветви, а выполнение остальных исключается.
Структура имеет вид
Структура типа ветвления в неполной форме – частный случай ветвления в полной форме, в которой, при невыполнении условия, управление просто передается следующей команде и больше никаких действий команда ветвления не осуществляет.
Структура повторения(цикл) служит для компактной записи одного и того же набора команд, повторяемых для различных значений параметров команд.
Цикл с проверкой условия до исполнения действия (с предусловием). Действие может не исполниться ни одного раза.
Цикл с проверкой условия после исполнения действия (с постусловием). Действие обязательно исполнится хотя бы один раз.
Телом цикла называется последовательность повторяемых команд («действие»), которая может быть и пустой (редко встречаемый случай).
Этот цикл выполняется по правилу: для начального значения переменной выполняются команды тела цикла по порядку и затем проверяется, превысило ли текущее значение переменной ее заданного конечного значения; если превысило – цикл заканчивается, иначе значение переменной увеличивается на единицу и снова повторяется тело цикла и т.д.
Циклический вычислительный процесс — это процесс, в котором вычисления выполняются многократно по одним и тем же математическим формулам, но при разных значениях исходных данных. Этот многократно повторяющийся участок вычислительного процесса называется циклом.
Для организации цикла необходимо предусмотреть:
задание начального значения параметра цикла — переменной, которая будет изменяться при повторении цикла;
изменение значения этой переменной перед каждым новым повторением цикла;
проверку условия окончания повторений по значению параметра и переход к началу цикла, если повторения не закончены.
Язык программирования — это система обозначений, служащая для точного описания программ или алгоритмов для ЭВМ. Языки программирования являются искусственными языками. От естественных языков они отличаются ограниченным числом “слов” и очень строгими правилами записи команд (операторов). Поэтому при применении их по назначению они не допускают свободного толкования выражений, характерного для естественного языка.
Можно сформулировать ряд требований к языкам программирования и классифицировать языки по их особенностям.
Основные требования, предъявляемые к языкам программирования:
наглядность- использование в языке по возможности уже существующих символов, хорошо известных и понятных как программистам, так и пользователям ЭВМ;
единство — использование одних и тех же символов для обозначения одних и тех же или родственных понятий в разных частях алгоритма. Количество этих символов должно быть по возможности минимальным;
гибкость — возможность относительно удобного, несложного описания распространенных приемов математических вычислений с помощью имеющегося в языке ограниченного набора изобразительных средств;
модульность — возможность описания сложных алгоритмов в виде совокупности простых модулей, которые могут быть составлены отдельно и использованы в различных сложных алгоритмах;
однозначность — недвусмысленность записи любого алгоритма. Отсутствие ее могло бы привести к неправильным ответам при решении задач.
В настоящее время в мире существует несколько сотен реально используемых языков программирования. Для каждого есть своя область применения.
Любой алгоритм, как мы знаем, есть последовательность предписаний, выполнив которые можно за конечное число шагов перейти от исходных данных к результату. В зависимости от степени детализации предписаний обычно определяется уровень языка программирования — чем меньше детализация, тем выше уровень языка.
По этому критерию можно выделить следующие уровни языков программирования:
машинно-независимые (языки высокого уровня).
Машинные языки и машинно-ориентированные языки— это языки низкого уровня, требующие указания мелких деталей процесса обработки данных. Языки же высокого уровня имитируют естественные языки, используя некоторые слова разговорного языка и общепринятые математические символы. Эти языки более удобны для человека.
Разные типы процессоров имеют разные наборы команд. Если язык программирования ориентирован на конкретный тип процессора и учитывает его особенности, то он называется языком программирования низкого уровня. В данном случае «низкий уровень» не значит «плохой». Имеется в виду, что операторы языка близки к машинному коду и ориентированы на конкретные команды процессора.
При программировании на машинном языке программист может держать под своим контролем каждую команду и каждую ячейку памяти, использовать все возможности имеющихся машинных операций. Но процесс написания программы на машинном языке очень трудоемкий и утомительный. Программа получается громоздкой, труднообозримой, ее трудно отлаживать, изменять и развивать.
Поэтому в случае, когда нужно иметь эффективную программу, в максимальной степени учитывающую специфику конкретного компьютера, вместо машинных языков используют близкие к ним машинно-ориентированные языки (ассемблеры).
Язык ассемблера — это машинно-зависимый язык низкого уровня, в котором короткие мнемонические имена соответствуют отдельным машинным командам. Используется для представления в удобочитаемой форме программ, записанных в машинном коде.
Язык ассемблера позволяет программисту пользоваться текстовыми мнемоническими (то есть легко запоминаемыми человеком) кодами, по своему усмотрению присваивать символические имена регистрам компьютера и памяти, а также задавать удобные для себя способы адресации. Кроме того, он позволяет использовать различные системы счисления (например, десятичную или шестнадцатеричную) для представления числовых констант, использовать в программе комментарии и др.
С помощью языков низкого уровня создаются очень эффективные и компактные программы, так как разработчик получает доступ ко всем возможностям процессора. С другой стороны, при этом требуется очень хорошо понимать устройство компьютера, затрудняется отладка больших приложений, а окончательная программа не может быть перенесена на компьютер с другим типом процессора. Подобные языки обычно применяют для написания небольших системных приложений, драйверов устройств, модулей стыковки с нестандартным оборудованием, когда важнейшими требованиями становятся компактность, быстродействие и возможность прямого доступа к аппаратным ресурсам. В некоторых областях, например в машинной графике, на языке ассемблера пишутся библиотеки, эффективно реализующие алгоритмы обработки изображений, требующие интенсивных вычислений.
Таким образом, программы, написанные на языке ассемблера, требуют значительно меньшего объема памяти и времени выполнения. Знание программистом языка ассемблера и машинного кода дает ему понимание архитектуры машины. Несмотря на то, что большинство специалистов в области программного обеспечения разрабатывают программы на языках высокого уровня, таких, как Object Pascal или C, наиболее мощное и эффективное программное обеспечение полностью или частично написано на языке ассемблера.
Языки высокого уровня были разработаны для того, чтобы освободить программиста от учета технических особенностей конкретных компьютеров, их архитектуры. Уровень языка характеризуется степенью его близости к естественному, человеческому языку. Машинный язык не похож на человеческий, он крайне беден в своих изобразительных средствах.
Средства записи программ на языках высокого уровня более выразительны и привычны для человека. Например, алгоритм вычисления по сложной формуле не разбивается на отдельные операции, а записывается компактно в виде одного выражения с использованием привычной математической символики. Составить свою или понять чужую программу на таком языке гораздо проще.
Важным преимуществом языков высокого уровня является их универсальность, независимость от ЭВМ. Программа, написанная на таком языке, может выполняться на разных машинах. Составителю программы не нужно знать систему команд ЭВМ, на которой он предполагает проводить вычисления. При переходе на другую ЭВМ программа не требует переделки.
Такие языки – не только средство общения человека с машиной, но и людей между собой. Программа, написанная на языке высокого уровня, легко может быть понята любым специалистом, который знает язык и характер задачи.
Таким образом, можно сформулировать основные преимущества языков высокого уровня перед машинными:
алфавит языка высокого уровня значительно шире алфавита машинного языка, что существенно повышает наглядность текста программы;
набор операций, допустимых для использования, не зависит от набора машинных операций, а выбирается из соображений удобства формулирования алгоритмов решения задач определенного класса;
формат предложений достаточно гибок и удобен для использования, что позволяет с помощью одного предложения задать достаточно содержательный этап обработки данных;
требуемые операции задаются с помощью общепринятых математических обозначений;
данным в языках высокого уровня присваиваются индивидуальные имена, выбираемые программистом;
в языке может быть предусмотрен значительно более широкий набор типов данных по сравнению с набором машинных типов данных.
Таким образом, языки высокого уровня в значительной мере являются машинно-независимыми. Они облегчают работу программиста и повышают надежность создаваемых программ.
Основные компоненты алгоритмического языка:
Алфавит— это фиксированный для данного языка наборосновных символов, т.е. букв алфавита, из которых должен состоять любой текст на этом языке — никакие другие символы в тексте не допускаются.
Синтаксис — это правила построения фраз, позволяющие определить, правильно или неправильно написана та или иная фраза. Точнее говоря, синтаксис языка представляет собой набор правил, устанавливающих, какие комбинации символов являются осмысленными предложениями на этом языке.
Семантика определяет смысловое значение предложений языка. Являясь системой правил истолкования отдельных языковых конструкций,семантика устанавливает, какие последовательности действий описываются теми или иными фразами языка и, в конечном итоге, какой алгоритм определен данным текстом на алгоритмическом языке.
Языки высокого уровня делятся на:
Процедурные (алгоритмические) языки предназначены для однозначного описания алгоритмов. При решении задачи процедурные языки требуют в той или иной форме явно записать процедуру ее решения.
Первым шагом в развитии процедурных языков программирования было появление проблемно-ориентированных языков. В этом названии нашел отражение тот факт, что при их разработке идут не от «машины», а «от задачи»: в языке стремятся максимально полно учесть специфику класса задач, для решения которых его предполагается использовать. Например, для многих научно-технических задач характерны большие расчеты по сложным формулам, поэтому в ориентированных на такие задачи языках вводят удобные средства их записи. Использование понятий, терминов, символов, привычных для специалистов соответствующей области знаний, облегчает им изучение языка, упрощает процесс составления и отладки программы.
Разнообразие классов задач привело к тому, что на сегодняшний день разработано несколько сотен алгоритмических языков. Правда, широкое распространение и международное признание получили лишь 10-15 языков. Среди них в первую очередь следует отметить: ФОРТРАНи АЛГОЛ-языки, предназначенные для решения научно-технических задач, КОБОЛ – для решения экономических задач, БЕЙСИК – для решения небольших вычислительных задач в диалоговом режиме.
В принципе каждый из этих языков можно использовать для решения задач не своего класса. Однако, как правило, применение оказывается не удобным.
В то же время в середине 60-х годов начали разрабатывать алгоритмические языки широкой ориентации – универсальные языки. Обычно они строились по принципу объединения возможностей узко-ориентированных языков. Среди них наиболее известны PL/1, PASCAL, C, C+ , Модула, АДА. Однако, как любое универсальное средство, такие широко-ориентированные языки во многих конкретных случаях оказываются менее эффективными.
Логические языки (Prolog, Lisp, Mercury, KLOи др.) ориентированы не на запись алгоритма решения задачи, а на систематическое и формализованное описание задачи с тем, чтобы решение следовало из составленного описания. В этих языках указывается что дано и что требуется получить. При этом поиск решения задачи возлагается непосредственно на ЭВМ.
Объектно-ориентированные языки (Object Pascal, C++, Java, Objective Caml. и др.).Руководящая идея объектно-ориентированных языковзаключается в стремлении связать данные с обрабатывающими эти данные процедурами в единое целое — объект. Характерной чертой объектов является инкапсуляция (объединение) данных и алгоритмов их обработки, в результате чего и данные, и процедуры во многом теряют самостоятельное значение. Объекты — это скрытые модули, чей внешний интерфейс состоит из набора операций. Фактически объектно-ориентированное программирование можно рассматривать как модульное программирование нового уровня, когда вместо во многом случайного, механического объединения процедур и данных акцент делается на их смысловую связь.
Программа на объектно-ориентированном языке, решая некоторую задачу, по сути описывает часть мира, относящуюся к этой задаче. Описание действительности в форме системы взаимодействующих объектов естественнее, чем в форме взаимодействующих процедур.
В качестве языка описания алгоритмов воспользуемся далее языком программирования Паскаль, так как он наиболее подходит для целей обучения и часто (обоснованно) используется в обучении.
На алгоритмическом языке Паскаль любой алгоритм простой (не модульной, не составной) структуры имеет следующий стандартный вид:
Источник: csaa.ru