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

Различают три базовые алгоритмические структуры: следование, ветвление, повторение.

Структура следованиесостоит из двух команд с указанной очередностью их выполнения и имеет вид:

<команда – предшественник>;

<команда – преемник>.

Такую структуру ещё называют линейным вычислительным процессом, в котором этапы вычислений выполняются в линейной последовательности и каждый этап выполняется только один раз. На схеме блоки размещаются сверху вниз в порядке их выполнения. Для таких процессов характерно, что направление вычислений не зависит от исходных данных или промежуточных результатов. В виде блок-схемы линейный вычислительный процесс можно представить следующим образом:

Структура типа ветвление в полной форме состоит из некоторого условия, проверяемого на истинность при выполнении структуры, команды, выполняемой при выполнении проверяемого условия, и команды, выполняемой при невыполнении условия.

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

Структура имеет вид

if <условие>

then <команда, выполняемая при выполнении условия>

else <команда, выполняемая при невыполнении условия>;.

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

.

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

Цикл с проверкой условия до исполнения действия (с предусловием). Действие может не исполниться ни одного раза.

Цикл с проверкой условия после исполнения действия (с постусловием). Действие обязательно исполнится хотя бы один раз.

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

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

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

Для организации цикла необходимо предусмотреть:

задание начального значения параметра цикла - переменной, которая будет изменяться при повторении цикла;

изменение значения этой переменной перед каждым новым повторением цикла;

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

Языки программирования

Язык программирования - это система обозначений, служащая для точного описания программ или алгоритмов для ЭВМ. Языки программирования являются искусственными языками. От естественных языков они отличаются ограниченным числом “слов” и очень строгими правилами записи команд (операторов). Поэтому при применении их по назначению они не допускают свободного толкования выражений, характерного для естественного языка.

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

Основные требования, предъявляемые к языкам программирования:

наглядность- использование в языке по возможности уже существующих символов, хорошо известных и понятных как программистам, так и пользователям ЭВМ;

единство - использование одних и тех же символов для обозначения одних и тех же или родственных понятий в разных частях алгоритма. Количество этих символов должно быть по возможности минимальным;

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

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

однозначность - недвусмысленность записи любого алгоритма. Отсутствие ее могло бы привести к неправильным ответам при решении задач.

В настоящее время в мире существует несколько сотен реально используемых языков программирования. Для каждого есть своя область применения.

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

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

машинные;

машинно-оpиентиpованные (ассемблеры);

машинно-независимые (языки высокого уровня).

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

Разные типы процессоров имеют разные наборы команд. Если язык программирования ориентирован на конкретный тип процессора и учитывает его особенности, то он называется языком программирования низкого уровня. В данном случае «низкий уровень» не значит «плохой». Имеется в виду, что операторы языка близки к машинному коду и ориентированы на конкретные команды процессора.

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

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

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

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

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

Таким образом, программы, написанные на языке ассемблера, требуют значительно меньшего объема памяти и времени выполнения. Знание программистом языка ассемблера и машинного кода дает ему понимание архитектуры машины. Несмотря на то, что большинство специалистов в области программного обеспечения разрабатывают программы на языках высокого уровня, таких, как Object Pascal или C, наиболее мощное и эффективное программное обеспечение полностью или частично написано на языке ассемблера.

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

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

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

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

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

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

требуемые операции задаются с помощью общепринятых математических обозначений;

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

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

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

Основные компоненты алгоритмического языка:

алфавит,

синтаксис,

семантика.

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

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

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

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

процедурные (алгоритмические);

логические;

объектно-ориентированные.

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

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

Разнообразие классов задач привело к тому, что на сегодняшний день разработано несколько сотен алгоритмических языков. Правда, широкое распространение и международное признание получили лишь 10-15 языков. Среди них в первую очередь следует отметить: ФОРТРАНи АЛГОЛ-языки, предназначенные для решения научно-технических задач, КОБОЛ – для решения экономических задач, БЕЙСИК – для решения небольших вычислительных задач в диалоговом режиме.

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

