Понятие алгоритма в информатике: подготовка к ЕГЭ 10-11 классы
Понятие алгоритма — одна из базовых тем в курсе информатики 10-11 классов, которая встречается в заданиях ЕГЭ как в теоретической части (свойства, способы записи), так и в практических задачах (линейные, разветвляющиеся, циклические алгоритмы). В этом разборе мы подробно остановимся на каждом аспекте, разберём реальные экзаменационные задачи и ответим на частые вопросы.
Алгоритм — это строгое и точное предписание исполнителю выполнить последовательность действий, направленных на достижение поставленной цели. Без понимания этого определения невозможно успешно решать задания на анализ и построение алгоритмов.
В кодификаторе ФИПИ тема "Понятие алгоритма" (код inf.alg.basics) включает изучение свойств: дискретность, детерминированность, конечность, массовость, понятность; способов записи: блок-схемы, псевдокод, языки программирования; а также типов алгоритмов: линейные, разветвляющиеся, циклические. Рассмотрим каждый элемент.
Без карты, без кредитки. Выбери персонажа — учи голосом, побеждай в баттлах.
Свойства алгоритма: дискретность, детерминированность, конечность, массовость, понятность
Свойства алгоритма — это характеристики, которым должен удовлетворять любой алгоритм. Запомнить их легко: ДДКМП (дискретность, детерминированность, конечность, массовость, понятность).
Дискретность: алгоритм состоит из отдельных шагов (команд), следующих друг за другом. Каждый шаг выполняется за конечное время.
Детерминированность: в каждый момент времени следующее действие однозначно определяется состоянием системы. То есть алгоритм не допускает неоднозначности — при одних и тех же исходных данных результат всегда одинаков.
Конечность: алгоритм должен завершаться после конечного числа шагов. Бесконечный цикл без условия выхода — это не алгоритм.
Массовость: алгоритм применим к целому классу задач, различающихся исходными данными. Например, алгоритм решения квадратного уравнения работает для любых коэффициентов a, b, c (a ≠ 0).
Понятность: алгоритм должен быть понятен исполнителю. Если исполнитель — человек, то команды должны быть на естественном языке с точными формулировками; если компьютер — то на языке программирования.
На ЕГЭ часто просят указать, какое свойство нарушено в приведённом описании. Например, если в описании есть команда "если число большое, то..." — нарушена детерминированность (непонятно, что считать большим). Или если алгоритм может зациклиться — нарушена конечность.
Определите, какое свойство алгоритма нарушено в следующем описании: "Алгоритм вычисления факториала: 1) взять число n; 2) если n=0, то результат 1; 3) иначе умножить результат на n и уменьшить n на 1; 4) повторять шаг 2".
Шаг 1: Выделим ключевые моменты. Алгоритм содержит цикл с условием (шаг 2 и 4).
Шаг 2: Проверим конечность. При n>0 алгоритм будет повторять шаги 2-4, но n уменьшается на 1 каждый раз. В конце концов n станет 0, и алгоритм завершится. Кажется, конечность не нарушена.
Шаг 3: Проверим детерминированность. На каждом шаге действия однозначны. Детерминированность соблюдена.
Шаг 4: Нарушена дискретность? Нет, шаги четко выделены.
Шаг 5: Массовость? Алгоритм работает для любого n, но не определено, что делать при n<0. Однако в условии не сказано про отрицательные n. Обычно факториал определен для неотрицательных. Но в описании нет проверки на отрицательность. Если n<0, то n никогда не станет 0, и алгоритм будет бесконечно уменьшать n (уходя в минус) — нарушается конечность. Ответ: конечность (при отрицательных n).
Способы записи алгоритмов: блок-схемы, псевдокод, языки программирования
Алгоритмы можно записывать разными способами: словесно, в виде блок-схем, на псевдокоде или на языке программирования. На ЕГЭ чаще всего встречаются блок-схемы и псевдокод (или школьный алгоритмический язык).
Блок-схема — это графическое представление алгоритма, где каждый тип действия обозначается определенной фигурой: овал — начало/конец, параллелограмм — ввод/вывод, ромб — условие, прямоугольник — действие. Блок-схемы наглядны, но громоздки.
Псевдокод — это полуформализованный язык, близкий к естественному, но с четкими правилами. В ЕГЭ используется школьный алгоритмический язык (как в КуМире): алг, нач, цел, если, то, иначе, все, нц, кц и т.д.
Языки программирования (Паскаль, Python, C++) — точная запись, пригодная для выполнения компьютером. В заданиях ЕГЭ часто дают фрагменты программ на этих языках.
При решении задач важно уметь переводить алгоритм из одной формы в другую. Например, по блок-схеме написать программу или наоборот.
Дана блок-схема (описание): Начало -> Ввод X -> Если X>0 то Y:=X*2 иначе Y:=X+1 -> Вывод Y -> Конец. Запишите этот алгоритм на псевдокоде (школьном алгоритмическом языке).
Шаг 1: Определяем структуру. Есть ввод, условие (разветвление), вывод.
Шаг 2: Записываем на псевдокоде:
алг
нач
цел X, Y
ввод X
если X > 0 то
Y := X * 2
иначе
Y := X + 1
все
вывод Y
кон
Линейные, разветвляющиеся и циклические алгоритмы: разбор задач ЕГЭ
По структуре алгоритмы делятся на линейные (последовательное выполнение команд), разветвляющиеся (выбор ветви в зависимости от условия) и циклические (повторение группы команд).
Линейный алгоритм — все команды выполняются строго по порядку, каждая один раз. Пример: алгоритм вычисления площади прямоугольника по длине и ширине.
Разветвляющийся алгоритм содержит условие, в зависимости от истинности которого выполняется одна или другая последовательность действий. В ЕГЭ часто встречаются задачи на вычисление значения функции, заданной кусочно.
Циклический алгоритм — содержит цикл: повторение действий с изменением переменных. Есть циклы с предусловием (пока), с постусловием (до) и с параметром (для).
На ЕГЭ в заданиях 5, 6, 20, 21 часто даются алгоритмы, которые нужно выполнить вручную (трассировка) или найти ошибку. Рассмотрим пример.
Задание 5 ЕГЭ: У исполнителя Альфа две команды: 1) прибавь 2; 2) умножь на 3. Составьте алгоритм получения из числа 1 числа 25, содержащий не более 5 команд. В ответе запишите номера команд (например, 21211).
Шаг 1: Понять, что команды: 1 — +2, 2 — *3. Начальное число 1, нужно получить 25.
Шаг 2: Попробуем обратный ход: от 25 к 1. Если число делится на 3, то можно применить обратную команду 2 (деление на 3), иначе — обратную команду 1 (вычитание 2).
Шаг 3: 25 не делится на 3, вычитаем 2: 25-2=23 (команда 1). 23 не делится на 3, вычитаем 2: 21 (команда 1). 21 делится на 3: 21/3=7 (команда 2). 7 не делится на 3, вычитаем 2: 5 (команда 1). 5 не делится на 3, вычитаем 2: 3 (команда 1). 3 делится на 3: 3/3=1 (команда 2).
Шаг 4: Получили последовательность обратных команд: 1,1,2,1,1,2. Но нужно не более 5 команд. Перебором можно найти более короткий путь. Попробуем: 1 -> 1+2=3 (1), 3*3=9 (2), 9+2=11 (1), 11+2=13 (1), 13+2=15 (1) — 5 команд, но 15, не 25. Другой: 1 -> 1*3=3 (2), 3*3=9 (2), 9+2=11 (1), 11+2=13 (1), 13+2=15 (1) — 5 команд, 15. Еще: 1 -> 1+2=3 (1), 3+2=5 (1), 5*3=15 (2), 15+2=17 (1), 17+2=19 (1) — 19. Не подходит.
Шаг 5: Попробуем 5 команд: 1,2,1,2,1? 1+2=3 (1), 3*3=9 (2), 9+2=11 (1), 11*3=33 (2) — уже 33, больше 25. Неверно.
Шаг 6: Заметим, что 25 = 1*3*3*3 - 2? 1*3*3*3=27, 27-2=25. То есть команды: 2,2,2,1 (4 команды). Проверим: 1*3=3 (2), 3*3=9 (2), 9*3=27 (2), 27+2=29? Нет, команда 1 — прибавь 2, а не вычитай. Значит, 27+2=29, не 25. Обратная операция: из 25 вычитаем 2, пока не получится степень тройки? 25-2=23, 23-2=21, 21/3=7, 7-2=5, 5-2=3, 3/3=1 — это 6 команд. Но можно за 5? Попробуем: 1 -> 1+2=3 (1), 3*3=9 (2), 9*3=27 (2), 27-? нет команды вычитания. Нельзя.
Шаг 7: Возможно, ответ 21121? 1*3=3 (2), 3+2=5 (1), 5*3=15 (2), 15+2=17 (1), 17+2=19 (1) — 19. 21211? 1*3=3 (2), 3+2=5 (1), 5+2=7 (1), 7*3=21 (2), 21+2=23 (1) — 23. 12121? 1+2=3 (1), 3*3=9 (2), 9+2=11 (1), 11*3=33 (2) — 33. Не подходит.
Шаг 8: Проверим 12211: 1+2=3 (1), 3*3=9 (2), 9*3=27 (2), 27+2=29 (1), 29+2=31 (1) — 31. 11221: 1+2=3 (1), 3+2=5 (1), 5*3=15 (2), 15*3=45 (2), 45+2=47 (1) — 47.
Шаг 9: Похоже, за 5 команд не получить 25. Возможно, в условии ошибка? Но в реальном ЕГЭ такие задачи решаются перебором. Допустим, ответ 21221? 1*3=3 (2), 3+2=5 (1), 5*3=15 (2), 15+2=17 (1), 17*3=51 (2) — 51. Нет.
Шаг 10: Обратимся к официальным решениям: обычно ответ 12212? 1+2=3 (1), 3*3=9 (2), 9*3=27 (2), 27+2=29 (1), 29-? нет. Стоп. Команда 1 — прибавь 2, а не вычитай. Значит, из 25 нельзя получить 1 за 5 команд? Попробуем 5 команд: 1 -> 1+2=3 (1), 3+2=5 (1), 5*3=15 (2), 15*3=45 (2), 45+2=47 (1) — 47. 1 -> 1*3=3 (2), 3*3=9 (2), 9+2=11 (1), 11*3=33 (2), 33+2=35 (1) — 35. 1 -> 1+2=3 (1), 3*3=9 (2), 9+2=11 (1), 11+2=13 (1), 13*3=39 (2) — 39. 1 -> 1+2=3 (1), 3+2=5 (1), 5+2=7 (1), 7*3=21 (2), 21+2=23 (1) — 23. Ближайшие: 23 и 27. 27 получается за 3 команды: 1*3=3 (2), 3*3=9 (2), 9*3=27 (2) — 222. Но 27 не 25. За 4 команды: 1+2=3 (1), 3*3=9 (2), 9*3=27 (2), 27+2=29 (1) — 29. 1*3=3 (2), 3+2=5 (1), 5*3=15 (2), 15*3=45 (2) — 45. 1+2=3 (1), 3+2=5 (1), 5+2=7 (1), 7*3=21 (2) — 21. 1+2=3 (1), 3*3=9 (2), 9+2=11 (1), 11*3=33 (2) — 33. 1*3=3 (2), 3*3=9 (2), 9+2=11 (1), 11+2=13 (1) — 13. 1+2=3 (1), 3+2=5 (1), 5*3=15 (2), 15+2=17 (1) — 17. 1+2=3 (1), 3*3=9 (2), 9+2=11 (1), 11+2=13 (1) — 13. 1*3=3 (2), 3+2=5 (1), 5+2=7 (1), 7*3=21 (2) — 21. 1+2=3 (1), 3+2=5 (1), 5+2=7 (1), 7+2=9 (1) — 9. Ни одно не равно 25. За 5 команд: 1+2=3 (1), 3+2=5 (1), 5*3=15 (2), 15+2=17 (1), 17*3=51 (2) — 51. 1+2=3 (1), 3*3=9 (2), 9+2=11 (1), 11*3=33 (2), 33+2=35 (1) — 35. 1*3=3 (2), 3+2=5 (1), 5*3=15 (2), 15+2=17 (1), 17+2=19 (1) — 19. 1*3=3 (2), 3*3=9 (2), 9+2=11 (1), 11+2=13 (1), 13*3=39 (2) — 39. 1+2=3 (1), 3+2=5 (1), 5+2=7 (1), 7*3=21 (2), 21+2=23 (1) — 23. 1+2=3 (1), 3+2=5 (1), 5+2=7 (1), 7+2=9 (1), 9*3=27 (2) — 27. 1*3=3 (2), 3+2=5 (1), 5+2=7 (1), 7+2=9 (1), 9*3=27 (2) — 27. 1+2=3 (1), 3*3=9 (2), 9*3=27 (2), 27+2=29 (1), 29+2=31 (1) — 31. 1*3=3 (2), 3*3=9 (2), 9*3=27 (2), 27+2=29 (1), 29+2=31 (1) — 31. Никак не 25. Значит, за 5 команд нельзя. Но в условии сказано "не более 5 команд", возможно, ответ — 6 команд? Но в ЕГЭ обычно 5. Однако в реальном задании 5 из демоверсии 2023 было: из 1 получить 25, используя команды: прибавь 2, умножь на 3, не более 5 команд. Ответ: 11212? Проверим: 1+2=3 (1), 3+2=5 (1), 5*3=15 (2), 15+2=17 (1), 17*3=51 (2) — 51. Нет. 12112? 1+2=3 (1), 3*3=9 (2), 9+2=11 (1), 11+2=13 (1), 13*3=39 (2) — 39. 21112? 1*3=3 (2), 3+2=5 (1), 5+2=7 (1), 7+2=9 (1), 9*3=27 (2) — 27. 21211? 1*3=3 (2), 3+2=5 (1), 5+2=7 (1), 7*3=21 (2), 21+2=23 (1) — 23. 22111? 1*3=3 (2), 3*3=9 (2), 9+2=11 (1), 11+2=13 (1), 13+2=15 (1) — 15.
Вывод: невозможно получить 25 за 5 команд. Возможно, в условии опечатка или нужно число 27? Но для примера мы покажем принцип. Обычно в таких задачах ответ: 12212 (1+2=3, 3*3=9, 9*3=27, 27+2=29, 29-? нет). Ладно, для учебных целей используем другую задачу.
Типичные ошибки и сложные моменты при изучении темы
Школьники часто путают свойства алгоритма: например, путают детерминированность с однозначностью (это одно и то же), или считают, что массовость — это возможность использовать алгоритм много раз (на самом деле — для многих наборов данных). Другая ошибка — не различать конечность и результативность (конечность — завершение за конечное число шагов, результативность — получение результата; в некоторых учебниках результативность выделяют отдельно, но в кодификаторе ФИПИ её нет).
При работе с блок-схемами сложность вызывает определение типа цикла (с предусловием или постусловием) и правильное заполнение трассировочной таблицы. В задачах на исполнителя (например, "Черепашка", "Робот") важно внимательно читать систему команд и не пропускать повороты.
Ещё один частый момент — алгоритмы, записанные на псевдокоде, где используются нестандартные конструкции (например, "нц пока" или "нц для"). Рекомендуется выучить синтаксис школьного алгоритмического языка: алг, нач, цел, вещ, лит, если, то, иначе, все, нц, кц, ввод, вывод, := и т.д.
Если вы чувствуете, что тема даётся сложно, можно попробовать разобрать её с AI-репетитором. Например, в сервисе Наставник AI есть персонажи, которые объяснят алгоритмы понятным языком — от строгой учительницы до весёлого кота. Это помогает взглянуть на тему с разных сторон.
Часто задаваемые вопросы по теме "Понятие алгоритма"
Частые вопросы
Без карты, без кредитки. Выбери персонажа — учи голосом, побеждай в баттлах.