Вот число:
2 9 3 8 7 1 0 5 6 4
Условие: нужно вычеркнуть ровно четыре цифры, а оставшиеся шесть цифр (в том же порядке!) должны составить максимально возможное число.
Простая задачка, но демонстрирует концепцию жадного алгоритма, когда мы на каждом шаге выбираем локально оптимальное решение.
Шаг 1: Стратегия
Ключевая идея:
1. Нам нужно шесть цифр.
2. Первую цифру будущего числа нужно выбрать как можно больше, но так, чтобы после неё оставалось ещё хотя бы пять цифр для остальных позиций.
Смотрим на начало:
2 9 3 8 7 1 0 5 6 4
Самая большая из первых пяти цифр (позиции 1–5) — это 9 (вторая позиция).
Если выбрать её первой, после 9 останется 8 цифр, из которых можно выбрать ещё 5 — идеально.
Первая цифра = 9.
Шаг 2: Вторая цифра
После 9 остаётся: 3 8 7 1 0 5 6 4
Теперь нужно выбрать вторую цифру как можно больше, но так, чтобы после неё оставалось хотя бы четыре цифры для остальных.
Смотрим на первые четыре из оставшихся: 3, 8, 7, 1.
Максимум — 8.
Вторая цифра = 8.
Теперь осталось: 7 1 0 5 6 4 (выбрать нужно ещё четыре цифры).
---
Шаг 3: Третья цифра
Осталось: 7 1 0 5 6 4
Выбираем третью цифру из первых трёх (7, 1, 0), чтобы после неё осталось хотя бы три цифры.
Максимум — 7.
Третья цифра = 7.
Осталось: 1 0 5 6 4 (выбрать нужно ещё три).
Шаг 4: Четвёртая цифра
Осталось: 1 0 5 6 4
Выбираем четвёртую цифру из первых трёх (1, 0, 5), чтобы после неё осталось хотя бы две.
Максимум — 5.
Четвёртая цифра = 5.
Осталось: 6 4 (выбрать нужно ещё две — берём обе).
---
Шаг 5: Собираем результат
Цифры по порядку:
9 8 7 5 6 4
Итоговое число: 987564
---
Проверка зачёркивания
Исходное: 2̶ 9 3̶ 8 7 1̶ 0̶ 5 6 4
Вычеркнули: 2, 3, 1, 0 (ровно четыре цифры).
Оставшиеся в порядке: 9 8 7 5 6 4.
Можно ли получить больше? Нет — каждый шаг мы выбирали максимально возможную цифру, не теряя возможности набрать нужное количество цифр дальше.
---
Ответ: 987564
Почему это полезно?
Эта задача — не просто головоломка. Это тренировка алгоритмического мышления: учит делать жадный выбор с учётом будущих ограничений. Такая логика применяется в программировании, оптимизации и даже в жизни, когда нужно выбирать лучшее, не загораживая себе путь вперёд.
А вы сразу увидели стратегию? Попробуйте на другом числе:
В числе 4508631729 зачеркните 3 цифры, чтобы оставшиеся 7 цифр дали наибольшее число. Пишите ваши варианты в комментариях!
Подписывайтесь, если любите задачи, где нужно думать на шаг вперёд. В следующий раз — задача на поиск закономерности в, казалось бы, случайной последовательности!
#математика #логика #головоломка #числа #задача #алгоритм #жадныйалгоритм #олимпиаднаяматематика