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

Само слово «алгоритм» происходит от algorithmi - латинской формы написания имени великого математика IX века аль-Хорезми, который сформулировал правила выполнения арифметических действий. Первоначально под алгоритмами и понима­ли только правила выполнения четырёх арифметических действий над многознач­ными числами.

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

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

Различают алгоритмы «в обстановке» (алгоритмы, в которых поведение исполнителя зависит от окружающей обстановки – пылесосик, кенгурёнок и др. исполнители) и алгоритмы работы с величинами - числовыми, символь­ными, логическими и т.д. Последние алгоритмы более привычны и имеют большее распространение.

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

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

2. Понятность. Используемые на практике алгоритмы составляются с ориентацией на опреде­ленного исполнителя. Поэтому все команды в алгоритме должны быть понятны этому исполнителю, т.е. принадлежать его СКИ.

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

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

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

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

Блок-схемы. Остановимся на графическом описании алгоритма, называемом блок-схемой. Этот способ имеет ряд преимуществ. Благодаря наглядно­сти, обеспечивающей высокую «читаемость» алгоритма и явное отображение управления в нем.

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

Функциональная вершина	Предикатная вершина	Объединяющая вершина

 

Функциональная вершина имеет один вход и один выход. Предикативная вершина имеет один вход и два выхода (в этом случае функция P передаёт управление по одной из ветвей в зависимости от значения – ложь или истина). Объединяющая вершина (вершина «слияния») обеспечивает передачу управления от одного из двух входов к выходу. Из данных элементарных блок-схем можно построить четыре основные алгоритмические структуры – следование (или композиция), ветвление (альтернатива, развилка), цикл (или итерация).  Развитием блок-схемы «альтернатива» является блок-схема «выбор» (на рисунке слева).

На практике при составлении блок-схем оказывается удобным использовать и другие графические знаки:

 

Название	Символ	Выполняемая функция
Блок ввода/вывода		Ввод или вывод данных
Блок печати		Вывод данных на печатающее устройство
Начало/конец (вход/выход)		Начало или конец программы, вход или выход в подпрограмму
Предопределенный процесс		Вычисления по стандартной или пользовательской подпрограмме
Блок модификации (цикл с параметром)		Выполнение действий, изменяющих пункты алгоритма
Соединитель		Указание связи между прерванными линиями в пределах одной страницы
Межстраничный соединитель		Указание связи между частями схемы, расположенной на разных страницах

 

При построении блок-схем необходимо придерживаться двух правил:

1) Блок-схема выстраивается в одном направлении либо сверху вниз, либо слева направо.

2) Все повороты соединительных линий выполняются под углом 90 градусов.

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

Основу этого словаря алгоритмического языка составляют слова, употребляемые для записи команд, входящих в СКИ того или иного алгоритма. Такие команды называют просты­ми командами. В алгоритмическом языке используют слова, смысл и способ упот­ребления которых задан раз и навсегда. Эти слова называют служебными. Исполь­зование служебных слов делает запись алгоритма более наглядной, а форму пред­ставления различных алгоритмов – единообразной.

Алгоритм, записанный на алгоритмическом языке, должен иметь название. Назва­ние желательно выбирать так, чтобы было ясно, решение какой задачи описывает данный алгоритм. Для выделения названия алгоритма перед ним записывают служеб­ное слово АЛГ (АЛГоритм). За названием алгоритма (обычно с новой строки) записывают его команды. Для указания начала и конца алгоритма его команды заключают в пару служебных слов НА Ч (НАЧало) и КОН (КОНец). Команды записывают последовательно.

 

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

Язык Паскаль является типичным языком структурного программирования. Это означает, что программист должен выражать свои мысли очень дисциплинированно, с использованием малого числа чётко оговоренных конструкций, используя как чередование их, так и вложения друг в друга. Не рекомендуется (хотя и возможно) использовать оператор перехода GOTO.

1) Реализация последовательности действий (т.е. структуры следования) выполня­ется с помощью составного оператора: begin <последовательность операторов> end;

Раздел операторов в программе всегда является составным оператором. Слу­жебные слова BEGIN и END часто называют операторными скобками.

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

а) Структура и действие условного оператора таковы:

if <логическое выражение> then <оператор 1> e1se <оператор 2>;

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

б) Оператор варианта имеет следующую форму:

case <выражение> of

<список констант 1>: <оператор 1>;

.................................;

<список констант N>: <оператор N> end;

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

Оператор варианта вычисляет значение выражения, записанного после CASE. Ес­ли его значение совпадает с одной из констант в некотором списке, то выполняется оператор, стоящий после этого списка. Если значение выражения не совпало ни с одной константой во всех вариантах, то оператор варианта ничего не делает.

Пример. Программа, которая в зависимости от номера ме­сяца указывает время года.

program seasons; var k:integer;

begin writеln('введите номер месяца'); readln(k);

сазе k of 1,2,12:writеln('зима'); З,4,5:writеln('весна');

6,7,8:writеln('лето'); 9,10,11:writeln('oceнь'); end; end.

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

а) Цикл с предусловием (цикл-пока) имеет следующий вид:

while <логическое выражение> do <оператор>

Сначала вычисляется значение логического выражения. Если оно равно true, то выполняется оператор, после чего снова вычисляется значение логического выра­жения, в противном случае действие заканчивается.

Пример. Пока не введено число 0, запрашивать введение числа.

program zapros1; var x:integer;

begin write(‘Введите число’); readln(x);

while x<>0 do begin write(‘Вы ввели не 0, введите 0: ’); readln(x);

end; end.

б) Оператор цикла с постусловием (цикл-до) реализован в Паскале следующим образом:

repeat <последовательность операторов> until <логическое выражение>

Сначала выполняется последовательность операторов. Далее вычисляется зна­чение логического выражения. Если оно равно true, то действие заканчивается, в противном случае снова выполняется последовательность операторов и т.д.

Пример. Пока не введено число 0, запрашивать введение числа.

program zapros2; var x:integer;

begin repeat write(‘Введите число 0: ’); readln(x) until x=0; end.

в) Оператор цикла с параметром предусматривает повторное выполнение некото­рого оператора с одновременным изменением по правилу арифметической прогрес­сии значения управляющей переменной (параметра) этого цикла. Оператор цикла с параметром имеет две формы.

Форма 1: for <параметр>:= <выр1> to <выр2> do <оператор>;

Параметр, выр1, выр2 должны быть одного ординального типа. Параметр в этом цикле возрастает. Действие эквивалентно действию следующего составного оператора:

begin <параметр>:=<выр1>;

while <параметр> <= <выр2> do begin <оператор>;

<параметр>:=suсс(<параметр>); end; end;

Если в этом описании отношение <= заменить на >=, а функцию SUCC на PRED, то параметр в цикле будет убывать, в этом случае цикл с параметром принимает форму 2.

Форма 2: for <параметр>:=<выр1> downto <выр2> do <оператор>;

Пример. Найти сумму всех чисел от 1 до 100.

program sum_1_to_100; var i,sum:integer;

begin sum:=0; for i:=1 to 100 do sum:=sum+i;

writeln(‘сумма от 1 до 100 равна: ’,sum); end.

 

 

Составные данные статической структуры: одномерные и двухмерные массивы – см. вопрос №17.