Алгоритмы-числа

  • 20
  • Недоступна
Ура, задачи на алгоритмы! Их очень любят резиденты планеты Линейный Хаос. И вы должны любить, по крайней мере, до того момента, как пройдёте пару-тройку собеседований. Итак, у вас есть число из некоторого количества чисел. Нужно найти все числа меньше N, которые удовлетворили бы некоторому критерию (о нём узнаете в самой задаче!).
Вы не можете решать эту задачу, т.к. не залогинены.
Комментарии (722)
  • популярные
  • новые
  • старые
Для того, чтобы оставить комментарий Вы должны авторизоваться
Benjam1nBTN
Уровень 24
31 января, 19:50
В этой задаче я опробовал очень многое, например: рекурсию, вложенный цикл do-while внутри do-while, интересные, а главное быстрые алгоритмы. В итоге для N = Long.MAX_VALUE следующие показатели:
memory 483
time = 3
Весь код без main'а около 70 строк. Но самое печальное, что валидатору я это решение так и не скормил. Протестил на куче параметров, убрал некоторые огрехи, вызывающие исключения, но все равно успеха не добился. Слишком много потраченного времени на валидатор, иду дальше. П.С. После изучения "правильного решения" был очень удивлен. Время исполнения программы константное и всегда равно 0 сек при 615 памяти - это просто самолёт. Также не совсем понял, почему при N = Long.MAX_VALUE в итоговый массив попадает число 4929273885928088826, ведь это и есть N, а мы должны вывести все числа меньше N.
Роман
Уровень 24
31 января, 15:24
2 дня.. Отдельная благодарность Павлу, надоумил на одно интересное решение.
memory 346
time = 2561
Liudzmila Sobaleva
Уровень 35
18 января, 12:24
Нуль - это число Армстронга, но не натуральное число. Поэтому 0 не входит в long[], который возвращает метод getNumbers(long N). Если пропустить этот момент, валидатор будет ругаться на четвертый пункт. И обязательна проверка N на отрицательное число. Без этого валидатор ругается на второй пункт. Нужно еще Long.Long.MAX_VALUE протестить. Вдруг кому-то пригодится.
Vkt Pra
Уровень 25
12 января, 11:50
Выражу мнение, задача учит не тому как выпендриваться, ломать голову в попытках высчитать по сути константы, сами искомые числа Армстронга - давно известный в математическом кругу набор констант, и вы не найдёте лучшего решения при оптимизации чем тупо и в наглую, вбить эти константы в массив и отсортировать необходимый диапазон. Не делать лишних движений, большего чем то что требует заказчик, как бы нормальная тема. Рекомендую, в будущем пригодится. Возможно это главная суть текущей задачи. Самое красивое и органичное решение, лежит на поверхности. Решение, {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, 4679307774L, 32164049650L, 32164049651L, 40028394225L, 42678290603L, 44708635679L, 49388550606L, 82693916578L, 94204591914L, 28116440335967L, 4338281769391370L, 4338281769391371L, 21897142587612075L, 35641594208964132L, 35875699062250035L, 1517841543307505039L, 3289582984443187032L, 4498128791164624869L, 4929273885928088826L}
Benjam1nBTN
Уровень 24
28 января, 21:20
Да нет, вроде суть задачи, чтобы самому найти эти числа Армстронга, применив необходимый алгоритм
Vkt Pra
Уровень 25
29 января, 13:44
нашёл, через более затратный алгоритм, а после того как нашёл - забил в список. Сам нашел, сам трансформіровал из затратного метода в менее затратный.
Viktar
Уровень 22
29 декабря 2022, 16:50
Мне вот непонятно, в каких единицах памяти выводится значение в этой строке?
System.out.println("memory " + (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) / (8 * 1024));
Серега Батенин
Уровень 34
4 января, 14:29
судя по тому на что делится итоговое значение, то в килобайтах. Типа из битов в байты, а потом в килобайты
Benjam1nBTN
Уровень 24
31 января, 19:39
Да, килобайты. Изначально методы возвращают биты, далее делим на 8 = байты, далее делим на 1024 = Кбайты
Grock
Уровень 29
28 декабря 2022, 14:59
Такое не работает. Слишком долго вычисляет:
public static long[] getNumbers(long N) {
    List<Long> list = new ArrayList<>();
    for (int i = 0; i < N; i++) {
        int numberLength = String.valueOf(i).length();
        long allMultNumbsSum = 0;
        char[] ch = String.valueOf(i).toCharArray();
        for (int j = 0; j < numberLength; j++) {
            int y = Integer.parseInt(String.valueOf(ch[j]));
            allMultNumbsSum += (long) Math.pow(y, numberLength);
        }
        if (i == allMultNumbsSum && i > 0) list.add(allMultNumbsSum); }
    long[] x = new long[list.size()];
    for (int i = 0; i < list.size(); i++) { x[i] = list.get(i); }
   return x; }
