Продолжаем вместе готовиться к ОГЭ по информатике с каналом "Информатика для всех"!
Рассмотрим задачу номер 5.
Условие задачи:
У исполнителя Квадратор две команды, которым присвоены номера:
1) возведи в квадрат
2) прибавь 1
Первая из них возводит число на экране во вторую степень, вторая – прибавляет к числу 1.
Составьте алгоритм получения из числа 3 числа 84, содержащий не более 5 команд. В ответе запишите только номера команд.
(Например, 21221 – это алгоритм
- прибавь 1
- возведи в квадрат
- прибавь 1
- прибавь 1
- возведи в квадрат,
который преобразует число 1 в число 36.)
Если таких алгоритмов более одного, то запишите любой из них.
Решение:
Для решения задач такого типа часто используют представление в виде графов, где по ветвям графа расписывают возможные варианты.
Всего у нас две операции:
- возведи в квадрат
- прибавь 1
Обозначим ^2 - возведение в квадрат. Получаем в виде графа:
Затем продолжаем ветви вниз:
Дальше подумаем, как нам сократить время перебора, рассмотрев сперва наиболее перспективные ветви дерева.
Нам требуется получить число 84. Можно ли его вообще получить возведением в квадрат чисел 10 и 16? Нет.
Но можно ли быстро перейти от 81 к 84 за счет операции +1? Да.
Будем добавлять по единице.
Получим 82, затем 83 и 84.
Полный вид дерева перехода от 3 к 84 имеет вид:
3^2 = 9
9^2 = 81
81 + 1 = 82
82 + 1 = 83
83 + 1 = 84
Команд именно 5, осталось записать их по номерам:
возведи в квадрат - команда 1
прибавь 1 - команда 2
Получаем, что мы использовали команды 1, 1, 2, 2, 2.
Ответ задачи: 11222
И немного теории алгоритмов
Алгоритм и исполнитель алгоритма — это ключевые понятия в информатике и программировании, которые помогают понять, как по шагам выполняются программы.
Алгоритм
Алгоритм — это последовательность четко определенных шагов или инструкций, предназначенных для решения конкретной задачи или достижения определенной цели.
Иначе говоря, алгоритм – это информационная модель, описывающая процесс преобразования объекта из начального состояния в конечное, в форме последовательности точных инструкций о содержании действий, необходимых для получения результата.
Алгоритмы могут быть представлены в различных формах, включая:
- Текстовые описания: Пошаговые инструкции на естественном языке.
- Блок-схемы: Графическое представление алгоритма с использованием фигур (прямоугольники, ромбы и т.д.) для обозначения различных действий и решений.
- Программный код: Алгоритмы могут быть реализованы на языках программирования (например, Python, Java, C++ и т.д.).
Исполнитель алгоритма
Исполнитель алгоритма — это объект или система, которая выполняет указанные в алгоритме действия. Исполнителем может быть:
- Человек: Например, когда человек следует рецепту приготовления блюда.
- Компьютерная программа: Программа или скрипт, которые выполняют инструкции алгоритма на компьютере.
- Автоматизированное техническое устройство: Например, робот или автоматизированная система, которая выполняет физические действия согласно заданному алгоритму.
Исполнитель с фиксированным набором команд — это абстрактная модель, которая описывает систему или устройство, способное выполнять определенные действия, заданные заранее определенным набором команд. Такой исполнитель ограничен в своих возможностях и может выполнять только те операции, которые входят в его фиксированный набор.
Анализ простых алгоритмов для конкретного исполнителя с фиксированным набором команд — это процесс оценки и проверки того, как данный алгоритм реализуется и работает на конкретном устройстве или интерпретаторе, обладающем ограниченным набором команд.
Основные аспекты такого анализа:
- Совместимость алгоритма с набором команд: проверка, можно ли реализовать алгоритм с помощью доступных команд.
- Эффективность выполнения: оценка времени и ресурсов, необходимых для выполнения алгоритма на данном исполнителе.
- Корректность: подтверждение, что алгоритм решает поставленную задачу правильно при использовании ограниченного набора команд.
- Оптимизация: поиск способов упростить или ускорить выполнение, используя особенности набора команд.
Свойства алгоритмов
Свойства алгоритмов — это важные характеристики, которые определяют их эффективность, надежность и применимость.
Основные свойства алгоритмов:
- Дискретность
Алгоритм состоит из конечного числа четко определенных шагов, которые выполняются последовательно. - Определенность (однозначность)
Каждый шаг алгоритма должен быть точно определен, чтобы не было неоднозначных интерпретаций. - Обратимость (детерминированность)
Для одних и тех же входных данных алгоритм всегда дает одинаковый результат. - Конечность
Алгоритм должен завершаться после выполнения конечного числа шагов, то есть не зацикливаться бесконечно. - Вход и выход
Алгоритм принимает входные данные и после выполнения дает результат (выходные данные). - Эффективность
Алгоритм должен решать задачу за разумное время и с использованием допустимых ресурсов (памяти, вычислительной мощности). - Масштабируемость
Способность алгоритма работать с разными объемами данных без существенных потерь в производительности. - Обобщенность
Возможность применения алгоритма к различным задачам или в различных условиях при небольших изменениях.
И еще решение задач ОГЭ:
Подборка решений всех задач ОГЭ по информатике (пополняется)