Слово «алгоритм» произошло от имени арабского математика 9 века аль-Хорезми, который сформулировал правила выполнения арифметический действий.

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

Примеры: распорядок дня, порядок приготовления блюда, инструкция и т.д.)

Исполнитель алгоритма – это тот, кто выполняет алгоритм (человек, животное, машина, компьютер).

Система команд исполнителя – это вся совокупность команд, которые исполнитель умеет выполнять (понимает). Алгоритм можно строить только из команд, входящих в систему команд исполнителя.

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

Свойства алгоритма:

1.Результативность (конечность) – возможность получения из исходных данных результата за конечное число шагов. (Например, при выполнении алгоритма сложения 2 чисел должны получить сумму).

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

3.Детерминированность (определенность, точность) – каждая команда должна однозначно определять действие исполнителя.

4.Понятность – команда должна быть записана на понятном компьютеру языке.

5.Дискретность – разбиение алгоритма на отдельные команды.

Способы записи алгоритма:

1) На естественном языке – запись в виде отдельных команд на понятном человеку языке.

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

3) На алгоритмическом языке – язык записи алгоритмов, для обучения программированию. Команды записываются на русском языке.

4) На языке программирования - программа. Языки программирования: Basic, Pascal, Си, Visual Basic.

Б7.Основные алгоритмические структуры: следование, ветвление, цикл; изображение на блок-схемах. Разбиение задач на подзадачи. Вспомогательные алгоритмы.

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

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

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

Так выглядит линейный алгоритм на языке блок схем:

Пример : алгоритм включения компьютера:

1. Включить питание компьютера (нажать кнопку на сетевом фильтре).
2. Включить монитор, принтер.
3. Нажать кнопку Power на системном блоке.
4. Дождаться загрузки операционной системы и появления Рабочего стола.
5. Приступить к работе.

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

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

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

Запись на алгоритмическом языке: ЕслиУсловие То Серия 1 (Если Условие истинно, то выполняется Серия 1 , если Условие ложно, то ничего не выполняется). Пример: Если сегодня воскресенье, то в школу идти не надо. Полная форма ветвления

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

Циклические алгоритмические структуры бывают двух типов:

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

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

Ключевые слова:

• алгоритм
• свойства алгоритма
  • дискретность
  • понятность
  • определённость
  • результативность
  • массовость
• исполнитель

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

3.1.1. Понятие алгоритма

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

Пример 1 . Задача «Найти среднее арифметическое двух чисел» решается в три шага:

• задумать два числа;
• сложить два задуманных числа;
• полученную сумму разделить на 2.

Пример 2 . Задача «Внести деньги на счёт телефона» подразделяется на следующие шаги:

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

Пример 3 . Этапы решения задачи «Нарисовать весёлого ёжика» представлены графически:

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

Алгоритм может представлять собой описание некоторой последовательности вычислений (пример 1) или шагов нематематического характера (примеры 2-3). Но в любом случае перед его разработкой должны быть чётко определены начальные условия (исходные данные) и то, что предстоит получить (результат). Можно сказать, что алгоритм - это описание последовательности шагов в решении задачи, приводящих от исходных данных к требуемому результату.

В общем виде схему работы алгоритма можно представить следующим образом (рис. 3.1):

Рис. 3.1.
Общая схема работы алгоритма

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

