Продолжаем готовиться к ОГЭ по информатике!
Рассмотрим задачу номер 5.
Условие задачи (ОГЭ 2025 года):
У исполнителя Удвоитель две команды, которым присвоены номера:
1. умножь на 2
2. прибавь 3
Первая из них увеличивает число на экране в 2 раза, вторая прибавляет к числу 3.
Составьте алгоритм получения из числа 4 числа 47, содержащий не более 5 команд. В ответе запишите только номера команд.
(Например, 12211 – это алгоритм:
умножь на 2
прибавь 3
прибавь 3
умножь на 2
умножь на 2
который преобразует число 1 в 32.)
Если таких алгоритмов более одного, то запишите любой из них.
Требования к предметным результатам освоения основной образовательной программы: Анализировать простые алгоритмы для конкретного исполнителя с фиксированным набором команд.
Примерное время выполнения задания (мин.) - 4
Для решения задач такого типа часто используют представление в виде графов, где по ветвям графа расписывают возможные варианты.
Всего у нас две операции: умножить на 2 и прибавить 3.
Получаем в виде графа:
Затем продолжаем ветви вниз:
Дальше подумаем, как нам сократить время перебора, рассмотрев сперва наиболее перспективные ветви дерева.
Пойдем с конца.
Нам требуется получить число 47. Можно ли его вообще получить умножением на 2? Нет, это число нечетное. Значит для получения числа придется использовать операцию +3. К какому числу прибавить 3, чтобы получить 47?
47 - 3 = 44.
Значит, нам потребуется получить число 44, которое может быть само получено умножением как 11 * 2 * 2 = 44.
И полный вид дерева перехода от 4 к 47:
Теперь нужно убедиться, что мы уложились в 5 команд.
4*2 = 8
8+3 = 11
11*2 = 22
22*2 = 44
44+3 = 47
Команд именно 5, осталось записать их по номерам:
умножение (*2) - команда 1
сложение (+3) - команда 2
Получаем, что мы использовали команды 1, 2, 1, 1, 2.
Ответ задачи: 12112
И немного теории
Алгоритм и исполнитель алгоритма — это два ключевых понятия в информатике и программировании, которые помогают понять, как по шагам выполняются программы.
Алгоритм
Алгоритм — это последовательность четко определенных шагов или инструкций, предназначенных для решения конкретной задачи или достижения определенной цели.
Иначе говоря, алгоритм – это информационная модель, описывающая процесс преобразования объекта из начального состояния в конечное, в форме последовательности точных инструкций о содержании действий, необходимых для получения результата.
Алгоритмы могут быть представлены в различных формах, включая:
- Текстовые описания: Пошаговые инструкции на естественном языке.
- Блок-схемы: Графическое представление алгоритма с использованием фигур (прямоугольники, ромбы и т.д.) для обозначения различных действий и решений.
- Программный код: Алгоритмы могут быть реализованы на языках программирования (например, Python, Java, C++ и т.д.).
Исполнитель алгоритма
Исполнитель алгоритма — это объект или система, которая выполняет указанные в алгоритме действия. Исполнителем может быть:
- Человек: Например, когда человек следует рецепту приготовления блюда.
- Компьютерная программа: Программа или скрипт, которые выполняют инструкции алгоритма на компьютере.
- Автоматизированное техническое устройство: Например, робот или автоматизированная система, которая выполняет физические действия согласно заданному алгоритму.
Исполнитель с фиксированным набором команд — это абстрактная модель, которая описывает систему или устройство, способное выполнять определенные действия, заданные заранее определенным набором команд. Такой исполнитель ограничен в своих возможностях и может выполнять только те операции, которые входят в его фиксированный набор.
Свойства алгоритмов
- Конечность (дискретность) команд и выполняемых по ним действий алгоритма.
- Выполнимость в определенной операционной среде (в определенном классе исполнителей).
- Результативность отдельных команд и всего алгоритма.
- Массовость - т.е. применимость алгоритма ко всем возможным входным данным конкретного класса задач.
- Определенность (детерминированность) команд и всего алгоритма для всех входных данных.
- Непротиворечивость любых команд алгоритма на любом наборе входных данных.
Виды алгоритмов
- Линейный алгоритм (следование) – это алгоритм, в котором команды выполняются последовательно одна за другой.
- Разветвляющийся алгоритм (ветвление) – это алгоритм, в котором та или иная серия команд выполняется в зависимости от истинности условия.
- Цикл - это такая алгоритмическая структура, в которой серия команд (тело цикла) выполняется многократно.
Авторское видео по задаче: