• ,

level20.lesson10.bonus01;

* Алгоритмы-числа
Число 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 МБ памяти.

*/
Программа начинает очень медленно считать после нахождения числа 4679307774.
Правильно ли я понял задачу, что макс число N = 922372036854775807L?
или числа в разы меньше? а то как то в 10 секунд не уложиться помоему ))

274 комментария

Groomsh
Раз у тебя задача не принимается, то ты либо сделал что-то не так, либо не оптимизировал свой код.
Строка в условии:
На выполнение дается 10 секунд и 50 МБ памяти.
— самая главная.
Mayer
Для тех кто еще не решил, фразу «среди натуральных чисел меньше N» следует понимать как «среди натуральных чисел меньше или равных N» и ноль в данном случае натуральным числом не считается.
Samurai

    public static int[] getNumbers(int N)
    {
        int[] arr = new int[]{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};
        int k = 0;
        for (int i = 0; i < arr.length; i++)
            if (arr[i] > N)
            {
                k = i;
                break;
            } else if (arr[i] == N)
            {
                k = i + 1;
                break;
            } else
            {
                k = i + 1;
            }
        int[] result = new int[k];
        for (int j = 0; j < k; j++)
            result[j] = arr[j];
        Arrays.sort(result);
        return result;
    }
Почему не проходит?
staffelhof
а зачем делать Arrays.sort?
tanzwud
да я и не пробовал ее проверить через сервер. сам вижу что вычисления очень долго. вот и спрашиваю. Правильно ли я понял чему равно число N или его можно к примеру выбрать равным допустим 100_000 вместо MAX_LONG 922372036854775807L, либо оптимизировать, алгоритмы оптимизации нашел, но чтобы вложиться опять же в 10 сек не выглядит реальным, если только заранее все нужные числа не вставить в матрицу. Все зависит от выбранного N можно вложиться и в 1 секунду.
tanzwud
точнее даже сказать число N может быть и 922372036854775807L только программе разрешено работать всего 10 сек?
Groomsh
Метод с сигнатурой и аргументами
public static int[] getNumbers(int N)
должен натолкнуть тебя на правильный ответ =)
tanzwud
Это да только как то нестыковка из условия «Реализовать логику метода getNumbers, который должен среди натуральных чисел меньше N (long)» а там int. Да задача сама по себе интересна. Не столько ради очков, сколько ради голову поломать над различными алгоритмами
tanzwud
точнее есть огромное число Long а количество получившихся N будет естественно (int). с этим ясно. Так программа должна остановиться после 10 ти секунд или нужно чтобы из чисел Long за 10 секунд нашло все числа удовлетворяющие условию)). тянет на нобелевскую походу))
Groomsh
Скажу тебе так — когда я делал эту задачу, я не зацикливался на максимальном числе. Я просто переписавал свой алгоритм поиска раза 4 пока не дооптимизировал до допустимого уровня.
hubert
В чем нестыковка, можно узнать?
goopnigoop
А можно еще подсказку, чтоб натолкнуть на правильный ответ?
tanzwud
Да как таковой нестыковки нету. Просто я видимо куда то не туда пошел в своем решении. Задача должна найти все нужные нам числа из множества Long за 10 секунд или работать 10 секунд и найти все числа из меньшего множества? код вылаживать не имеет смысла, алгоритм работает, находит числа из 922372036854775807L множества, работая при этом пару дней и то не думаю что дошел до половины. Но как оптимизировать алгоритм чтобы он те же числа нашел за 10 сек. Читал литература о данных числах, видел что люди советуют для отпимизации но как применить на практике понятия не имею
hubert
Ну вот Groomsh решил ведь…
Не зацикливайся на граничных значениях. И не пытайся тестить на 922372036854775807L.
В тесте на таких значениях не проверяется
djfedor
Друзья, не подскажете так навскидку какие есть узкие места в плане производительности/величины объема памяти, выделяемого для переменных?

Решал правда ну очень в тупую…


public static int[] getNumbers(int N) {
        int[] result = null;
        List<Integer> result_list = new ArrayList<>();
        char[] s_mass;
        int tmp;

        for (int i = 1; i <= N; i++) {
            s_mass = String.valueOf(i).toCharArray();
            tmp = 0;
            for (char s_mass_element : s_mass) {
                tmp += Math.pow(Integer.parseInt(String.valueOf(s_mass_element)), s_mass.length);
            }
            if (tmp == i)
                result_list.add(i);
        }

        if (result_list.size() > 0) {
            Collections.sort(result_list);
            result = new int[result_list.size()];
            for (int m = 0; m < result_list.size(); m++) {
                 result[m] = result_list.get(m);
            }
        }

        return result;
    }
tanzwud
Да задача очень интерестная, я не углублялся в ее решение со стороны алгоритмов, банальное улучшение поисковика чисел Армстронга дает просто удивительные результаты.
AlRays
какие ты улучшения реализовал, если не секрет?
provisota
Подсказите пожалуйста, на каком значении надо тестировать алгоритм? У меня сейчас при N = 10^7 вычисления идут около 3 секунд, а при N = 10^8 уже около 26 секунд. Я так понимаю что максимольное N = Integer.MAX_VALUE т.е. 2147483647?
djfedor
provisota , глянь ЛС, кинул пару идей =)
tanzwud
у меня задача принялась когда N = 10^8 высисления чуть больше 10 сек заняли.
Потребление памяти ~30 мб. Хотя там и так не сильно ело память.
provisota
А не подскажешь где можно посмотреть потребляемую програмой память?
tanzwud
Отчего не подсказать. Только мой метод какой то очень простой, не знаю работает правильно или нет.
Вобщем тестирование памяти
long memoryStart = Runtime.getRuntime().freeMemory();
long memoryEnd = Runtime.getRuntime().freeMemory();
long memoTaken = memoryStart — memoryEnd; // итог получаем байты.
На всякий случай памятка сколько времени заняла работа программы
Long t0 = System.currentTimeMillis();
Long t1 = System.currentTimeMillis();
out.println(«Time need to create the arrray = » + (t1 — t0));
Про память тут есть с рисунком в низу.
stackoverflow.com/questions/3571203/what-is-the-exact-meaning-of-runtime-getruntime-totalmemory-and-freememory
provisota
действительно очень просто :) спасибо.
tanzwud
да видимо ошибся с вычислениями памяти. поправка не 30 а ~ 3Mb
kolega69
Вот результаты моей программы:

N = 2147483647

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

1 MB
318 ms

Но приниматься не хочет…
provisota
Ни фига себе результат 8О! Как-то слишком уж быстро! Где-то ты смухлевал походу. У меня приняло при N = 10^8 со временем выполнения 16секунд.
kolega69
Угу, алгоритмом смухлевал )) Можно уменьшить количество перебираемых чисел при 10^9 приблизительно до 200000. Плюс можно схитрить с возведением в степень, но я этого не делал.
tanzwud
а можно решение данного алгоритма в личку? я его пробовал тоже применить, но мне он прироста не дал почему то.
tanzwud
основная проблема была в том что проверяя числа к примеру 123 не надо проверять 321 и 213. Но создавать надо дополнительный массив, и делать дополнительную проверку. у меня время для 10*8 это не уменьшало, а дальше да прирост был но не настолько. Хотя согласен если проверить всего 200 000 чисел время вполне реальное
kolega69
Чувствую, что все черпают идеи из одного и того же ресурса ))
Sant9Iga
та да) только вот у меня запара получается с числами в которых есть ноль и которые являются числами Армстронга(370, 8208). Ведь для них числа которые нужно считать это 037 и 0288 соответственно.
kolega69
Да да да, именно здесь необходимо найти путь решения с нолями. Плюс есть числа, где их несколько, и при этом способе они должны стоять впереди. Хотя для прохождения задачи хватает и более грубых решений.
Sant9Iga
ну вот я нашел его) но код так и не проходит)
kolega69
У меня не проходило, потому что я принял 0 как натуральное число. На JavaRush принята позиция, что 0 не является натуральным числом )
tanzwud
да честно признаться думал такое решение скорее размышление на тему как уменьшить количество чисел, а нет, вполне реально создать алгоритм и применить. Значит не зря я хотя бы пытался воплотить его в жизнь)
TbI_MHE_BPELLIb
Не только на ДжаваРаш дружище, не только)
Razor
Ноль не нужен.
Сам сейчас из-за этого часа два сидел втыкал в казалось бы уже полностью оптимизированный код.

Кстати, результат:
Running for 446 milliseconds
Memory taken : 12733520 bytes
HonyaSaar
  • HonyaSaar
  • 0
  • Комментарий отредактирован 2014-01-29 20:54:31 пользователем HonyaSaar
Подскажите кто сделал, на каких пограничных значениях тестить?
мой результат для N= 2147467259

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
потрачено мили секунд: 406
память МБ: 32.019920349121094
пробовал и с нуля начинать, но тест фейлиться все равно
holodnsk
  • holodnsk
  • 0
  • Комментарий отредактирован 2014-03-10 21:26:03 пользователем holodnsk
1мс, память меньше 1к.
не идет
holodnsk
  • holodnsk
  • 0
  • Комментарий отредактирован 2014-03-10 21:31:48 пользователем holodnsk
теперь идет, и можно еще быстрее.
условия 1-912985154
goopnigoop
не укладываюсь в 10 секунд. Подскажите, дело только в оптимизации алгоритма?
LastLost
Да, попробуй оптимизировать затратные операции внутри цикла
MSBlast
На заметку тем кто ещё не прошёл.
Пол-дня просидел из-за одной строчки if (String.valueOf(i).contains(«0»)) break; которая съедала огромную кучу памяти, проходя в цикле.
jekamell
public static void main(String[] args) {
        Long t0 = System.currentTimeMillis();
        long n = (long) Math.pow(10, 8);
        int[] numbers = getNumbers(n);
        Long t1 = System.currentTimeMillis();
        System.out.println("time: " + (t1 - t0) / 1000d + " sec");
        for (int i = 0; i < numbers.length; i++) {
            System.out.print(numbers[i] + ", ");
        }
    }


time: 10.742 sec
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,

Понимаю, что 10.842 > 10, но в задании не сказано на каких параметрах тестировать… Да и у людей вроде как принималось с 18 секундами…

jvm запускается с
-Xms50m


На валидации задания отваливается менее чем за 10 секунд… Что может быть не так? :(
max
выше в ветке пишут, что надо проверять значения 1-912985154, а Math.pow(10, 8) — это всего лишь 100000000. Возможно, большая задержка в getNumbers именно при вычислении значений свыше 10^8?
jekamell
Может…
1-912985154 выполняется 100+ сек. Эх… печаль-беда… х3 что там еще оптимизировать
MSBlast
У меня принялось при проверке числа 100000000 примерно за 16 сек, смотри сколько памяти съедает процесс java.exe при выполнении
jekamell
java.exe у меня нету, на Ubunte сижу, но вроде как действительно выедается много оперативки. Спасибо за хинт
MSBlast
long memoryStart = Runtime.getRuntime().freeMemory();
long memoryEnd = Runtime.getRuntime().freeMemory();
long memoTaken = memoryStart — memoryEnd; // итог получаем байты.

Добавь в main для подсчёта затраченного объёма ОЗУ. У меня съедало около 30-35 МБ за весь цикл. Самый главный хинт, используй только примитивные типы. Никаких обёрток и объектов.
jekamell
у меня так не меряется. числа постоянно скачут, а частенько бывает, что израсходовало отрицательное кол-во памяти :).
Попробовал измерять так, как написано тут

Вот что получилось:
public static void main(String[] args) {
        Long t0 = System.currentTimeMillis();
        long n = 100000000;
        int[] numbers = getNumbers(n);
        Long t1 = System.currentTimeMillis();
        System.out.println("time: " + (t1 - t0) / 1000d + " sec");
        System.out.println("memory: " + (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) / (1024 * 1024) + " mb");
        for (int i = 0; i < numbers.length; i++) {
            System.out.print(numbers[i] + ", ");
        }
        System.out.println();
    }


Вывод:
time: 10.541 sec
memory: 37 mb
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, 
jekamell
попробовал считать для 10000000 (меньше в 10 раз) — стало жрать по 90-100 метров %) чудеса
MSBlast
Кажется мне что для степени ты используешь Math.pow(). Если это так срочно избавляйся от него.
jekamell
сделал без пова, через фор — результат тот же… 90-150 мб на 10^7… :( Дома поставлю какой-то профайлер, гляну куда память девается.
MSBlast
Постарайся использовать в цикле только int,short,byte и возможно List.
jekamell
Спасибо, MSBlast Вечером отпишусь что и как :)
jekamell
Все жрет и жрет память :)
Если после всех операций вызвать gc, то расход памяти сокращается до минимума :) Но это, наверное, все таки не совсем правильно
MSBlast
Скинь код в ЛС, разберёмся)
alnero
Не использовать Math.pow() — это очень полезное замечание.
rmk
А как тогда без него?
prodigy
time: 11.656 sec
memory: 2 mb
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,
j_stud
Задачу можно сделать за 0 сек и 0 мб :)
jekamell
можно. а примит такое «решение»? :)
j_stud
Конечно, у меня приняло.
frey
Спасибо за подсказку!)
PolyMorph
Мозги уже лопаются, в третий раз код переписан. Гугл быстро вывел на ссылку, где есть интересная фраза:
Этот метод снижает число перебираемых чисел почти в N! раз. Сам же перебор осуществляется довольно просто: рассматриваются все числа, у которых любая цифра не меньше предыдущей и не больше последующей.
Но 407 не удовлетворяет этому условию!
И вариант оттуда же с инициализацией массива тоже не подходит, занимает просто уйму памяти. Подскажите, как быть с повторяющимися цифрами?
j_stud
Подкрути счетчик.
OceanBee
Привет, я так понимаю, что нужно рассмотреть набор из цифр (0, 4, 7) где любая цифра не меньше предыдущей, посчитать сумму степеней (== 407) и затем проверить можно ли составить полученное число из представленных цифр.
Выигрыш в скорости получается за счёт того что мы даже не рассматриваем остальные варианты (0, 7, 4) (4, 0, 7) (4, 7, 0) (7, 0, 4) ( 7, 4, 0)
masterSporta
за 16 сек сделало, но тест прошла ) и всегда показывало 1 мегабайт памяти.
OceanBee
Мои результаты для числа 2_147_483_647:
time 340 ms
memory 18 Mb
Задача прошла только после того как исключил 0 из итогового результата.
Пошел учить матчасть.:)
rmk
  • rmk
  • 0
  • Комментарий отредактирован 2015-01-04 14:22:41 пользователем rmk
+1, а почему 0 не входит… вики вот например не согласна, там есть 0.
ru.wikipedia.org/wiki/%D7%E8%F1%EB%E0_%C0%F0%EC%F1%F2%F0%EE%ED%E3%E0
darkstone
  • darkstone
  • 0
  • Комментарий отредактирован 2014-06-18 02:04:29 пользователем darkstone
Memory: 2.5801162719726562 Mb.
Time: 0.855 sec.
N = 100.000.000
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
Не проходит…
darkstone
Может кто подскажет почему не принимает? Вроде памяти 2.6 Мб, по времени 1 лярд за 7.6 сек.

public class Solution {
    public static int[] getNumbers(int N) {
        final int NUMBERS = 10;
        final int SQRT = 12;
        List<Integer> list = new ArrayList<>();
        long [][] przv = new long[NUMBERS][SQRT];
        for (int i = 0; i < NUMBERS; i++) {
            for (int j = 0; j < SQRT; j++) {
                long temp = i;
                for (int z = 0; z < j - 1; z++) {
                    temp *= i;
                }
                przv[i][j] = temp;
            }
        }

        for (int i = 1; i < N; i++) {
            long mult = 0;
            int stp = 0;

            boolean flag = false;

            int num = i;
            int last = -1;
            while (num > 0) {
                if (last == -1) {
                    last = num % 10;
                    num = num / 10;
                    stp++;
                } else if (num % 10 <= last) {
                    last = num % 10;
                    if (last == 0) {
                        last = 10;
                    }
                    num = num / 10;
                    stp++;
                    continue;
                } else {
                    flag = true;
                    break;
                }
            }

            if(flag) continue;

            long res = 0;
            for (int j = i; j > 0; j /= 10) {
                res += przv[j % 10][stp];
            }
            int len = 0;
            for (long j = res; j > 0; j /= 10) {
                mult += przv[(int)(j % 10)][stp];
                len++;
            }

            if (res == mult && stp == len) {
                boolean flag2 = true;
                for (Integer num1 : list) {
                    if (num1.intValue() == res) {
                        flag2 = false;
                        break;
                    }
                }
                if (flag2) {
                    list.add((int) res);
                }
            }
        }
        int [] result = new int[list.size()];
        Collections.sort(list);
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        return result;
    }

