Начнём анализ условия. Известно, что N — произведение цифр Q. Следовательно, будем рассматривать числа от 2 до 9 в качестве сомножителей. Думаю, что ясно, почему 0 и 1 не рассматриваются.
Среди чисел от 2 до 9 простыми являются 2, 3, 5, 7, остальные можно получить как произведение простых, например 6 = 2 × 3. В таком случае факторизация, т.е. разложение исходного числа N на простые сомножители, даст нам цифры, из которых можно составить число, произведение цифр которого равно N.
Теперь озадачимся вопросом минимальности полученного числа. Очевидно, что простые сомножители можно «склеивать» в большие числа. Наибольший эффект даст преобразование трёх двоек в восьмёрку.
Таким образом, мы приходим к следующему алгоритму:
- Проверить частные случаи: N = 0 — ответ «10»; N = 1 — ответ «1».
- Завести массив K — количеств вхождений каждой цифры в итоговое произведение.
- Разложить N как произведение 2, 3, 5, 7 и заполнить K[2], K[3], K[5] и K[7] соответственно.
- Если N не раскладывается на такое произведение, то решения нет.
- Если же раскладывается, то последовательно пытаться выполнить преобразования произведения простых чисел в 8, 9, 6 и 4 (в таком порядке). При этом соответствующим образом модифицировать значения в K.
- Вывести число Q: сначала K[2] двоек, затем K[3] троек, K[4] четвёрок и т.д. до K[9].
Привет. Хотел спросить. А разве цифры c 0 по 9 не раскладываются как:
ОтветитьУдалить0 = 1*0
1 = 1*1
2 = 1*2
...
4 = 1*4 меньше чем 2*2
6 = 1*6 меньше чем 2*3
...
?
С разложением и преобразованием намудрил.
ОтветитьУдалитьПроще раскладывать циклом
for(k=9; k>=2; k++) while (n%k==0) n/=k;
если n==1 то ответ существует и чтоб его вывести достаточно отсортировать множители
Забросил блог, а тут, оказывается, комментарии появились...)
ОтветитьУдалитьSergey, (4 = 1*4) > (4 = 4), а требуется вывести минимальное допустимое число.
Александр, да, Вы правы - циклом действительно проще (хотя в сущности выполняется то же самое)