План урока:

Базовые алгоритмы

Вспомогательные алгоритмы

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

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

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

Базовые алгоритмы

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

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

Следование

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

Плакат для детского сада с линейным алгоритмом

Особенности алгоритмической конструкции следование:

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

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

 
Пример использования линейного алгоритма для записи рецепта Источник

Ветвление

Если решение задачи может меняться в зависимости от определенного условия, появляется «если», возникает необходимость в разветвлении хода решения, в одном случае будет один перечень команд, в другом – иной. Таким образом, это конструкция с несколькими альтернативными блоками команд, выбор того или иного пути зависит от выполнения условий/значения входных данных.

Мама дает указание, как попасть на представление Источник

Чтобы кратко записать условие, используют операции сравнения: >, < или =, логические связки (и, или, не). Для универсализации переменные обозначают большими латинскими буквами.

Если в задаче одно сравнение, то это простое условие, а если несколько – составное, сложное.

Особенности алгоритмической конструкции ветвления:

• не линейная;
• выполняемые команды будут зависеть от входных данных, есть от того, выполняется ли указанное условие (вопрос, на который есть ответ «да/нет»);
• есть полная и неполная форма ветвления.

Алгоритмы решения на базе такой структуры называют разветвляющимися.

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

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

Пример решения одной задачи при помощи полной (а) и неполной (б) форм:

Нахождение модуля числа 

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

Плакат, как правильно себя вести, если расстроен или зол Источник

Повторение

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

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

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

• Продолжения выполнения цикла (цикл-пока или конструкция с предусловием).
• Окончания работы алгоритма (цикл-до или структура с постусловием).
• Заданное число повторений (с параметром).

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

Цикл с предусловием

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

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

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

Цикл с постусловием

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

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

Схемы циклических алгоритмов на примерах:

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

Цикл с параметром

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

Параметр или счетчик цикла – величина, которая изменяется на определенный шаг с каждым выполнением команд. Параметр имеет исходное значение, он является целым числом, в процессе выполнения параметр постоянно сравнивается с условием, пока не достигнет указанного максимума. Шаг=1 не пишут, это значение по умолчанию. Благодаря счетчику в таких программах нет зацикливания.

На этом популярном ныне плакате указан линейный алгоритм выполнения гигиенической процедуры. Но в конце мы видим указанием на повтор выполняемых действий – повторить этапы для второй руки. Если бы процесс описывался в виде блок-схемы, очистка одной руки была бы выделена в отдельное тело цикла с указанием количества раз – 2 раза, по 1 разу для каждой руки.

Еще гигиенический пример – чистить зубы 3 минуты, то есть выполнять очищающие движения по наружной и внутренней стороне зубов, пока не истечет указанное время. Можно указать, сколько раз нужно пройтись по каждому зубу (приблизительно по 10 движений в одной точке), но так сложнее – количество зубов, их размеры отличаются у людей разного возраста, как и скорость движений.

Разные циклические алгоритмы на примере произведения чисел 1…5:

Матмодель Р=1*2*3*4*5

Источник

Вспомогательные алгоритмы

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

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