Расщепление и сумма символов - PullRequest
Новая
       16

Расщепление и сумма символов

0 голосов
/ 26 января 2020

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

public int sumN(int N) {
        int total = 10;
        char[] n;
        ArrayList<Integer> nrs = new ArrayList<Integer>();
        int sum = 0;
        String x = "";
        if(N<=9)
            return N;
        else
        {
            while(true)
            {   
                x = Integer.toString(total);
                n = x.toCharArray();
                for(char c : n)
                {
                    nrs.add(Character.getNumericValue(c));
                }
                for(Integer i : nrs)
                {
                    sum = sum + i;
                }
                if(sum == N)
                {
                    return total;
                }
                total++;
            }
        }

1 Ответ

0 голосов
/ 26 января 2020

Ваш заголовок и описание немного расходятся, поэтому я, возможно, неправильно понял вопрос, но было интересно поработать в любом случае.

Но я думаю, что вы спрашиваете алгоритм для получения наименьшего числа чьи базовые 10 цифр складываются в N. (вопрос лучше подходит для обмена по математике).

Одно предположение: 

N > 0

Сделано несколько замечаний:

  1. Наибольшее значение для любого одиночного основания-10 di git равно 9.
  2. Наибольшее значение N, которое можно получить с помощью w цифр, равно Math.pow(10,w) - 1. (Например, если w равно 2 цифрам, то наибольшее число (10 ** 2) -1 или 99.
  3. Минимальное количество цифр x для числа, добавляемого к N, должно быть ceil (N / 9 ). (Например, для N = 20 значение должно иметь не менее 3 цифр, поскольку наибольшее значение из суммы 2 цифр равно 18 = 9 + 9.)

Таким образом, проблема уменьшается чтобы минимизировать наиболее значимое значение di git, поскольку оно будет представлять собой наименьшее возможное число независимо от младших цифр.

Таким образом, чтобы минимизировать наиболее значимое значение di git, необходимо максимизировать оставшиеся цифры ( 1) 9.

Таким образом, если x вычисляется как минимальное количество цифр: 

x = ceil(N/9)               // e.g. N=82, x=10

, то наименее значащие цифры представляют собой последовательность (x-1) 9: 

y = pow(10,(x-1))-1         // 999999999

, так что минимизация самого значительного di git становится 

z = ((N - (9 * (x-1))) * pow(10,(x-1))   // 1000000000

, а затем получается 

r = (z + y)                // 1999999999

Так как же доказать, что это наименьшее возможное число чьи цифры составляют N?

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

Вот попытка доказательства:

Предположим, что существует m, значение которого меньше чем r (выше): 

m < r

Предположим, что m содержит меньше цифр, чем r, что по определению удовлетворяет условию.

Но если 

SUM(digits of m) == SUM(digits of r) == N

и r имеет '9' для каждого ди git, который имеет m (все 9, кроме наиболее значимого ди git), а r имеет один дополнительный ди git, нет m, который может содержать меньше цифр и удовлетворять вышеуказанному условию.

Предположим, что m имеет такое же количество цифр и меньше r. В этом случае, чтобы быть меньше чем r, наиболее значимое значение di git из m должно быть меньше, чем наиболее значимое значение di git из r. Поскольку оставшиеся цифры (если они есть) r равны 9, у 'm' нет возможных оставшихся цифр, которые могли бы составить число, составляющее разницу в наиболее значимых цифрах, поэтому m не может быть тем же самым числом. цифр и имеют наиболее значимое значение di git меньше r.

Если m имеет такое же количество цифр, но наиболее значимое число di git больше r, то по определению это большее число.

Если m имеет больше цифр, чем r, то по определению это большее число.

...