16 статей
Здесь будет текст
В рамках этого задания мы займёмся развитием алгоритмического мышления, и будем рассматривать различные положения теории алгоритмов. Прежде всего, определим понятие «Алгоритм».
Алгоритм – это последовательность действий, преобразующая исходные данные в результат и обладающая некоторыми свойствами.
Приведённое определение не является строгим, поскольку в нём присутствует ссылка на «некоторые свойства». Чтобы подробно описать понятие Алгоритма рассмотрим эти свойства.
1) Конечность. Последовательность действий является алгоритмом только тогда, когда преобразование любых допустимых входных данных в результат происходит за конечное число шагов.
Например, можно составить алгоритм для решения задачи: «Выпишите в строчку все цифры двадцатеричной системы счисления», но нельзя составить алгоритм для решения задачи: «Выпишите все натуральные числа», поскольку в этом случае количество действий – бесконечное.
2) Детерминированность. Это свойство обозначает, что если применить алгоритм сколь угодно раз к одним и тем же входным данным, результат всегда получится одинаковым.
3) Дискретность. О данном понятии рассказывалось в рамках предыдущего задания по алгебре логики. Свойство дискретности применительно к алгоритму обозначает, что выполнение алгоритма разбивается на последовательность законченных действий. То есть каждое действие должно завершиться, прежде чем начнётся следующее.
4) Понятность. Чтобы описать это свойство, стоит упомянуть, что алгоритм всегда рассчитан на некоторого конкретного исполнителя, который умеет производить некоторый набор действий. Свойство понятности заключается в том, что все действия, входящие в алгоритм должны принадлежать к набору действий исполнителя. Набор действий, которые может исполнить исполнитель, называется «системой команд». Стоит отметить, что исполнитель не должен ничего додумывать. Его задача – исключительно исполнять команды.
5) Массовость. Это свойство означает, что алгоритм пишется не для одних конкретных входных данных, а для некоторого множества задач. В отличие от предыдущих свойств, которые являются просто неотъемлемой частью любого алгоритма, свойство массовости является ещё и характеристикой алгоритма, то есть можно говорить, что алгоритм `"A"` является более массовым, чем алгоритм `"C"`. Это будет означать, что все задачи, которые можно решить алгоритмом C также можно решить и алгоритмом `"A"`, но существуют задачи, которые можно решить алгоритмом `"A"` и нельзя решить алгоритмом `"C"`.
Рассмотрим несколько примеров исполнителей алгоритмов.
1) Исполнителем является любой человек сознательного возраста. Здесь могут решаться такие задачи как переход улицы, приём пищи, приготовление сладкого стола, украшение комнаты и т. д. Для всех перечисленных задач можно составить алгоритмы. Например, классический алгоритм перехода улицы формулируется так: «Посмотри налево, если ближе некоторого расстояния нет машин, иди до середины дороги, остановись, посмотри направо, и если ближе некоторого расстояния нет машин, то иди до конца». В приведённой формулировке есть переменная величина – безопасное расстояние, на котором могут находиться машины. Она зависит от конкретного человека, поэтому для конкретного человека наш алгоритм надо будет уточнять.
2) Исполнителем является человек, обладающий определёнными умениями. Один из простых примеров задач для такого исполнителя – это удаление аппендицита. Алгоритм составить можно, но исполнять его может не любой человек, а только тот, кто обладает умением хирургического вмешательства.
3) Исполнителем может быть робот, живущий в прямоугольном лабиринте и умеющий ходить в разные стороны. В этом случае можно поставить задачу перехода из одной точки лабиринта в другую и составить алгоритм её решения.
4) Исполнителем может являться компьютер. Здесь, как и для человека, можно поставить огромный набор задач. Примеры рассмотрим в дальнейшем.
Как уже упоминалось выше, у каждого исполнителя есть своя система команд – набор простых действий, которые может выполнить данный исполнитель. Если мы составляем алгоритм для этого исполнителя, то все шаги алгоритма должны входить в систему команд исполнителя. Наиболее простым из рассмотренных исполнителей является робот в лабиринте. Его система команд достаточно простая, и мы можем легко выписать её:
«ИДИ ВПРАВО НА 1 КЛЕТКУ»
«ИДИ ВЛЕВО НА 1 КЛЕТКУ»
«ИДИ ВВЕРХ НА 1 КЛЕТКУ»
«ИДИ ВНИЗ НА 1 КЛЕТКУ»
«ПРОВЕРЬ НАЛИЧИЕ СТЕНКИ СПРАВА»
«ПРОВЕРЬ НАЛИЧИЕ СТЕНКИ СЛЕВА»
«ПРОВЕРЬ НАЛИЧИЕ СТЕНКИ СВЕРХУ»
«ПРОВЕРЬ НАЛИЧИЕ СТЕНКИ СНИЗУ»
Очевидно, что уже у такого простого исполнителя набор команд неоднородный. Есть команды, результатом которых является сдвиг робота, а есть команды проверки, результатом которых является логическое значение «Истина» или «Ложь». (Подробно о логических значениях рассказывалось в рамках прошлого задания). Наличие команд проверки позволит нам ввести алгоритмические конструкции ветвления и цикла, но об этом чуть позже.
При изучении алгоритмов для лучшего понимания иногда мы будем пользоваться псевдоисполнителем алгоритмов, языком которого является блок-схема. Блок-схема является достаточно удобным представлением алгоритма, чтобы проследить логику его выполнения. Состоит она из блоков и связей между блоками. Связи обозначаются стрелками, которые показывают последовательность исполнения блоков. Из блоков нас будут интересовать 4 типа:
1) Начало/Конец алгоритма
2) Получение исходных данных/Выдача результатов
3) Линейное вычисление
4) Ветвление
В блок-схемы линейный участок обозначается прямоугольником. Все команды, записанные в прямоугольнике, исполняются ровно в том порядке, в котором они записаны (будем считать, что сверху вниз). Аналогично Паскалю, будем отделять команды друг от друга в линейном блоке точкой с запятой. Присваивание также будем обозначать символом «`:=`», а вот арифметическое выражение можно записывать, используя как синтаксис Паскаля, так и математики (этим можно пользоваться при решении задач). Аналогично с арифметическим, логическое выражение можно записывать, используя как синтаксис Паскаля, так и алгебры логики.
Алгоритм на языке блок-схемы всегда начинается с блока начала, затем идёт блок ввода входных данных, если они есть, далее блок вычислений, затем блок вывода результата и блок завершения алгоритма. В качестве примера рассмотрим блок-схему вычисления площади треугольника по длинам его `3` сторон с использованием формулы Герона. Входными данными в этой задаче являются длины сторон, а результатом – значение площади. Соответственно, мы будем решать задачу, используя пять переменных. Три стороны – a, b, c. Площадь – s. И полупериметр – p. Будем считать, что стороны всегда будут заданы таким образом, что треугольник существует. Рассмотрим блок-схему решения этой задачи:
В блок-схемы линейный участок обозначается прямоугольником. Все команды, записанные в прямоугольнике, исполняются ровно в том порядке, в котором они записаны (будем считать, что сверху вниз). Аналогично Паскалю, будем отделять команды друг от друга в линейном блоке точкой с запятой. Присваивание также будем обозначать символом «`:=`», а вот арифметическое выражение можно записывать, используя как синтаксис Паскаля, так и математики (этим можно пользоваться при решении задач). Аналогично с арифметическим, логическое выражение можно записывать, используя как синтаксис Паскаля, так и алгебры логики.
Алгоритм на языке блок-схемы всегда начинается с блока начала, затем идёт блок ввода входных данных, если они есть, далее блок вычислений, затем блок вывода результата и блок завершения алгоритма. В качестве примера рассмотрим блок-схему вычисления площади треугольника по длинам его `3` сторон с использованием формулы Герона. Входными данными в этой задаче являются длины сторон, а результатом – значение площади. Соответственно, мы будем решать задачу, используя пять переменных. Три стороны – a, b, c. Площадь – s. И полупериметр – p. Будем считать, что стороны всегда будут заданы таким образом, что треугольник существует. Рассмотрим блок-схему решения этой задачи:
Тест