Анимации «Работа с алгоритмом», «Наибольший общий делитель», «Наименьшее общее кратное» (http://school-collection.edu.ru/) помогут вам вспомнить некоторые алгоритмы, изученные на уроках русского языка и математики.

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

1. Вычисляется длина (в символах) исходной цепочки символов.
2. Если длина исходной цепочки нечётна, то к исходной цепочке справа приписывается цифра 1, иначе цепочка не изменяется.
3. Символы попарно меняются местами (первый - со вторым, третий - с четвёртым, пятый - с шестым и т. д).
4. Справа к полученной цепочке приписывается цифра 2.

Получившаяся таким образом цепочка является результатом работы алгоритма.

Так, если исходной была цепочка А#В, то результатом работы алгоритма будет цепочка #А1В2, а если исходной цепочкой была АБВ@, то результатом работы алгоритма будет цепочка БА@В2.

3.1.2. Исполнитель алгоритма

Каждый алгоритм предназначен для определённого исполнителя.

Различают формальных и неформальных исполнителей. Формальный исполнитель одну и ту же команду всегда выполняет одинаково. Неформальный исполнитель может выполнять команду по-разному.

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

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

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

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

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

Рассмотрим примеры исполнителей.

Пример 5 . Исполнитель Черепашка перемещается на экране компьютера, оставляя след в виде линии. Система команд Черепашки состоит из двух команд:

Вперёд n (где n - целое число) - вызывает передвижение Черепашки на n шагов в направлении движения - в том направлении, куда развёрнуты её голова и корпус;

Направо m (где m - целое число) - вызывает изменение направления движения Черепашки на m градусов по часовой стрелке.

Запись Повтори k [<Команда1> <Команда2> ... <Командаn>] означает, что последовательность команд в скобках повторится k раз.

Подумайте, какая фигура появится на экране после выполнения Черепашкой следующего алгоритма.

Повтори 12 [Направо 4 5 Вперёд 20 Направо 45]

Пример 6 . Система команд исполнителя Вычислитель состоит из двух команд, которым присвоены номера:

1 - вычти 1
2 - умножь на 3

Первая из них уменьшает число на 1, вторая увеличивает число в 3 раза. При записи алгоритмов для краткости указываются лишь номера команд. Например, алгоритм 21212 означает следующую последовательность команд:

умножь на 3
вычти 1
умножь на 3
вычти 1
умножь на 3

С помощью этого алгоритма число 1 будет преобразовано в 15: ((1-3-1)-3-1)-3 = 15.

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

1 - Вверх
2 - Вниз
3 - Вправо
4 - Влево

При выполнении каждой такой команды Робот перемещается в соседнюю клетку в указанном направлении. Если же в этом направлении между клетками стоит стена, то Робот разрушается. Что произойдёт с Роботом, если он выполнит последовательность команд 32323 (здесь цифры обозначают номера команд), начав движение из клетки А? Какую последовательность команд следует выполнить Роботу, чтобы переместиться из клетки А в клетку В, не разрушившись от встречи со стенами?

При разработке алгоритма:

1. выделяются фигурирующие в задаче объекты, устанавливаются свойства объектов, отношения между объектами и возможные действия с объектами;
2. определяются исходные данные и требуемый результат;
3. определяется последовательность действий исполнителя, обеспечивающая переход от исходных данных к результату;
4. последовательность действий записывается с помощью команд, входящих в систему команд исполнителя.

Можно сказать, что алгоритм - модель деятельности исполнителя алгоритмов.

3.1.3. Свойства алгоритма

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

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

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

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

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

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

Пример 8 . Рассмотрим один из методов нахождения всех простых чисел, не превышающих n. Этот метод называется «решето Эратосфена», по имени предложившего его древнегреческого учёного Эратосфена.

Для нахождения всех простых чисел, не больших заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги:

1. выписать подряд все целые числа от 2 до n (2, 3, 4, ..., n);
2. заключить в рамку 2 - первое простое число;
3. вычеркнуть из списка все числа, делящиеся на последнее найденное простое число;
4. найти первое неотмеченное число (отмеченные числа - зачёркнутые числа или числа, заключённые в рамку) и заключить его в рамку - это будет очередное простое число;
5. повторять шаги 3 и 4 до тех пор, пока не останется неотмеченных чисел.

Более наглядное представление о методе нахождения простых чисел вы сможете получить с помощью анимации «Решето Эратосфена» (http://school-collection.edu.ru/).

Рассмотренная последовательность действий является алгоритмом, так как она удовлетворяет свойствам:

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

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

3.1.4. Возможность автоматизации деятельности человека

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

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

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

Рассмотрим алгоритм, следуя которому первый игрок наверняка обеспечит себе выигрыш.

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

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

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

Самое главное

Исполнитель - некоторый объект (человек, животное, техническое устройство), способный выполнять определённый набор команд. Формальный исполнитель одну и ту же команду всегда выполняет одинаково. Для каждого формального исполнителя можно указать: круг решаемых задач, среду, систему команд и режим работы.

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

Способность исполнителя действовать формально обеспечивает возможность автоматизации деятельности человека.

Вопросы и задания

1. Что называют алгоритмом?
2. Подберите синонимы к слову «предписание».
3. Приведите примеры алгоритмов, изучаемых вами в школе.
4. Кто может быть исполнителем алгоритма?
5. Приведите пример формального исполнителя. Приведите пример, когда человек выступает в роли формального исполнителя.
6. Какие команды должны быть у робота, выполняющего функции: а) кассира в магазине; б) дворника; в) охранника?
7. От чего зависит круг решаемых задач исполнителя «компьютер»?
8. Рассмотрите в качестве исполнителя текстовый процессор, имеющийся на вашем компьютере. Охарактеризуйте круг решаемых этим исполнителем задач и его среду.
9. Что такое команда, система команд исполнителя?
10. Перечислите основные свойства алгоритма.
11. К чему может привести отсутствие какого-либо свойства у алгоритма? Приведите примеры.
12. В чём важность возможности формального исполнения алгоритма?
13. Последовательность чисел строится по следующему алгоритму: первые два числа последовательности принимаются равными 1; каждое следующее число последовательности принимается равным сумме двух предыдущих чисел. Запишите 10 первых членов этой последовательности.
14. Некоторый алгоритм получает из одной цепочки символов новую цепочку следующим образом. Сначала записывается исходная цепочка символов, после нее записывается исходная цепочка символов в обратном порядке, затем записывается буква, следующая в русском алфавите за той буквой, которая в исходной цепочке стояла на последнем месте. Если в исходной цепочке на последнем месте стоит буква Я, то в качестве следующей буквы записывается буква А. Получившаяся цепочка является результатом работы алгоритма. Например, если исходная цепочка символов была ДОМ, то результатом работы алгоритма будет цепочка ДОММОДН. Дана цепочка символов КОМ. Сколько букв О будет в цепочке символов, которая получится, если применить алгоритм к данной цепочке, а затем ещё раз применить алгоритм к результату его работы?
15. Найдите в сети Интернет анимацию шагов алгоритма Эратосфена. С помощью алгоритма Эратосфена найдите все простые числа, не превышающие 50.
16. Что будет результатом исполнения Черепашкой (см. пример 5) алгоритма?
    Повтори 8 [Направо 45 Вперёд 45]
