Базовые структуры программирования

 

Алгоритм любой сложности может быть представлен комбинацией трех базовых структур:

• следование;

• ветвление (альтернатива, если–то–иначе);

• цикл (повторение).

Особенностью этих структур является наличие у них одного входа и одного выхода.

 

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

 

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

Возможные пути выполнения алгоритма помечают соответствующими метками: истина/ложь, да/нет, 1/0 и т.д.

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

 

Рисунок 11 Рисунок 12

 

Алгоритм, в состав которого входит базовая структура ветвление, называется разветвляющимся.

Если в алгоритме имеется три и более направления ветвления, то его можно представить в виде совокупности нескольких базовых структур если–то–иначе (Рисунок 11). Такую разновидность структуры разветвление часто называют множественный выбор.

 

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

Различают две разновидности этой структуры: цикл–пока и цикл–до.

Группа операторов, повторяющаяся в цикле, называется телом цикла. Основное отличие структуры цикл–пока (Рисунок 13) от структуры цикл–до (Рисунок 14) заключается в том, что в первой структуре операторы тела цикла в зависимости от условия могут не выполняться совсем, тогда как в структуре цикл–до тело цикла будет выполняться хотя бы один раз. Легко заметить, что в структуре цикл–пока проверка выполнения условия осуществляется перед выполнением операторов тела цикла, а в структуре цикл–до осуществляется после прохождения тела цикла.

Рисунок 13 Рисунок 14

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

Алгоритмы, имеющие в своем составе базовую структуру «цикл», называются циклическими.

Рассмотренные выше базовые структуры рекомендуется применять для соблюдения структурного подхода к разработке алгоритмов.

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

 

ЯЗЫКИ ПРОГРАММИРОВАНИЯ

 

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

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

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

Семантика – это значения языковых единиц (слов, словосочетаний, предложений).

Составление программ для ЭВМ первого поколения велось исключительно на машинном языке, который представляет собой свод правил кодирования действий ЭВМ с помощью чисел. Для всех цифровых ЭВМ «понятна» только двоичная система счисления (СС), которая для сокращения записи часто заменяется восьмеричной или шестнадцатеричной СС. Восьмеричная и шестнадцатеричная СС используются лишь для облегчения работы программистов. Для технической реализации ЭВМ нужна только двоичная СС.

Более высоким уровнем, по сравнению с машинными языками, являются машинно-ориентированные языки символического кодирования. Основной принцип создания языков символического кодирования состоит в замене машинных кодов на их буквенные обозначения, а также в автоматизации процесса распределения памяти и диагностики ошибок. Такой машинно-ориентированный язык получил название языка Ассемблера.

ЭВМ «понимает» только машинный язык, только команды, операнды и адреса, записанные с помощью двоичных чисел. Поэтому для преобразования программы, написанной на языке Ассемблера, в машинные коды необходим «переводчик».

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

Недостатком машинно-ориентированных языков является невозможность выполнения программы, составленной для процессора одного типа, на ЭВМ, которая построена на процессоре другого типа. Другими словами, вид программы зависит от типа машины.

На следующем уровне развития языков находятся процедурно-ориентированные языки. В отличие от машинно-ориентированных языков, синтаксис и семантика этих языков не зависят от состава имеющихся команд конкретной ЭВМ (конкретного процессора). Привязку составленной программы к конкретному типу ЭВМ осуществляет транслятор (программа-переводчик).

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

Процесс перевода программы и процесс ее исполнения могут происходить двумя способами.

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

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

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

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

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

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