    public static void main(String[] args) {
        Long t0 = System.currentTimeMillis();
        int[] m = getNumbers(920000000);
        Long t1 = System.currentTimeMillis();
        for (int a : m) {
            System.out.println(a);
        }
        System.out.println("Memory: " + (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory())/(1024*1024d) + " Mb.");
        System.out.println("Time: " + (t1 - t0)/1000d + " sec.");
    }
}
darkstone
В первой части создаю таблицу для цифр возведённых в определённую степень.
Во второй части отсекаю повторы: 123 321 132 312 и т. п. Рассматриваю только для 1 варианта и получившуюся сумму проверяю на число Армстронга.(Короче всё, как предлагалось в широко известном всем загугленном варианте :)) ). Может размер не правильно считаю али ещё чего? Все ресурсоёмкие операции выкинул из кода.
hubert
а давай запустим твое решение для 146511208
darkstone
  • darkstone
  • 0
  • Комментарий отредактирован 2014-06-19 17:35:14 пользователем darkstone
хах) Пробовал на другом числе, не выплыла эта ошибка. Действительно не доработал… спс!
Я уж не знал чего ещё оптимизировать…
maxim343
среди натуральных чисел меньше N
исправили бы условие
pandaFromMinsk
Это и правда отличный тест на этом числе!
strEaM
Ребят, кто уже сдал эту задачу, скажите пожалуйста, какие у вас показатели для этого числа 146511208. Сделал задачу двумя абсолютно разными способами, один почти две минуты считает, второй три минуты. Такое чувство, что в 10 секунд просто нереально уложиться, разве что заполнить список уже готовыми числами(да, с читами тоже не принимает, хоть время 0 секунд :))
4fun
[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]
Memory: 1.0004425048828125 Mb.
Time: 6.34 sec.
Все идеи по оптимизации есть в инете, большинство на англоязычных сайтах. Главное работать только с числами, не переводить в строку(я так сначала делал). Подскажу одно только, для более быстрого возведения в степень числа я сделал двумерный массив уже с готовыми числами возведенными в степень.
strEaM
Спасибо, буду пробовать
pandaFromMinsk
  • pandaFromMinsk
  • 0
  • Комментарий отредактирован 2016-04-21 22:33:29 пользователем pandaFromMinsk
Кстати, отличный совет с двумерным массивом. У меня время выполнения на тесте 146511208 с использованием массива уменьшилось примерно раза в полтора. Потом где можно было сделал преобразования int -> byte и написал процедуру сортировки данных: у меня итог выводился чуточку разбросанным.
В итоге на 146511208:
time: 4.337 sec
memory: 3 mb

Не использовал ни строки, ни коллекции, ни функции Math.
kostyazyu
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 
Memory: 14.736343383789062 Mb.
Time: 22.733 sec.

Не мудрствовал вообще. Только возведение в степень сделал через цикл(с Math.pow() было сильно дольше), а так всё вполне тривиальными методами. Думал сложнее будет.
darkstone
Memory: 0.9602279663085938 Mb.
Time: 2.014 sec.
voxfoot
Запарился с этой задачей, по времени никак не могу уложиться. Может кто — нибудь подскажет, что можно улучшить?
public static int[] getNumbers(int N) {
        int[] result = null;

        List<Integer> list = new ArrayList<>();

        for (int i = 1; i < N; i++) {
            int degree = getDegree(i);
            int input = i;
            int sum = 0;
            int k;

            do {
                k = input % 10;
                sum += Math.pow(k, degree);
            } while ( (input /= 10) > 0);

            if (sum == i) {
                list.add(i);
            }
        }
        result = new int[list.size()];

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

        return result;
    }

    public static int getDegree(int i) {
        int degree = 0;

        do {
            degree += 1;
        } while ( (i /= 10) > 0);

        return degree;
    }
voxfoot
Решено
generatorideas
Молодец! После небольшой доработки летает!
vmlopach
  • vmlopach
  • 0
  • Комментарий отредактирован 2015-06-02 12:10:09 пользователем vmlopach
хороший алгоритм, и считает быстро!
у меня чуть помедленнее, можт из-за того, что раскидал по методам,
но мне так удобней ))
QQRuZa
getNumbers(100_000_000);
Затрачено времени: 96.119 c
memory: 3.815880 mb

Задачка прошла.
Pablon
Классная задачка! Спасибо авторам за нее!
У меня прошло с такими показателями:
getNumbers(150 000 000);
Затрачено времени: 25.5 c
memory: 10 mb
Eldqs
for (int i = 1; i < N; i++) {
            int lastch = Integer.MAX_VALUE;
            int chislo  = i;
            boolean b = false;
            int count = 0;
            boolean nol = true;
            while(chislo > 0){
                if(chislo % 10 <= lastch){
                    lastch = chislo % 10;
                    chislo = chislo / 10;
                    if(lastch > 0)
                        nol = false;
                    if(nol && lastch == 0)
                        lastch = 10;
                    count++;
                }
                else{
                    b = true;
                    break;
                }
            }


участок кода перебирает числа всем известному алгоритму поиска чисел
она работает 65 секунд, а остальная часть программы работает уже меньше секунды
как еще можно оптимизировать
CoolerB
  • CoolerB
  • 0
  • Комментарий отредактирован 2014-08-06 18:12:22 пользователем CoolerB
Как правильно подсчитать объем сжираемой памяти и время?
У меня «тупой» код, без всяких проверок с любым значением выдает такой результат и не проходит проверку. Т.е. явно что-то я неправильно подсчитываю.
Memory: 0.72198486328125 Mb.
Time: 0.005 sec.
Вывожу так:
Long t0 = System.currentTimeMillis();
        System.out.println(Arrays.toString(getNumbers(1234567089)));
        Long t1 = System.currentTimeMillis();
        System.out.println("Memory: " + (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) / (1024 * 1024d) + " Mb.");
        System.out.println("Time: " + (t1 - t0) / 1000d + " sec.");
CoolerB
Кажется, я не понимаю задание. Например передаем в метод: 213, результат будет массив из:
2*2*2, 1*1*1, 3*3*3, т.е. массив из 3 чисел: [1, 8, 27] правильно?
CoolerB
понял)) клевая задачка)
CoolerB
есть смысл что-то подобное для курса многопоточности добавить, рассчет каких-то чисел со временем, которого можно добиться только в многопоточности :)
Olga-Shavkunova
  • Olga-Shavkunova
  • 0
  • Комментарий отредактирован 2014-08-12 02:30:38 пользователем Olga-Shavkunova
Мой результат (для N=146511208):

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 
Memory: 0.5377731323242188 Mb.
Time: 7.545 sec.
konstantin_v
Задачка порядком съела мозг.
В течении 2х дней возвращался к задаче, оптимизировал алгоритм. В результате задача для числа 100_000_000 решалась чуть более секунды, но памяти ела порядочно и не принималась.
В основу алгоритма оптимизации взял «идею уменьшения класса исследуемых чисел» из известного источника) Для формирования числа, «у которого любая цифра не меньше предыдущей и не больше последующей» или ноль использовал StringBuilder. Для проверки переводил полученную строку в массив цифр — bytes[] и дальше оперировал с цифрами. Но даже после всевозможных оптимизаций использования памяти задача не принималась.
В итоге плюнул, оптимизировал алгоритм voxfoot'a с банальным перебором и задача прошла.
nanoezhik
Задачка нервы потрепала… Совет от себя могу дать только один — никаких методов, только чистая арифметика!
rustamakhmetov
Проходит для N = 146511209
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

Memory: 0.0
Time: 6.283 sec на Intel i5-3330
если процессор меньше, то время будет больше…

НЕ проходит при использовании алгоритма отсечения чисел
Использование коллекций не влияет на прием задачи.
Incensus
  • Incensus
  • +1
  • Комментарий отредактирован 2014-11-15 19:57:52 пользователем Incensus
видимо 6 сек для 146 млн много, у меня за 2 сек обрабатывает это число или с алгоритмом что-то не так
levka
  • levka
  • 0
  • Комментарий отредактирован 2014-11-17 16:58:48 пользователем levka
Главное не использовать строки.
Прошло!
N=150 000 000
Time: 14.453s
31 Mb
Sdu
  • Sdu
  • 0
Пройдено. Для числа 146511208 — time: 3.586 sec. на i5-3330. Память в районе 11 mb.
С оптимизацией особо не заморачивался. Использовался доп. массив со степенями, степени рассчитывались без Math.pow (хотя, выигрыш копеечный, замерял), многопоточность ( максимум четыре потока, в зависимости от числа).
pro100boy
public static int[] getNumbers(int N) {
        // list - список с найденными числами Армстронга
        List<Integer> list = new ArrayList<>();

        // карта: String - число (одно из например 123, 132, 231 и т.п.), Long - степенная сумма
        Map<String, Integer> map = new LinkedHashMap<>();

        // заполняем 1 раз!! матрицу степеней pow_val
        int pow_val[][] = new int[10][10];
        for (int i = 0; i < 10; i++)
            for (int j = 1; j < 10; j++)
                pow_val[i][j] = (int) Math.pow(i,j);

        int stepsum = 0; // степенная сумма
        for (int i = 0; i < N ; i++)
        {
            String[] strI = (i+"").split(""); // текущее число в строку, напр. 8 7 1
            Arrays.sort(strI);                // сортируем цифры по возрастнию
            String strI_sorted = "";          // текущее число, но с цифрами по возрастанию 1 7 8
            for (int j = 0; j < strI.length; j++)
            {
                strI_sorted += (strI[j]);
            }
            int i_sorted = Integer.parseInt(strI_sorted.toString()); //178


            if (!map.containsKey(strI_sorted))
            {
                // вычисляем степенную сумму
                int r; int ss=0;
                while (i_sorted != 0) {
                    r = i_sorted % 10;
                    ss += pow_val[r][strI.length];
                    i_sorted = i_sorted / 10;
                }

                stepsum = ss;
                map.put(strI_sorted, stepsum);

            } else stepsum = map.get(strI_sorted);

            // если текущее число = степенной сумме, то в список
            if (i == stepsum) list.add(i);
        }

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

        return result;
    }


Друзья, подскажите плиз, че ж оно так долго лопатит? 10_000_000 аж за 20 сек. Вроде учитываю советы из acmp.ru/article.asp?id_text=198, но…
pro100boy
ух блин… После 2хдневных родов явил миру детище.
ЗАЧЛО!
Результат на числе 24678050:
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 
Memory, Mb: 2
Time,  sec: 3.49
nicolas
Вопрос: почему не проходит при использования алгоритма отсечения ненужных чисел?
При его использовании считает быстро:
Для 146511208:
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  
Memory: 10.560867309570312 Mb.
Time: 179ms

Да, ест больше памяти. Но тут же в приоритете время? Или нет?
nicolas
Почитал комментарии — делать в лоб. Сделал. Без Math.pow. Получил следующие результаты:
Для 146511208:
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  
Memory: 17.835693359375 Mb.
Time: 21241ms

Засчитало.
Denys_Sh
  • Denys_Sh
  • 0
  • Комментарий отредактирован 2014-12-28 23:08:16 пользователем Denys_Sh
После оптимизации и использования где возможно byte вместо int ест памяти ровно столько сколько и при пустом цикле)). Самое ресурсо/время-емкая операция оказалась разбить число на цифры.
byte[] massTemp = new byte[100]; //Массив для конвертирования числа в массив пример: 123 -> {1,2,3}
       byte currentLength = 0; //Длина массива;

static byte GetLenghtOfNumberAndConvertToArray(int N, byte[] massTemp)
    {
        int n = N;

        byte length = 0;

        while (true)
        {
            massTemp[length] = (byte) (n - ((int) n / 10) * 10);
            length++;
            if (n < 10)
                break;
            n /= 10;
        }

        byte temp;
        for (int i = length; i < length/2; i--)
        {
            temp = massTemp[i];
            massTemp[i] = massTemp[length - i - 1];
            massTemp[length - i - 1] = temp;
        }
        return length;
    }


Результат для 146511208:
<code>time: 7.776 sec
memory: 3 mb
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, 
</code>
За задачу большой респект!
iggelt
Ответ не принимается в чем может быть проблема?

public static void main(String args[]){
        long a=System.currentTimeMillis();

        int[] rez=getNumbers(146511208);
        long b=System.currentTimeMillis();

        System.out.println("time seconds "+(b-a)/1000);
        System.out.println("memory "+(Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()));
        for(int i=0;i<rez.length;i++){
            System.out.print(rez[i]+", ");
        }
    }


Возвращает:
time seconds 4
memory 1342472
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,

Вроде все цифры сходятся, что еще надо???
PikselNsk
Запустил у себя с вашими входящими данными, результат:
[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]
memory 47273104
Значит где то потеряли одно число после 88593477
iggelt
Ну, в задании написано «среди натуральных чисел меньше N » т.е. если я передаю в метод grtNumbers число 146511208, то само это число не должно проверятся на принадлежность к числам Армстронга.
Но я попробовал исправить свой алгоритм, чтобы это число выводилось тоже — не помогло…
PikselNsk
Может быть поделитесь реализацией?
DarkCloud
  • DarkCloud
  • 0
  • Комментарий отредактирован 2015-01-24 21:06:26 пользователем DarkCloud
Кстаи, есть еще один хитрющий способ: взять числа Армстронга, скажем, до миллиарда, записать их в массив… и дальше думаю уже всё ясно ))
я схитрил и таким образом решил задачу, но всё равно пытаюсь ща легальным образом решить :)
Helga
Моя первая идея, когда увидела этот ужас)
Почему-то не оставляет мысль, что задача как-то рекурсивно должна решаться.
MadHead
Идея конечно супер, но тут мы учимся, а не просто делаем что бы задача зачлась.
Я сделал 2 оптимизации.
1. Создал массив степеней чисел от 0 до 9 int[10][20] заполнил его 1 раз и уже степени брал из массива.
2. Не каждый раз преобразовывал число в массив цифр, а просчитывал в процессе.

        int count = 1;
        int[] digits = new int[]{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
        for (int i = 1; i <= N; i++)
        {
            for (int j = 0; j < count; j++)
            {
                if(digits[j] == 9){
                    digits[j] = 0;
                }else{
                    digits[j]++;
                    break;
                }
            }
            if(digits[count-1] == 0){
                count++;
                digits[count-1] = 1;
            }

        }


в итоге максимальное число int. На моем компьютере считает 40 секунд. Из мэйна выше результат 2 секунды, 2 мегабайта
SkY
  • SkY
  • 0
Наверное, просто похвастаюсь, но если интересно наведу на мысль
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
4679307774
32164049650
32164049651
40028394225
42678290603
44708635679
49388550606
82693916578
94204591914
28116440335967
4338281769391370
4338281769391371
21897142587612075
35641594208964132
35875699062250035
Time: 2014 msec
Memory: 12566 KBytes
VAS_BeasT
Натолкни, плиз.
Мои результаты:
1) 24678050
[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]
Memory: 45.85 Mb
Time: 9.29 sec
2) 124678050
[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]
Memory: 14.6 Mb
Time: 42.96 sec
3)1246780
[1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407, 1634, 8208, 9474, 54748, 92727, 93084, 548834]
Memory: 50.14 Mb
Time: 0.65 sec

т.е. чем меньше число тем больше памяти, чем больше число тем больше времени.
Заранее спс.
pavel2107
Давай, наводи.
Кстати, у тебя с нулем принялось? У меня с нулем не принимается, хотя сам Армстронг требует нуля…
Вообще не решал. Почитал, подумал, ушел. Через день пришел с работы и написал :)
RavenAoD
Тоже, что ли, похвастаться?

