Номер армстронга на яве

5 ответов

Лучший ответ

Некоторые наблюдения:

Если ваш начальный максимум равен , ваши результаты также должны быть типов, на всякий случай ( работает для вас, поскольку нарциссические числа сильно различаются)
Если вы измените тип возвращаемого значения на «большой» , вы можете использовать для переупаковки результатов в массив …
… хотя на самом деле вам нужно просто вернуть связанный список …
Вам не нужно постоянно пересчитывать полномочия. Для каждой декады во внешнем цикле вам нужно только i ^ j, где i = 0..9, а j — количество цифр в текущей декаде.
На самом деле, вам вообще не нужно , так как вы можете просто использовать умножение для каждого десятилетия

Применяя мои идеи из моего комментария выше, а также изменяя подпись метода, вы получаете то, что работает примерно в 30 раз быстрее:

dovetalk
17 Мар 2016 в 17:46

Я не профессиональный программист, просто самоучка без опыта работы, поэтому прошу прощения, если мой код немного неаккуратен.

Я взял решение dovetalk и 1) написал его сам, чтобы лучше понять его b) внес некоторые изменения, которые значительно улучшили время выполнения для больших чисел. Надеюсь, это поможет всем, кто ищет помощь с этой проблемой:

Guadalupe Gagnon
27 Дек 2018 в 21:59

Можно довольно эффективно сгенерировать числа Армстронга. Например, все целые числа могут быть сгенерированы за 10-15 мс.

Мы можем отметить, что для каждого множества цифр, например , существует только одна сумма степеней, которая, в свою очередь, может либо быть, либо не быть представлена цифрами из набора. В примере , который может быть представлен цифрами и, следовательно, является числом Армстронга.

Исходя из этого, мы можем построить алгоритм.

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

Количество наблюдений, рассчитанное для каждой длины , равно количеству комбинаций . Таким образом, для всех меньше 10 мы сгенерируем только 92 377 множеств. Для : 20 030 009.

mnille
23 Июн 2016 в 14:52

wiredniko
17 Мар 2016 в 16:39

Основная оптимизация — не проверять все числа в диапазоне (). Загляните сюда.

David Soroko
19 Окт 2020 в 13:35

Что такое номер Армстронга в Java?

Число Армстронга в Java. Армстронг — это число, в котором сумма кубов отдельных цифр числа равна самому числу. Номер Армстронга — это особый вид номера, в котором сначала выбираются цифры, затем они кубируются, и, наконец, все кубы отдельных цифр добавляются для получения номера. Если найденное число равно исходному, то соответствующее число называется числом Армстронга. Примером числа Армстронга является 153. Если мы разбиваем цифры 153, то это 1, 5 и 3. Затем мы находим куб соответствующих чисел и, наконец, вычисляем куб чисел.

Таким образом, мы можем вычислить, является ли число числом Армстронга или нет.

Примеры числа Армстронга в Java

Мы увидим иллюстрацию числа Армстронга на Java с помощью примеров.

Пример № 1

В примере кодирования мы используем язык программирования Java, чтобы определить, является ли число числом Армстронга или нет. Если введенный номер является номером Армстронга, то программа автоматически печатает его как номер Армстронга, и если он не один, он автоматически отвечает, что номер не является номером Армстронга. Мы можем ввести трехзначные или четырехзначные значения, чтобы проверить, является ли число числом Армстронга или нет.

Логика программы такова, что во временной переменной хранится каждая цифра соответствующего числа. Затем число кубизируется, чтобы найти куб соответствующей цифры, которая хранится в другой переменной итога. Наконец, общее количество проверяется с соответствующим исходным номером. Цифры получают одну за другой, получая число, деленное на 10 на каждом шаге, а затем получая остаток от числа и затем кубируя число, чтобы получить куб соответствующей цифры.

Код:

Выход:

В первой программе мы вводим числа 370 и 153 как числа, чтобы проверить, являются ли они Армстронгом или нет. Кроме того, мы вводим 269 как число, чтобы проверить, является ли номер Армстронгом. Мы получаем соответствующий вывод программы, что числа 370 и 153 являются числами Армстронга, а число 269 не является числом Армстронга.

Пример № 2

Во втором примере кодирования мы выбираем диапазон чисел, которые проверяются, являются ли они числами Армстронга или нет. Диапазон составляет от 150 до 160. Мы выбираем диапазон и проверяем вывод, является ли число числом Армстронга или нет. Затем мы видим вывод. Используемая логика аналогична логике, используемой для поиска числа Армстронга. Соответствующие цифры числа вычисляются, а затем они кубируются и суммируются, чтобы найти окончательное общее число. Если итоговое общее число равно исходному, то они считаются числами Армстронга, которые рассчитываются.

Код:

Выход:

В примере вывода мы видим, что все числа в диапазоне от 150 до 160 были проверены на предмет того, являются ли они числами Армстронга или нет. Программа сообщила, что только 153 является числом Армстронга, чья сумма кубов цифр равна исходному числу. Все остальные цифры были указаны как не-Армстронг.

Пример № 3

