ftd

4.3. СПОСОБЫ ЗАПИСЕЙ АЛГОРИТМОВ

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

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

Алгоритм можно записывать разными способами:

• с помощью рисунка, (например, процесс подключения монитора),

Рис. 4.2. Пример записи алгоритма с помощью рисунка

• построчно, каждая команда - с новой строки (последовательность проявления фотопленки, последовательность склеивания поверхностей на тюбике с клеем и т.д.) (рис. 4.3).

Рис.4.3. Пример построчной записи алгоритма

• в блок-схеме, каждая команда в отдельной рамочке, блоки соединяются стрелками (рис.4.4).

Вход

Выполнить А

Выполнить В

Выход

Рис. 4.4. Блок-схема записи алгоритма

4.4. ОСНОВНЫЕ АЛГОРИТМИЧЕСКИЕ КОНСТРУКЦИИ. Различают несколько алгоритмических конструкций.

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

Характерная форма для линейного алгоритма - последовательное выполнение команд (рис. 4.5а).

Конец

На самом деле нам постоянно приходится принимать решения в зависимости

от создавшейся ситуации. Если идет дождь, мы берем зонт. Если жарко, мы идем купаться.

Разумеется, встречаются и более сложные положения, когда надо сделать выбор. Появляется несколько направлений для продолжений. Алгоритм как бы раздваивается, разветвляется. В этом случае говорят, что алгоритм содержит ветвление (рис.4.5б – ответвление, рис.4.5в – раздвоение).

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

Варианты (направления вычислений), по которым может реализоваться вычислительный процесс, называют ветвями.

Выбор ветви зависит от результатов проверки некоторого условия. Если условие выполняется, то выбирается одна ветвь, если не выполняется, то другая ветвь.

В конце ветви должен быть специальный указатель, показывающий последнее действие. Можно, например, употребить слова "Конец ветвления".

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

гайку, пока не завернешь до отказа и т.д.). Для этого нужна новая форма организации действий – цикл.

Цикл - многократно повторяющийся участок вычислительного процесса.

Рис.4.6. Пример записи разветвляющегося алгоритма

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

В цикле всегда имеется четыре действия:

•подготовка – задание начального значения параметру цикла,

•основные действия (тело цикла) – реализация необходимых вычислений,

•подготовка к следующему циклу (модификация) – изменение параметра цикла,

•проверка условия – проверка условия окончания цикла.

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

Основные Нет действия

Проверка

Модификация

Да

Рис. 4.7. Блок-схема циклического алгоритма

•с послепроверкой, при этом программа выполняется до тех пор, пока не будет удовлетворено условие выхода из цикла,

•с предпроверкой – условие проверяется сразу же после подготовки. Основное различие обеих форм заключается в том, что в первом случае

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

Способ организации цикла зависит от условия задачи. Иногда указывается количество повторений цикла. Это так называемые циклы со счетчиками (или арифметические алгоритмы).

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

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

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

ВОПРОСЫ ДЛЯ САМОПРОВЕРКИ

1.Что такое алгоритм, от какого слова произошло это понятие?

2.Назовите основные алгоритмические конструкции.

3.Назовите особенности линейного алгоритма.

4.Назовите особенности разветвляющегося алгоритма.

5.Назовите особенности циклического алгоритма.

6.Какой алгоритм называют вспомогательным?

7.Что такое алгоритмизация?

8.Что такое программирование?

Глоссарий

Алгоритм – система точно сформулированных правил, определяющая процесс

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

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

Алгоритмизация – это процесс создания алгоритма решения задачи.

Линейные алгоритмы, в которых все действия совершаются одно за другим,

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

решения задачи.

Программирование – теоретическая и практическая деятельность, связанная с

созданием программы.

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

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

возможных вариантов.

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

многократным выполнением одних и тех же операций.

ПОСЛЕ ИЗУЧЕНИЯ ГЛАВЫ ВЫ ДОЛЖНЫ ЗНАТЬ:

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

Языки программирования – это формальные языки, специально созданные для общения человека с компьютером.

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

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

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

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

При описании языка и его применении используют понятия языка.

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

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

Языки программирования служат различным целям, и их выбор определяется удобностью пользователя, пригодностью для данного компьютера и данной задачи. А задачи для компьютера бывают самые разнообразные: вычислительные, экономические, графические, экспертные и т.д. Такая разнотипность решаемых задач и определяет многообразие языков программирования.