Решил в итоге так: В десятичной системе существует всего 88 чисел Армстронга. В промежутке 1 <= N <= 11 находится следующие 35 чисел Армстронга: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407, 1634, 8208, 9474, 54 748, 92 727, 93 084, 548 834, 1 741 725, 4 210 818, 9 800 817, 9 926 315, 24 678 050, 24 678 051, 88 593 477, 146 511 208, 472 335 975, 534 494 836, 912 985 153, 4 679 307 774, 32 164 049 650, 32 164 049 651. Самое большое число Армстронга содержит 39 цифр: 115 132 219 018 763 992 565 095 597 973 971 522 401. Поскольку от нас требуют значение long, которое состоит из 19 знаков, достаточно добавить в список все подобные числа и сравнивать их с аргументом метода getNumbers(). Это и самый эффективный по времени и самый тупой вариант решения :)
Aleksey Работает в DжаваРаш
28 декабря 2022, 01:23
Ребят, всем привет, в итоге решил этого монстра через алгоритм который описан в Энтернете, + тот же самый алгоритм описал тут неплохо в комментах Павел. Далее решил ознакомиться с решением от авторов задачи. Так вот - посидел, подебажил, почесал репу - и кто нибудь может обьяснить, что там происходит вообще ?? Оно считает - прям сверхбыстро, при значении long.MAX_VALUE решение проходит за 0 секунд и тратит статичное значение памяти, что то около 0,3 Мб (статичное - не зависит от входного значения, что с 1000, что с MAX_VALUE одно и то же)
Benjam1nBTN
Уровень 24
28 января, 21:24
Я тоже в шоке, но остальных это как будто не впечатлило)
Aleksey Работает в DжаваРаш
27 декабря 2022, 12:01
/* Комментарий удален */
Aleksey Работает в DжаваРаш
27 декабря 2022, 12:19
посидел, еще спустя час понял что от меня хотят Итак читатель садись поудобнее, опишу условие этого монстра. 1. В метод getNumbers передается число допустим - число 1000 (N =1000) 2. Метод getNumbers должен перебрать все числа от 0 до 999 и заполнить массив long[] числами Армстронга (это так называются те самые числа) (число S - это значения которые перебираются в методе т.е. 0 - 999, числа M - это грубо говоря длина этого числа) Если видео было полезно то ставим лайки, подписываемся на канал 🙃
Иван Овчаренко
Уровень 23
22 декабря 2022, 13:32
Решил по подсказкам Павла (см. популярные комментарии). Но выделю два момента на которые нужно обратить внимание да же с их учётом: 1) Math.pow - может давать разные результаты при возведении в степень и лучше использовать другие способы составления таблицы умножения например: multiplyMassive[i][j] = new BigInteger((i) + "").pow(j).longValue(); 2) Валидадор может ругаться по 2 и 4 пунктам если вы не учли возможность заданного значения 0, да в условии говориться про натуральные числа, но валик считает все числа из множества long так что его то же надо учесть. Удачи;)
Виктор
Уровень 22
9 декабря 2022, 08:01
Жестко, очень жестко, часов 20 потратил, но на самом деле многому научился, первый приличный алгоритм и код написанный самостоятельно за 20 уровней. [] memory 246 time = 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, 1517841543307505039, 3289582984443187032, 4498128791164624869, 4929273885928088826] memory 2501 time = 2
Benjam1nBTN
Уровень 24
31 января, 08:53
Это решение принял валидатор? Последнего числа не должно быть в массиве, так как это N, а мы должны вывести все, что меньше N.