В этом примере кодирования мы увидим список чисел Армстронга, которые присутствуют между 365 и 375. Мы изменяем диапазон значений, которые будут проверяться для чисел Армстронга. Примерная логика кодирования точно такая же, как и у предыдущих. Основное отличие состоит в том, что диапазон проверяемых чисел изменяется, и они немного отличаются от последней строки кода.

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

Код:

Выход:

В примере выходных данных, приведенных программой, мы видим, что только числа Армстронга 371 и 370 являются числами, в то время как другие числа не являются суммой кубов отдельных цифр, не суммирующих исходное число.

Вывод — число Армстронга в Java

В этой статье мы увидели работу и определение числа Армстронга. Сначала мы проверяем, является ли введенный номер номером Армстронга или нет. Во-вторых, мы вводим диапазон значений от 150 до 160 и проверяем количество чисел Армстронга между этими значениями. В-третьих, мы вводим диапазон чисел от 365 до 375 и выясняем, что 370 и 371 являются числами Армстронга. Числа Армстронга — это специальные числа, которые используются в теории чисел и могут использоваться для определения характера цифр некоторых чисел наряду с суммированием их кубов.

Алгоритм поиска чисел Армстронга

Найти числа Армстронга меньше N можно несколькими способами. Я выбрал следующий — создать матрицу, содержащую i строк (числа от 1 до 9) и j столбцов (степени от 1 до N.length(), то есть длины числа) в каждой ячейке которой находится число i в степени j, то есть например degreeMatrix = 2^3 = 8

Собственно встает вопрос по созданию алгоритма перебора чисел и поиск среди найденных подходящих чисел. Есть смысл искать только среди чисел которые не повторялись ранее — например от 1 до 9 — проверяются все, от 11 до 99 проверяются лишь 45 раз и только те, что идут друг за другом с условием что каждое число не меньше предыдущего и не больше следующего — 11, 12 .. 19, далее 22, 23 .. 29, далее 33, 34 .. 39 и таким образом до 99. С трех и более значными числами ситуация аналогична. Таким образом можно избежать огромного числа лишних проверок (для 2-ух значных почти в два раза уменьшается, для 3-х значных количество проверок менее 200 и т.д.)

Соответственно нужно реализовать алгоритм с использованием данных из матрицы (назовем ее проще М)

Для однозначных чисел все просто —

М(1,1), М(2,1) .. М(9,1) степень равна 1

Для двузначных как раз таки начинаются проблемы —

от 11 до 19 — М(1,2) + М(1,2), М(1,2) + М(2,2) .. М(1,2) + М(9,2)

от 22 до 29 — М(2,2) + М(2,2), М(2,2) + М(3,2) .. М(2,2) + М(9,2)

Требуется создать алгоритм суммирующий значения из матрицы в зависимости от длины числа (длин = количесвто чисел и их степень) с учетом правильной последовательности (каждое число не меньше предыдущего и не больше последующего, например 11, 129, 371 и т.д.)

Источник

➤

JAVA. ЗАДАЧА 20.10.01+. ЧИСЛА АРМСТРОНГА.

ВАРИАНТ, КОТОРЫЙ Я СПИСАЛ:

package com.javarush.test.level20.lesson10.bonus01;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/* Алгоритмы-числа
Число S состоит из M чисел, например, S=370 и M(количество цифр)=3
Реализовать логику метода getNumbers, который должен среди натуральных чисел меньше N (long)
находить все числа, удовлетворяющие следующему критерию:
число S равно сумме его цифр, возведенных в M степень
getNumbers должен возвращать все такие числа в порядке возрастания

Пример искомого числа:
370 = 3*3*3 + 7*7*7 + 0*0*0
8208 = 8*8*8*8 + 2*2*2*2 + 0*0*0*0 + 8*8*8*8

На выполнение дается 10 секунд и 50 МБ памяти.
*/
public class Solution {
    public static int[] getNumbers(int N) {
        int[] result = null;
        List<Integer> list = new ArrayList<>();
        for (int n = 1; n < N; n++) {
            int sum = 0, temp, r;
            int q = 0;
            temp = n;
            int length = (int) (Math.log10(n) + 1);
            while (temp != 0) {
                for (int i = 0; i < length; i++) {
                    int prod = 1;
                    r = temp % 10;
                    for (int j = 0; j < length; j++) {
                        prod = prod * r;
                    }
                    sum = sum + prod;
                    temp = temp / 10;
                }
            }
            if (n == sum) {
                list.add(n);
            }
        }
        result = new int;
        for (int i = 0; i < list.size(); i++) {
            result = list.get(i);
        }
        System.out.println(Arrays.toString(result));
        return result;
    }

    public static void main(String args[]) {
        long memoryStart = Runtime.getRuntime().freeMemory();
        Long t0 = System.currentTimeMillis();
        int[] result = getNumbers(10000000);
        long memoryEnd = Runtime.getRuntime().maxMemory();
        long memoTaken = memoryStart - memoryEnd;
        System.out.println(memoTaken);
        Long t1 = System.currentTimeMillis();
        System.out.println("Time need to create the arrray = " + (t1 - t0));
        System.out.println("Used Memory in JVM: " + (Runtime.getRuntime().maxMemory() - Runtime.getRuntime().freeMemory()));
    }
}

