Решение задачи Произведение цифр с Acmp

С пояснением   Просмотров: 24


Требуется найти наименьшее натуральное число Q такое, что произведение его цифр равно заданному числу N.

Код

#include <iostream>
 
using namespace std;
int main()
{
    int n;
    cin >> n;
    if(0 == n){
        cout << 10;
        return 0;
         
    }
    if(n == 1){
        cout << 1;
        return 0;
         
    }
     
    unsigned long a[10];
    for(int i =  0; i < 10; ++i)
        a[i] = 0;
    for(int i = 9; i > 1; --i){
        while(!(n % i)){
            n/=i;
            a[i]++;
        }
    }
    if(n == 1){
        for(int i = 2; i <= 9; ++i){
            while(a[i]){
                a[i]--;
                cout << i;
            }
        }
    }
    else
        cout << -1;
    return 0;
}

         

Администратор Photo Автор: Администратор


Итак, от нас требуют найти минимальное число, произведение цифр которого равно заданному значению. Первая мысль, которая может возникнуть — перебирать числа в порядке возрастания, делить их на цифры и перемножать. Однако, с учетом допустимых диапазонов входных данных — работать это будет слишком долго.

На самом деле, в задаче есть смысл стараться подобрать делители числа N. Можно заметить, что если число делится на 8 — то его делителями будут также 2 и 4, однако, 2 разряда дадут однозначно большее число, чем один (8 < 24). Поэтому по возможности надо выбирать как можно большие цифры. Тогда логика решения заключается в том, чтобы делить число на 9 пока делится нацело и считать число девяток, потом на 8 и т.д. Если в результате такой операции получается единица - вывод осуществляется в обратном порядке (от двойки к девятке выводится количество цифр). Если же единицу получить не удалось - выводим -1 (искомого Q не существует). Дальше остается только учесть все детали. Первое - допустимым значением является ноль, но для такого значения наш алгоритм зациклится - его необходимо обработать отдельно. Кроме того, минимальным натуральным числом, таким, что произведение его цифр равно нулю является 10 (вычислить такое значение никак не получилось бы без перебора). Другая проблема - если исходное число равно единице. По описанному выше алгоритму мы продолжаем делить число на цифры пока не получим единицу, но если мы получили ее сразу - то у нас нет ни одной цифры и в файл мы ничего не выведем.


Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться