а) Приведите пример семизначного числа из которого, вычёркивая цифры, можно получить каждое из чисел: 123, 426, 786.
б) Существует ли девятизначное число из которого, вычёркивая цифры, можно получить каждое из чисел: 123, 238, 435, 567, 791?
в) Найдите наименьшее натуральное число, из которого можно получить все числа от 1 до 40 включительно, вычёркивая из него цифры.
Посмотреть решение
Предварительное решение, не проверено экспертом.
Ранее доступное решение переведено в общий параметрический рецепт; новая независимая проверка не проводилась.
Шаг 1. Состояние хранит, сколько начальных цифр каждой требуемой записи уже встретилось. При добавлении цифры d продвигаемся на один знак во всех записях, у которых следующий нужный знак равен d. Это жадное сопоставление эквивалентно существованию подпоследовательности; первая цифра исходного числа не может быть нулём.
Шаг 2. Всего состояний не больше произведения увеличенных длин требуемых записей. Начинаем с нулевого состояния и последовательно строим все достижимые состояния после 1,2,… добавленных цифр. Первое полное состояние даёт наименьшую длину. Приведённая запись реализует найденные переходы. Если нужна большая длина, можно приписать слева ненулевые цифры.
T=((1;2;3);(4;2;6);(7;8;6))
Шаг 3. Записываем найденный результат.
1423786
Шаг 1. Состояние хранит, сколько начальных цифр каждой требуемой записи уже встретилось. При добавлении цифры d продвигаемся на один знак во всех записях, у которых следующий нужный знак равен d. Это жадное сопоставление эквивалентно существованию подпоследовательности; первая цифра исходного числа не может быть нулём.
Шаг 2. Всего состояний не больше произведения увеличенных длин требуемых записей. Начинаем с нулевого состояния и последовательно строим все достижимые состояния после 1,2,… добавленных цифр. Первое полное состояние даёт наименьшую длину. Приведённая запись реализует найденные переходы. Если нужна большая длина, можно приписать слева ненулевые цифры.
T=((10;9);(1;2;4;3;5;6;7;8;9;1))
Шаг 3. Нет. Полная конечная область либо доказанная нижняя граница исключает возможность.
Шаг 1. Для получения всех чисел от 1 до M, где 10≤M≤99, нужны все цифры от 1 до 9 и цифра 0. Если число 11a≤M, цифра a нужна по крайней мере дважды, чтобы получить aa. Эти требования задают нижнюю границу количества цифр и минимальный набор их кратностей.
T=(1;2;2;2;1;1;1;1;1;1)
Шаг 2. Для каждой требуемой двузначной записи ab отмечаем, появилась ли b после хотя бы одной a. Проверяем все записи с найденными минимальными кратностями цифр: состояние состоит из оставшихся кратностей, уже встреченных цифр и ещё не полученных пар. Если пара ab не получена, в остатке должна быть b, а при отсутствии a в префиксе - ещё и a; для aa нужны две оставшиеся a. Эти необходимые отсечения ничего не теряют. Полный конечный разбор в порядке цифр от 0 до 9 находит лексикографически наименьшую допустимую запись, с запретом начального нуля. Она достигает нижней границы длины, значит, является наименьшим натуральным числом.