Задание 14. Позиционные системы счисления: ЕГЭ по информатике

Задание 14 ЕГЭ по информатике проверяет умение работать с позиционными системами счисления в нестандартной постановке: дан исполнитель с двумя командами (прибавь 1 и поменяй местами две младшие цифры при условии, что цифра десятков меньше цифры единиц). Требуется найти количество различных…

Что нужно знать

• Позиционная система счисления: значение цифры зависит от позиции; в задании используются десятичные числа, но команда B меняет местами цифры десятков и единиц.
• Команда A: прибавь 1 — применима всегда, увеличивает число на 1.
• Команда B: поменяй местами — применима только если цифра десятков строго меньше цифры единиц; меняет местами две младшие цифры (десятки и единицы), остальные разряды не меняются.
• Программа — последовательность команд; порядок важен; разные последовательности могут давать одну траекторию, но считаются разными программами.
• Траектория — последовательность чисел, получаемых после каждой команды; для подсчёта программ нужно учитывать все возможные траектории, а не только кратчайшие.
• Количество программ для числа n — это сумма количеств программ для чисел, из которых можно получить n одной командой (A или B), с учётом применимости B.

Термины и понятия

• Позиционная система счисления: система, в которой значение каждой цифры зависит от её позиции в записи числа.
• Исполнитель: абстрактное устройство, выполняющее команды над числами.
• Команда: элементарное действие исполнителя.
• Программа: последовательность команд.
• Траектория: последовательность чисел, получаемых после выполнения каждой команды программы.
• Динамическое программирование: метод решения задач путём разбиения на подзадачи и сохранения результатов.
• Граф достижимых состояний: ориентированный граф, вершины — числа, рёбра — возможные переходы по командам.
• Мемоизация: сохранение результатов вычислений для повторного использования.

Частые ошибки

• Не учитывают условие применимости команды B: применяют B к числам, где цифра десятков не меньше цифры единиц.
• Меняют местами не только две младшие цифры, а все цифры числа (например, для 123 получают 321 вместо 132).
• Считают только кратчайшие программы, игнорируя более длинные.
• Забывают, что разные последовательности команд могут давать одинаковые траектории, но считаются разными программами.

Как пройти тему

В курсе «Информатика» тема «Задание 14. Позиционные системы счисления» занимает 6 занятий по 40 минут: репетитор объясняет материал, задаёт вопросы как на экзамене, разбирает ваши ответы и в конце ставит оценку. Это обзор темы, полный разбор — в занятии. ИИ может ошибаться: проверяйте важное по учебнику. Занятия не заменяют живого репетитора и не гарантируют результат на экзамене.

Другие темы раздела

• Задание 1. Представление и считывание данных в информационных моделях
• Задание 2. Таблицы истинности и логические схемы
• Задание 3. Поиск информации в реляционных базах данных
• Задание 4. Кодирование и декодирование информации
• Задание 5. Формальное исполнение алгоритма
• Задание 6. Результаты работы алгоритмов управления исполнителями

← Предыдущая тема: Задание 13. Анализ хода исполнения алгоритма
Следующая тема: Задание 15. Основные понятия и законы математической логики

Все темы: ЕГЭ по информатике