17. Запишите алгоритм для исполнителя Вычислитель (пример 6), содержащий не более 5 команд:
    а) получения из числа 3 числа 16;
    б) получения из числа 1 числа 25.
18. Система команд исполнителя Конструктор состоит из двух команд, которым присвоены номера:
    1 - приписать 2
    2 - разделить на 2

    По первой из них к числу приписывается справа 2, по второй число делится на 2. Как будет преобразовано число 8, если исполнитель выполнит алгоритм 22212? Составьте алгоритм в системе команд этого исполнителя, по которому число 1 будет преобразовано в число 16 (в алгоритме должно быть не более 5 команд).

19. В какой клетке должен находиться исполнитель Робот (пример 7), чтобы после выполнения алгоритма 3241 в неё же и вернуться?

ТЕМА 8. ОСНОВЫ АЛГОРИТМИЗАЦИИ И ПРОГРАММИРОВАНИЯ

8.1. Понятие об алгоритме и исполнителе алгоритмов. Свойства алгоритмов

"Алгоритм" является фундаментальным понятием информатики. Представление о нем необходимо для эффективного применения вычислительной техники к решению практических задач. Алгоритм - это предписание исполнителю (человеку или автомату) выполнить точно определенную последовательность действий, направленных на достижение заданной цели. Алгоритм - это сформулированное на некотором языке правило, указывающее на действия, последовательное выполнение которых приводит от исходных данных к искомому результату. Значение слова алгоритм очень схоже со значением слов рецепт, процесс, метод, способ . Однако любой алгоритм, в отличие от рецепта или способа, обязательно обладает следующими свойствами.
Свойства алгоритма (отличающие его от любых других предписаний): понятность (для конкретного исполнителя); дискретность (команды последовательны, с точной фиксацией моментов начала и конца выполнения команды); точность (после выполнения каждой команды точно известно, завершено ли исполнение алгоритма или же какая команда должна выполниться следующей); результативность (после конечного числа шагов задача решается или же становится ясно, что процесс решения не может быть продолжен): массовость (алгоритм единым образом применяется к любой конкретной формулировке задачи, для которой он разработан).
1. Дискретность - разбиение алгоритма на ряд отдельных законченных действий - шагов. Выполнение алгоритма разбивается на последовательность законченных действий - шагов. Каждое действие должно быть закончено исполнителем алгоритма прежде, чем он приступит к исполнению следующего действия.
2. Точность - однозначные указания. На каждом шаге однозначно определено преобразование объектов среды исполнителя, полученной на предыдущих шагах алгоритма. Если алгоритм многократно применяется к одному и тому же набору исходных данных, то на выходе он получает каждый раз один и тот же результат. Запись алгоритма должна быть такой, чтобы на каждом шаге его выполнения было известно, какую команду надо выполнять следующей.
3. Понятность - однозначное понимание и исполнение каждого шага алгоритма его исполнителем. Алгоритм должен быть записан на понятном для исполнителя языке.
4. Результативность - обязательное получение результата за конечное число шагов. Каждый шаг (и алгоритм в целом) после своего завершения дает среду, в которой все объекты однозначно определены. Если это по каким-либо причинам невозможно, то алгоритм должен сообщать, что решение задачи не существует. Работа алгоритма должна быть завершена за конечное число шагов. Информатика оперирует только с конечными объектами и конечными процессами, поэтому вопрос о рассмотрении бесконечных алгоритмов остается за рамками теории алгоритмов. 5. Массовость - применение алгоритма к решению целого класса однотипных задач.
Система команд исполнителя - точно описанная обстановка, включающая формулировку решаемой задачи, перечень объектов, вовлекаемых в условие задачи и в ее решение, и возможности исполнителя: свойства объектов, которые он может узнать и действия, которые он может совершить. Формальное исполнение алгоритма производит компилятор или интерпретатор, проверяя семантику.

