Представление основных структур программирования

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

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

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

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

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

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

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

Арифметический цикл (цикл с параметром)

Требуется вычислить набор  значений функции f(x) для заданного набора значений аргумента х.

Формирование набора значений аргумента определяется одним из двух вариантов.

А. Заданы начальное значение аргумента xn, шаг его изменения dx и количество точек счета k; тогда набор значений аргумента формируется по правилу: x_i = xn + (i – 1)dx, где i = 1, 2, 3, …, k.

Б. Заданы начальное и  конечное значения аргумента xn и xk и шаг его изменения dx; набор значений аргумента формируется по тому же правилу, но предварительно требуется вычислить количество точек счета k:

, где int( ) – целое от ( ).

Данные задачи носят название задач табулирования, т. е. вычисления таблицы значений функции.

Пример решения задачи табулирования для вычисления набора значений функции y = sinx где  , с шагом dx приведен на рис. П.3.7.

Итерационный цикл

Определить минимальное  целое N, для которого выполняется условие N³ – 820N + 1 > 100.

Задача решается последовательным перебором значений N до достижения желаемого результата. Обозначив левую часть неравенства как S, получаем два условия: продолжение цикла S ≤ 100; выход из цикла S > 100.

Структурограммы решения  этой задачи с помощью циклов WHILE-DO и REPEAT-UNTIL приведены на рис. П.3.8, а и б соответственно.

Рис.  П.3.7. Структурограмма цикла с параметром

Рис. П.3.8. Структурограмма итерационного цикла: 
а – с предусловием, б – с постусловием

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

Требуется вычислить значение функции y = sinx для данного значения аргумента x с точностью e путем разложения функции в степенной ряд

В общем виде 

Соответствующая структурограмма  представлена на рис. П.3.9.

Рис. П.3.9. Структурограмма вычисления  
тригонометрической функции

Вложенный цикл

Требуется ввести в ЭВМ  элементы матрицы A, содержащей n строк и m столбцов. В структурограмме (рис. П.3.10) внутренний цикл организован по параметру j, а внешний – по i. Легко убедиться, что в данном примере ввод элементов матрицы производится по строкам.

Рис. П.3.10. Структурограмма 
вложенного цикла (ввод матрицы)

Суммируя сказанное, отметим, что программирование циклических  процессов разбивается на три  этапа:

·     вход в цикл, т. е. задание действий, которые обеспечили бы корректное значение условия до выполнения цикла;

·     тело цикла, содержащего повторяющуюся вычислительную часть и действия по изменению условия;

·     выход из цикла, т. е. задание критериев останова.

Особенно важно в операторах цикла WHILE-DO и REPEAT-UNTIL обращать внимание на включение в тело цикла действий, изменяющих условие. Если тело цикла  никак не влияет на условие, цикл может  оказаться бесконечным.

Подводя итог рассмотрению приемов программирования, отметим, что с помощью трех описанных  выше базовых структур СЛЕДОВАНИЕ, РАЗВЕТВЛЕНИЕ и ЦИКЛ реализуется  алгоритм любой сложности.

Для иллюстрации изобразим  структурограмму (рис. П.3.11) вычисления функции

для схемы алгоритма (рис. П.2.3).

Как видно из примера (рис. П.3.11), полученный алгоритм хорошо структурирован, легко читаем и не требует для своего изображения больших графических навыков.

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

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

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

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

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

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

Операторы языка программирования являются минимальными компонентами, из которых строятся модули. Разнообразие операторов в языках программирования даже высокого уровня сравнительно невелико и составляет величину порядка 50–100 типов. Однако с повышением уровня языка  программирования возрастает функциональная сложность операторов, т. е. число машинных команд ЭВМ, требуемых для его выполнения.

Функциональные или программные  модули решают небольшую функциональную задачу и реализуются, как правило, 10–100 операторами языка программирования высокого уровня.

Упомянутые выше приемы функциональной композиции (объединения) и декомпозиции (разбиения) задач относятся к  области технологии конструирования  программ и определяют структурный  подход к разработке алгоритмов и  программ.

2. ПРЕДСТАВЛЕНИЕ ОСНОВНЫХ  СТРУКТУР ПРОГРАММИРОВАНИЯ: ИТЕРАЦИЯ, ВЕТВЛЕНИЕ И ПРОЦЕДУРЫ В РАЗЛИЧНЫХ  ЯЗЫКАХ ПРОГРАММИРОВАНИЯ.

2.1. Итерация

Итерация-это организация обработки данных, при кот. действия повторяются многократно, не приводя при этом к вызовам самих себя.

Когда действие необходимо повторить большое кол-во раз, в программировании useся циклы. Напр-р, нужно вывести 100 раз на экран  текст «Hello, World!». Вместо 100-кратного повторения 1и той же команды вывода текста часто создается цикл, кот прокручивается 100 раз, и 100 раз выполняет то, что написано в теле цикла. 1 шаг цикла наз-ся итерацией. Еще 1 пример: Факториал(!) — N! = 1 х 2 х 3 x … x (N-1) x N.

