Основы алгоритмизации

Определение

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

Слово «алгоритм» происходит от имени персидского учёного IX века Аль-Хорезми (Мухаммад ибн Муса аль-Хорезми), который сформулировал правила выполнения арифметических действий.

Свойства алгоритма

1. Дискретность — алгоритм состоит из отдельных шагов, выполняемых последовательно.
2. Понятность — все команды алгоритма должны входить в систему команд исполнителя.
3. Определённость (детерминированность) — каждое действие должно быть чётко и однозначно определено.
4. Результативность — алгоритм должен приводить к конкретному результату.
5. Массовость — алгоритм должен быть применим к целому классу однотипных задач, а не к одной конкретной.
6. Конечность — алгоритм должен завершаться за конечное число шагов.

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

Исполнитель — это объект (человек, животное, робот, компьютер), способный выполнять определённые команды. Исполнитель имеет:

• Систему команд исполнителя (СКИ) — полный набор команд, которые исполнитель понимает и может выполнить.
• Среду исполнителя — условия, в которых работает исполнитель.

Примеры исполнителей: ученик (умеет писать, чертить, вычислять), робот-пылесос (умеет двигаться вперёд, поворачивать), компьютер (умеет выполнять арифметические и логические операции).

Способы записи алгоритмов

1. Словесный способ

Запись на естественном (человеческом) языке. Подходит для простых алгоритмов, но может быть неоднозначным.

Пример: «Чтобы включить компьютер, нужно нажать кнопку питания на системном блоке, затем кнопку включения монитора, дождаться загрузки системы и ввести пароль».

2. Графический способ (блок-схемы)

Используются стандартные геометрические фигуры — блоки, соединённые стрелками:

Фигура	Назначение
Овал	Начало или конец алгоритма
Прямоугольник	Выполнение действия (команда)
Ромб	Проверка условия (ветвление)
Параллелограмм	Ввод или вывод данных

3. Псевдокод

Запись на формализованном языке, промежуточном между естественным языком и языком программирования. Использует чёткие конструкции без строгого синтаксиса.

АЛГ Включение компьютера
НАЧ
  Нажать кнопку питания на системном блоке
  Нажать кнопку включения монитора
  ЖДАТЬ загрузки системы
  ЕСЛИ есть пароль ТО
    Ввести пароль
  ВСЕ
КОН

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

Любой алгоритм можно построить из трёх базовых конструкций:

1. Следование (линейный алгоритм)

Действия выполняются одно за другим в строго определённом порядке.

2. Ветвление (разветвляющийся алгоритм)

В зависимости от условия выполняется одна из двух последовательностей действий.

Полная форма:

ЕСЛИ <условие> ТО <действия 1> ИНАЧЕ <действия 2>

Краткая форма:

ЕСЛИ <условие> ТО <действия 1>

3. Цикл (циклический алгоритм)

Многократное повторение действий (тела цикла), пока выполняется условие.

Цикл с предусловием (цикл «ПОКА»): Проверка условия выполняется перед очередным повторением тела цикла. Тело цикла может не выполниться ни разу.

ПОКА <условие> ДЕЛАТЬ
  <действия>

Цикл с постусловием: Тело цикла выполняется хотя бы один раз, проверка — после выполнения.

Цикл с параметром (со счётчиком): Заранее известно количество повторений.

ДЛЯ i ОТ 1 ДО N ДЕЛАТЬ
  <действия>

Примеры

Пример 1. Линейный алгоритм

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

Словесная запись:

1. Ввести длину прямоугольника (a).
2. Ввести ширину прямоугольника (b).
3. Вычислить S = a × b.
4. Вывести S.

Блок-схема: (овал «Начало») → (параллелограмм: ввод a, b) → (прямоугольник: S = a × b) → (параллелограмм: вывод S) → (овал «Конец»).

Пример 2. Алгоритм с ветвлением

Составьте алгоритм, определяющий, является ли число чётным.

Псевдокод:

АЛГ Проверка на чётность
НАЧ
  ВВЕСТИ число N
  ЕСЛИ N mod 2 = 0 ТО
    ВЫВЕСТИ «Чётное»
  ИНАЧЕ
    ВЫВЕСТИ «Нечётное»
  ВСЕ
КОН

Пример 3. Циклический алгоритм

Составьте алгоритм, выводящий на экран все числа от 1 до 5.

Псевдокод:

АЛГ Вывод чисел 1..5
НАЧ
  i := 1
  ПОКА i ≤ 5 ДЕЛАТЬ
    ВЫВЕСТИ i
    i := i + 1
  КОНЕЦ ПОКА
КОН