8.2. Способы записи алгоритма

На практике наиболее распространенными являются следующие формы записи алгоритмов:
1) графическая запись (блок-схемы);
2) словесная запись (псевдокоды);
3) язык программирования.
Словесная форма записи алгоритма представляет собой описание на естественном языке последовательных этапов обработки данных. Словесный способ не имеет широкого распространения, так как такие описания строго не формализуемы, допускают неоднозначность толкования отдельных предписаний. Алгоритм, записанный с помощью псевдокода, представляет собой полуформализованное описание на условном алгоритмическом языке, включающее как основные элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и другие.
Графическая форма записи, называемая также схемой алгоритма, представляет собой изображение алгоритма в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий. Графическая запись является более компактной и наглядной по сравнению со словесной. В схеме алгоритма каждому типу действий соответствует геометрическая фигура. Фигуры соединяются линиями переходов, определяющими очередность выполнения действий.
Графическая форма записи, называемая также структурной схемой или блок-схемой алгоритма, представляет собой изображение алгоритма в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий.
В дальнейшем мы будем использовать блок-схемы алгоритмо в. Они позволяют представить алгоритмы в более наглядном виде, это дает возможность анализировать их работу, искать ошибки в их реализации и т.д. В блок-схемах всегда есть начало и конец , обозначаемые эллипсами, между ними - последовательность шагов алгоритма, соединенных стрелками .

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

Если решение задачи сложное и достаточно длинное, то алгоритм может получиться очень большим. Избежать этого можно, заменив некоторую законченную последовательность шагов алгоритма блоками, которые будут являться вспомогательными алгоритмами. Блок обычно не элементарен, его размеры выбираются в зависимости от необходимости, однако если он правильно составлен, то обладает всеми необходимыми признаками алгоритмического шага: имеет точку входа (четко выделенное начало) и может быть условным или безусловным. Разные блоки алгоритма связаны друг с другом только через точки входа и выхода, поэтому если блок верно решает свою задачу, то его внутренняя структура несущественна для остальной части алгоритма. Такое блочное представление особенно удобно на первых этапах решения сложных задач, когда детализация блоков производится позднее и, возможно, другими разработчиками.
Язык программирования - язык, используемый для формальной записи алгоритмов. Большинство языков программирования относятся к алгоритмическим языкам. Запись алгоритма на алгоритмическом языке называют программой.
Язык, используемый для формальной записи алгоритмов, называется алгоритмическим языком . При описании любого языка (в том числе естественного, например, русского, английского и т.д.) используются следующие понятия: алфавит, синтаксис и семантика .
Алфавит языка - это множество простейших знаков, которые могут быть использованы в текстах этого языка. Последовательность символов алфавита называют словом . Правила, согласно которым образуются слова из алфавита, называются грамматикой. Сам же язык - это множество всех слов, записываемых в данном алфавите согласно данной грамматике.
Синтаксис - это набор правил, определяющих возможные сочетания (конструкции) из букв алфавита. Для описания синтаксиса языка, как правило, используют другой язык (метаязык) или синтаксические диаграммы.
Семантика - это набор правил, определяющих значение (смысл) отдельных конструкций языка.
Одним из самых распространенных алгоритмических языков является язык Pascal, который полезен как для начинающих, так и для опытных программистов. Обучение программированию чаще всего основывается на этом языке.