Инструкция (цикл) while useся в том случае, если некотор послед-ть действий надо выполнить  неск-ко раз, причем необходимое число  повторений во время разработки проги  неизвестно и м.б. определено только во время работы проги.

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

Инструкция repeat, как и инструкция while, useся в  проге в том случае, если необходимо выполнить повторные вычисления, но число повторений во время разработки проги неизвестно и м.б. определено только во время работы проги, т. е. определяется ходом вычислений.

2.2.Ветвление.

На практике редко встречаются задачи, алгоритм реш-я кот явл-ся линейным. Часто  оказывается, что алгоритм реш-я  даже элементарной задачи не явл-ся линейным.

Выбор в  точке разветвления алгоритма очередного шага проги м.б. реализован при помощи инструкций if и case. Инструкция if позволяет  выбрать 1 из 2 возможных вариантов, инструкция case — 1 из неск-ких.

 

 

2.3. Оператор ветвления (условная  инструкция, условный оператор)

Оператор  ветвления (условная инструкция, условный оператор) — оператор, конструкция языка программирования, обеспечивающая выполнение определённой команды (набора команд) только при условии истинности некоторого логического выражения, либо выполнение одной из нескольких команд (наборов команд) в зависимости от значения некоторого выражения. Оператор ветвления применяется в случаях, когда выполнение или невыполнение некоторого набора команд должно зависеть от выполнения или невыполнения некоторого условия. Ветвление — одна из трёх (наряду с последовательным исполнением команд и циклом) базовых конструкций структурного программирования. Существует две основные формы условной инструкции, встречающиеся в реальных языках программирования: условный оператор (оператор if) и оператор многозначного выбора (переключатель, case, switch).

Условный  оператор с одной ветвью. При выполнении такого оператора вычисляется условие, и если оно истинно, то выполняются  команды, заключенные в фигурные скобки, в противном случае выполнение программы продолжается со следующей  за условным оператором команды. В языках низкого уровня (ассемблерах) это — единственная доступная форма условного оператора. В некоторых языках для условного оператора с одной ветвью используется специальное ключевое слово (обычно это when). if (<условие>){<операторы>}.

Условный  оператор с двумя ветвями. Здесь  при истинности условия выполняются  команды1 при ложности — команды2. При необходимости проверить последовательно несколько условий возможно каскадирование условных операторов. if (<условие>){<операторы>}else{<операторы>}.

Условный  оператор с несколькими условиями.

if (условие1){команды1;}

else if (условие2){команды2;}

...

else {командыN};

 

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

switch (i)

{

case 0:

case 1: // последовательность операторов

break;

case 2: // последовательность операторов

break;

default:

}

Здесь i — выражение-селектор, которое обязано иметь приводимый к целому тип, каждая ветвь исполнения начинаются с ключевого слова case, за ним следует значение выражения, при котором должна выполняться данная ветвь. Интересной особенностью языка Си является то, что в нём переключатель трактуется именно как команда перехода по вычисляемой метке, а роль меток играют заголовки ветвей (case значение :). Чтобы после завершения кода ветви произошёл выход из оператора переключателя, используется специальная команда break.

 

 

2.4.Процедура

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

Процедуры разделяются на стандартные и  пользовательские, внеш и внутр отн-но проги.

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

Внеш процедура  хранится независимо от проги, в кот  имеется обращение к этой процедуре, а внутр- входит в состав проги.

2.5. Процедуры и функции –  методы класса.

Весьма популярным при построении программных систем был метод функциональной декомпозиции "сверху вниз", и сегодня еще  играющий важную роль. Но с появлением ООП архитектурная роль функциональных модулей отошла на второй план. Для  ООП-языков, к которым относится  и язык C#, в роли архитектурного модуля выступает класс. Программная система  строится из модулей, роль которых играют классы, но каждый из этих модулей имеют  содержательную начинку, задавая некоторую  абстракцию данных.

Процедуры и функции связываются теперь с классом, они обеспечивают функциональность данных класса и называются методами класса. Главную роль в программной  системе играют данные, а функции  лишь служат данным. Напомню здесь, что в C# процедуры и функции  существуют только как методы некоторого класса, они не существуют вне класса. Функция отличается от процедуры  двумя особенностями:

• всегда вычисляет некоторое значение, возвращаемое в качестве результата функции;
• вызывается в выражениях.

Процедура C# имеет свои особенности:

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

Хорошо известно, что одновременное существование  в языке процедур и функций  в каком-то смысле избыточно. Добавив  еще один выходной аргумент, любую  функцию можно записать в виде процедуры. Справедливо и обратное. Если допускать функции с побочным эффектом, то любую процедуру можно  записать в виде функции. В языке  С - дедушке C# - так и сделали, оставив  только функции. Однако значительно  удобнее иметь обе формы реализации метода: и процедуры, и функции. Обычно метод предпочитают реализовать  в виде функции тогда, когда он имеет один выходной аргумент, рассматриваемый  как результат вычисления значения функции. Возможность вызова функций  в выражениях также влияет на выбор  в пользу реализации метода в виде функции. В других случаях метод  реализуют в виде процедуры.