Задание 18. Системы счисления: ЕГЭ по информатике

Задание 18 ЕГЭ по информатике проверяет умение работать с системами счисления, но в экзаменационном варианте оно представлено задачей на динамическое программирование по сетке с монетами и стенами. Ученик должен по электронной таблице N×N (1<N<30) определить максимальную и минимальную суммы…

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

• Робот стартует в левой верхней клетке (1,1) и движется только вправо или вниз.
• Монета в каждой клетке имеет достоинство от 1 до 100 и забирается при посещении, включая стартовую и конечную клетки.
• Конечная клетка — это клетка, из которой нельзя продолжить движение: либо правый нижний угол, либо клетка, у которой есть стена справа и стена снизу (или граница поля).
• Внутренние стены между клетками запрещают переход в соответствующем направлении; внешние стены ограничивают поле.
• Нужно найти максимальную и минимальную суммы среди всех возможных маршрутов из (1,1) в любую конечную клетку.
• Задача решается методом динамического программирования: для каждой клетки храним максимальную и минимальную достижимые суммы.

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

• Динамическое программирование: метод решения задач путём разбиения на подзадачи и сохранения результатов для повторного использования.
• Конечная клетка: клетка, из которой Робот не может продолжить движение из-за стен или границы поля.
• Внутренняя стена: препятствие между соседними клетками, запрещающее переход в одном направлении.
• Внешняя стена: граница поля, за которую нельзя выйти.
• Монета: число от 1 до 100, лежащее в клетке и забираемое при посещении.
• Маршрут: последовательность клеток от стартовой до конечной, где каждый шаг — вправо или вниз.
• Достижимая клетка: клетка, в которую можно попасть из стартовой, не нарушая стен.
• Максимальная сумма: наибольшее возможное значение собранных монет по всем допустимым маршрутам.

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

• Не учитывают монету в начальной клетке — тогда сумма занижается на её значение.
• Не учитывают монету в конечной клетке — аналогично занижение.
• Считают конечной только правую нижнюю клетку, игнорируя другие клетки, ограниченные стенами справа и снизу.
• Не проверяют наличие внутренних стен и рассматривают переходы сквозь них.

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

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

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

• Задание 11. Кодирование изображений и звука
• Задание 16. Анализ алгоритмов
• Задание 24. Обработка символьных данных
• Задание 25. Обработка натуральных чисел
• Задание 26. Массивы и последовательности

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

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