Процессор: Core i5-760 @ 2800 MHz
Интервал вычислений: [ 0, 10^18 )

Результаты (наилучшее время за 10 запусков):
IntelliJ IDEA 13.1.5 Ultimate:
   Time: 1586 ms
   Memory: 676 KB
Скомпилированная программа (запускалась с ключом -Xmx50M):
   Java 7 (последняя, наверное):
      Time: 1585 ms
      Memory: 266 KB
   Java 8 (jre1.8.0_25):
      Time: 1610 ms
      Memory: 256 KB

Измерялся только вызов метода, возвращающего массив с числами Армстронга. Сервисные операции не измерялись. То есть:
long timeStart = System.currentTimeMillis();
long memoryStart = Runtime.getRuntime().freeMemory();

long[] numbers = getArmstrongNumbers();

long timeEnd = System.currentTimeMillis();
long memoryEnd = Runtime.getRuntime().freeMemory();

long time = timeEnd - timeStart;
long memory = (memoryStart - memoryEnd) / 1024;
System.out.println(String.format("Time: %d ms", time));
System.out.println(String.format("Memory: %d KB", memory));


Значения памяти какие-то странные. Хотя, я её особо и не трачу.

Собственно, ничего нового я не изобрёл. Суть метода описана в уже мелькавшей здесь ссылке на алгоритм отсечения чисел. Также воспользовался некоторыми идеями, высказанными в этой теме.

Интересно. Если верить Википедии, то самое большое число Армстронга содержит 39 цифр. А что если использовать вместо лонгов что-нибудь другое?.. :)
RavenAoD
Сказано — сделано. Заменил все лонги на БигИнтежеры, решил все проблемы совместимости, потестил на «маленьких» числах, отметил удовлетворительный результат. Выкрутил сразу на максимум, до 10^39, и запустил. Этот монстр собрался с мыслями, сожрал 700 мегабайт оперативки, довольно быстро выдал начальные числа и впал в глубокую задумчивость. Прошло уже больше двух часов, чудище до сих пор что-то считает, насилует одно ядро процессора и потихоньку пухнет, периодически выплёвывая в консоль страшные числа.
RavenAoD
Оно живое! Только что, почти шесть часов спустя, чудовище выплюнуло число:
12639369517103790328947807201478392
Что-то мне лень проверять, является ли оно числом Армстронга. Пойду лучше спать.
RavenAoD
  • RavenAoD
  • 0
  • Комментарий отредактирован 2015-03-30 10:42:19 пользователем RavenAoD
Аллилуйя! Оно досчитало!

В итоге:
Список найденных чисел Армстронга (всего 89 штук): pastebin.com/PjTY18aj
Интервал поиска: [ 0, 10^39 )
Затраченное время:
63697193 мс (63697 с = 1061 мин 37 сек = 17 часов 41 минута 37 секунд)
Вычислительная мощность: Core i5-760 @ 2800 MHz / одно ядро
Можно ещё распараллелить алгоритм, чтобы задействовать 4 ядра, но… не в этот раз. :) Засим позвольте откланяться!
Gradus
Я сдам тебя Информационной Полиции, они тебя посадят за изнасилование компьютера))
RavenAoD
Так я ч0, я нич0. :) Я не при делах, это всё она! Программа! Пусть её сажают, я невиновен! :D
ttt
Надо было с самого начала параллелить)
Nimmo
  • Nimmo
  • 0
  • Комментарий отредактирован 2015-05-24 00:36:49 пользователем Nimmo
Кто может помочь? Я не понимаю, почему не проходит алгоритм. На моем слабеньком макбуке все нормально выходит, а тесты не проходит.
<code>[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]
Memory: 1.6739883422851562 Mb.
Time: 4.319 sec.</code>
Добавлено. БОЖЕ, надо просто поставить не < N, а <= N. Ошибка в условии, класс.
serhioluis
Пипец, столько убитого времени: перестановки цифр, дополнительные массивы, хэшсеты, сортировки… А решается все простым перебором, но без использования Math.pow.
vmlopach
  • vmlopach
  • 0
  • Комментарий отредактирован 2015-06-02 14:13:02 пользователем vmlopach
не верьте тому, что написано в этой статье
на самом деле реализация этих алгоритмов требует намного больше ресурсов, чем простой перебор
ttt
Столкнулся с траблой. Вроде все ок оптимизировано, но не пускает
public static int[] getNumbers(int N) {
        int[] result = null;
        List <Integer> lst = new LinkedList<Integer>();
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        int sum = 0;
        for(int i = 1; i<N; i++){
            int n = i;

            List <Integer> stv = new LinkedList<Integer>();
            while(n != 0){
                
                stv.add(0,n%10);
                n/=10;
            }
            if(!stv.contains(new Integer(0)))
                Collections.sort(stv);
            sum=0;
            int x = 0;
            for(;x!=stv.size();x++){
                sum += stv.get(stv.size()-x-1)*(Math.pow(10,x));
            }
            if(i==sum){

                int sum2 = 0;
                for (int j = 0; j < stv.size(); j++)
                {
                    sum2 += Math.pow(stv.get(j),stv.size());
                }
                
                map.put(i,sum2);
                if(sum2==i)
                    lst.add(i);
            }
            else{
                if(i==map.get(sum))
                    lst.add(i);
            }
        }

        result = new int [lst.size()];

        for (int i = 0; i < lst.size(); i++)
        {
            result[i] = lst.get(i);
        }
        return result;
    }
BigVOVA
Вы наверное не обращали внимания какие результаты добиваются в решении этой задачи. Можно заставить работать задачу под 100 раз быстрее по сравнению с вашим результатом. Это на значении всего лишь n = 10 000 000 А на значении n = 100 000 000 вы вылетаете на OutOfMemory По крайней мере если сравнивать с моим решением которое только что зачлось.

Вот ваш результат на n = 10 000 000
time: 16.148 sec
memory: 360 mb
1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407, 1634, 8208, 9474, 54748, 92727, 93084, 548834, 1741725, 4210818, 9800817, 9926315,

Вот мой на значении в 10 раз больше n = 100 000 000
time: 1.308 sec
memory: 2 mb
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,


Я не сильно разбирался с вашим алгоритмом, но в глаза бросаются очевидные вещи. В рабочем цикле где вы проверяете весь диапазон значений, а он большой:
— не стоит применять Integer, только примитивные int, а лучше byte
— Math.pow стоит заменить на заранее рассчитанный двумерный массив, мы же знаем диапазон с которым работаем. Лично мне это дало ускорение в разы.
— никаких Collections

ну а далее оптимизация самого алгоритма, мне помогла вот эта статейка
vladimirsencov
Вот мой результат
time: 0.227 sec
memory: 11 mb
[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]
public static void main(String[] args) {
		Long t0 = System.currentTimeMillis();
		int n = Integer.MAX_VALUE;
		int[] numbers = getNumbers(n);
		Long t1 = System.currentTimeMillis();
		System.out.println("time: " + (t1 - t0) / 1000d + " sec");
		System.out.println("memory: " + (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) / (1024 * 1024) + " mb");
		System.out.println(Arrays.toString(numbers));

	}
diagel
… блин, хоть на стенку в рамочку вешай такие результаты! :)))
vladimirsencov
Однако надо читать, что ноль не натуральное число хотя в Wiki последовательность идет с нулем.
aleratorio
Блин, пропарился два часа, а всего то не учёл того что «getNumbers должен возвращать все такие числа в порядке возрастания»… И даже прочитал всю ветку, и ни один пример вывода мне не намекнул…
diagel
… не знаю пока что как решить эту задачу, но на моих компах просто перебор:
for (int i = 1; i < Integer.MAX_VALUE; i++){}

занимает трындец как много времени… :( попробую «копать» со стороны реззультатов возведения в степень :) хотя хз!
diagel
… лучше перебздеть ;) чем недобздеть!!!
LincolnShow
Подскажите, что из плохо-оптимизированого первым делом бросается в глаза? Делал по комменту в этом топике: help.javarush.ru/questions/4444/level20-lesson10-bonus01, но все равно медленно — 100_000_000 считает по 30 секунд. Также не совсем врубаюсь в метод перебора чисел отсюда: acmp.ru/article.asp?id_text=198 — на ум приходят только банальные медленные переборные способы.
Помощь очень нужна! Спасибо всем, кто уже отписался, но видимо я тупой, т.к. не удается до конца вникнуть в некоторые комменты.

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

import java.util.ArrayList;
import java.util.Date;

