УРОК 1.
Введение в алгоритмизацию и простые алгоритмы на Python
Введение
Основы алгоритмизации
Когда вы думаете над задачей, вы строите в голове путь к её решению. Последовательность действий, которая ведёт к результату — это и есть алгоритм. С одним условием: решение должно быть применимо к разным исходным данным. Обобщим сказанное в одной формулировке.
Понятие алгоритма
Классический алгоритм — это совокупность действий (инструкций), которая приводит к достижению результата за конечное число шагов.
Почему мы говорим «совокупность», а не «последовательность»? Потому что действия в алгоритме не всегда выполняются последовательно — они могут повторяться, меняться местами или опускаться в зависимости от заданных условий.
Для более глубокого понимания алгоритма посмотрим, какими свойствами он должен обладать, чтобы с его помощью удобно было решать задачи.
Свойства алгоритмов:
1. Дискретность (прерывность, раздельность). Алгоритм должен состоять из элементарных действий, которые выполняются последовательно. Пока не закончится выполнение одного действия, следующее не начинается.
2. Детерминированность. Все действия в алгоритме должны быть строго определены: ни одно из них не может двояко трактоваться исполнителем.
3. Конечность. Алгоритм должен выполняться за определенное количество шагов.
4. Массовость. Алгоритм должен вести к результату при любых исходных данных.
5. Результативность. Работа алгоритма всегда должна приводить к ожидаемому результату.
Основная цель алгоритмизации — составление алгоритмов для определенного класса задач, решаемых исполнителем.
Несколько примеров алгоритма из повседневной жизни:
1. Инструкция по эксплуатации бытового прибора — это, по сути, алгоритм правильного пользования устройством.
2. Правила дорожного движения однозначно регламентируют поведение всех участников движения. Когда водитель соблюдает правила, он действует по определенному алгоритму.
3. Чтобы запустить массовое промышленное производство, нужно определить порядок (алгоритм) сборки продукции на конвейере. Алгоритм сборки — это набор действий, в результате выполнения которых мы получаем продукт.
Способы представления алгоритма
Разработку алгоритма можно условно разбить на три этапа:
● обдумывание общей идеи алгоритма,
● формализация идей,
● написание программного кода — реализация алгоритма для конкретного исполнителя.
На каждом этапе алгоритм принимает разную форму. Сначала мы описываем ход решения задачи словами. Это называется «словесное представление». Затем мы постепенно конкретизируем алгоритм (создаём псевдокод, блок-схему) и в итоге приходим к цельной конкретизированной реализации алгоритма — описываем его с помощью алгоритмического языка.
Итак, формы представления алгоритма, т.е. виды формализации алгоритма:
● словесная — на естественном языке;
● псевдокод — описание алгоритма на искусственном (формальном) языке с использованием зарезервированных ключевых слов. В псевдокоде отсутствуют несущественные для понимания алгоритма человеком детали: описания переменных, системно-зависимый код, директивы компилятора и др.;
● блок-схема — графическое представление;
● код программы — на алгоритмическом языке программирования.
Чтобы понять, как это работает, решим задачу — найдем частное двух чисел.
Сначала опишем порядок обработки данных словами:
● Шаг 1. Получаем на вход два числа, одно из них делимое, второе — делитель.
● Шаг 2. Проверяем, не нарушается ли математическое правило деления на нуль.
● Шаг 3. Если правило деления на нуль не нарушено и делитель не равен нулю, рассчитываем частное и запоминаем ответ.
● Шаг 4. Если правило деления на нуль нарушено и делитель равен нулю, рассчитывать частное мы не можем и задача не имеет решения.
Исполнитель алгоритма в данном случае — человек, который выполняет наши инструкции.
Чем плохо словесное описание? Оно лишено строгой формализации: высказывания могут быть избыточными и даже противоречить друг другу. Мы не достигаем свойств алгоритма, о которых говорили выше.
Теперь посмотрим на псевдокод. Это симбиоз словесной и программной форм. Плюс в том, что мы пишем алгоритм на языке, близком к естественному, но при этом можем пользоваться формальными конструкциями и математическими символами.
У псевдокода нет строгих синтаксических правил, поэтому он удобен на этапе проектирования алгоритма. От такого проекта легко перейти к реализации алгоритма на конкретном формальном языке. Поэтому псевдокод — промежуточное звено между описанием алгоритма для человека и описанием для вычислительного исполнителя.
Система команд псевдокода в табл. 1.1.
| Название структуры | Псевдокод |
| Присваивание | = |
| Ввод | Ввод (данные) |
| Вывод | Вывод (данные) Вывод (“строка”) |
| Ветвление | Если условие то действие иначе действие |
| Повторение | Пока условие начало пока действие конец пока |
Представим алгоритм решения нашей задачи в псевдокоде:
| Начало вывод ("введите два числа") ввод (первого числа) ввод (второго числа) если (второе число) делитель <> нуля то частное = (первое число) делимое / (второе число) делитель вывод (“Результат: =” частное) иначе вывод ("нет решения") конец алгоритма |
Мы используем три переменные. Первая хранит делимое, вторая — делитель, третья — частное. Делимое и делитель вводятся с клавиатуры. Частное считаем только при условии, что не нарушается правило деления на нуль.
Чтобы выбросить из псевдокода всё лишнее, представим алгоритм в виде блок-схемы.
Блок-схема
Блок-схему строят из графических функциональных блоков. Каждое действие алгоритма представляют отдельной геометрической фигурой. Чтобы показать последовательность выполнения действий, блоки связывают соединительными линиями.
Это позволяет наглядно описать алгоритм человеку, даже незнакомому с предметной областью, в которой работает алгоритм. Элементы блок-схемы определены стандартом «ГОСТ 19.701-90. Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения».
| Таблица 1.2. Базовые элементы блок-схемы | ||
| Название | Обозначение | Функция |
| Терминатор | 
| Определяет начало и конец алгоритма. |
| Процесс | 
| Определяет процесс выполнения одного или нескольких действий (шагов). |
| Решение | 
| Определяет ход алгоритма (решение) и отображает альтернативные ветви алгоритма. |
| Предопределенные процесс | 
| Определяет функции (отдельные подпрограммы основного алгоритма). |
| Данные | 
| Определяет действия ввода/вывода данных. |
| Соединитель | 
| Определяет переход между частями блок-схемы, когда необходимо ее разбить на части. |
| Комментарий | 
| Пояснение какого-либо действия алгоритма. |
Исполнители алгоритма
Исполнитель алгоритма — это абстрактная или реальная (техническая, биологическая, биотехническая) система, способная выполнить предписанные в алгоритме действия. Исполнителями могут быть физические устройства или специальные программы — среды разработки.
Исполнителя характеризуют:
● среда разработки алгоритма (JetBrains PyCharm, JetBrains IDEA Community и т.д.);
● простые действия;
● система команд (язык программирования: Java, Python, C++ или др.);
● отказы.
Виды алгоритмов
По способу организации алгоритмы бывают трёх видов:
- Линейный. Пример: движение по карте из одной точки в другую.
- Разветвляющийся. Пример: «Чай или кофе?»
- Циклический. Пример: работа часов.
Разберем каждый вид алгоритма подробнее.
Линейный алгоритм
В линейном алгоритме, который еще называют следованием, все действия выполняются одно за другим и только один раз.
Когда вы прокладываете путь из пункта А в пункт Б, вы создаёте линейный алгоритм. Давайте представим алгоритм, по которому студент возвращается домой из университета.
Как убедиться, что это линейный алгоритм? Все действия следуют одно за другим, выполняются однократно и без условий.