При изучении информатики немало внимания уделяется изучению алгоритмов и их видам. Не зная основных сведений о них, нельзя написать программу или проанализировать ее работу. Изучение алгоритмов начинается еще в школьном курсе информатики. Сегодня мы рассмотрим понятие алгоритма, свойства алгоритма, виды.
Понятие
Алгоритм – это определенная последовательность действий, которая приводит к достижению того или иного результата. Составляя алгоритм, детально прописывают каждое действие исполнителя, которое в дальнейшем приведет его к решению поставленной задачи.
Довольно часто алгоритмы используют в математике для решения тех или иных задач. Так, многим известен алгоритм решения квадратных уравнений с поиском дискриминанта.
Свойства
Прежде чем рассматривать виды алгоритмов в информатике, необходимо выяснить их основные свойства.
Среди основных свойств алгоритмов необходимо выделить следующие:
- Детерминированность, то есть определенность. Заключается в том, что любой алгоритм предполагает получение определенного результата при заданных исходных.
- Результативность. Означает, что при наличии ряда исходных данных после выполнения ряда шагов будет достигнут определенный, ожидаемый результат.
- Массовость. Написанный единожды алгоритм может использоваться для решения всех задач заданного типа.
- Дискретность. Она подразумевает, что любой алгоритм можно разбить на несколько этапов, каждый из которых имеет свое назначение.
Способы записи
Вне зависимости от того, какие виды алгоритмов в информатике вы рассматриваете, существует несколько способов их записи.
- Словесный.
- Формульно-словесный.
- Графический.
- Язык алгоритма.
Наиболее часто изображают алгоритм в виде блок-схемы, используя специальные обозначения, зафиксированные ГОСТами.
Основные виды
Выделяют три основных схемы:
- Линейный алгоритм.
- Ветвящийся алгоритм, или разветвленный.
- Циклический.
Далее мы рассмотрим виды алгоритмов в информатике, примеры, которые помогут более детально понять, как они работают.
Линейный
Наиболее простым в информатике считается линейный алгоритм. Он предполагает последовательность выполнения действий. Приведем наиболее простой пример алгоритма такого вида. Назовем его «Сбор в школу».
1. Встаем, когда звенит будильник.
2. Умываемся.
3. Чистим зубы.
4. Делаем зарядку.
5. Одеваемся.
6. Кушаем.
7. Обуваемся и идем в школу.
8. Конец алгоритма.
Разветвляющийся алгоритм
Рассматривая виды алгоритмов в информатике, нельзя не вспомнить о разветвляющейся структуре. Данный вид предполагает наличие условия, при котором в случае его выполнения действия выполняются в одном порядке, а в случае невыполнения – в другом.
Например, возьмем следующую ситуацию – переход дороги пешеходом.
1. Подходим к светофору.
2. Смотрим на сигнал светофора.
3. Он должен быть зеленым (это условие).
4. Если условие выполняется, мы переходим дорогу.
4.1 Если нет – ждем, пока загорится зеленый.
4.2 Переходим дорогу.
5. Конец алгоритма.
Циклический алгоритм
Изучая виды алгоритмов в информатике, детально следует остановиться на циклическом алгоритме. Данный алгоритм предполагает участок вычислений или действий, который выполняется до выполнения определенного условия.
Возьмем простой пример. Если ряд чисел от 1 до 100. Нам необходимо найти все простые числа, то есть те, которые делятся на единицу и себя. Назовем алгоритм «Простые числа».
1. Берем число 1.
2. Проверяем, меньше ли оно 100.
3. Если да, проверяем простое ли это число.
4. Если условие выполняется, записываем его.
5. Берем число 2.
6. Проверяем, меньше ли оно 100.
7. Проверяем, простое ли оно.
…. Берем число 8.
Проверяем, меньше ли оно 100.
Проверяем, простое ли число.
Нет, пропускаем его.
Берем число 9.
Таким образом перебираем все числа, до 100.
Как видите, шаги 1 – 4 будут повторяться некоторое число раз.
Среди циклических выделяют алгоритмы с предусловием, когда условие проверяется в начале цикла, или с постусловием, когда проверка идет в конце цикла.
Другие варианты
Алгоритм может быть и смешанным. Так, он может быть циклическим и разветвленным одновременно. При этом используются разные условия на разных отрезках алгоритма. Такие сложные структуры приеняются при написании сложных программ и игр.
Обозначения в блок-схеме
Мы с вами рассмотрели, какие виды алгоритмов есть в информатике. Но мы не рассказали о том, какие обозначения используются при их графической записи.
- Начало и конец алгоритма записываются в овальной рамке.
- Каждая команда фиксируется в прямоугольнике.
- Условие прописывается в ромбе.
- Все части алгоритма соединяются при помощи стрелок.
Выводы
Мы с вами рассмотрели тему «Алгоритмы, виды, свойства». Информатика уделяет немало времени изучению алгоритмов. Их используют при написании различных программ как для решения математических задач, так и для создания игр и различного рода приложений.
Алгоритм. Свойства алгоритмов.
Блок-схемы. Алгоритмические языки
Код ОГЭ: 1.3.1. Алгоритм, свойства алгоритмов, способы записи алгоритмов.
Блок-схемы. Представление о программировании
Понятие алгоритма является одним из основных понятий вычислительной математики и информатики.
■ Алгоритм
— строго определенная последовательность действий для некоторого исполнителя, приводящая к поставленной цели или заданному результату за конечное число шагов.
Любой алгоритм составляется в расчете на конкретного исполнителя с учетом его возможностей. Исполнитель — субъект, способный исполнять некоторый набор команд. Совокупность команд, которые исполнитель может понять и выполнить, называется системой команд исполнителя.
Для выполнения алгоритма исполнителю недостаточно только самого алгоритма. Выполнить алгоритм — значит применить его к решению конкретной задачи, т. е. выполнить запланированные действия по отношению к определенным входным данным. Поэтому исполнителю необходимо иметь исходные (входные) данные — те, что задаются до начала алгоритма.
В результате выполнения алгоритма исполнитель должен получить искомый результат — выходные данные, которые исполнитель выдает как результат выполненной работы. В процессе работы исполнитель может создавать и использовать данные, не являющиеся выходными, — промежуточные данные.
Свойства алгоритмов
Алгоритм должен обладать определенными свойствами. Наиболее важные свойства алгоритмов:
- Дискретность. Процесс решения задачи должен быть разбит на последовательность отдельных шагов — простых действий, которые выполняются одно за другим в определенном порядке. Каждый шаг называется командой (инструкцией). Только после завершения одной команды можно перейти к выполнению следующей.
- Конечность. Исполнение алгоритма должно завершиться за конечное число шагов; при этом должен быть получен результат.
- Понятность. Каждая команда алгоритма должна быть понятна исполнителю. Алгоритм должен содержать только те команды, которые входят в систему команд его исполнителя.
- Определенность (детерминированность). Каждая команда алгоритма должна быть точно и однозначно определена. Также однозначно должно быть определено, какая команда будет выполняться на следующем шаге. Результат выполнения команды не должен зависеть ни от какой дополнительной информации. У исполнителя не должно быть возможности принять самостоятельное решение (т. е. он исполняет алгоритм формально, не вникая в его смысл). Благодаря этому любой исполнитель, имеющий необходимую систему команд, получит один и тот же результат на основании одних и тех же исходных данных, выполняя одну и ту же цепочку команд.
- Массовость. Алгоритм предназначен для решения не одной конкретной задачи, а целого класса задач, который определяется диапазоном возможных входных данных.
Способы представления алгоритмов:
- словесная запись (на естественном языке). Алгоритм записывается в виде последовательности пронумерованных команд, каждая из которых представляет собой произвольное изложение действия;
- блок–схема (графическое изображение). Алгоритм представляется с помощью специальных значков (геометрических фигур) — блоков;
- формальные алгоритмические языки. Для записи алгоритма используется специальная система обозначений (искусственный язык, называемый алгоритмическим);
- псевдокод. Запись алгоритма на основе синтеза алгоритмического и обычного языков. Базовые структуры алгоритма записываются строго с помощью элементов некоторого базового алгоритмического языка.
Словесная запись алгоритма
Произвольное изложение этапов алгоритма на естественном языке имеет свои недостатки. Словесные описания строго не формализуемы, поэтому может быть нарушено свойство определенности алгоритма: исполнитель может неточно понять описание этапа алгоритма. Словесная запись достаточно многословна. Сложные задачи трудно представить в словесной форме.
■ Пример 1. Записать в словесной форме правило деления обыкновенных дробей.
Решение.
Шаг 1. Числитель первой дроби умножить на знаменатель второй дроби.
Шаг 2. Знаменатель первой дроби умножить на числитель второй дроби.
Шаг 3. Записать дробь, числителем которой являет результат выполнения шага 1, знаменателем — результат выполнения шага 2.
Описанный алгоритм применим к любым двум обыкновенным дробям. В результате его выполнения будут получены выходные данные — результат деления двух дробей (исходных данных).
Формальные исполнители алгоритма
Формальный исполнитель — это исполнитель, который выполняет все команды алгоритма строго в предписанной последовательности, не вникая в его смысл, не внося ничего в алгоритм и ничего не отбрасывая. Обычно под формальным исполнителем понимают технические устройства, автоматы, роботов и т. п. Компьютер можно считать формальным исполнителем.
Программы на языке произвольного формального исполнителя могут состоять только из элементарных команд, которые входят в его систему (которые исполнитель «понимает»).
Исполнитель может иметь свою среду (например, систему координат, клеточное поле и др.). Среда исполнителя — это совокупность объектов, над которыми он может выполнять определенные действия (команды), и связей между этими объектами. Алгоритмы в этой среде выполняются исполнителем по шагам.
■ Пример 2. Исполнитель Крот имеет следующую систему команд:
- вперед k — продвижение на указанное число шагов вперед;
- поворот s — поворот на s градусов по часовой стрелке;
- повторить m [команда1 … командаN] — повторить m раз серию указанных команд.
Какой след оставит за собой исполнитель после выполнения следующей последовательности команд?
Повторить 5 [вперед 10 поворот 72]
Решение. Команда вынуждает исполнителя 5 раз повторить набор действий: пройти 10 шагов вперед и повернуть на 72° по часовой стрелке. Так как поворот происходит на один и тот же угол, то за весь путь исполнитель повернет на 5 х 72° = 360°. Поскольку все отрезки пути одинаковой длины и сумма внешних углов любого многоугольника составляет 360°, то в результате будет оставлен след в форме правильного пятиугольника со стороной в 10 шагов исполнителя.
Заметим, что если увеличить количество повторов серии команд, то исполнитель будет повторно передвигаться по тем же отрезкам (произойдет повторное движение по тому же пятиугольнику).
■ Пример 3. В системе команд предыдущего исполнителя Крот сформировать алгоритм вычерчивания пятиступенчатой лестницы (длина ступеньки — 10 шагов исполнителя).
Решение. За каждый шаг цикла должно происходить 4 действия: движение вперед на 10 шагов исполнителя, поворот на 90° по часовой стрелке, еще 10 шагов вперед и поворот на 90° против часовой стрелки (= 270° по часовой). В результате за один шаг цикла формируется ломаная из двух отрезков длиной 10 под прямым углом. За пять таких шагов сформируется 5–ступенчатая лестница (ломаная будет содержать 10 звеньев).
Повторить 5 [вперед 10 поворот 90 вперед 10 поворот 270]
Блок–схема
Блок–схема — наглядный способ представления алгоритма. Блок–схема отображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий. Определенному типу действия соответствует определенная геометрическая фигура блока. Линии, соединяющие блоки, определяют очередность выполнения действий. По умолчанию блоки соединяются сверху вниз и слева направо. Если последовательность выполнения блоков должна быть иной, используются направленные линии (стрелки).
Основные элементы блок–схемы алгоритма:
Общий вид блок–схемы алгоритма:
■ Пример 4. Алгоритм целочисленных преобразований представлен в виде фрагмента блок–схемы. Знаком := в нем обозначен оператор присваивания некоторого значения указанной переменной. Запись X := 1 означает, что переменная Х принимает значение 1.
Определить результат работы алгоритма для исходных данных Х = 7, Y = 12.
Решение.
- Блок ввода данных определит исходные значения переменных Х и Y (7 и 12 соответственно).
- В первом условном блоке осуществляется сравнение значений Х и Y. Поскольку условие, записанное в блоке, неверно (7 < 12), происходит переход по линии «нет».
- Во втором условном блоке выполняется второе сравнение, которое для исходных данных оказывается верным. Происходит переход по линии «да».
- Вычисляется результат выполнения алгоритма: X := 0, Y := 1.
Ответ: X := 0, Y := 1.
Алгоритмические языки
Алгоритмический язык — это искусственный язык (система обозначений), предназначенный для записи алгоритмов. Он позволяет представить алгоритм в виде текста, составленного по определенным правилам с использованием специальных служебных слов. Количество таких слов ограничено. Каждое служебное слово имеет точно определенный смысл, назначение и способ применения. При записи алгоритма служебные слова выделяют полужирным шрифтом или подчеркиванием.
В алгоритмическом языке используются формальные конструкции, но нет строгих синтаксических правил для записи команд. Различные алгоритмические языки различаются набором служебных слов и формой записи основных конструкций.
Алгоритмический язык, конструкции которого однозначно преобразуются в команды для компьютера, называется языком программирования. Текст алгоритма, записанный на языке программирования, называется программой.
Псевдокод
Псевдокод занимает промежуточное положение между естественным языком и языками программирования. Пример псевдокода — учебный алгоритмический язык. Алфавит учебного алгоритмического языка является открытым. Существенным достоинством этого языка является то, что его служебные слова, конструкции и правила записи алгоритма весьма схожи с теми, что применяются в распространенных языках программирования. Благодаря этому учебный алгоритмический язык позволяет легче освоить основы программирования.
Служебные слова учебного алгоритмического языка:
Стандартная структура алгоритма
Представление алгоритма на алгоритмическом языке (в том числе и языке программирования) состоит из двух частей. Первая часть — заголовок — задает название алгоритма и включает описание переменных, которые используются в нем. Вторая часть — тело алгоритма — содержит последовательность команд алгоритма.
Общий вид записи алгоритма на учебном алгоритмическом языке:
В начале заголовка записывается служебное слово алг, после чего указывается имя алгоритма. Описание переменных, являющихся аргументами алгоритма и его результатами, приводится после названия в круглых скобках.
В следующих строках конкретизируют, какие именно переменные являются аргументами алгоритма (входными данными), а какие — его результатами (выходными данными). Для этого после служебного слова арг приводится список имен переменных–аргументов; в следующей строке после служебного слова рез приводится список имен переменных–результатов.
Между служебными словами нач и кон размещается тело алгоритма — конечная последовательность команд, выполнение которых предписывает алгоритм. Команды алгоритма записывают одну за одной в отдельных строках. В случае необходимости можно записать две или более команд в одной строке, тогда соседние команды разделяют точкой с запятой. Если в алгоритме применяются промежуточные переменные, их описание приводят в начальной строке тела алгоритма рядом со словом нач.
Примеры заголовков алгоритмов:
В первом примере алгоритм имеет название Объем_шара, один вещественный аргумент Радиус и один вещественный результат Объем. Во втором примере алгоритм под названием Choice имеет три аргумента — целые M и N и логический b, а также два результата — вещественные Var1 и Var2.
Пример алгоритма вычисления гипотенузы прямоугольного треугольника:
На вход алгоритму даются два вещественных аргумента a и b (величины катетов), результатом является вещественная переменная с (гипотенуза). Для ее расчета используется функция вычисления квадратного корня sqrt.
Описание величин и действия над ними
При описании алгоритма необходимо указать названия (обозначения) всех величин, которые будут в нем найдены или использованы.
При представлении алгоритма решения в виде блок–схемы выбранные обозначения величин приводятся отдельно от блок–схемы (как объяснение к ней). Если алгоритм представлен на языке программирования, то характеристика обрабатываемых величин включается в программу. Учебный алгоритмический язык также предусматривает описание величин, используемых в алгоритме.
Все величины в алгоритме разделяют на постоянные (константы) и переменные. Константа не может изменять свои значения в процессе работы алгоритма. Переменная может приобретать различные значения, которые сохраняются до тех пор, пока она не получит новое значение. Переменным величинам назначают имена. Таким образом, переменная — это именуемая величина, которая в процессе выполнения алгоритма может приобретать и хранить различные значения.
В алгоритмическом языке не существует специальных правил именования переменных. Однако их названия не должны совпадать со служебными словами алгоритмического языка. Во многих языках программирования для имен можно использовать только латинские буквы, цифры, знак подчеркивания. Имена обязательно должны начинаться с буквы, при этом строчные и прописные буквы в именах не различаются. В одном алгоритме не могут существовать разные объекты с одинаковыми именами. Все имена являются уникальными. Имена переменных и констант стараются выбирать так, чтобы они напоминали их смысл. Например, имена переменных и констант: S, p12, result, итог.
При представлении алгоритма на алгоритмическом языке именуются не только величины, но и сам алгоритм, и другие объекты. Имя алгоритма выбирают так же, как и имена переменных.
Величина — переменная, с которой связывается определенное множество значений. Этой величине присваивается имя (в языках программирования его называют идентификатор).
Значение — то, чему равна переменная в конкретный момент. Значение переменной можно задать двумя способами: присваиванием и с помощью процедуры ввода.
Тип переменной определяет диапазон всех значений, которые может принимать данная переменная, и допустимые для нее операции. Существует несколько предопределенных типов переменных. К стандартным типам относятся числовые, литерные и логические типы.
Числовой тип предназначен для обработки числовых данных. Различают целый и вещественный числовые типы. Целый тип в учебном алгоритмическом языке обозначается служебным словом цел, к нему относятся целые числа некоторого определенного диапазона. Они не могут иметь дробной части, даже нулевой. Число 123,0 является не целым, а вещественным числом. Вещественные величины относятся к вещественному типу данных и обозначаются в учебном алгоритмическом языке служебным словом вещ. Такие величины могут отображаться двумя способами: в форме с фиксированной запятой (например, 0,0511 или –712,3456) и с плавающей запятой (те же примеры: 5,11*10-2 и –7,123456*102).
Над числовыми данными можно выполнять арифметические операции и операции сравнения.
Над целыми числами можно также выполнять две операции целочисленного деления div и mod. Операция div обозначает деление с точностью до целых чисел (остаток от деления игнорируется). Операция mod позволяет узнать остаток при делении с точностью до целых чисел. Например, результатом операции 100 div 9 будет число 11, а результатом 100 mod 9 — число 1.
Литерный тип представляет собой символы и строки, он дает возможность работать с текстом. Литерные величины — это произвольные последовательности символов. Эти последовательности заключаются в двойные кавычки: «результат», «sum_price». В качестве символов могут быть использованы буквы, цифры, знаки препинания, пробел и некоторые другие специальные знаки (возможными символами могут быть символы таблицы ASCII). В учебном алгоритмическом языке литерные величины обозначаются лит.
Над литерными величинами возможны операции сравнения и слияния. Сравнение литерных величин производится в соответствии с их упорядочением: «a» < «b», «b» < «с» и т. д. Слияние (конкатенация) литерных величин приводит к образованию новой величины: «пол» + «е» образует «поле».
Логический тип определяет логические переменные, которые могут принимать только два значения — истина (True) или ложь (False). Над логическими величинами можно выполнять все стандартные логические операции.
Команды учебного алгоритмического языка
Учебный алгоритмический язык использует следующие команды для реализации алгоритма:
ОПЕРАЦИЯ ПРИСВАИВАНИЯ
Ко всем типам величин может быть применена операция присваивания, которая обозначается знаком «:=» и служит для вычисления выражения, стоящего справа, и присваивания его значения переменной, указанной слева. Например, если переменная H имела значение 12, а переменная М — значение 3, то после выполнения оператора присваивания H := М + 10 значение переменной H изменится и станет равным 13.
Вычисления в операторе присваивания выполняются справа налево: сначала необходимо вычислить значение выражения справа от знака присваивания. Поэтому допустимы конструкции вида H := Н + 10. В этом случае сначала будет вычислено выражение в правой части (12 + 10), а его результат будет присвоен в качестве нового значения переменной Н (значение 22).
Для оператора присваивания обязательно должны быть определены значения всех переменных в его правой части. Кроме того, типы данных в левой и правой части должны соответствовать друг другу.
ВВОД И ВЫВОД ДАННЫХ
В процессе работы алгоритма происходит обработка исходных данных для получения выходных (результирующих) данных. В процессе этого преобразования могут быть найдены некоторые промежуточные результаты. Входные данные должны быть переданы алгоритму («введены»), а по окончании работы алгоритм должен вывести результат.
При записи алгоритма с помощью блок–схемы ввод и вывод данных отображаются с помощью блоков ввода/вывода (параллелограммов). При этом только указывается перечень данных для ввода или вывода, а сам процесс не детализируется.
Описание алгоритма средствами псевдокода может вовсе не предусматривать команды ввода или вывода данных. В заголовке алгоритма указывается, какие данные являются аргументами, какие — результатами работы алгоритма. Считается, что аргументы будут предоставлены до выполнения алгоритма, результаты будут выведены после его выполнения, и описывается лишь процесс превращения аргументов в результаты.
В записи алгоритма с помощью учебного алгоритмического языка для операций ввода/вывода используются команды ввод и вывод. После этих служебных слов указывается список ввода или вывода. Элементы этих списков перечисляются через запятую.
Список ввода может содержать только имена переменных. После выполнения команды ввод алгоритм получит значения перечисленных в списке переменных.
Список вывода может содержать имена переменных, константы и выражения. Если в списке вывода указано имя переменной, будет выведено ее значение. Если список вывода содержит выражение, будет выведен результат его вычисления. Текстовые константы следует записывать в списке вывода в кавычках (выводиться они будут без кавычек).
Если при выполнении алгоритма ввести значения 20 и 10, то переменная v примет значение 20, а переменная t — значение 10. По окончании работы алгоритма будет выведен результат:
Путь 200 м
Тот же результат был бы получен, если бы изменить строку вывода на
вывод «Путь «, v * t, » м»
Конспект по информатике «Алгоритм. Свойства алгоритмов. Блок-схемы. Алгоритмические языки».
Вернуться к Списку конспектов по информатике.
План урока:
Алгоритмы, которыми мы пользуемся
Исполнители, система команд исполнителя (СКИ)
Свойства алгоритмов
Классификация алгоритмов
Виды записи алгоритмов
Пример алгоритма на Turbo Pascal
Начнем урок с простой задачи. Что нужно сделать, если хочется выпить чая?
Один человек сразу включает чайник, потом начинает искать чашки, заварку, сахар.
Второй действует согласно плану:
- Проверить наличие заварки и сахара.
- Если их нет, купить.
- Если все есть, найти чашку, проверить ее чистоту.
- Поставить чайник греться.
- Ополоснуть чашку кипятком.
- Насыпать заварку, залить кипятком.
- Добавить сахар.
Первый человек сразу бежит к цели, сломя голову, а второй – определяется с целью, разбивает сложный процесс на простые этапы и шаг за шагом идти к результату. Такой линейный алгоритм из жизни позволяет не запутаться, не пропустить что-то важное. Второй подход рациональнее, логичнее и удобнее, позволяет сложную задачу разбить на более простые.
Система команд или алгоритм, не просто удобнее, она позволяет выполнить задачу даже тому, кто не делает это часто, то есть новичку.
Алгоритмы, которыми мы пользуемся
Алгоритм – конечная последовательность действия, пошаговый план, инструкция, способ действия позволяющие достичь желаемого результата. Состоит из простейших команд.
Такие удобные инструкции мы используем постоянно, даже не осознавая это.
Давайте вспомним, какими детальными инструкциями мы пользуемся:
- пошаговые кулинарные рецепты;
- мастер-классы по рукоделию;
- инструкции к оборудованию;
- план действия при ЧП.
Имея цель, мы обрабатываем входные данные и получаем результат или объяснение, почему результат не может быть получен. Это напоминает функцию, но в случае с алгоритмами даны четкие рекомендации, что и как делать.
Пример в виде красочной инструкции и сухой пошаговой рекомендации:
Работа за компьюетром Инструкция по настройке
А в информатике без них не обойтись – именно на алгоритмах основано программирование.
При написании такой последовательности команд важно разбивать процесс на самые простые действия, которые понимаются однозначно как разработчиком, так и тем, кто будет ими пользоваться.
Если действия однотипные, например, «набрать ковш воды и вылить» или «взять яблоко и проверить, есть ли червоточина», то его записывают 1 раз и повторяют конечное число раз.
Когда все задания/этапы будут выполнены, они должны привести к желаемому результату.
Исполнители, система команд исполнителя (СКИ)
Алгоритм разрабатывается с учетом определенного исполнителя. Это означает, что инструкция для пользователя спутниковой антенны и рекомендации для инженера-настройщика будут совершенно разными, хотя в обоих случаях каждый этап будет элементарный.
Исполнитель – субъект/объект, который может выполнить команды данного алгоритма.
Исполнителем может быть живое существо и неживой механизм. Человек, животное, которое понимает команды, робот, станок, компьютер – все они могут быть исполнителями.
Компьютер (ПК) – автоматизированный исполнитель команд. Алгоритмы программ для ПК пишут на языках программирования (С++, Basic, Pascal, Delphi, Ассемблер, Фортран).
Для каждого типа и уровня исполнителей существует своя система команд исполнителя (СКИ).
Свойства алгоритмов
Независимо от того, разрабатывается ход приготовления яичницы или запуска космического корабля, они должны обладать 5 основными свойствами:
- Детерминированность – все описания должны быть однозначными, понятными.
Понятность – процедура должна быть на языке, который понятен той категории исполнителей, для которых она пишется.
Для ребенка 2 лет обучение пользованию игрушкой будет происходить простыми словами, с минимумом этапов (возьми, нажми эту кнопочку, поставь на пол). А для ребенка 10 лет инструкция уже будет включать проверку и замену батареек, установку отпавшей части.
- Дискретность – строгие команды, идущие в определенной последовательности.
Точность – команды должны быть конкретными, понятными, однозначными.
Пример непонятного и неточного задания мы помним из сказки: “Пойди туда, не знаю куда. Принеси то, не знаю что”.
- Массовость – план действия подходит под аналогичные ситуации с разными исходными данными. То есть инструкция по приготовлению бутерброда с колбасой позволяет брать разный хлеб и мясопродукт или заменить его сыром.
- Результативность – выполнение команд должно приводить к результату. Не должно быть ошибок. При использовании допустимых исходных параметров алгоритм должен давать правильный результат всегда.
- Конечность – каждая команда и процедура в целом должны выполняться за конечное число шагов, то есть он не должен быть бесконечным, зацикленным.
Пример бесконечного алгоритма
Мытье рук:
- включить воду;
- намочить руки и мыло;
- выключить воду;
- намылить руки;
- включить воду.
В этом примере нет конечных команд: вымыть руки и выключить воду. Пользователь по этой инструкции будет бесконечно мыть руки, точить воду.
Классификация алгоритмов
Если выполняемые действия идут одно за другим, то инструкция будет последовательной, линейной. Если же операции повторяются при разных условиях, то порядок действия будет меняться. Следует использовать различные виды алгоритмов.
Виды алгоритмов:
- линейный – этапы выполняются один раз, друг за другом;
- алгоритм с повторением или циклический – действия повторяются необходимое количество раз или до достижения результата. Повторение действий называют циклом;
- разветвляющийся – исходя из указанного условия выбирается одна последовательность команд или другая;
- вспомогательный – процедура, которая является отдельной частью и может выполняться самостоятельно, но обычно используется в составе других алгоритмов, после указания названия.
Чаще используют алгоритмы повторения с условием, так как идеальные условия встречаются редко.
Источник
Линейная модель подходит для простых задач, когда нет условий или повторений. Для нее важна последовательность команд алгоритма. Например, вычисление среднего арифметического, площади фигуры. В обычной жизни – это список действий, которые нужно выполнить, чтобы купить хлеб, сварить яйцо или сделать бутерброд.
Запишем схему линейного алгоритма (покупки чая):
- Взять пакет и кошелек с деньгами.
- Зайти в любой продуктовый маркет.
- Выбрать нужный сорт чая.
- Заплатить за товар.
- Чай положить в пакет, пойти домой.
Для многих задач важно выполнение определенного условия.
Пример алгоритма ветвления – если нужного сорта нет, то процесс покупки чая усложняется:
- Взять пакет и кошелек с деньгами.
- Зайти в любой продуктовый маркет.
- Посмотреть, есть ли чай «Элитный».
- Если да, то узнать цену, отдать деньги.
- Покупку положить в пакет, пойти домой.
- Если нет, найти сорт «Белый, китайский», узнать цену, отдать деньги.
- Упаковку положить в пакет, вернуться домой.
- Если нет ни «Элитного», ни «Белого, китайского», то пойти в другой магазин и повторить все с пункта №3.
Эту же задачу можно описать при помощи циклического алгоритма, если есть повторение определенной операции.
Данный пример включает в себя ветвление «если» и повторение команд:
- Взять пакет и кошелек с деньгами.
- Зайти в любой продуктовый маркет.
- Взять коробку с чаем в руки, посмотреть, это сорт «Элитный».
- Если да, то узнать цену, заплатить.
- Забрать покупку, вернуться домой.
- Если нет, взять следующую упаковку и повторить пункты 3-6.
- Если весь чай перебран, но «Элитного» нет, то пойти в другой магазин и повторить все с пункта №3.
Цикличные инструкции следует писать так, чтобы не было вечного цикла или зацикливания – бесконечного повторения операции без достижения результата.
Виды записи алгоритмов
Самый простой способ записать алгоритм построчно – словесно. Но текстовая форма оформления подобных детальных инструкций не всегда наглядна и удобна из-за большого количества вспомогательных слов.
Легче воспринимается такой план, если его дополнять картинками.
Источник
Особенно неудобно описывать словами математические, физические и химические процессы. Без специальных символов, формул не обойтись. Поэтому используются отраслевые сокращения и обозначения.
Но все эти способы записи алгоритмов уступают формальному, схематическому. Именно такой обобщенный подход позволяет пользователям и исполнителям со всего мира лучше понимать друг друга.
Блок-схема – графическая форма представления алгоритмов при помощи геометрических объектов и стрелок.
Блок схема линейного алгоритма вычисления площади прямоугольника:
Алгоритм – это инструкция к решению определенной задачи. А на этом основании можно написать программу вычисления алгоритма, которая реализует данный вариант решения, плюс ее можно установить, проверить и выполнить на ПК.
Пример алгоритма на Turbo Pascal
При программировании на компьютерных языках используется такой же подход, как и при написании инструкций вручную.
Для примера попробуем программирование линейных алгоритмов при помощи языка Turbo Pascal.
Запустить среду программирования следующими шагами:
Меню Пуск → Все программы → Turbo Pascal
На экране монитора появится оболочка, которая позволяет освоить азы программирования и даже реализовывать непростые проекты.
Оболочка разработана под DOS, что объясняет необычную реализацию интерфейса.
Пишем самый простой алгоритм программы для выведения на экран слов приветствия.
На латинской раскладке набираем в синем окне такие команды:
program Test;
begin
write(‘Доброе утро!’);
end.
Учитываем важные моменты при использовании языка Турбо Паскаль:
- все пишется латинскими буквами;
- регистр неважен;
- каждая строка – команда, в конце строки ставится Enter и «;»;
- после «end» должна быть «.».
Как видим, в программе есть свои слова-команды, как в письменных алгоритмах. Слово program – как заголовок, название объекта, а тest – непосредственно название программы.
Началом является команда begin, end – окончанием, а между ними стоят операторы или команды-действия («write» – напиши на экране). А текст, который нужно выводить на экране берется в скобки и ’….’.
Чтобы запустить программу, следует нажать Ctrl+F9 или набор команд Run Run.
Если нет ошибок в командах, появится такой результат:
Чтобы выйти обратно, можно нажать любую кнопку клавиатуры.
При каждом запуске будет новая запись, на той же строке. Если заменить write на writeln, то текст будет выводиться в новой строчке:
Изучение алгоритмов не только позволяет применять их во всех сферах жизни, начиная с ежедневных домашних дел и заканчивая учебой. Это первый и один из важнейших шагов понимания работы программируемой техники, в том числе ПК. Понимание простейших, линейных алгоритмов, умение их создавать позволяет узнать, как компьютер обрабатывает данные, находит верный результат и выдает его. Далее следует осваивать варианты с ветвлением или повторением.
Без умения создавать алгоритмы в виде блок-схемы, знания их видов и принципов создания невозможно начать изучение языков программирования.
Каждый человек на протяжении своей жизни решает множество задач разной сложности. Но даже самые простые из задач выполняются последовательно, то есть за несколько шагов. Эту последовательность можно назвать алгоритмом. Последовательности бывают разные, но начинать их изучение лучше всего с линейных.
Прежде чем приступить к рассмотрению основной темы статьи, следует сделать краткое отступление и сказать несколько слов про алгоритмический язык.
Алгоритмический язык
Представьте, что человеку, работающему за компьютером, поставлена некая вычислительная задача. В языке программирования решение этой задачи выполняется с помощью алгоритмизации. Решение предполагает:
— разбиение на этапы;
— разработку алгоритма;
— составление программы решения на алгоритмическом языке;
— ввод данных;
— отладку программы (возможны ошибки — их надо исправить);
— выполнение на ПК;
— анализ результатов.
Алгоритмический язык является средством описания алгоритмов, а уже алгоритм, в свою очередь, представляет собой чёткое описание определённой последовательности действий, направленных на решение необходимой задачи.
Свойства алгоритма
Их несколько:
— конечность. Любой алгоритм должен быть завершённым, а окончание наступает после выполнения определённого числа шагов;
— однозначность, понятность. Не допускается разных толкований, неопределённости и двусмысленности — всё должно быть чётко и ясно, а также понятно исполнителю — и правила выполнения действий линейного алгоритма, и сами действия;
— результативность. Итог работы — результат, полученный за конечное число шагов;
— универсальность, массовость. Качественный алгоритм способен решать не одну задачу, а целый класс задач, имеющих схожую постановку/структуру.
Линейная структура
Любой алгоритм составляется из ряда базовых структур. Простейшей базовой структурой является следование — структура с линейными характеристиками. Из этого можно сформулировать определение.
Линейный алгоритм — это алгоритм, образуемый командами, которые выполняются однократно и именно в той последовательности, в которой записаны. Линейная структура, по сути, проста. Записать её можно как в текстовой, так и в графической форме.
Представим, что у нас стоит задача пропылесосить ковёр в комнате. В текстовой форме алгоритм будет следующим:
— принести пылесос к месту уборки;
— включить;
— пропылесосить;
— выключить;
— унести пылесос.
И каждый раз, когда нам надо будет пылесосить, мы будем выполнять один и тот же алгоритм.
Теперь поговорим про графическую форму представления.
Блок-схема
Для изображения алгоритма графически используют блок-схемы. Они представляют собой геометрические фигуры (блоки), соединённые стрелками. Стрелки показывают связь между этапами и последовательность их выполнения. Каждый блок сопровождается надписью.
Рассмотрим фигуры, которые используются при визуализации типичной линейной последовательности.
Блок начала-конца:
Блок ввода-вывода данных (отображает список вводимых и выводимых переменных):
Арифметический блок (отображает арифметическую операцию/группу операций):
Условный блок (позволяет описать условие). Алгоритмы с таким блоком используются при графической визуализации алгоритмов с ветвлением:
Условного блока нет в классическом линейном алгоритме, так как в нём, как уже было сказано ранее, все операции выполняются последовательно, то есть одна за другой. В линейном алгоритме размещение блоков выглядит следующим образом:
А вот, как решается задача по нахождению площади треугольника по формуле Герона. Здесь a, b, c – это длины сторон, S – площадь треугольника, P – периметр.
Следует обратить внимание, что запись «=» — это не математическое равенство, а операция присваивания. В результате этой операции переменная, стоящая слева от оператора, получает значение, которое указано справа. Значение не обязательно должно быть сразу определено (a = 3) — оно может вычисляться посредством выражения (a = b + z), где b = 1, a z = 2.
Примеры линейных алгоритмов
Если рассмотреть примеры решения на языке Pascal (именно этот язык до сих пор используется для изучения основ алгоритмизации и программирования), то можно увидеть следующую картину:
И, соответственно, блок-схема программы линейной структуры будет выглядеть следующим образом:
Как составить программу линейной структуры?
Порядок следующий:
— определите, что именно относится к исходным данными, а также каков типы/класс этих данных, выберите имена переменных;
— определите, каков тип данных будет у искомого результата, выберите название переменных (переменной);
— определите, какие математические формулы связывают результат и исходные данные;
— если требуется наличие промежуточных данных, определите класс/типы этих данных и выберите имена;
— опишите все используемые переменные;
— запишите окончательный алгоритм. Он должен включать в себя ввод данных, вычисления, вывод результатов.
На этом всё, в следующий раз рассмотрим на примерах программу разветвлённой структуры. Если же вас интересует тема алгоритмизации в контексте разработки программного обеспечения, ждём вас на профессиональном курсе OTUS!
Источники:
• https://inep.sfedu.ru/wp-content/uploads/2018/05/25/lection_27.pdf;
• https://www.sites.google.com/site/415ict/textbooks/prog-9/02-linejnyj-algoritm.