Изучение свойств алгоритмов и основных алгоритмических конструкций.

Теоретический материал

Изучение свойств алгоритмов

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

Основные свойства алгоритмов

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

---

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

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

1. Линейная конструкция (следование)

Суть: последовательное выполнение действий друг за другом. Каждое действие выполняется ровно один раз, причём после $i$-го действия следует $(i+1)$-е (если $i$-е не является завершающим).

Примеры применения:

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

Псевдокод линейного алгоритма (сложение двух чисел):

Ввод a, b
S = a + b
Вывод S
Конец

На блок‑схеме линейная конструкция изображается последовательностью блоков обработки и/или ввода‑вывода, расположенных друг за другом.

2. Разветвляющаяся конструкция (ветвление)

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

Виды ветвления:

• Полное ветвление (если — то — иначе): две ветви, каждая из которых ведёт к общей точке слияния. Выполнение алгоритма продолжается независимо от выбранного пути.
• Неполное ветвление (если — то): действия выполняются только на одной ветви, вторая ветвь отсутствует.

Пример: проверка, является ли число положительным.

Псевдокод (полное ветвление):

Ввод x
Если x > 0 Тогда
    Вывод "Число положительное"
Иначе
    Вывод "Число не положительное"
Конец Если
Конец

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

3. Циклическая конструкция (цикл)

Суть: многократное повторение одного и того же действия (или группы действий) над новыми исходными данными до выполнения заданного условия.

Основные типы циклов:

• Цикл с предусловием (пока): проверка условия выполняется перед телом цикла. Если условие ложно с самого начала, тело цикла не выполнится ни разу.
• Цикл с постусловием (до): проверка условия выполняется после тела цикла. Тело цикла выполнится хотя бы один раз.
• Цикл с параметром (для): используется, когда известно количество повторений.

Пример (цикл с предусловием): вычисление суммы чисел от 1 до $N$.

Псевдокод:

Ввод N
Сумма = 0
i = 1
Пока i <= N Выполнить
    Сумма = Сумма + i
    i = i + 1
Конец Пока
Вывод Сумма
Конец

На блок‑схеме цикл изображается с помощью блока, обозначающего начало и конец цикла, внутри которого располагается тело цикла.

4. Рекурсивная конструкция

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

Обязательные элементы рекурсивного алгоритма:

• Базовый случай (условие выхода) — ситуация, при которой рекурсия прекращается.
• Рекурсивный вызов — обращение алгоритма к самому себе с изменёнными параметрами.

Пример: вычисление факториала числа $n$:

• Базовый случай:* если $n=0$ или $n=1$, то $n!=1$.
  Рекурсивный случай: $n!=n\times (n-1)!$.

Псевдокод:

Функция Факториал(n)
    Если n <= 1 Тогда
        Возврат 1
    Иначе
        Возврат n * Факториал(n - 1)
    Конец Если
Конец Функции

---

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

Алгоритмы можно записывать разными способами:

1. Словесное описание — на естественном языке. Подходит для общего понимания, но может быть многословным и допускать неоднозначности.
2. Псевдокод — частично формализованный язык с элементами естественного языка и математической символики. Удобен для проектирования алгоритмов перед программированием.
3. Блок‑схема — графическое представление с помощью стандартных блоков (прямоугольники, ромбы и т. д.) и стрелок, показывающих порядок выполнения. Обеспечивает наглядность.
4. Программа — запись на языке программирования. Максимально формализована и пригодна для исполнения на компьютере.

Хотите, я раскрою какой‑то из аспектов темы подробнее или помогу с решением конкретной задачи?

Практическая работа

«КуМир» (Комплект Учебных МИРов) —  система программирования, предназначенная для поддержки начальных курсов информатики и программирования в средней и высшей школе.

Синтаксис и основные команды

Язык «КуМир» использует русский синтаксис.

Общие команды:

• алг — начало алгоритма;
• нач — начало тела программы;
• кон — конец программы;
• ввод — ввод данных с клавиатуры;
• вывод — вывод данных на экран.

Команды для исполнителя «Робот»:

• вверх — перемещение на одну клетку вверх;
• вниз — перемещение на одну клетку вниз;
• влево — перемещение на одну клетку влево;
• вправо — перемещение на одну клетку вправо;
• закрасить — закрасить текущую клетку.

Команды для исполнителя «Чертёжник»:

• опустить перо — начать рисование;
• поднять перо — прекратить рисование;
• сместиться в точку (x, y) — перемещение в заданную точку;
• сместиться на вектор (dx, dy) — смещение на заданный вектор.

Пример программы для «Робота»

Задача: закрасить 3 клетки вправо от начальной позиции.