8.3. Основные алгоритмические конструкции

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

	Данный блок имеет один вход и один выход . Из простых команд и проверки условий образуются составные команды, имеющие более сложную структуру и тоже один вход и один выход . Структурный подход к разработке алгоритмов определяет использование только базовых алгоритмических структур (конструкций): следование, ветвление, повторение, которые должны быть оформлены стандартным образом.
	Рассмотрим основные структуры алгоритма. Команда следования состоит только из простых команд. На рисунке простые команды имеют условное обозначение S1 и S2 . Из команд следования образуются линейные алгоритмы. Примером линейного алгоритма будет нахождение суммы двух чисел, введенных с клавиатуры.
	Команда ветвления - это составная команда алгоритма, в которой в зависимости от условия Р выполняется или одно S1 , или другое S2 действие. Из команд следования и команд ветвления составляются разветвляющиеся алгоритмы (алгоритмы ветвления). Примером разветвляющегося алгоритма будет нахождение большего из двух чисел, введенных с клавиатуры.
	Команда ветвления может быть полной и неполной формы. Неполная форма команды ветвления используется тогда, когда необходимо выполнять действие S только в случае соблюдения условия P . Если условие P не соблюдается, то команда ветвления завершает свою работу без выполнения действия. Примером команды ветвления неполной формы будет уменьшение в два раза только четного числа.
	Команда повторения - это составная команда алгоритма, в которой в зависимости от условия Р возможно многократное выполнение действия S . Из команд следования и команд повторения составляются циклические алгоритмы (алгоритмы повторения). На рисунке представлена команда повторения с предусловием. Называется она так потому, что вначале проверяется условие, а уже затем выполняется действие. Причем действие выполняется, пока условие соблюдается. Пример циклического алгоритма может быть следующий. Пока с клавиатуры вводятся положительные числа, алгоритм выполняет нахождение их суммы. Команда повторения с предусловием не является единственно возможной. Разновидностью команды повторения с предусловием является команда повторения с параметром. Она используется тогда, когда известно количество повторений действия. В блок-схеме команды повторения с параметром условие записывается не в ромбе, а в шестиугольнике. Примером циклического алгоритма с параметром будет нахождение суммы первых 20 натуральных чисел.
	В команде повторения с постусловием вначале выполняется действие S и лишь затем, проверяется условие P . Причем действие повторяется до тех пор, пока условие не соблюдается. Примером команды повторения с постусловием будет уменьшение положительного числа до тех пор, пока оно неотрицательное. Как только число становится отрицательным, команда повторения заканчивает свою работу. С помощью соединения только этих элементарных конструкций (последовательно или вложением) можно "собрать" алгоритм любой степени сложности.

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

8.4. Линейный алгоритм

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

8.5. Разветвляющийся алгоритм

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

8.6. Циклический алгоритм

Рассмотрим алгоритм нахождения суммы первых натуральных нечетных чисел до n . Представим запись алгоритма тремя способами: в виде блок-схемы, школьного алгоритмического языка и на языке программирования Pascal.

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

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

Вопросы для самоконтроля

1. Понятие алгоритма. Свойства алгоритма. Пример алгоритма. Понятие "переменная".
2. Оператор присваивания. Примеры.
3. Стили программирования (логический, функциональный).
4. Понятие подпрограммы, модуля и объекта
5. Что такое переменная? Правила наименования переменных в Паскале. Примеры.
6. Оператор присваивания. Запись выражений в Паскале. Примеры. Объяснить, как действует оператор x:=x+1;
7. Операторы ввода и вывода в Паскале. Примеры. Форматированный вывод.
8. Условный оператор (if ). Пример. Сравнить с оператором case .
9. Оператор выбора. Пример. Сравнить с оператором if .
10. Логические выражения. Операции or, and и not . Примеры. Таблица истинности.
11. Числовые типы переменных в языке Паскаль. Правила преобразования типов. Примеры.
12. Логический тип данных. Пример использования в программе. Символьный тип данных. Пример. Функции chr и ord , succ и pred .
13. Массивы. Определение. Индексы массивов. Объявления массивов. Обращения к элементам массива. Одномерные и двумерные массивы. Примеры. Сходство и различие массивов и строк.
14. Процедуры. Определение. Зачем нужны процедуры? Примеры. Правила описания процедур. Сравнить процедуры и функции.