МОЙ ВАРИАНТ, СЛИШКОМ ДОЛГИЙ:

package com.javarush.test.level20.lesson10.bonus01;

import java.util.ArrayList;

/* Алгоритмы-числа
Число S состоит из M чисел, например, S=370 и M(количество цифр)=3
Реализовать логику метода getNumbers, который должен среди натуральных чисел меньше N (long)
находить все числа, удовлетворяющие следующему критерию:
число S равно сумме его цифр, возведенных в M степень
getNumbers должен возвращать все такие числа в порядке возрастания

Пример искомого числа:
370 = 3*3*3 + 7*7*7 + 0*0*0
8208 = 8*8*8*8 + 2*2*2*2 + 0*0*0*0 + 8*8*8*8

На выполнение дается 10 секунд и 50 МБ памяти.
*/
public class Solution {
    public static void main(String[] args) {
        int N = 10000000;
        long start = System.currentTimeMillis();
        int[] m = getNumbers(N);
        long finish = System.currentTimeMillis();
        for (int i : m) {
            System.out.println(i);
        }
        System.out.printf("Execution spend %d,%d sec & %d mb of memory.",
                ((finish - start)/1000), ((finish - start) % 1000), (Runtime.getRuntime().totalMemory()
                        - Runtime.getRuntime().freeMemory())/1024/1024);
    }

    public static int[] getNumbers(int N) {
        ArrayList<Integer> list = new ArrayList<>();
        ArrayList<Integer> listOfPow = new ArrayList<>();    //список степенных сумм чисел Армстронга
        for (int i = 0; i < N; i++) {
            if (i < 10) list.add(i);
            else {
                int sum = 0;
                int[] digits = new int;
                int x = 0;
                for (int j = i; j != 0; j /= 10) {
                    sum += j % 10;
                    digits = j % 10;
                }
                if (!listOfPow.contains(sum)) {
                    int summ = 0;
                    for (int digit : digits) {
                        summ += Math.pow((double) digit, (double) digits.length);
                    }
                    if (i == summ) {
                        list.add(i);
                        listOfPow.add(sum);
                    }
                }
            }
        }

        int[] result = new int;
        for (int i = 0; i < result.length; i++) {
            result = list.get(i);
        }
        return result;
    }
}

By |

Январь 12th, 2017|Categories: Уровень 20||

Решение

Конечно, данную задачу можно было решить «в лоб», т.е. сделать простой перебор всех 109 чисел и каждое число проверить. При этом на весьма солидной машине программа могла бы работать достаточно долго. Если
бы цель задания заключалась только в нахождении чисел Армстронга, а не в составлении универсальной программы, разработка которой могла бы занимать большое время, то конечно, лучше было бы за 10 минут написать и 3 часа подождать.

Идея уменьшения класса исследуемых чисел заключается в следующем : можно делать перебор не самих чисел, а значений, которые могут получаться в результате степенной суммы ( т.е. суммы цифр числа, возведенных в степень числа цифр этого числа ). Здесь используется следующее свойство : от перемены цифр местами в числе степенная сумма не меняется. Т.е. например, незачем рассматривать все числа из класса : 135, 153, 315, 351, 531 и 513; достаточно рассмотреть одно из них, например, число 135; вычислить его степенную сумму : (135)ст = 153, а потом лишь убедиться в том что число 153 — это число Армстронга. Этот метод снижает число перебираемых чисел почти в N! раз. Сам же перебор осуществляется довольно просто : рассматриваются все числа, у которых любая цифра не меньше предыдущей и не больше последующей. Например: 12, 1557, 333 и т.д.

Итак, вышеописанный метод снизил число перебираемых чисел с 109 до приблизительно 200000. Но это не все на чем стоит остановливаться. Можно применить еще одну хитрость, которая заключается в следующем : можно значительно ускорить вычисление степенной суммы. Можно заметить, что при вычислениях часто приходится многократно возводить некоторое число в некоторую степень. Чтобы это оптимизировать вводится двухмерный массив, в i-ой строке и j-ом столбце которого находится значение степенной суммы i с основанием j (например, Degree = 1j + 2j + 3j ). Таким образом , используется значение массива Degree. Это существенно ускоряет процесс вычисления, если это сравнивать с некоторым процессом, в котором
используется функция Degree(i,j), каждый раз вычисляющая значение ij. Для вычисления выражения 10j аналогичнo используется массив Degree10. Нужно заметить, что такая операция возведения в степень в программе вы полняется более 10000 раз; матрица Degree заполняется в начале программы, где операция возведения i в степень j выполняется около 8000 раз.

В промежутке 1
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407, 1634, 8208, 9474, 54748, 92727, 93084, 548834, 1741725, 4210818, 9800817, 9926315, 24678050, 24678051, 88593477, 146511208, 472335975, 534494836, 912985153.