5.1. Алгоритмы и исполнители
Раздел 5. Основы алгоритмизации и программирования (5 часов)
Понятие алгоритма
Алгоритм — это конечная последовательность команд (шагов), выполнение которых приводит к решению задачи.
Термин происходит от имени средневекового математика аль-Хорезми (783–850), который описывал правила выполнения арифметических действий.
Свойства алгоритмов
| Свойство | Описание | Пример нарушения |
|---|---|---|
| Дискретность | Алгоритм состоит из отдельных, чётко разделённых шагов | Непрерывное описание без разделения на шаги |
| Понятность | Каждая команда понятна исполнителю | Команда «сделай красиво» — непонятна |
| Определённость | Каждая команда однозначна, нет двусмысленности | «Возьми любое число» — неопределённо |
| Результативность | Алгоритм завершается за конечное число шагов | Бесконечный цикл без условия выхода |
| Массовость | Применим к целому классу задач одного типа | Алгоритм для конкретного числа 7 — не массовый |
Способы записи алгоритмов
- Словесный — описание на естественном языке
- Графический — блок-схемы
- Псевдокод — полуформализованный язык (школьный алгоритмический язык)
- Программа — запись на языке программирования
Элементы блок-схем:
| Фигура | Название | Назначение |
|---|---|---|
| Овал | Терминатор | Начало / конец алгоритма |
| Параллелограмм | Ввод/вывод | Ввод или вывод данных |
| Прямоугольник | Действие | Выполнение операции |
| Ромб | Условие | Разветвление (выбор ветви) |
Пример словесного алгоритма:
Задача: Найти сумму двух чисел.
- Ввести первое число A
- Ввести второе число B
- Вычислить S = A + B
- Вывести результат S
Исполнители
Исполнитель — объект, способный выполнять команды алгоритма.
Характеристики исполнителя:
| Характеристика | Описание |
|---|---|
| Круг решаемых задач | Какие задачи может решать данный исполнитель |
| Среда | Объект, над которым выполняются команды |
| Режим работы | Последовательный или параллельный |
| Система команд (СКИ) | Полный набор допустимых команд исполнителя |
Примеры исполнителей:
- Черепашка — рисует на экране, перемещаясь по координатной плоскости
- Чертежник — чертит на координатной плоскости по заданным размерам
- Робот — перемещается по клетчатому полю, выполняет действия с кирпичами
СКИ Черепашки:
| Команда | Действие |
|---|---|
forward(n) | Двигаться вперёд на n единиц |
backward(n) | Двигаться назад на n единиц |
left(90) | Повернуть влево на 90° |
right(90) | Повернуть вправо на 90° |
penup() | Поднять «перо» (прекратить рисование) |
pendown() | Опустить «перо» (начать рисование) |
Объекты алгоритмов
Алгоритмы описывают последовательность действий над информационными объектами (величинами).
Постоянные и переменные:
| Тип | Описание | Пример |
|---|---|---|
| Постоянная | Значение не меняется в ходе выполнения | pi = 3.14 |
| Переменная | Значение может изменяться присваиванием | s = 0; s = s + 1 |
Операция присваивания:
Запись X := E (или X = E) означает: вычислить значение выражения E и записать его в переменную X.
a := 5 переменная a содержит значение 5. После a := a + 1 переменная a содержит значение 6.Выражения:
Выражение — это комбинация констант, переменных и операций, которая вычисляется для получения нового значения.
s := a * (b + c) / 2 # арифметическое выражение x > 0 and y > 0 # логическое выражение
Классификация алгоритмов
Как доказал Э. Дейкстра, для записи любого алгоритма достаточно трёх основных конструкций:
| Тип | Описание | Когда использовать |
|---|---|---|
| Линейный | Все команды выполняются последовательно, одна за другой | Когда каждая команда выполняется ровно один раз |
| Разветвляющийся | Выбор ветви зависит от условия («да» или «нет») | Когда действие зависит от условия |
| Циклический | Некоторые команды многократно повторяются | Когда одна и та же команда выполняется много раз |
Алгоритмическая конструкция «Следование»:
Команды выполняются строго последовательно, одна за другой.
Алгоритмическая конструкция «Ветвление»:
В зависимости от истинности условия выбирается одна из двух ветвей.
Краткая форма: если условие то A.
Алгоритмическая конструкция «Повторение»:
- Цикл со счётчиком:
для i от 1 до N— тело цикла выполняется N раз - Цикл с предусловием:
пока условие истинно— проверка условия перед каждым повторением - Цикл с постусловием:
выполнять до наступления условия— проверка после каждого повторения
Практические задачи
Задание 1. Определите вид алгоритма
Для каждой последовательности команд определите, к какому типу алгоритма она относится:
а) a := 2; b := 3; c := a + b
б) если a > 0 то вывод «Положительное» иначе вывод «Не положительное»
в) пока i <= 10 выполнить: вывод i; i := i + 1
Задание 2. Составьте алгоритм
Составьте словесный алгоритм: «Найти сумму цифр трёхзначного числа».
Задание 3. Определите свойства
Какое из свойств алгоритма нарушено в данном описании?
«Возьмите подходящее число и прибавьте к нему ещё одно подходящее число.»