/* Алгоритмы-числа
Число 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[] digits = new int[] {0,1,2,3,4,5,6,7,8,9};
        byte[] number = new byte[10];
        ArrayList<Integer> foundNumbers = new ArrayList<>();
        int sum = 0;
        byte count, lastCount = 1;

        for (int i = 0; i <= N; i++)
        {
            count = (byte) String.valueOf(i).length();
            if (count > lastCount){
                updateDigits(digits);
                lastCount += 1;
            }
            int iBackup = i;
            for (byte j = 0; j < 10; j++){ //Добавляем цифры из числа в массив number[]
                number[j] = (byte) (i % 10);
                i /= 10;
            }
            i = iBackup;

            for (byte k = 0; k < 10; k++){ //Находим сумму 
                sum += digits[number[k]];
            }
            if (sum == i) foundNumbers.add(i);
            sum -= sum;
        }
        int[] result = new int[foundNumbers.size()];
        for (int i = 0; i<result.length; i++) result[i] = foundNumbers.get(i);
        return result;
    }
    public static int[] updateDigits(int[] digits){ //метод возводит в степень все числа из массива digits[]
        for (int i = 0; i<digits.length; i++){
            digits[i] = digits[i]*i;
        }
        return digits;
    }
}
forza
Программа не компилируется на сервере… подскажите, в чем косяк


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 int[] getNumbers(int N) {

        int[][] matrix = new int[11][10]; //i - степень/строка, j - цифра/столбец
        for (int i = 0; i < 11; i++){
            for (int j = 0; j < 10; j++){
                int pr = 1;
                for (int k = 0; k < i ; k++){
                    if (i == 10 && j == 9)
                        break;
                    pr *= j;
                }
                matrix[i][j] = pr;
            }
        }

        ArrayList<Integer> listres = new ArrayList<>();

        for (int n = 1; n <= N; n++){

            boolean ournumber = true;

            int nt = n;
            byte b1 = 0;
            byte b2 = 0;
            while(nt > 0) {
                b2 = (byte)(nt % 10);
                b1 = (byte)(nt % 100 / 10);
                if (b1 > b2){
                    ournumber = false;
                    break;
                }
                nt /= 10;
            }

            nt = n;
            b1 = 0;
            while(nt > 0) {
                b1 = (byte)(nt % 10);
                if (b1 == 0 ){
                    ournumber = true;
                    break;
                }
                nt /= 10;
            }

            if (ournumber){

                nt = n;
                byte pow = 0;
                while(nt > 0) {
                    nt /= 10;
                    pow++;
                }

                nt = n;
                int summ = 0;
                byte temp = 0;
                while(nt > 0) {
                    temp =(byte)(nt % 10);
                    summ += matrix[pow][temp];
                    nt /= 10;
                }

                //get a summ===============================================

                int st = summ;
                pow = 0;
                while(st > 0) {
                    st /= 10;
                    pow++;
                }

                st = summ;
                int ns = 0;
                temp = 0;
                while(st > 0) {
                    temp =(byte)(st % 10);
                    ns += matrix[pow][temp];
                    st /= 10;
                }

                if (summ == ns && !listres.contains(summ)){
                    if (summ <= N)
                        listres.add(summ);
                }
            }
        }

        int[] result = new int[listres.size()];
        listres.sort(null);
        for (int i = 0; i < listres.size(); i++)
            result[i] = listres.get(i);

        return result;
    }

    public static void main(String[] args) throws Exception{

        long timeStart = System.currentTimeMillis();
        long memoryStart = Runtime.getRuntime().freeMemory();


        int[] arr = getNumbers(146511208);

        long timeEnd = System.currentTimeMillis();
        long memoryEnd = Runtime.getRuntime().freeMemory();

        long time = timeEnd - timeStart;
        long memory = (memoryStart - memoryEnd) / 1024;
        System.out.println(String.format("Time: %d ms", time));
        System.out.println(String.format("Memory: %d KB", memory));


        for (int i : arr)
            System.out.print(i + " ");
    }
}


Отправляю без метода main.
Результаты для 146511208:
Time: 11695 ms
Memory: 983 KB
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
forza
  • forza
  • 0
  • Комментарий отредактирован 2015-08-16 23:13:44 пользователем forza
Приняло после того, как отказался от использования коллекций. Хотя в условии ничего об этом ограничении не сказано…
P.S. После небольшой модернизации результат для 146511208: [Time: 2422 ms Memory: 3 MB]
Dark
  • Dark
  • 0
  • Комментарий отредактирован 2015-08-19 15:32:07 пользователем Dark
Решил с первого раза. Логика такая: самое трудоемкое — возведение в степень, следовательно этот процесс надо сделать всего один раз, а потом уже брать готовые результаты. Дальше — простой перебор. Больше ничего не оптимизировал. Задача принята.
На счёт нуля в википедии:
… В русской литературе обычно нуль исключён из числа натуральных чисел...
То есть спорить можно долго, но в данной задаче 0 не нужен.

На счёт включать ли число N в поиск.
В задаче четко сказано:
среди натуральных чисел меньше N
ни о каких до <= N речи не идет, а комменты выше только запутывают…

Ну, и естественно, ни о каких приведениях типов к строке и обратно речи быть не может.
chekist
  • chekist
  • 0
  • Комментарий отредактирован 2015-08-20 17:44:37 пользователем chekist
Печально, решил задание простым сопоставление известных чисел Армстронга(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). Хотя до этого два алгоритма не приняло. Тут подробнее про числа Армстронга и оптимизацию
Patrio
  • Patrio
  • 0
  • Комментарий отредактирован 2015-09-14 21:39:42 пользователем Patrio
Да-да, слушайте больше тех людей, которые говорят что оптимизация ничего не дает… Вот вам 3 результата у меня: сначала перебор в лоб (суть ясна, здесь время в сек., дальше в мс.), потом оптимизация №1 из ссылки выше, затем к ней добавляем оптимизацию с двумерным массивом.
p.s. Сдал кучу вариантов, а оказалось цикл крутить надо с 1, а не с 0 ))))

без оптимизации:
<code>
548834 time: 0sec
1741725 time: 0sec
4210818 time: 2sec
9800817 time: 6sec
9926315 time: 6sec
24678050 time: 14sec
24678051 time: 14sec
88593477 time: 65sec
146511208 time: 102sec</code>

Оптимизация №1
<code>
548834 time: 0sec
9800817 time: 0sec
4210818 time: 0sec
1741725 time: 0sec
9926315 time: 0sec
24678051 time: 3sec
24678050 time: 7sec
88593477 time: 12sec
146511208 time: 29sec</code>

Оптимизация №2
<code>
548834 time: 22 ms
9800817 time: 41 ms
4210818 time: 41 ms
1741725 time: 48 ms
9926315 time: 53 ms
24678051 time: 350 ms
24678050 time: 799 ms
88593477 time: 1394 ms
146511208 time: 3504 ms
Fulltime: 5985 ms</code>
Liclic
  • Liclic
  • 0
  • Комментарий отредактирован 2015-09-28 22:46:31 пользователем Liclic
Помогите! Вот код. Вроде все учел. Результат при 146511208 Memory: 3.258026123046875 Mb.
Time: 1.469 sec. Что делаю не так?
public class Solution {
    public static int[] getNumbers(int N) {
        final byte NUMBERS = 10;
        final byte SQRT = 12;
        List<Integer> list = new ArrayList<>();
        int [][] przv = new int[NUMBERS][SQRT];
        for (byte i = 0; i < NUMBERS; i++) {
            for (byte j = 0; j < SQRT; j++) {
                int temp = i;
                for (int z = 0; z < j-1; z++) {
                    temp *= i;
                }
                przv[i][j] = temp;
            }
        }

        for (int i = 1; i <N; i++) {
            long mult = 0;
           byte stp = 0;

            boolean flag = false;

            int num = i;
            int last = -1;
            while (num >0) {
                if (last == -1) {
                    last = num % 10;
                    num = num / 10;
                    stp++;
                } else if (num % 10 <= last) {
                    last = num % 10;
                    if (last == 0) {
                        last = 10;
                    }
                    num = num / 10;
                    stp++;
                    continue;
                } else {
                    flag = true;
                    break;
                }
            }

            if(flag) continue;

            int res = 0;
            for (int j = i; j > 0; j /= 10) {
                res += przv[j % 10][stp];
            }
            for (int j = res; j > 0; j /= 10) {
                mult += przv[j % 10][stp];
            }

            if (res == mult&&res<N) {
                boolean flag2 = true;
                for (Integer num1 : list) {
                    if (num1.intValue() == res) {
                        flag2 = false;
                        break;
                    }
                }
                if (flag2) {
                    list.add(res);
                }
            }
        }
        int [] result = new int[list.size()];
        Collections.sort(list);
        for (int i = 0; i < list.size(); i++) {

                result[i] = list.get(i);

        }
        return result;
    }

    public static void main(String[] args) {
        Long t0 = System.currentTimeMillis();
        int[] m = getNumbers(146511208);
        Long t1 = System.currentTimeMillis();
        for (int a : m) {
            System.out.println(a);
        }
        System.out.println("Memory: " + (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) / (1024 * 1024d) + " Mb.");
        System.out.println("Time: " + (t1 - t0)/1000d + " sec.");
    }
}
Lexw
откомментируйте свой код пожалуйста
на первый взгляд у вас много лишнего

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

Время не засекал, приняло с 1го раза
NTFS
  • NTFS
  • 0
  • Комментарий отредактирован 2015-10-15 14:41:33 пользователем NTFS
не актуально
Snusmum
Подскажите пожалуйста, какие в данный момент требования к результату и коду:
1. Требуется, чтобы выведены были числа <N или <=N?
2. Допустимо ли использовать ArrayList?
3. Другие специфические ограничения?
Отрабатывает для числа 912985154 за 2.624 сек, <0.7 Mb (для 2147483647 — 6.233 сек), но не принимается ни с отказом от ArrayList, ни с включением/исключением N.
Lexw
1. for (int i = 1; i <N; i++)
2. Можно
3. проверье вывод. числа должны быть такими(Числа арсмтронга):
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, 4679307774, 32164049650, 32164049651

если ВСЕ числа совпадают — скинь свой код, можно в личку, я посмотрю.
Snusmum
Совпадают до 912985153.
А как быть с тем, что в метод getNumbers передаётся число типа int?
Lexw
а что не так?
в метод передаётся число N, нужно найти все числа от 1 до <N
Snusmum
Так максимальное значение 2147483647.
Или надо изменить на long?
Lexw
Менять не надо
У меня приняло с int
Snusmum
  • Snusmum
  • 0
  • Комментарий отредактирован 2015-10-06 14:50:56 пользователем Snusmum
… промахнулся
Lexw
я вообще тестировал только до 1 000 000
если алгоритм работает правильно, то он и дальше должен работать верно
Snusmum
Ясно. Мой вариант работает правильно и укладывается в рамки только для чисел типа int. Если переделать на long, то уже не проходит по времени, да и числа хотя бы 4679307774 не смог выявить.
Сейчас ещё покопаюсь и если не заработает, то отправлю в личку.
Спасибо за помощь.
Snusmum
Для long тоже работает, но уже медленнее 10и секунд.
Отправил код в личку.
Snusmum
  • Snusmum
  • 0
  • Комментарий отредактирован 2015-10-06 15:03:11 пользователем Snusmum
А как корректно тестировать протестировать на числах большего, чем максимальное целое, чтобы получить 4679307774, 32164049650, 32164049651?
Snusmum
В советы по решению:
Код приняло после того, как убрал все static переменные из класса. Остались только
public static int[] getNumbers(int N)
и ещё одна функция, необходимая для реализации алгоритма.
Спасибо Lexw за совет.
sheyl
спасибо тебе, человечек. разбил отдельные операции по public static методам и потратил на поиски недочета 2 дня. Ты сделал мой день!!! Еще раз спасибо!
smoomrik
Получился алгоритм который очень быстро считает. Делал по рекомендациям из того самого источника через рекурсию и матрицу возведения в степень.
на Integer.MAX_VALUE
time: 0.036 sec
memory: 1 mb
NataliaIlchenko
Простите глупую IT-шницу. А на каком процессоре должно быть 10 сек? У меня старенький-старенький :))))
staffelhof
не особо задавайтесь вопросом времени, у меня получалось по тестам — 113 секунд на числе 912985154, но решил попробовать сдать — и задача принялась
NataliaIlchenko
Сдала на AMD 3200+
N = 100000000
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
Memory: 0 Mb
Time: 78 s
Алгоритм простейший. Один ArrayList, один массив int и примитивы int.
Peras
  • Peras
  • 0
  • Комментарий отредактирован 2015-12-08 10:49:21 пользователем Peras
Объясните, пожалуйста, глупому! ГДЕ ЧИСЛО S????????????? Во всех кодах, выложенных вами я его не нашел
Snusmum
Все анализируемые числа меньше N и есть числа S, которые надо проверить самовлюблённость.
Peras
Спасибо тебе, добрый человек. Я б не догадался
Peras
Кому, не сложно, скиньте, пожалуйста, в личку код, который работает при проверке на 100 000 000 менее 80 сек. Сам то я решил, только при проверке на 100 000 000 отметки в менее 100 сек я не достиг.
olegshan
При просчете числа 534 494 836 программа принялась со следующим показателем:



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

Тот редкий случай, когда я в глубине души хотел бы, чтобы проверка была более строгой и все же заставила меня переделать решение :)
ksandr
Вообщем я не могу понять что не так то:( Пробовал по разному, и массив степеней перебором заполнял без Math.pow, и вместо ArrayList массив использовал, на скорость влияют в районе +-0,5 сек, так что оставил варианты с меньшим листингом. Посмотрите пожалуйста, все таки хочется сдать оптимизированный вариант, хотя уже и мысли есть забить и переделать все в лоб:)
public class Solution {

	public static void main(String[] args) {

		long timeStart = System.currentTimeMillis();
		int[] result = getNumbers(146511208);
		long timeEnd = System.currentTimeMillis();
		long memoryStart = Runtime.getRuntime().totalMemory();
		long memoryEnd = Runtime.getRuntime().freeMemory();
		for (int i : result) {
			System.out.println(i);
		}
		System.out.println(timeEnd - timeStart + "ms");
		System.out.println((memoryStart - memoryEnd) / 1024 + "kb");
	}

	public static int[] getNumbers(int N) {

		List<Integer> list = new ArrayList<>();

		int[][] degree = new int[10][11];
		for (int i = 0; i < 10; i++) {
			for (int j = 0; j < 11; j++) {
				degree[i][j] = (int) (Math.pow(i, j));
			}
		}

		for (int i = 1; i < N; i++) {
			boolean isTrue = true;
			byte pow = 0;
			int tmp = i;
			while (tmp > 0) {
				if (tmp % 100 / 10 > tmp % 10 && tmp > 9 && tmp % 10 != 0) {
					isTrue = false;
					break;
				}
				tmp /= 10;
				pow++;
			}

			if (isTrue) {
				byte newPow = 0;
				int sum = 0;
				tmp = i;
				while (tmp > 0) {
					sum += degree[tmp % 10][pow];
					tmp /= 10;
				}
				tmp = sum;
				while (tmp > 0) {
					tmp /= 10;
					newPow++;
				}
				int controlSum = 0;
				tmp = sum;
				while (tmp > 0) {
					controlSum += degree[tmp % 10][newPow];
					tmp /= 10;
				}

				if (controlSum == sum && !list.contains(sum) && sum < N) {
					list.add(sum);
				}
			}
		}

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

		return result;
	}
}


Вот вывод
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
2182ms
2703kb
ksandr
Не актуально, уже решил.
sheyl
  • sheyl
  • 0
  • Комментарий отредактирован 2016-01-13 19:33:04 пользователем sheyl
не актуально. решил
ab_random
Как???? 8-значные Армстронги за 1,2 ± секунды выводит, а задача не принимается:(
mysterio7
что не так, не подскажите? тест для 10 в 8 степени проходит за 3,5 секунды и тратится около 1.6 мб.
import java.util.*;
import java.util.ArrayList;
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 n=(""+(N-1)).toCharArray().length;
        int mp[][]=new int[10][];
        for(int i=0;i<10;i++)
            mp[i]=new int[n];
        for(int i=0;i<=9;i++)
            for(int j=1;j<=n;j++)
            {
                int f=1;
                for(int k=1;k<=j;k++)
                    f*=i;
                mp[i][j-1]=f;
            }

        // выборка чисел (каждая последующая цифра
        // не меньше предыдущей)
        List<Integer> sp=new ArrayList<Integer>();
        th: for(int S=1;S<N;S++)
        {
            int ns = S;
            int nt,np=-1;
            while (true)
            {
                nt =  (ns - ( ns / 10) * 10);
                if(nt<np)
                    continue th;
                if (ns < 10)
                    break;
                ns /= 10;
                np=nt;
            }
            sp.add(S);
        }

        // перебор списка
        String rs="";
        int t=0;
        byte mc[]=new byte[100];
        byte mr[]=new byte[100];
        for(int S:sp)
        {
            int ns = S;
            int M = 0;
            while (true)
            {
                mc[M++] = (byte) (ns - ( ns / 10) * 10);
                if (ns < 10)
                    break;
                ns /= 10;
            }

            int res=0;
            for(int k=0;k<M;k++)
            {
                res+=mp[mc[k]][M-1];
            }

            // проверка на совпадение массивов цифр
            int ks=0,nres=res;
            int j=0;
            while (true)
            {
                mr[j++] = (byte) (nres - ( nres / 10) * 10);
                if (nres < 10)
                    break;
                nres /= 10;
            }
            if(M==j)
            {
                Arrays.sort(mc,0,M);
                Arrays.sort(mr,0,M);
                for (int e=0;e<M;e++)
                {
                    if(mc[e]==mr[e])
                        ks++;
                    else break;
                }
            }
            if(ks==M)
            {
                rs += res + " ";
                t++;
            }
        }

        //формирование массива чисел Армстронга
        String mst[]=rs.split(" ");
        int[] result = new int[t];
        int p=0;
        for(String b:mst)
        {
            result[p++]=Integer.parseInt(b);
        }
        Arrays.sort(result);
        return result;
    }

    public static void main(String[] args)
    {
        long t,m;
        t=System.currentTimeMillis();
        m=Runtime.getRuntime().freeMemory();
        int N=(int)Math.pow(10,8);
        int[] ms=getNumbers(N);
        for(int s:ms)
            System.out.println(s);
        System.out.println("Time: "+(System.currentTimeMillis()-t));
        System.out.println("Memory: "+(m-Runtime.getRuntime().freeMemory()));

    }
}
mysterio7
вопрос решён!
Sygurny
Гы-гы-гы! Я не знаю как, но я решил эту дол… замечательную задачу! хехе! ура!
Если кому поможет, то есть такой метод для строки как toCharArray(). И мой основной цикл уместился в 10 строк!
ab_random
Люди добрые, помогите, пожалуйста!!! Шайтан-машина задачу не принимает.
Высчитывает результат для 8-значного N чуть больше секунды (9-значные за 11-13):
99999999
1
2
3
4
5
6
7
8
9
153
370
371
407
1634
8208
9474
4150
4151
54748
92727
93084
548834
1741725
4210818
9800817
9926315
24678050
24678051
88593477
Time: 1161 ms
Memory: 1908 KByte

Алгоритм составлял на основе этого описания. Только степенную сумму брал максимальную, чтобы с ведущими нулями не запариваться.
Вот мой код с комментариями:
package com.javarush.test.level20.lesson10.bonus01;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Date;

/* Алгоритмы-числа
Число 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) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        long start = Runtime.getRuntime().totalMemory();
        long timeStart = (new Date()).getTime();
        for (int i: getNumbers(N)) {
            System.out.println(i);
        }
        long timeEnd = (new Date()).getTime();
        long end = Runtime.getRuntime().freeMemory();
        System.out.println("Time: " + (timeEnd - timeStart) + " ms");
        System.out.println("Memory: " + (start-end)/1024+ " KByte");
    }

    public static int[] getNumbers(int N) {
        int[] armstrongs = new int[88];     // массив удовлетворяющих условию чисел
        int armstrong;                      // число, проверяемое на соответствие условию (используется в самом конце)
        int countArm = 0;                   // количество найденных чисел Армстронга
        int count = 0;                      // счетчик, используется постоянно в разных местах
        // считаем количество цифр в N
        int local = N;
        while (local > 0) {
            local /= 10;
            count++;
        }

        // создайм массив degree (степень) и заполняем его; столбцы - цифры 0-9, строки - их степени, ^1 - ^count
        int[][] degree = new int[10][count];
        for (int i = 0; i < degree.length; i++) {
            for (int j = 0; j < degree[i].length; j++) {
                degree[i][j] = 1;
                for (int k = 0; k < j + 1; k++) {
                    degree[i][j] *= i;
                }
            }
        }

        // ищем числа Армстронга через степенную сумму
        int[] numbers = new int[12];                // массив для хранения цифр числа
        int suspect;                                // число, подозреваемое на Армстронга
        int temp;                                   // просто временная переменная
        local = 1;
        for (int i = 0; i < count; i++) {           // 10^count - для ограничения перебора
            local *= 10;
        }
        outer: for (int i = 1; i < local; i++) {
            suspect = i;                            // "подозреваем" текущее i
            count = 0;
            while (suspect > 0) {                   // тут мы разбиваем нашу степенную сумму по цефрам
                numbers[count] = suspect % 10;      // и если она не максимальная из своих цифр,
                if ((count > 0) && (numbers[count] < numbers[count-1]))
                    continue outer;                 // т.е. 153 или 315 вместо 531, то перещелкиваем ВНЕШНИЙ цикл
                suspect /= 10;
                count++;
            }
            // получаем степенную сумму из "максимального" распределения цифр - suspect - (531)ст == 153
            for (int j = 0; j < count; j++) {
                suspect += degree[ numbers[j] ][count - 1];
            }

            // получаю степенную сумму из степенной суммы - armstrong - (153)ст ? 153
            temp = suspect;
            armstrong = 0;
            while (temp > 0) {
                armstrong += degree[temp % 10][count - 1];
                temp /= 10;
            }

            // если они совпадают, значит нашли число Армстронга. Добавляем его к массиву чисел Армстронга
            if (armstrong == suspect) {
                armstrongs[countArm] = suspect;
                countArm++;
                //System.out.println(armstrong + " " + countArm);
            }
        }

        //т.к. для N == xyz мы ищем вплоть до 999, отсекаем числа, большие N
        for (int i = 0; i < countArm; i++) {
            if (armstrongs[i] > N) {
                countArm = i;
                break;
            }
        }

        // в массив попадают единички от 10, 100, 1000... - считаем их
        count = 0;
        for (int i = 1; i < countArm; i++) {
            if (armstrongs[i] == 1)
                count++;
        }

        // составлем результирующий массив, пропуская единички
        int[] result = new int[countArm - count];   // их количество учитывается при создании result
        count = 0;
        for (int i = 0; i < countArm; i++) {
            if ((armstrongs[i] != 1) || (i == 0))
                result[count++] = armstrongs[i];
        }

        return result;
    }
}

Что в нём не так?
ksandr
Протестируйте с этим числом 146511208.
ab_random
24678051
88593477
146511208
Time: 12131 ms
Memory: 1909 KByte

Немного превышает время, но это девятизнак. А тут писали, что задача принимается с восьмизначным N.
ksandr
И Вас в выводе ничего не смущает? Ничего лишнего нет? Прочитайте еще раз задание. В принципе можно даже на «1» протестировать и будет видна ошибка.
ab_random
Должен возвращать все такие числа в порядке возрастания.
Мой getNumbers() и возвращает отсортированный (вначале не сортировал, в середине не сходилось, исправил) массив этих чисел. Весь вывод в консоль- от функции main(), но я её затираю перед проверкой.
ksandr
«который должен среди натуральных чисел меньше N»
ab_random
Мамин ёжик!!! Несколько дней над этой задачей бился, а дело лишь в простой невнимательности… Спасибо большое:-)
Foxandr
time: 0.253 sec
memory: 2 mb
Foxandr
  • Foxandr
  • 0
  • Комментарий отредактирован 2016-01-31 23:57:27 пользователем Foxandr
решил с 3ей попытки, а всё потому, что забыл про то, что числа должны быть меньше N (((
для числа N=2147483647 время такое выполнения:
time: 0.343 sec
memory: 3 mb
Процессор AMD 6 ядер.
ereomamd86
  • ereomamd86
  • 0
  • Комментарий отредактирован 2016-02-11 21:47:55 пользователем ereomamd86
Люди помогите! прочитал про оптимизацию Сам же перебор осуществляется довольно просто: рассматриваются все числа, у которых любая цифра не меньше предыдущей и не больше последующей. Например: 12, 1557, 333 и т.д. Но как это зделать?

public class Solution {
    public static void main(String[] args) {
        Long t0 = System.currentTimeMillis();
        long n = 100000000;
        int[] numbers = getNumbers(2000000);
        Long t1 = System.currentTimeMillis();
        System.out.println("time: " + (t1 - t0) / 1000d + " sec");
        System.out.println("memory: " + (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) / (1024 * 1024) + " mb");
        for (int i = 0; i < numbers.length; i++) {
            System.out.print(numbers[i] + ", ");
        }
    }
    public static int[] getNumbers(int N) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        int[][] matrix = new int[10][10];
        for(int i=0;i<10;i++)
        {
            for(int j=0;j<10;j++)
            {
                int a=1;
                for(int k=0;k<j;k++)
                {
                    a*=i;
                }
                matrix[i][j]=a;
            }
        }
        for(int i=1;i<N;i++)
        {
            int length = String.valueOf(i).length();
            int number=i;
            int sum=0;
            int div;
            while (number != 0)
            {
                sum+=matrix[number%10][length];
                number=number/10;
            }
            if(sum==i)
                list.add(sum);
        }
        int[] result = new int[list.size()];
        for(int i=0;i<list.size();i++)
        {
            result[i]=list.get(i);
        }
        return result;
    }
}
hixel
Кому лень читать все комменты(а часть из них еще и не верна):

1. Меньше N означает СТРОГО меньше, а не меньше либо равно
2. 0 — не является натуральным числом, пусть и в вики сказано что является
3. Самая главная оптимизация — это занесение всех степеней до K(я выбрал до 11, т.к разрядность Int не больше). Именно это по максимуму и ускоряет расчет.

П. С Буду благодарен если кто-нибудь все-таки объяснит что значит фраза из статьи которую все тут читали с acmp: «число дожно быть не меньше предыдущего, но и не больше следующего»
Например в числе 4 210 818 двойка меньше 4-х и больше следующей еденички
abbath0767
Плюсую — ссылка не доступна, может у кого осталась копия?
abbath0767
  • abbath0767
  • 0
  • Комментарий отредактирован 2016-02-19 20:59:48 пользователем abbath0767
для таких как я:
Конечно, данную задачу можно было решить «в лоб», т.е. сделать простой перебор всех 10^9 чисел и каждое число проверить. При этом на весьма солидной машине программа могла бы работать достаточно долго. Если бы цель задания заключалась только в нахождении чисел Армстронга, а не в составлении универсальной программы, разработка которой могла бы занимать большое время, то конечно, лучше было бы за 10 минут написать и 3 часа подождать.

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

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

В промежутке 1<=N<=9 программа находит следующие 32 числа Армстронга:

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.
GabbazovRuslan
  • GabbazovRuslan
  • 0
  • Комментарий отредактирован 2016-02-24 01:56:32 пользователем GabbazovRuslan
Во-первых БОЛЬШОЕ СПАСИБО ребятам за отличную задачу. Мозг мой поскрипел над ней весьма конкретно и это было приятно.

Мои пять копеек к посту выше (может уже было — я все не читал извиняюсь):
Уходите от преобразований чисел в строки и обратно. Лично меня это сильно выручило. Насчет того как находить «составляющие» цифры и длину — % и / вам в помощь (погуглите просто там ничего трудного). Это подлиннее чем просто взять строку и ее длину конечно, но сильно быстрее тем не менее.

Уважаемый hixel, вот как я понял ответ на ваш вопрос и применил это в своем решении:
Не за чем проходить в цикле и возводить в степень каждое число, ибо от перемены слагаемых сумма не меняется (1^3+5^3^3^3 = 5^3+1^3^3^3 и т.п.). Конкретно из вашего примера: надо проверить число 1240(!)188 (я это делал так — ноль «игнорировал», что «добавляло» некоторое количество дубликатов, затираемых в set'е, но думаю это не совсем прям оптимум) и все остальные комбинации этих цифр уже нет необходимости проверять. В вашей же цитате уже готовый алгоритм по отсеву «лишних» цифр (там правда надо еще про нули добавить иначе у меня по крайней мере не сходилось, ибо «0112488» вам просто не встретится если не заниматься этим отдельно конечно).

Соответственно как вариант (по крайней мере я пошел таким путем) внутри основного цикла находим всех «кандидатов» сузив перед этим список проверяемых цифр и кидаем их в TreeSet (не производительная коллекция, но зато избавляет от последующих поисков дубликатов и сортировок — у меня с ней сдалось), а потом уже исключительно для элементов внутри этого сета делаем все то же и так же чтобы уже только числа Армстронга закинуть в итоговый массив.

Всем удачи!
arver
Спасибо огромное за задачу! Мучился над ней целых два дня....(очень радовался когда сдал).
Тестировал для 10^7 сначала занимало 34мб и 9 секунд, довел до 40мб и 36мс.
Joysi
  • Joysi
  • 0
  • Комментарий отредактирован 2016-03-09 16:59:23 пользователем Joysi
Ради принципа решал «не вглубь, а вширь». Результаты (для Integer.MAX_VALUE на i7 3+ GHz 8 Gb JDK7 64bit):
Memory used=665 Кilobytes
Time wasted=11232 ms

Оптимизировал по занимаемому месту в памяти + ускорил, отказавшись в цикле от операций возведения в степень и деления по модулю. Для этого заранее строил массив степеней цифр от 0 до 10 в памяти (int[100] int[10][10] будет медленнее) и держал еще два массива int[10] для хранения текущих цифр числа (чтобы избавиться от тормозных делений и остатков от делений). В цикле честно подсчитывал сумму степеней для всех 2+ миллиардов возможных значений. Если бы раскидал по потокам возможно было бы еще быстрее (уже лень было).

P.S. Я это к тому, Так что пора ужесточать условия по времени работы :).

Оценка времени/памяти:
public static void main(String[] args) {
  long memStart = Runtime.getRuntime().freeMemory();
  long timeStart = System.currentTimeMillis();
  int[] numbers = getNumbers(2147483647);
  long memEnd = Runtime.getRuntime().freeMemory();
  long timeEnd= System.currentTimeMillis();
  for (int i = 0; i < numbers.length; i++) System.out.println(numbers[i]);
  System.out.println("Memory used=" + ((memStart-memEnd)>>10) + " Кbytes");
  System.out.println("Time wasted=" + (timeEnd-timeStart) + " ms");
}
Byshevsky
Для этого заранее строил массив степеней цифр

Читал топик и заметил что у многих весьма странный по моему мнению подход к решению.
Объясните, зачем изобретать велосипед, если вы таки отказались от изобретения колеса и применили имеющееся решение (таблица степеней)Так если вы уже согрешили в малом то почему не пустится во все тяжкие и не записать в программу таки не таблицу степеней, а таблицу чисел Армстронга хоть до трилиона трилионов, и тупо при запуске считать за пару наносекунд нужные значения из неё?
Joysi
Просто грубый деревенский метод убивает алгоритмизацию задачи.
Я просто хотел поэкспериментировать и донести, что пора менять условия задачи и, например, уже требовать укладывать вычисления в 0.1 — 1 сек.
Хранить и выдавать заранее посчитанные — это уже не задача будет (тогда можно и готовый код сгуглить и скопипастить — зачем тогда учиться тут вообще). А смена требований по времени — подстегнет к алгоритмам (типа вот так правильнее сказать) когда деревенские методы уже не справятся.
Byshevsky
буквально в следующем уровне, в лекции № 12 ты прочитаешь следующее:
— Я хочу, чтобы ты крепко запомнил две вещи:

1. Программирование появилось более 50 лет назад. Языку Java скоро 20 лет.

99% кода, который тебе нужен, уже написан.

2. Прежде, чем что-то писать с нуля, поищи в интернете – скорее всего кому-то это понадобилось раньше, и проблема уже решена.
Byshevsky
И как согласуются вот эти твои две цитаты:
Хранить и выдавать заранее посчитанные — это уже не задача будет
Для этого заранее строил массив степеней цифр от 0 до 10 в памяти
Joysi
К теме задачи уже не имеет отношение. Тем не менее.
Фраза «изобретать велосипед» появилась в расцвет второй мировой войны. Однако лет 15 назад что-то новой таки изобрели:


Заранее посчитанное не всегда есть возможно выдать. Можно провести аналогию. Пусть у тебя на ремонте дома работает парень. Надо разобрать кафельный пол 100 квадрат. Ставишь задачу — на тебе штукобакс (объем ОЗУ) и 3 часа(время работы). 90% решат следующим образом: сходят в магаз, купят отбойный молоток электрический (или мощный перфоратор ) в эти деньги и за полчаса снимут кафель. Но есть 10% здоровых парней (ПК с мошным ЦПУ) пойдут в магаз, купят кувалду «Маруся» за 6% цены (потратят меньше ОЗУ) и за 3 часа (уложатся) тоже снимут кафель.

С оффтопом завязываем. Основная цель — надо сменить условия задачи по времени.

2. Прежде, чем что-то писать с нуля, поищи в интернете – скорее всего кому-то это понадобилось раньше, и проблема уже решена. Не всегда согласен. Если бы фраза была верна — не было бы прогресса ни в какой области.
Kiranatos
Есть два очень хитрых числа, которые могут попасть в ряд и их можно пропустить из-за невнимательности и запутанности алгоритма: 4150 и 4151.
Сами числа 4-хзначные, но при 5-тизначном поиске могут удовлетворять условие:
04150 = 0*0*0*0*0 + 1*1*1*1*1 + 4*4*4*4*4 + 5*5*5*5*5 + 0*0*0*0*0
04151 = 0*0*0*0*0 + 1*1*1*1*1 + 1*1*1*1*1 + 4*4*4*4*4 + 5*5*5*5*5
Даже когда вручную пересчитывал, не сразу заметил. ))
maksimys87
Да-да. Есть такая фигня. У меня тоже так было. Немного со степенями намутил. Потом подправил и стало все ок. Сейчас у меня другая проблема. При выводе до этого числа 912985153, у меня пропускает числа 472335975, 534494836. Почему так, я пока не разобрался. Видимо где-то у меня баг. Хотя все числа кроме этих двух выводит. ХЗ, буду разбираться еще.
maksimys87
Разобрался. На самом деле все было не так. У меня наоборот выводило лишнее число 912985153. Последнее должно было быть вот это 146511208. Просто я не делал проверку, если сумма степеней больше, чем данное число N. Вот поэтому и вылезло лишнее число, которое было больше, чем N. По итогу сделал эту проверку и все стало гуд)
Yurets_Y
  • Yurets_Y
  • 0
  • Комментарий отредактирован 2016-03-20 11:18:48 пользователем Yurets_Y
Чесно, уже схожу с ума с этой задачей, дооптимизировался дальше некуда, сначала отфильтровывал числа по общеизвесному критерию, правое больше левого, и не учитывая 0, алгоритм занимал много времени, дальше создал матрицу чисел возведенных в степень, тоже не помогло. Закончилось все тем, что написал ужасающий с точки зрения читабельности код с 10 этажным циклом, в который попросту не попадают некондиционные числа типа 153 и прочие, отдельно написал код по последующей проверке чисел уже в готовом массиве, чтобы отсеять некондицию типа 04150, 04151, со всеми этими приколами на решение до max int затрачивается чуть меньше 111 мс и 10 мб памяти и… нет не проходит, уже и не знаю как ее решать, 3-й день задача с головы не выходит, что еще здесь нужно сделать чтобы прошла тест не пойму

вот результат работы с просчетом до максималки:
<code>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
Memory used=10486 Кbytes
Time wasted=134 ms</code>
Код выкладывать не буду, ведь я и сам в нем разобраться порой не могу, но так называемого дьявольского костыля с готовыми числами там нет.
Byshevsky
дальше создал матрицу чисел возведенных в степень,
а почему это ты не называешь «дьявольским костылем»?
Yurets_Y
  • Yurets_Y
  • 0
  • Комментарий отредактирован 2016-03-20 16:19:38 пользователем Yurets_Y
Потому-что в основе не массив со всеми значениями чисел армстронга, а многоэтажный цикл, который перебирает числа по принципу, который проверяет только числа, в которых каждая последующая цифра больше предыдущей, допуская наличие нулей, частичка кода:
<code>
for(byte h = 0; h<10; h++){
   for(byte i = h; i<10; i++){
      for(byte k = i; k<10; k++){
          getSummAndCheckNumber(new byte[]{a,b,c,d,e,f,g,h,i,k});
      }
   }
}</code>
Ну начинается эта ужасающая конструкция с буквы a, и в методе getSumm все это дело суммируется и делается проверка на число армстронга, но… труды напрастны, сам от этого быдлокода не в восторге, хотя работает быстро, и левые числа даже проверять не нужно. (в предыдущем варианте самой трудоемкой задачей была проверка чисел
<code>private static boolean chechNumber(int numb){
        int testNumb = numb;
        while(testNumb> 0){
            byte x = (byte)(testNumb%10);
            testNumb /=10;
            byte y = (byte)(testNumb%10);
            if((x < y)&&(x !=0)) return false;
        }
        return true;
    }</code>
вот и избавился от него, но наверное скорость перебора валидатор воспринимает как нае… во и не проходит проверку, стоит попробовать вставить в код какуюто ресурсоемкую хрень чтобы задержать процесс пересчета чтобы обмануть валидатор. Или забить на эту задачу, следующую с прямоугольниками решил за пол часа, а это какой-но ужасс.
DenisIbrahimau
день мучал. в конце принял и без усовершенствований в виде не проверки ранее проверенных сочетаний цифр (просто не смог адекватно реализовать) Из усовершенствований накидал массив степеней, дабы после в коде их не перемножать. после сдачи вспомнил свою ошибку — 9 в 10 степени выходит за размерность int, у меня в массиве степеней обрабатывалось и выставляло 0. Значит сервер тестит не на предельных размерах int. Непонятные манипуляции с размером массива при объявлении сделаны чтобы ячейка
degree[8][3] выдавала 8 в 3 степени.
код набивания массива степеней прилагаю, можете протестить.
int length  = String.valueOf(N).length();
        int [][] degree = new int[10][length+1];
        label:
        for ( int i = 1; i<10; i++){
            int temp = i;
            degree [i][1] = i;
            for(int j = 2; j < length+1; j++){
                try
                {
                    temp*=i;
                }
                catch (Exception e)
                {
                   continue label;
                }
                if (temp>N||temp<0){
                    continue label;
                }
                degree [i][j] = temp;

            }
        }

Адекватного кода игнорирования ранее проверенных сочетаний цифр нигде не увидел(чтоб не в 100 строк с кучей циклов и проверок)Но он есть, попой чую
mOPs
Как и многие, мучался 2 дня.
В итоге приняло.
Вот результат для 146511208
Время подсчета 14.538 c
Использованная память 0.0 МБ
Массив степеней не делал.
Отбрасывание схожих вариантов также не делал.
Цикл гонял от 1 до N включительно:
for (int i = 1; i <= N; i++){ 
... 
}

От String и Math.pow отказался.
Вместо Math.pow сделал отдельно свой метод, который в цикле перемножал значения.

Для тех кто еще не решил, вот рабочий метод main для проверки:

public static void main(String[] args) {
        long memoryStart = Runtime.getRuntime().freeMemory();
        long startTime = System.currentTimeMillis();

        System.out.println(Arrays.toString(getNumbers(146511208)));

        long estimatedTime = System.currentTimeMillis() - startTime;
        long memoryEnd = Runtime.getRuntime().freeMemory();
        long estimatedMemory = memoryStart - memoryEnd;
        System.out.println("Время подсчета: " + (double) estimatedTime / 1000 + " c");
        System.out.println("Использованная память: " + (double)estimatedMemory / 1024 / 1024 + " МБ");
    }
Pegas
  • Pegas
  • 0
  • Комментарий отредактирован 2016-04-13 21:36:26 пользователем Pegas
Так а если изначально создать массив с числами Армстронга и потом выдавать все, которые меньше числа N? Мысль вроде правильная, но почему-то не принимает такой код.
<code>public class Solution
{
    public static int[] getNumbers(int N)
    {
        int[] mas = {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};
        int[] result = new int[mas.length];

        for (int j = 0; j < mas.length; j++)
        {
            if (mas[j] <= N) result[j] = mas[j];
        }
        return result;
    }
}</code>
Joysi
Во первых, такой код формирует всегда массив одинаковой размерности и у него последние элементы будут нулевыми — а это не правильно:)
Во вторых, реализовать в валидаторе фейл, если результат достигнут быстрее 10мс при копеечных расходах памяти — плевое дело :)
Pegas
С массивом уже допер сам, спасибо:) А по поводу задачи в целом: ее нельзя решать таким методом, как я предлагаю? Нужно продумать какой-то другой алгоритм?
Joysi
Представьте, что вы в обществе любителей средневековой старины (толкинутый +-). На опушке после 4х часового перехода в кольчугах под средневековые напевы самопальных волынок и лютен люди по полчаса кремниевыми камушками высекают искру на утром собранную, высошенную и бережно сохраненную бересту в надежде разжечь костер. А тут вы весь такой героический и красивый, достаете из кармана смятый утренний богомерзкий «КоммерсантЪ», пшикаете на него бензинчику и зажигалкой поджигаете. Реакцию представляете?!
Задача изначально на алгоритмику и/или оптимизацию. Аналогично некоторые математики вычисляют опять тысячами-миллионами цифры после запятой для ПИ (хотя эти цифры опубликованы еще в прошлом веке). Цель — собственно процесс и его характеристики, а не собственно результат.
Pegas
Понятно, спасибо. Думал, что может это очередная хитрая задача на джавараше)
Joysi
Хотите хитрых задач?
Они тут есть и даже не так далеко:
welcome to package com.javarush.test.level20.lesson10.bonus04 :)
Zavulon
Задача крутецкая. Решил за 2 дня 10 вложеными друг в друга циклами. Может и не элегантно, зато работает.
Счетчики этих циклов крутились на основании элементов массива. Каждый элемент массива соответствует порядку цифры в числе.
Кстати N входить должен! Специально писал, чтобы N не входил, валидатор показал фигу, потратил попытку :(. Убрал условие, и валидатору понравилось.
Степени всех чисел считал заранее и тоже хранил в массиве (я сомневаюсь, что то было необходимо). Коллекции не использовал совсем, сразу писал в массив. Когда надо было добавить новое число, делел System.arrayCopy с диапазоном +1 и вписывал в конец новое значение.
Grif
Два часа ночи…
С семи утра решаю ...

Не могу ни как приклеить оптимизацию, Уважаемые подскажите пожалуйста как этому зверю прикрутить… (тут матюк был)… эту етить оптимизацию, пытался… получалось только хуже…

public class Solution {
    // Таблица степеней
    private static final int[][] DEGREE = new
            int[String.valueOf(Integer.MAX_VALUE).length()]
            [String.valueOf(Integer.MAX_VALUE).length() + 1];
    // Разложенное число в обратном порядке INTS[0] содержит длину числа
    private static final int[] INTS = new
            int[String.valueOf(Integer.MAX_VALUE).length() + 1];

    // Заполняем таблицу степеней
    static {
        for (int i = 0; i < DEGREE.length; i++) {
            int[] ints = DEGREE[i];
            for (int j = 0; j < ints.length; j++) {
                ints[j] = degreeNumber(i, j);
            }
        }
    }

    // Число для таблицы степеней
    private static int degreeNumber(int number, int degree) {
        int integer = 1;
        for (int i = 0; i < degree; i++) {
            integer = integer * number;
        }
        return integer;
    }

    // Главный метод
    public static int[] getNumbers(int N) {
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i < N; i++) {
            getInts(i);
            if (i == getSumDegrees()) {
                list.add(i);
            }
        }

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

    // Возвращаем сумму степеней
    private static int getSumDegrees() {
        int number = 0;
        int degreeOfNumber = INTS[0];
        for (int i = 1; i <= degreeOfNumber; i++) {
            number += DEGREE[INTS[i]][degreeOfNumber];
        }
        return number;
    }

    // Раскладываем число на составляющие
    private static void getInts(int number) {
        int count = 0;
        do {
            INTS[++count] = number % 10;
        } while ((number /= 10) > 0);
        INTS[0] = count;
    }
}
IgorBrest
Вот что бывает, если слишком заработаться. Надеюсь, Вы уже выспались и удалили весь этот код. Это должно будет сэкономить Вам кучу времени.
И, если и будете создавать вспомогательный массив для хранения степеней чисел (что не обязательно) то подумайте о его минимально необходимом размере…
Grif
:) Спасибо за внимание, но я Вас не понял…
Grif
Буду признателен, если укажите узкие места и почему я его должен удалить?

Вроде вполне работоспособный код, правда Integer.MAX_VALUE находит за 130 сек (ноут AMD A10-4600M, что-то среднее между i3 и i5 для мобильных версий)… а надо за 10… памяти вообще почти не жрёт — менее 1 мб.
Grif
На счёт размера таблицы степеней тоже не понял… получается таблица размером 10 Х 11 чисел, что тут не так?
ArtemShch
  • ArtemShch
  • 0
  • Комментарий отредактирован 2016-05-11 10:34:43 пользователем ArtemShch
Может кому-то пригодиться.
1) Прошло без особой оптимизации кода, для N = 146511208 14сек (Pentium E2180, 3 Гб ОП).
2) В метод входит значение int, значит придется считать максимум до 2147483647.
3) Всего 31 число, последнее 912985153.
4) в цикле прогнал от 1 до N — 1.
5) числа армстронга добавил в лист и перевел в массив.
6) Метод 30 строк кода
ako
Написал такое решение:
import java.util.ArrayList;
import java.util.Arrays;

public class Solution {
    public static void main(String[] args)
    {
        long memoryStart = Runtime.getRuntime().freeMemory();
        long startTime = System.currentTimeMillis();

        System.out.println(Arrays.toString(getNumbers(146511208)));

        long estimatedTime = System.currentTimeMillis() - startTime;
        long memoryEnd = Runtime.getRuntime().freeMemory();
        long estimatedMemory = memoryStart - memoryEnd;
        System.out.println("Время подсчета: " + (double) estimatedTime / 1000 + " c");
        System.out.println("Использованная память: " + (double)estimatedMemory / 1024 / 1024 + " МБ");
    }


    public static int[] getNumbers(long N) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        long[][] pws = new long[10][11];//таблица степеней
        for (int i = 0; i < 10; i++)
        {
            long pw = 1;
            for (int j = 1; j < 11; j++)
            {
                pw = pw * i;
                pws[i][j] = pw;
            }
        }
        int[] symbols = new int[10];
        for (int i = 1; i < N; i++)
        {
            int value = i;
            int lastSym = -1;
            int length = 0;
            boolean uselessNumber = false;
            while (value != 0)//разбираю число на цифры
            {
                int sym = value % 10;
                if (sym < lastSym)//отсекаю ненужные варианты
                {
                    uselessNumber = true;
                    break;
                }
                lastSym = sym;
                symbols[length] = sym;
                value = value / 10;
                length++;
            }
            if (uselessNumber)
            {
                continue;
            }
            int res = 0;//вычисляю сумму степеней цифр
            for (int num = 0; num < length; num++)
            {
                res += pws[symbols[num]][length];
            }
            if (res >= N || res < 0)//отсекаю все суммы не укладывающиеся в диапазон
            {
                continue;
            }
            value = res;
            length = 0;
            while (value != 0)//разбираю полученную сумму степеней цифр на цифры
            {
                symbols[length] = value % 10;
                value = value / 10;
                length++;
            }
            int res2 = 0;
            for (int num = 0; num < length; num++)//опять вычисляю сумму степененй цифр
            {
                res2 += pws[symbols[num]][length];
            }
            if (res == res2 && (!list.contains(res)))//сравниваю две суммы степеней цифр и, если они равны, то это нужное число
            {
                list.add(res);
            }
        }
        int[] ret = new int[list.size()];
        for (int i = 0; i < list.size(); i++)//перекладываю найденные числа Армстронга в массив
        {
            ret[i] = list.get(i);
        }
        Arrays.sort(ret);//сортирую массив
        return ret;
    }
}

Вот результат:
[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]
Время подсчета: 11.543 c
Использованная память: 0.0 МБ

Подскажите, плиз, люди добрые, что я не так делаю. (Комментарии вставил только для того, чтобы поместить текст сюда. На проверку отправляю, естественно, без комментариев. Измучился весь, с ног до головы. И еще не понятно, почему памяти 0 съедает.
Cepr0
Чуть выше писали, что проверять нужно до N включительно.
(У меня так приняло решение.)
ako
  • ako
  • 0
  • Комментарий отредактирован 2016-05-20 23:17:43 пользователем ako
Писали и что включая, и что исключая. Я делал и так, и так. Сейчас сделал включая N, но все-равно не принимает. 8(
Cepr0
Странно…
Я делал так:
1. Сделал массив степеней 10х11
2. Создал АррейЛист для хранения найденных чисел
3. В цикле от 1 до N включительно я складывал степени каждой цифры текущего числа
(вот так получил набор цифр: char[] digits = Integer.toString(i).toCharArray(); где i — текущее число)
4. Сравнивал полученную сумму с текущим числом, и если она не вылазит за Integer.MAX_VALUE, добавлял число в АррейЛист.
5. Сконвертировал АррейЛист в массив и вернул результат.
ako
Переделал. Стал использовать «char[] digits = Integer.toString(i).toCharArray()». Сделал включая N — не прошло. Сделал исключая N — не прошло. В чем дело не пойму.
Cepr0
Так приложили бы код сразу!.. )
ako
  • ako
  • 0
  • Комментарий отредактирован 2016-05-21 23:48:42 пользователем ako
Вот код исключая N. Код включая N в двух строках отличается.
<code>import java.util.ArrayList;
import java.util.Arrays;

public class Solution {
    public static void main(String[] args)
    {
        long memoryStart = Runtime.getRuntime().freeMemory();
        long startTime = System.currentTimeMillis();

        System.out.println(Arrays.toString(getNumbers(146511208)));

        long estimatedTime = System.currentTimeMillis() - startTime;
        long memoryEnd = Runtime.getRuntime().freeMemory();
        long estimatedMemory = memoryStart - memoryEnd;
        System.out.println("Время подсчета: " + (double) estimatedTime / 1000 + " c");
        System.out.println("Использованная память: " + (double)estimatedMemory / 1024 / 1024 + " МБ");
    }


    public static int[] getNumbers(long N) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        int[][] pws = new int[10][11];
        for (int i = 0; i < 10; i++)
        {
            int pw = 1;
            for (int j = 1; j < 11; j++)
            {
                pw = pw * i;
                pws[i][j] = pw;
            }
        }
        for (int i = 1; i < N; i++)
        {
            char[] digits = Integer.toString(i).toCharArray();
            int length = digits.length;
            boolean uselessNumber = false;
            for (int j = 1; j < length; j++)
            {
                if (digits[j - 1] < digits[j])
                    uselessNumber = true;
            }
            if (uselessNumber)
            {
                continue;
            }
            int res = 0;
            for (int num = 0; num < length; num++)
            {
                res += pws[Integer.parseInt(String.valueOf(digits[num]))][length];
            }
            if (res >= N || res < 0)
            {
                continue;
            }
            digits = Integer.toString(res).toCharArray();
            length = digits.length;
            int res2 = 0;
            for (int num = 0; num < length; num++)
            {
                res2 += pws[Integer.parseInt(String.valueOf(digits[num]))][length];
            }
            if (res == res2 && (!list.contains(res)))
            {
                list.add(res);
            }
        }
        int[] ret = new int[list.size()];
        for (int i = 0; i < list.size(); i++)
        {
            ret[i] = list.get(i);
        }
        Arrays.sort(ret);
        return ret;
    }
}
</code>
Вот результат:
<code>[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]
Время подсчета: 18.221 c
Использованная память: 2.9924697875976562 МБ
</code>
Пойду, поплачу пока. 8)
Cepr0
Похоже, что у вас лишние секунды парсеИнт забирает. Я вот так сумму считал:

int len = digits.length;
long sum = 0L;
try {
   sum += POW[digits[0] - 48][len];
   sum += POW[digits[1] - 48][len];
   sum += POW[digits[2] - 48][len];
   sum += POW[digits[3] - 48][len];
   sum += POW[digits[4] - 48][len];
   sum += POW[digits[5] - 48][len];
   sum += POW[digits[6] - 48][len];
   sum += POW[digits[7] - 48][len];
   sum += POW[digits[8] - 48][len];
   sum += POW[digits[9] - 48][len];
   } catch (ArrayIndexOutOfBoundsException e) {
}
ako
Не выходит. 8(
Сперва сделал так:
int res = 0;
            for (int num = 0; num < length; num++)
            {
                res += pws[digits[num] - 48][length];
            }

Не прошло.
Тогда передала, прямо, как в примере (даже имена переменных поменял:
int sum = 0;
            try {
                sum += POW[digits[0] - 48][len];
                sum += POW[digits[1] - 48][len];
                sum += POW[digits[2] - 48][len];
                sum += POW[digits[3] - 48][len];
                sum += POW[digits[4] - 48][len];
                sum += POW[digits[5] - 48][len];
                sum += POW[digits[6] - 48][len];
                sum += POW[digits[7] - 48][len];
                sum += POW[digits[8] - 48][len];
                sum += POW[digits[9] - 48][len];
            }
            catch (ArrayIndexOutOfBoundsException e)
            {
            }
            if (sum >= N || sum < 0)
            {
                continue;
            }

Все-равно не проходит. 8(
Уважаемый Серг0, не пришлешь в личку решение? Посмотрю, что делаю не так. Обещаю поделиться наблюдениями.
Cepr0
У меня sum типа long. Может в этом дело?..
ako
Переделал, результат тот-же.
Причем, такое наблюдение: отказ приходит через пару секунд после нажатия кнопки, т.к., судя по всему, программу не пытается запуститься или сразу после записка вылетает с ошибкой.
И еще вопрос: main перед отправкой на проверку нужно удалять?
Cepr0
Не помню (
Но лучше удалить, на всякий случай…
ako
С удалением main тоже не работает.
Cepr0
Мой код посмотрели?..
ako
Спасибо! Смотрю. Похоже, я перемудрил с оптимизацией.
Сейчас буду по частям избавляться от всего лишнего и попытаюсь понять, в чем был затык.
Cepr0
спасибо == ++карма
;)
ako
  • ako
  • 0
  • Комментарий отредактирован 2016-05-23 22:55:32 пользователем ako
Серг0, спасибо тебе. Выводы такие:
Долго мучился, изменял свой код по частям, дошел то того, что мой код стал полностью твоему соответствовать, за исключением пустых строк (но в этом виде не стал его отправлять на проверку), потом обнаружил, что у меня в метод передается long (откуда он взялся в моем коде, не понимаю (видимо, ночное кодирование дает себя знать)). Тогда загрузил пустой шаблон задания, перенес в него свой изначальный код и начал сначала.
Выводы такие:
1. У меня была лишняя оптимизация (отсечение ненужных чисел).
2. У меня был неправильный тип параметра.
GreenJedi
сделал 2 варианта, на выходе результаты одинаковые, но:
72607 мс
memory: 1 mb
«Тест не пройден» (делал дополнительные private static методы, массив степеней был int[10], значения которого умножались на индекс при увеличении разрядности числа (в нулевом нулевом хранил текущую степень (разрядность))

110080 мс
memory: 4 mb
«Тест принят» (сделано а-ля «как у всех», в одном методе с кучей циклов и 2-мерным массивом [число][степень] )

в обоих вариантах использовался ArrayList для хранения найденных чисел и потом создание из них массива result. тестировал с N=912985154

ну и где тут «оптимизируй алгоритм»? тут тест на «погугли алгоритм», мну разочарован =_=
Cepr0
Честно говоря, там простой алгоритм в один цикл (от 1 до N) с одной, по сути, операцией (вычисление суммы степеней) и одной проверкой на совпадение. Все остальное — служебные нюансы.
Посмотрите мой пост чуть выше…
GreenJedi
  • GreenJedi
  • 0
  • Комментарий отредактирован 2016-05-22 20:26:25 пользователем GreenJedi
нуу… если использовать try-catch при сумме степеней, то да, можно уменьшить количество циклов, но проблема в том, что более медленный вариант с кучей циклов как раз и прошел проверку =_=

кстати, а почему никто не использует log10 для вычисления длинны S?
123456misha12345
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 int sum = 0;
public static int[] getNumbers(int N) {
ArrayListnumber_list = new ArrayList();
for(int i=1;i<N;i++){
if(Solution.is_unique(i)){
if(Solution.is_armstrong(i)){
number_list.add(Solution.sum);
}
}
}
int[] result = new int[number_list.size()];
for(int i=0;i<number_list.size();i++){
result[i] = number_list.get(i);
}
return result;
}

public static ArrayListget_digit(int N){
int digit = 0;
int d = 1;
ArrayListlist = new ArrayList();
while(true){
N = N — digit;
N = N/d;
if(N == 0){
break;
}
digit = N%10;
list.add(0,digit);
d = 10;
}
return list;
}

public static boolean is_unique(int number) {
int lastDigit = 0;
int currentDigit;
while (number > 0) {
currentDigit = number % 10;
if (lastDigit > currentDigit) {
return false;
}
lastDigit = currentDigit;
number /= 10;
}
return true;
}
public static boolean is_armstrong(int num){
boolean result = false;
ArrayListd_list = Solution.get_digit(num);
int sum1 = 0;
for (Integer temp: d_list){
sum1 += Math.pow(temp,d_list.size());
}
ArrayListd_list2 = Solution.get_digit(sum1);
int sum2 = 0;
for (Integer temp: d_list2){
sum2 += Math.pow(temp,d_list2.size());
}
if((sum1 == sum2)&&(d_list.size()==d_list2.size())){
Solution.sum = sum1;
result = true;
}
return result;
}
}

вроде бы все работает, но принимать не хочет. Кто что посоветовать может?
gorby777
Ноль не является натуральным числом
gorby777
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
Time need to create the arrray = 7006 ms
Memory need to create the arrray = 2 Mb

N = 10^8. Повод вспомнить Concurrency и многомерные массивы
shamil
Задача понравилась, поэтому продолжил с ней возиться уже после того как чудо-проверялка ее приняла с 19 раза, да и вообще весь курс закончил.

Изначально идея была в том, чтобы разбить число на две примерно равные части, перебрать все числа из второй части, посчитать сумму степеней и для каждой записать разницу второй части и степени в некий хэш. Затем перебрать все числа из первой части и поискать в хеше ту разницу, которой недостаточно для того, чтобы составить число Армстронга. Этот алгоритм нужно запустить для всех длин числа до 9. Алгоритм работал за 50 мс и прошел тесты. Его сложность в 10^(половина длины числа) лучше чем простой bruteforce. Он так же работал приемлемое время для long (до 10^19) но если ничего не поменять — вылетало Out Of Memory — уж слишком большой нужен был хеш.


Вторая идея в том, что для любого набора цифр может существовать одно единственное число Армстронга.
1. Для всех чисел длины N
2. Распределяем N всеми различными способами между цифрами 0..9 (например, 3 нуля, две единицы, ноль двоек, пять троек и т.д)
3. Параллельно считаем сумму степеней
4. Определяем, можно ли составить сумму степеней из цифр сгенерированных в п.2
5. Если можно, добавляем число к ответу

По сути этот алгоритм делает выборку Cn/k (ц из эн по ка), т.е. просчитывает C из (N+10) по 10 вариантов = N!/(K!(N-K)!), что при N=10 равно 184756. Это ничтожно мало.

Этот алгоритм почти сходу дал результаты лучше чем первый.
* Для всех int (N<10): 15 ms
* Для всех long (N < 20): 1 s
* Переписанный для BigInteger (N<40): 3610 секунд (час и 10 секунд)

Более того, этот алгоритм, в отличие от первого, можно существенно оптимизировать в нескольких местах. После оптимизаций у меня получились такие результаты:
* Для всех int (N<10): 11 ms
* Для всех long (N < 20): ~ 0.5 s
* Переписанный для BigInteger (N<40): пол-часа

Использование памяти для N<10 исчезающе мало.

По поводу оптимизаций.
0. Предподсчет всех степеней в двухмерный массив обязателен. Об этом даже не стоит говорить.
1. Работа со строками для разбиения числа на цифры — трудоемка в случае int и long. Лучше брать остаток от деления на 10. Но, в случае длинных BigInteger toString может работать в 10 раз быстрее, чем остаток от деления на 10.
2. Нужно оптимизировать количество операций умножения и сложения. Например, степень нужно считать постепенно, в процессе генерации набора чисел, а не в конце.
3. Можно отсекать достаточно много вариантов, если проверять что, например, длина степени на данном шаге уже больше чем N.
4. Я также усовершенствовал алгоритм начав генерировать с 9 до нуля, а не наоборот.
5. В одном месте выделение массива я вынес в глобальную переменную.
6. Разные штуки по-мелочам.

К сожалению, пока не получилось скрестить оба алгоритма. Буду думать :)

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

Также для подсчета памяти используется Runtime.getRuntime().totalMemory() — Runtime.getRuntime().freeMemory() — в определенные моменты запускается Garbage Collection и этот весь смысл замера умножается на ноль )
DefNeo
А ты Онлайн — Стажировку проходил?
sergentum
1689871 ms
Memory used, kb: 825
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
с одной стороны жалко, что такое прошло, но с другой оптимизировать мат вычисления немного не тот профиль)
sergentum
  • sergentum
  • 0
  • Комментарий отредактирован 2016-07-04 17:12:07 пользователем sergentum
Господа, а разве нет встроенного инструмента для анализа производительности? вроде в 1с достаточно наглядно показывает на какой строке долго работает, нет ли здесь подобного?
Я бы рад сделать быстрее и лучше, но хотелось бы понимать как найти узкое место.
madalexfiesta
Не мудрите с отсечением лишних цифр, как это делал я. Не мешайте программе работать)
private static void function(число от 1 до N, int N){
        String start=String.valueOf(число от 1 до N);
        int m=0;
        for (int i = 0; i <start.length() ; i++) {
            m+=Двухмерный массив[символ i из строки start][степень];
            if (m>N)break;
        }
        if (m<N||m==N) {
       if (String.valueOf(m).equals(start))добавляем в массив нужное нам число
        }
    }

Тут показан весь смысл проверки
d0wn
Утомился я бодадться с валидатором.
Чую, где-то что-то не усмотрел какую нить мелочь…

Объясните мне, зачем все выкладывают результат именно для этой цифры 146511208?

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
912985153

Len : 29
Mem : 1.9502410888671875 Mb.
Time: 4.635 sec.


Сам код:
(переменные можно не делать глобальными — все равно не прходит, но я посчитал, что так меньше памяти будет выделяться\вычищаться в случае, если у нас одна переменная)
Кто-то писал, что с тримапом приняло.

public class Solution
{
    public static int degree;
    public static int theLast;
    public static int thePrevious;
    public static int temp01;
    public static int temp02;
    public static int armstrong;


    public static void main(String[] args)
    {
        int L = 146511208;

        long t0 = System.currentTimeMillis();

        int n[] = getNumbers(L);

        long t1 = System.currentTimeMillis();

        for ( int a : n)
            System.out.println(a);

        System.out.println();
        System.out.println("Len : " + n.length);
        System.out.println("Mem : " + (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) / (1024 * 1024d) + " Mb.");
        System.out.println("Time: " + (t1 - t0) / 1000d + " sec.");



    }


    public static int[] getNumbers(int N)
    {
        TreeMap<Integer, Integer> list = new TreeMap<>(); // no duplicates, auto-sort

        for (int n = 1; n < N; n++)
        {
            if (checkTheRule(n))
            {
                temp01 = calcFunction(n);  // 153 находим из 135
                if (temp01 == calcFunction(temp01)) // убеждаемся, что 153 это 153 (считаем еще раз)
                    list.put(temp01, 0);
            }
        }


        // возвращаем из аррея простой массив, according to the task
        int temp[] = new int[list.size()];
        int b = 0;
        for (Integer a : list.keySet())
        {
            temp[b] = a;
            b++;
        }
        return temp;
    }


    public static boolean checkTheRule(int n)
    {
        while (n > 0)
        {
            theLast = n % 10;       // take two neighbor digits
            thePrevious = (n / 10) % 10;    // and compare them to each other

            // если не подходит под наше условие
            if ( !(thePrevious <= theLast || theLast == 0) )
                return false;

            n = n / 10;  // decrement our var for one character (from tail)
        }

        return true;
    }


    public static int getDegree(int n)
    {
        degree = 0;
        while (n > 0)
        {
            n = n / 10;
            degree++;  // the times we have decremented our var is the count of degree
        }
        return degree;
    }



    public static int calcFunction(int n)
    {
        degree = getDegree(n);
        armstrong = 0;

        while (n > 0)
        {
            temp02 = 1;
            int k = n % 10;     // takes the last digit

            for (int a = 0; a < degree; a++)
                temp02 *= k;      // do the k^degree

            armstrong += temp02;

            n = n / 10;         // prepares for the next number
        }
        return armstrong;
    }

}
d0wn
  • d0wn
  • 0
  • Комментарий отредактирован 2016-07-16 00:30:14 пользователем d0wn
так же читал\видел, что паблик статик тоже у людей принимается, но были также и противоположные высказывания…

процессор хлам на ноуте селерон 1.5гг
весь (максимально возможный) диапазон интов считает за 46 сек

и еще видел мнение, что не обязательно использовать двумерный массив

и да, задача приятно возбуждает и побуждает к приятному красноглазию))
d0wn
эхх… а ответ-то прост, хоть и не лежит на поверхности)) неким образом создать подмножество чисел, удовлетворяющих известному правилу, и только потом проверять на армстронга. Например, из диапазона от 9000 до 9999 таких чисел будет всего три — 9009, 9099, 9999 — вот и надо выцапать эти три числа, не перебирая всю тысячу, тут то экономия тактов и выйдет знатная.
kototim
Взрыв мозга… Задача очень крутая, уже раз 10 переписывал код. Сейчас бьюсь головой об стену. Очень долго раздуплял, как извлечь число, не прибегая к строкам, придумал, расписал с использованием double и тут вдруг оказалось, что:
Число 0.1 (одна десятая) записывается просто в десятичном формате. Но в двоичной системе счисления это бесконечная дробь, так как единица на десять в двоичной системе так просто не делится.Когда мы складываем 0.1 и 0.2, то две неточности складываются, получаем незначительную, но всё же ошибку в вычислениях. 0.1 + 0.2 = 0.30000000000000004
Из-за этого моя программа посыпалась, не все числа отлавливает.
Создалось впечатление, что double вообще доверять нельзя и избегать всеми возможными способами.
Сижу думаю дальше…
kototim
И вот это я не учел…
getNumbers должен возвращать все такие числа в порядке возрастания
Сервер принял с числа 146511209 — 13 секунд… Всё, больше не могу. Может когда-нибудь вернусь к этой задаче.
noxior
  • noxior
  • 0
  • Комментарий отредактирован 2016-08-15 20:33:09 пользователем noxior
Вобщем что тут скажешь, код конечно диковиный) некоторые советы учел типо массива степеней, а некоторые не учел, так как не успел про них прочитать, так как начал делать сам) в итоге все работает, даже легко можно ускорить, и уменьшить количество используемой памяти. Но факт в том что код рабочий, а тестирование не проходит, и в чем проблема не понятно, поэтому я тут и прошу помощи)

<code>package com.javarush.test.level20.lesson10.bonus01;

import java.util.Arrays;
import java.util.HashSet;

/* Алгоритмы-числа
Число 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) {
        long memoryStart = Runtime.getRuntime().freeMemory();
        long startTime = System.currentTimeMillis();

        System.out.println(Arrays.toString(getNumbers(500)));

        long estimatedTime = System.currentTimeMillis() - startTime;
        long memoryEnd = Runtime.getRuntime().freeMemory();
        long estimatedMemory = memoryStart - memoryEnd;
        System.out.println("Время подсчета: " + (double) estimatedTime / 1000 + " c");
        System.out.println("Использованная память: " + (double) estimatedMemory / 1024 / 1024 + " МБ");
    }

    public static int[] getNumbers(int N) {

        int[][] b = new int[11][12]; //массив степеней
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++) {
                int a = 1;
                for (int k = 0; k < j; k++) {
                    a = a * i;
                }
                b[i][j] = a;
            }
        }

        HashSet<Integer> set = new HashSet();//хешсет для чисел армстронга

        for (int i = 1; i <= N; i++) {//перебераю числа анчиная с 1, с шагом согласно известному алгоритму где
            int[] a = new int[(int) (Math.log10(i) + 1)];//все числа, у которых любая цифра не меньше предыдущей и не больше последующей
            int q = 0;
            int t = i;
            while (t > 0) {
                int f = t % 10;
                a[q] = f;
                t = t / 10;
                q++;
            }


            for (int j = 0; j < a.length; j++) {//разбераю число, на составлющие цифры дабы осуществить алгоритм
                try {
                    while (a[j] < a[j + 1]) {
                        a[j] = a[j] + 1;
                        j = 0;
                    }
                } catch (Exception e) {
                }
            }



            int h = 0; // собераю обратно
            for (int k = 0; k < a.length; k++) {
                h = h + (a[a.length - k - 1] * b[10][a.length - k - 1]);
            }
            i = h;



            for (int j = 0; j < 4; j++) { //вычисляю сумму числа, которое собрал выше. Данный цикл существует, чтобы 
                int m = (int) Math.log10(h) + 1;//перемножать на 10, это в свою очередь необходимо для получения нулей
                int sym = 0;
                int w = h;
                while (w > 0) {
                    int c = w % 10;
                    sym += b[c][m];
                    w = w / 10;
                }
                int starms = (int) Math.log10(sym) + 1;//и тут же вычисляю сумму суммы, и получаю необходимое число армстронга
                int arms = 0;
                int e = sym;
                while (e > 0) {
                    int c = e % 10;
                    arms += b[c][starms];
                    e = e / 10;
                }
                if (arms == sym && arms != 0) {
                    set.add(arms);
                }
                h = h * 10;
            }
            if (i < 0) break;//числа выходят за предел максимального значения инт, и преобразуются в числа с минусом
        }//что приводит к бесконечности главного цикла с 1 по N

        int[] result = new int[set.size()];//создаю массив 

        int y = 0;
        for (int c : set) {//заполняю его
            result[y] = c;
            y++;
        }

        Arrays.sort(result);

        return result;
    }
}</code>
noxior
исправил слегка, в прошлом варианте была ошибка

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

import java.util.ArrayList;
import java.util.Arrays;
import java.util.TreeSet;

/* Алгоритмы-числа
Число 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) {
        long memoryStart = Runtime.getRuntime().freeMemory();
        long startTime = System.currentTimeMillis();

        System.out.println(Arrays.toString(getNumbers(Integer.MAX_VALUE)));

        long estimatedTime = System.currentTimeMillis() - startTime;
        long memoryEnd = Runtime.getRuntime().freeMemory();
        long estimatedMemory = memoryStart - memoryEnd;
        System.out.println("Время подсчета: " + (double) estimatedTime / 1000 + " c");
        System.out.println("Использованная память: " + (double) estimatedMemory / 1024 / 1024 + " МБ");
    }

    public static int[] getNumbers(int N) {

        int[][] b = new int[11][12]; //массив степеней
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++) {
                int a = 1;
                for (int k = 0; k < j; k++) {
                    a = a * i;
                }
                b[i][j] = a;
            }
        }

        TreeSet<Integer> set = new TreeSet();//хешсет для чисел армстронга
        ArrayList<Integer> list = new ArrayList<>();

        for (int i = 1; i <= N; i++) {//перебераю числа анчиная с 1, с шагом согласно известному алгоритму где
            int[] a = new int[(int) (Math.log10(i) + 1)];//все числа, у которых любая цифра не меньше предыдущей и не больше последующей
            int q = 0;
            int t = i;
            while (t > 0) {
                int f = t % 10;
                a[q] = f;
                t = t / 10;
                q++;
            }


            for (int j = 0; j < a.length; j++) {//разбераю число, на составлющие цифры дабы осуществить алгоритм
                try {
                    while (a[j] < a[j + 1]) {
                        a[j] = a[j] + 1;
                        j = 0;
                    }
                } catch (Exception e) {
                }
            }



            int h = 0; // собераю обратно
            for (int k = 0; k < a.length; k++) {
                h = h + (a[a.length - k - 1] * b[10][a.length - k - 1]);
            }
            i = h;



            for (int j = 0; j < 4; j++) { //вычисляю сумму числа, которое собрал выше. Данный цикл существует, чтобы
                int m = (int) Math.log10(h) + 1;//перемножать на 10, это в свою очередь необходимо для получения нулей
                int sym = 0;
                int w = h;
                while (w > 0) {
                    int c = w % 10;
                    sym += b[c][m];
                    w = w / 10;
                }
                int starms = (int) Math.log10(sym) + 1;//и тут же вычисляю сумму суммы, и получаю необходимое число армстронга
                int arms = 0;
                int e = sym;
                while (e > 0) {
                    int c = e % 10;
                    arms += b[c][starms];
                    e = e / 10;
                }
                if (arms == sym && arms != 0) {
                    set.add(arms);
                }
                h = h * 10;
            }
            if (i < 0) break;//числа выходят за предел максимального значения инт, и преобразуются в числа с минусом
        }//что приводит к бесконечности главного цикла с 1 по N

        int y = 0;
        for (int c: set){
            list.add©;
            if (c == N) break;
            y++;
        }

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

        return result;
    }
}
kototim
Задайте 372. Что-то лишнее вылезло
noxior
вы правы, изменил одну строчку… теперь все верно

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

import java.util.ArrayList;
import java.util.Arrays;
import java.util.TreeSet;

/* Алгоритмы-числа
Число 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) {
long memoryStart = Runtime.getRuntime().freeMemory();
long startTime = System.currentTimeMillis();

System.out.println(Arrays.toString(getNumbers(10500)));

long estimatedTime = System.currentTimeMillis() — startTime;
long memoryEnd = Runtime.getRuntime().freeMemory();
long estimatedMemory = memoryStart — memoryEnd;
System.out.println(«Время подсчета: » + (double) estimatedTime / 1000 + " c");
System.out.println(«Использованная память: » + (double) estimatedMemory / (1024 * 1024) + " МБ");
}

public static int[] getNumbers(int N) {

int[][] b = new int[11][12];
for (int i = 0; i < 11; i++) {
for (int j = 0; j < 11; j++) {
int a = 1;
for (int k = 0; k < j; k++) {
a = a * i;
}
b[i][j] = a;
}
}

TreeSetset = new TreeSet();
ArrayListlist = new ArrayList<>();

for (int i = 1; i <= N; i++) {
int[] a = new int[(int) (Math.log10(i) + 1)];
int q = 0;
int t = i;
while (t > 0) {
int f = t % 10;
a[q] = f;
t = t / 10;
q++;
}

for (int j = 0; j < a.length; j++) {
try {
while (a[j] < a[j + 1]) {
a[j] = a[j] + 1;
j = 0;
}
} catch (Exception e) {
}
}

int h = 0;
for (int k = 0; k < a.length; k++) {
h = h + (a[a.length — k — 1] * b[10][a.length — k — 1]);
}
i = h;

for (int j = 0; j < 4; j++) {
int m = (int) Math.log10(h) + 1;
int sym = 0;
int w = h;
while (w > 0) {
int c = w % 10;
sym += b[c][m];
w = w / 10;
}
int starms = (int) Math.log10(sym) + 1;
int arms = 0;
int e = sym;
while (e > 0) {
int c = e % 10;
arms += b[c][starms];
e = e / 10;
}
if (arms == sym && arms != 0) {
set.add(arms);
}
h = h * 10;
}
if (i < 0) break;
}

int y = 0;
for (int c: set){
if (c > N) break;
list.add©;
y++;
}

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

return result;
}
}
kototim
Так принялось или нет? Перезалейте код через code, а то всё поплыло.
noxior
вот новый код, изменил одну строку, теперь все по фэншую)) но все равно не проходит(

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

import java.util.ArrayList;
import java.util.Arrays;
import java.util.TreeSet;

/* Алгоритмы-числа
Число 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) {
        long memoryStart = Runtime.getRuntime().freeMemory();
        long startTime = System.currentTimeMillis();

        System.out.println(Arrays.toString(getNumbers(10500)));

        long estimatedTime = System.currentTimeMillis() - startTime;
        long memoryEnd = Runtime.getRuntime().freeMemory();
        long estimatedMemory = memoryStart - memoryEnd;
        System.out.println("Время подсчета: " + (double) estimatedTime / 1000 + " c");
        System.out.println("Использованная память: " + (double) estimatedMemory / (1024 * 1024) + " МБ");
    }

    public static int[] getNumbers(int N) {

        int[][] b = new int[11][12];
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++) {
                int a = 1;
                for (int k = 0; k < j; k++) {
                    a = a * i;
                }
                b[i][j] = a;
            }
        }

        TreeSet<Integer> set = new TreeSet();
        ArrayList<Integer> list = new ArrayList<>();

        for (int i = 1; i <= N; i++) {
            int[] a = new int[(int) (Math.log10(i) + 1)];
            int q = 0;
            int t = i;
            while (t > 0) {
                int f = t % 10;
                a[q] = f;
                t = t / 10;
                q++;
            }


            for (int j = 0; j < a.length; j++) {
                try {
                    while (a[j] < a[j + 1]) {
                        a[j] = a[j] + 1;
                        j = 0;
                    }
                } catch (Exception e) {
                }
            }



            int h = 0;
            for (int k = 0; k < a.length; k++) {
                h = h + (a[a.length - k - 1] * b[10][a.length - k - 1]);
            }
            i = h;



            for (int j = 0; j < 4; j++) {
                int m = (int) Math.log10(h) + 1;
                int sym = 0;
                int w = h;
                while (w > 0) {
                    int c = w % 10;
                    sym += b[c][m];
                    w = w / 10;
                }
                int starms = (int) Math.log10(sym) + 1;
                int arms = 0;
                int e = sym;
                while (e > 0) {
                    int c = e % 10;
                    arms += b[c][starms];
                    e = e / 10;
                }
                if (arms == sym && arms != 0) {
                    set.add(arms);
                }
                h = h * 10;
            }
            if (i < 0) break;
        }

        int y = 0;
        for (int c: set){
            if (c > N) break;
            list.add©;
            y++;
        }

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

        return result;
    }
}
kototim
Ну почти =)))
должен среди натуральных чисел меньше N
noxior
  • noxior
  • +1
  • Комментарий отредактирован 2016-08-16 22:46:18 пользователем noxior
спасибо… ахахахах… эта задача поражает своей зашкварностью) проморочил себе голову почти неделю) задача конечно класс, обожаю такие, на алгоритмы) в итоге с 41 раза:D
imp
а дальше все веселее и веселее :)
noxior
ну этот уровень богат сложными задачами, они конечно интересные, но суть тем уровня теряется, пора следовать дальше к сожалению)
Iskandar
  • Iskandar
  • 0
  • Комментарий отредактирован 2016-09-20 19:31:33 пользователем Iskandar
Интересно, сколько я потерял попыток, пытаясь сдать код, который возвращает массив с элементам в обратном порядке? ЛОЛ

У меня такие результаты:
n = 2147483647
Memory 3328 kb
Time 45 sec

Зачло. Я так думаю — на серваке у валидатора оно быстрее работает )) Или ограничение по времени не проверяется настолько жестко.

Встречающийся здесь код — где в одном цикле мы считаем количество цифр (степень), а в другом просматриваем двумерный массив и собираем степенное число для проверки я переделал так:
1. избавился от второго цикла расширив функционал первого (заполняю маленький массив (о нем ниже) — в итоге в методе на одну операцию деления и один цикл меньше, чем в оригинальном коде).
2. Создал массив на 10 элементов (до основного цикла перебора числа), в который складывал отдельные цифры каждого числа (всегда один и тот же массив — новых инициализаций в цикле не объявлял), а затем суммировал сразу десять элементов (десять операций подряд — без цикла (в цикле дольше секунд на 8)), беря из этого массива число — первый индекс для двухмерного массива. Здесь try-catch не нужен.

Это на указанном мною числе дало мне секунд 15 экономии времени при той же цифре памяти (если я ее вообще корректно измеряю память). Также моя логика заполняет сразу массив результата от 1 до последнего числа Армстронга — дополнительных сортировок нету.

з.ы. как-то странно у меня использования цикла for вместо while подъедает аж 3 секунды времени :)

з.з.ы. число N в финальный массив у меня не входило (не знаю, надо оно или нет валидатору), т.е. если передать число 371 — то будут все числа Армстронга, включая 370, но переданного числа 371 не будет.
Artem_Novikov
У меня 5114 мс. И не принимает.
Artem_Novikov
Обманул, был баг:)
Nata
  • Nata
  • 0
  • Комментарий отредактирован 2016-09-30 17:07:20 пользователем Nata
Задача прошла за 9 сек.
1. Каждое натуральное число от 1 до N( НЕ включая N) переводила в массив char.
2. Каждый элемент массива переводила в инт. и далее в цикле М раз(длинна массива char) умножала этот элемент массива на себя же. (чтобы избавиться от Math.pow)
3. Суммировала результат, и если сумма равна рассматриваемому натуральному числу, записывала в лист.
4. Result заполнила данными из лист и отсортировала (Arrays.sort).
Artem_Novikov
за 9 секунд на каком входном числе?
Hustlers
Перепробовал кучу несколько вариантов алгоритмов, всегда тестировал на не самом большом числе Армстронга, чтобы не ждать порой по 20+ секунд. Стоило вбить 912985154, как задача принялась… то есть я даже не знаю на каком этапе оптимизации уже скорость была «ок».
В итоге решение через матрица степеней + линейный перебор не переводя ничего в String или char.
Artem_Novikov
Очень странно.
RelaxeR
Тоже не очень вкурил в решение )) 4 дня решал, как определить уникальные числа через массив или вложенные циклы быстрее, чем чредованием "/" и "%" так и не понял )) максимум задача до max int решалась за 13 сек (и 7 сек если искусственно ограничить перебор 1 млрд) и 15 мбайт памяти, но не проходило решение. Пытался подсунуть валидатору читерное решение с забиванием тела мусором для времени около 5 сек и памяти 30 мб — не получилось ))
В итоге полез копать хелп и гугл, по комментам тут убрал метод на определение уникального числа, сделал тупо перебор всех чисел и проверку суммы на равенство самому числу, и решение приняло, время около 2х минут (проц i7 4700HQ).
Но зато пока решал узнал много нового про скорость обработки различной информации )) Обнаружил, что из 13 сек решения 10 секунд уходило на проверку числа на уникальность и 3 секунды — на сравнение сумм уникальных чисел. Долго пытался оптимизировать эту вот проверку на уникальность, но так и не смог сделать быстрее без хардкода значений, получалось еще дольше каждый раз. Возможно, надо было попробовать через побитовый сдвиг, но не успел ))
vyacheslavivanov
  • vyacheslavivanov
  • 0
  • Комментарий отредактирован 2017-02-08 18:09:01 пользователем vyacheslavivanov
Необходима помощь в решении задачи. Показатели по производительности проходят, числа в массиве в возрастающем порядке, если вариант где коллекции НЕ используются, есть вариант где все помещено в рамки одного ведущего (getNumbers) метода. Задачу не принимает.

package com.javarush.task.task20.task2025;
import java.util.ArrayList;
import java.util.Arrays;

/*
Алгоритмы-числа
*/
public class Solution {

public static void main(String[] args)
{
long start = System.currentTimeMillis();
for (long t: getNumbers(912985153))
System.out.println(t);
System.out.println();
System.out.println((System.currentTimeMillis() — start) / 1000);
System.out.println((Runtime.getRuntime().totalMemory() — Runtime.getRuntime().freeMemory()) / 1048576);
}

public static long[] getNumbers(long N){ // Основной метод
ArrayListlist = new ArrayList<>();
for (int i = 1; i < N; i++) // без цифры 0 и меньше N
{
if (step(i))
{
long q = sum(i);
if (q == sum(q) && !list.contains(q))
list.add(q);
}
}
long[] c = new long[list.size()];
for (int i = 0; i < list.size(); i++)
c[i] = list.get(i);
Arrays.sort©;
return c;
}

public static boolean step(long i) // Уникальность числа (Если проверено 123, то 321 проверять не будет)
{
long a,b,c,d; d = 0; c = 0;
boolean q; q = false;
while(i > 0){
a = i % 10;
if (a != 0){
q = true;
c = d;
}
if (q && d > c)
return false;
i /= 10;
b = i % 10;
if (a < b && a != 0)
return false;
d++;
}
return true;
}

public static int len(long i) // длина числа
{
int w = 0;
while(i > 0){
i/=10;
w++;
}
return w;
}

public static int sum(long i) // возведения числа в степень
{
int q = len(i);
int y = 0;
long w;
while(i > 0){
w = i % 10;
y += Math.pow(w, q); 
i /= 10;
}
return y;
}
}
Artem_Novikov
public static boolean step(long i) напиши комментарии, как эта функция работает… а если 312 будет, то тоже проверять не будет?
Artem_Novikov
  • Artem_Novikov
  • 0
  • Комментарий отредактирован 2017-02-28 11:33:36 пользователем Artem_Novikov