В то же время в середине 60-х годов начали разрабатывать алгоритмические языки широкой ориентации – универсальные языки. Обычно они строились по принципу объединения возможностей узко-ориентированных языков. Среди них наиболее известны PL/1, PASCAL, C, C+ , Модула, АДА. Однако, как любое универсальное средство, такие широко-ориентированные языки во многих конкретных случаях оказываются менее эффективными.

Логические языки (Prolog, Lisp, Mercury, KLOи др.) ориентированы не на запись алгоритма решения задачи, а на систематическое и формализованное описание задачи с тем, чтобы решение следовало из составленного описания. В этих языках указывается что дано и что требуется получить. При этом поиск решения задачи возлагается непосредственно на ЭВМ.

Объектно-ориентированные языки (Object Pascal, C++, Java, Objective Caml. и др.).Руководящая идея объектно-ориентированных языковзаключается в стремлении связать данные с обрабатывающими эти данные процедурами в единое целое - объект. Характерной чертой объектов является инкапсуляция (объединение) данных и алгоритмов их обработки, в результате чего и данные, и процедуры во многом теряют самостоятельное значение. Объекты - это скрытые модули, чей внешний интерфейс состоит из набора операций. Фактически объектно-ориентированное программирование можно рассматривать как модульное программирование нового уровня, когда вместо во многом случайного, механического объединения процедур и данных акцент делается на их смысловую связь.

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

Программирование

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

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

Program <имя (заголовок) алгоритма>;

Uses <список подключаемых библиотек, если они нужны>; { комментарии, если нужны }

Label <список меток (имен участков программ), если они нужны>; { комментарии }

Const <список констант (не изменяемых величин), если они нужны>; { комментарии }

Type <список имен и типов структур данных, если они нужны>; { комментарии }

Var <список имен и типов переменных, если они нужны>;{комментарии }

{ < условия задачи и применимости алгоритма > }

{ < цель составления и выполнения алгоритма > }

Begin

<команды ввода входных данных, если они нужны>; { комментарии }

<тело алгоритма (команды управления и преобразования алгоритма)>; { комментарии }

<команды вывода результатов (выходных данных), если они нужны>; { комментарии }

End.

Пример. Программа вычисления объема v правильного цилиндра с радиусом основания r и высотой h.

Program VСil;

Uses Crt { подключение библиотеки ввода/вывода на экран "в звуке и цвете" }

Const pi = 3.14;

Var r, h, v: real;

{ для правильного цилиндра с радиусом основания r и высотой h }

{ вычислить и выдать на экран значение его объема v }

Begin

ClrScr; { команда очистки экрана (от данных предыдущей задачи) }

ReadLn (r, h); { ввод входных параметров }

v:=pi*r*r*h; { вычисление объема по формуле для цилиндра }

WriteLn (‘Вычисленный объем цилиндра равен ’, v) { вывод результата }

End.

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

Обычная запись	Паскаль
Квадрат числа х	sqr(x)
Корень квадратный из x	sqrt (x)
Модуль |х|	abs (x)
sin x	sin(x)
cos x	cos(x)
tg x	tg(x)
ctg x	ctg(x)
arcsin x	arcsin (x)
arccos x	arccos(x)
arctg x	arctg(x)
Натуральный логарифм ln x	ln(x)
Степень числа е = 2, 7... или еx	exp(x)
Остаток от деления целого х на целое у	x mod y
Частное от деления целого х на целое y	x div y
Целая часть числа х (вещественного)	int(x)
Случайное число от 0 до х	rnd(x)
Длина текста х в символах	length (x)

Пример. Результаты применения этих функций: sqrt(9) = 3, abs(–5) = 5, sin(0) = 0, cos(0) = 1, ln(1) = 0, exp(1 ) =e, 23 mod 5 = 3, 20 mod 5 = 0, 23 div 5 = 4, 20 div 5 = 4, int(2.7) = 2, int(2) = 2, rnd(0) = 0.231356, length(‘информ’) = 6.

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

вычисление выражений в скобках;

вычисление стандартных функций;