Например, Бейсик широко употребляется при написании простых программ, Фортран – классический язык для решения математических и инженерных задач, Кобол ориентирован на деловые задачи, ЛОГО для детей, которые решают задачи управления черепашкой, Пролог – язык программирования для создания систем искусственного интеллекта, Паскаль (развитие идеи Алгол) – учебный для обучения программированию в школах и ВУЗах, АДА – прямой наследник Паскаля – предназначен для создания больших программных систем, Си – сочетает в себе черты языка программирования высокого уровня и машинно-ориентированного языка, допуская программиста ко всем машинным ресурсам, чего не обеспечивает Бейсик и Паскаль.

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

Языки программирования высокого уровня существенно отличаются от машинно-ориентированных (низкого уровня) языков.

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

Во-вторых, каждая ЭВМ имеет неограниченный набор машинных операций, ориентированных на структуру процесса. Как правило, этот набор состоит из сравнительно небольшого числа простейших операций, типа: переслать число в ячейку; считать число из ячейки; увеличить содержимое ячейки на +1 и т.п. Команда на машинном языке содержит очень ограниченный объем информации, поэтому она обычно определяет простейший обмен содержимого ячеек памяти, элементарные арифметические и логические операции. Команда содержит код и адреса ячеек, с содержимым которой выполняется закодированное действие.

Языки программирования высокого уровня имеют следующие достоинства:

•алфавит языка значительно шире машинного, что делает его гораздо более выразительным и существенно повышает наглядность и понятность текста,

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

•конструкции команд (операторов) отражают содержательные виды обработки данных и задаются в удобном для человека виде,

•используется аппарат переменных и действия с ними,

•поддерживается широкий набор типов данных.

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

5.2. МЕТАЯЗЫКИ ОПИСАНИЯ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ

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

Для строгого и точного описания синтаксиса языка программирования, как правило, используют специальные метаязыки (языки описания других языков). Наиболее распространенными метаязыками являются металингвистические формулы Бэкуса – Наура (язык БНФ) и синтаксические диаграммы Вирта.

Язык БНФ (называемый также языком нормальных форм) представляет компактную форму в виде некоторых формул, похожих на математические. Для каждого понятия языка существует единственная метаформула (нормальная форма). Она состоит из левой и правой частей. В левой части указывается определяемое понятие, а в правой – задается множество допустимых конструкций языка, которые объединяются в это понятие.

В формуле используют специальные мета символы в виде угловых скобок, в которых заключено определяемое понятие (в левой части) или ранее определенное понятие (в ее правой части), а разделение левой и правой частей указывается метасимволом «::=», смысл которого эквивалентен словам «по определению есть».

Например, метаформулы

<переменная>::=А|В <выражение>::=<переменная>|<переменная>+<переменная>|<переменная>–<переменная>

означают, что в том (сугубо модельном) языке, на который эта метаформула распространяется, под термином <переменная> понимается любая из букв А

или В, а под термином <выражение> – любая из следующих десяти записей: А; В; А+А; А+В; В+А; В+В; А–А; А–В; В–А; В–В. Знак | следует читать «или».

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

Например, пусть необходимо ввести понятие <двоичный код >, под которым понимается любая непустая последовательность цифр 0 и 1. Тогда простое и компактное рекурсивное определение с помощью метаформул выглядит так:

<двоичная цифра>::=0|1 <двоичный код>::=<двоичная цифра>|<двоичный код><двоичная цифра>

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

<двоичный код>::=<двоичная цифра><двоичная цифра>

И еще, для полноты множества синтаксических конструкций, определим конструкцию <пусто>:

<пусто>::= .

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

Синтаксическая диаграмма является графическим представлением значения метапеременной метаязыка. Диаграмма состоит из основных символов или понятий языка.

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

<переменная>::=

А

В

эквивалент метаформуле <переменная>::= А|В Металингвистические формулы в некотором виде заложены в трансляторы.

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

Транслятором называют программу, производящую трансляцию (от лат. translatio – перенесение) - процесс преобразования с одного языка программирования в другой.

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

Различают два вида трансляции:

- компиляцию (от лат. сompilatio – присваивать), при которой результат

получается в виде готовой программы, выполняемой независимо от исходного текста программы,

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

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

Составление или редактирование программы

Текстовый редактор

Компилятор

Объектный модуль

Редактор связей

Исполнимый код (.exe, .com)

Рис. 5.1 Схема компиляции

Интерпретация (от лат. Interpretatio – толкование) – это единый процесс, в котором происходит «понимание» команды и получение результата ее работы, в отличие от компиляции, когда процесс трансляции и выполнения разъединены.

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

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

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

<буква>::= AaBbCcDdEeFf и т.д. <цифра>::= 0123456789 <знак арифметической операции>::=*/+– <разделитель>::= . , ; ( ) [ ] { } ’