До Integer.MAX_VALUE считает примерно 23-25 секунд, а до 999 999 999 примерно 4 секунды.
Проц Core i3 2350m
Но валидатору не нравится.
apollox
Для 2147483647: 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 Time = 51 sec. Mem: 0,89 Mb.

Валидатор выдает: Метод getNumbers должен возвращать массив чисел удовлетворяющих условию задачи.

Что ему не нравится? (

public class Solution {
    public static long[] getNumbers(long N) {
        long[] result = null;

        int pow = (int) Math.log10(N) + 1;
        int [][] powArr = new int[10][pow];
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < pow; j++) {
                int temp = i;
                for (int z = 0; z < j; z++) {
                    temp *= i;
                }
                powArr[i][j] = temp;
            }
        }

        TreeSet<Integer> list = new TreeSet<>();
        for (int i=1; i<N; i++) {
            if (isNumberToCalc(i)) {
                int sumOfPowers = sumPowers(i, powArr);
                if (sumOfPowers<N && isArmstrong(sumOfPowers, powArr))
                    list.add(sumOfPowers);
            }
        }

        result = new long[list.size()];

        int i=0;
        for (Integer l : list) {
            result[i] = l;
            i++;
        }

        return result;
    }

    private static boolean isNumberToCalc(int number) {
        byte lastDigit = 0;
        byte currentDigit;

        while (number > 0) {
            currentDigit = (byte)(number % 10);
            if (lastDigit > currentDigit) {
                return false;
            }
            lastDigit = currentDigit;
            number /= 10;
        }

        return true;
    }


    private static int sumPowers(int number, int [][] powArr) {
        short pow = (short) (Math.log10(number) + 1);
        int sum = 0;
        byte digit;
        int numberSource = number;
        while (number > 0) {
            digit = (byte) (number % 10);
            if (digit > 0) {
                sum += powArr[digit][pow - 1];
                if (sum > numberSource)
                    return 1;
            }
            number /= 10;
        }
        return sum;
    }


    private static boolean isArmstrong(int number, int [][] powArr) {
        if (sumPowers(number, powArr) == number) {
            return true;
        }
        return false;
    }


    public static void main(String[] args) {
        getNumbers(2147483647);
    }
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.