умножение и деление (обозначаются "*" и "/");

сложение и вычитание (обозначаются "+" и "–").

Рассмотрим базовые простые команды языка Паскаль.

Команда описания (заголовка) алгоритма (программы):

Program <имя алгоритма>;,

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

Ввод – команда ввода в рассмотрение (в тело алгоритма) тех или иных входных параметров:

Read (<список вводимых параметров>);

или

ReadLn (<список вводимых параметров>);.

Первая команда вводит данные с текущей позиции экрана (где стоит курсор), вторая – с новой строки экрана.

Вывод – команда вывода на экран тех или иных входных или выходных параметров алгоритма:

Write (<список выводимых параметров>);

или

WriteLn (<список выводимых параметров>);.

Первая команда выводит данные с текущей позиции экрана (где стоит курсор), вторая – с новой строки экрана.

Присваивание – команда изменения текущего значения переменной вида:

<идентификатор> := <выражение>;,

где <идентификатор> соответствует имени переменной, <выражение> – корректно записанное выражение. Знак ":=" означает последовательное выполнение двух действий: определение текущего значения <выражения> и замена текущего значения переменной, имя которой задано <идентификатором>, на новое значение, равное значению <выражения>.

Команда начала алгоритма (блока) – команда Begin.

Команда завершения алгоритма (блока) – команда End.

Команда вставки комментариев в текст алгоритма имеет вид:

<комментируемое в программе> {текст комментария}.

Комментировать можно любой объект в программе. Обычно комментируют переменную, структуру данных, команду, группу команд.

Рассмотрим ряд задач, решаемых с помощью массивов.

Пример. Составим алгоритм (программу) нахождения суммы и произведения всех элементов одномерного массива. Метод решения: начиная с нулевого значения суммы, добавляем поочередно новый элемент ряда и находим значение искомой суммы; начиная с начального, единичного произведения, находим искомое произведение, умножая текущее значение произведения на очередной элемент ряда. Алгоритм (программа) имеет вид

Program SPM1;

Uses Crt;

Var x: array [1..100] of real;

n, i: integer;

s, р: real;

Begin

ClrScr;

WriteLn('Введите размерность массива :'); { приглашение к вводу входного параметра }

ReadLn(n); { ввод входного параметра }

WriteLn('Введите элементы массива:'); { приглашение к вводу массива }

for i:=1 to n do { цикл ввода элементов массива }

begin

write('x[',i,']='); { приглашение к вводу текущего элемента массива}

readln(x[i]) { ввод текущего элемента массива }

end;

s:=0; { начальное значение суммы – нуль }

p:=1; { начальное значение произведение – единица [u1]}

for i:=1 to n do { цикл вычисления суммы и произведения }

begin

s:=s+x[i]; { добавление к сумме очередного слагаемого }

p:=p*x[i] { домножение произведения на очередной множитель }

end;

WriteLn('Полученная сумма равна ', s: 3:3); { вывод полученной суммы }

WriteLn('Полученное произведение равно ', p: 3:3); { вывод полученного произведения }

End.

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

"Забудем" временно чисто математическое решение этой задачи – с использованием суммы арифметической прогрессии с шагом 2.

Алгоритм (программа) имеет вид

Program Summa;

Uses Crt; { подключение библиотеки ввода/вывода на экран "в звуке и цвете"}

Var i, n, s: real;

{ для ряда чисел 1, 3, 5, …, }

{ найти и выдать сумму s всех первых чисел ряда, для которых впервые s > n }

Begin

ClrScr; { команда очистки экрана (от данных предыдущей задачи) }

ReadLn (n); { ввод входного параметра }

s:=1; { начальное значение суммы до входа в цикл }

i:=1; { количество просуммированных чисел в начале }

while (s<=n) do { заголовок цикла (проверка условия выхода из цикла) }

begin

i:=i+2; { находим новое слагаемое }

s:=s+i { добавили к предыдущему значению суммы новое слагаемое }

end;

WriteLn (‘Вычисленная сумма равна ’, s); { вывод результата }

End.