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

  • 20
  • Недоступна
Ура, задачи на алгоритмы! Их очень любят резиденты планеты Линейный Хаос. И вы должны любить, по крайней мере, до того момента, как пройдёте пару-тройку собеседований. Итак, у вас есть число из некоторого количества чисел. Нужно найти все числа меньше N, которые удовлетворили бы некоторому критерию (о нём узнаете в самой задаче!).
Вы не можете решать эту задачу, т.к. не залогинены.
Комментарии (434)
  • популярные
  • новые
  • старые
Для того, чтобы оставить комментарий вы должны авторизоваться
Vitalachka20 уровень, Лондон
Thursday, 19:30
[1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407] memory 317 time = 0 [1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407, 1634, 8208, 9474, 54748, 92727, 93084, 548834] memory 11131 time = 0 и что делать теперь?
Vitalachka20 уровень, Лондон
Thursday, 19:50
от же сAбака при Long.MAX_VALUE завис мой гениальный код 😵
Карим24 уровень
28 June, 09:26
Наверно из 5483 только 500 человек придумали сами решения, не стал изобретать велосипед так как если даже просто запустить массив до 10^19 то придется ждать очень долго, кароче воспользовался этим алгоритмом ArmstrongNumbersMultiSetLongOpt ,
Дмитрий22 уровень
24 June, 15:32
Для особо ленивых, вроде меня, находите своим некрасивым алгоритмом(либо просто гуглите) числа Армстронга, выписываете их в массив - выводите нужный массив, вуаля)).
Vad24 уровень
28 June, 09:36
Сколько надо чисел? Я забивал 32. Валидатор не принял. Хотя вывод в тесте для N = 1000 и N = 1000000 был правильный.
Дмитрий22 уровень
28 June, 22:02
Чисел надо Long.MAX_VALUE
Vad24 уровень
28 June, 23:08
Их всего 50 в этом диапазоне.))) ДописАл все в лист. Тест прошёл. А то валидатор не ограничивался диапазоном поиска, указанном в тестовой части программы.Там 1000 и 1000000. Вот я и поленился весь комплект забить..))) Только у меня почему-то по итогам теста получается нулевое врямя выполнения. И памяти совсем чуть-чуть. Больше, чем Long.MAX_VALUE, мы и не сможем в Long записать. А для нахождения самого большого числа Армстронга достабочно примерно половины от этого значения: 4_929_273_885_928_088_826 L
Axl NeferSky24 уровень, Нижний Новгород
14 June, 21:35
Задача зачтена со следующими таймингами: 1_000: memory 259, time = 0 1_000_000: memory 436, time = 0 1_000_000_000: memory 566, time = 0 1_000_000_000_000L: memory 361, time = 1 1_000_000_000_000_000L: memory 175, time = 3 1_000_000_000_000_000_000L: memory 444, time = 18 Long.MAX_VALUE: memory 344, time = 27 Также отмечу, что генерация массива степеней как Math.round(Math.pow(digit, power)) на больших числах (от 17 разрядов, емнип) выдает неверные результаты. ЗЫ: убито несколько дней. 10 попыток. В новый квест без долгов)))
Евгений28 уровень, Санкт-Петербург
14 June, 07:25
Самая сложная задача за весь курс, сразу нашлась статья с описанием общего алгоритма, которую в обсуждении все советуют. Но завис с реализацией алгоритма генерации чисел, который был бы еще и быстр. В итоге, почти два вечера и решение зачтено. Для Long.MAX_VALUE проходило, в среднем, за 2,2с и 80 МБ памяти. Только прочитав обсуждение, понял, что моя реализация жрет память за двоих и стал искать на чем сэкономить. И тройная радость была, когда стало считать за 2,8с и потреблять 14МБ памяти для того же числа, хотя добавил всего одну строчку, отсекающие очевидно лишние числа для проверки. Это, конечно, не лучший результат, но уже достойный. И кто может пояснить, почему изначально в main память считается делением на 8*1024, хотя по логике должно быть 1024*1024?
Denis.Yakovinov23 уровень, Санкт-Петербург
10 June, 13:57
эхх) ну вот и я сделал это.. долго бился с рекурсией и в итоге добил именно ей, получал в рекурсивных вызовах листы c комбинациями и сразу проверял их на Армстронгов, нули можно не добавлять - а циклить возведение в степень(возводить в степень от длины комбинации(грубо говоря) до того, сколько нужно нулей), можно было ускорить, заменив листы массивами, но уже сил не было. Ну и небольшой совет тем, кто возможно только в процессе начала решения (а у вас впереди много веселья - поверьте :D) - не парсите числа в массивы интов через стринги и сплиты, это сожрет кучу времени и памяти, и это можно сделать простыми расчетами (если, конечно, это вам понадобится - мне понадобилось)
Valery Lvov20 уровень, Москва
5 June, 12:19
Коллеги, в чем может быть причина "Метод getNumbers должен возвращать массив чисел удовлетворяющих условию задачи", без комментария ментора "массив содержит лишнее или не содержит нужного" ? При проверке на Long.MAX_VALUE получаю результат, совпадающий с приведенным читерами: [1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407, 1634, .... 4498128791164624869, 4929273885928088826] Может с форматом что не так? Вроде верно: long[] result = new long[in.size()]; Может ли эта ошибка означать превышение времени выполнения? Вроде там другая ошибка, "программа работала очень долго и была остановлена" :((
Valery Lvov20 уровень, Москва
7 June, 06:04
Дело оказалось во времени исполнения :(
Алексей Иванов22 уровень, Cheboksary
9 June, 13:50
А что у вас со временем было? У меня время - 2 секунды и тоже валик не принимает. И ещё прошу пояснить в чём валик измеряет память?
System.out.println("memory " + (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) / (8 * 1024));
freeMemory(), вроде возвращает количество байт
Valery Lvov20 уровень, Москва
9 June, 16:23
У меня не принимал при времени исполнения 10-12 секунд (на моем компе) и пропустил при 7 секундах
Алексей Иванов22 уровень, Cheboksary
9 June, 17:06
А. Ну на моём компе 7 секунд, это если степень каждый раз заново вычислять. В общем понял я. Проблема была не во времени, а в том, что в конце метода я не подчистил переменные, которые потом использовались заново при повтортном вызове метода
Константин28 уровень, Курган
3 June, 17:36
Метод getNumbers должен возвращать массив чисел удовлетворяющих условию задачи. В массиве возвращаемом методом getNumbers не хватает элементов или есть лишние. ЧТО НАДО????? Числа с 1. Считаю не Math.pow, а собственным методом для точности. ЧТО НАДО? Короче: просидел 3 часа на тесте long_max. Мой ПК досчитал до 38 числа, а надо 50. Так что я решил эту задачу методом массива.
Алексей Иванов22 уровень, Cheboksary
9 June, 13:51
у вас проблема в переполнении int int currentDigit = (int) counter%10; - вот так на значениях counter (типа long), не влезающих в int, будет неправильный результат, поскольку сначала даункастится счетчик, получается фиг знает что, и потом от этого непонятно чего берется крайняя цифра. а правильно так: int currentDigit = (int) (counter%10);
taketori23 уровень, Санкт-Петербург
23 May, 11:21
Без рекурсии, без доп. потоков: memory 477 time = 10 Задача вытянула из меня жилы. Хотел растащить ее на потоки, но уже не хочется ничего. Все потом, после, позже, если будет время...
Павел32 уровень, Харьков
19 May, 10:55
Поиск чисел Армстронга: отчёт 1. Генерирование матрицы степеней Поскольку при поиске чисел Армстронга очень часто выполняется операция возведения в степень какого-либо однозначного числа, можно уменьшить затраты процессорного времени, предварительно вычислив результаты возведения в степень всех однозначных чисел и сохранив их в двухмерном массиве. Когда в ходе дальнейшего выполнения программы возникает необходимость возвести в степень одно из чисел, сама операция не выполняется; вместо этого готовый результат берётся из созданной ранее матрицы. 2. Генерирование уникальных числовых последовательностей Чтобы избежать затрат времени на проверку чисел, состоящих из одних и тех же цифр, следует рассматривать только то число, каждая цифра в котором не меньше предыдущей и не больше последующей. Очевидно, что при использовании такого способа отбора будут отсеяны также все числа, содержащие хотя бы один ноль. Для разрешения этой проблемы число можно представить в виде массива, каждый элемент которого содержит одну цифру исходного числа. Сначала создаётся массив длиной, соответствующей порядку введённого числа N (то есть верхней границе диапазона поиска); все ячейки массива инициализируются значением 9. Затем проводится уменьшение на 1 значения в [0] элементе массива до тех пор, пока это значение не достигнет 0. Тогда уменьшается значение элемента с индексом [1], а все предыдущие также элементы получают это новое значение. Пример: [0, 9, 9] становится [8, 8, 9]. После этого массив снова декрементируется по описанной выше схеме, начиная с [0] элемента. Так происходит до тех пор, пока значение последней ячейки не окажется равным нулю, что будет являться сигналом о достижении нижней границы диапазона генерации. Описанный способ генерации всегда соблюдает условие уникальности полученного «числа», а также сохраняет все лидирующие нули.
Павел32 уровень, Харьков
19 May, 10:57
3. Проверка уникальной последовательности Каждое сгенерированное в п.2 «число», представленное в виде массива цифр, проверяется (вычисляется степенная сумма его цифр). Полученный результат «раскладывается» на цифры, для которых опять вычисляется степенная сумма. Если результат будет равен числу до «разложения» на цифры, то это и есть число Армстронга. Примечание: исходные числовые последовательности с лидирующими нулями следует проверять несколько раз, отбрасывая перед каждой следующей проверкой один ноль от начала последовательности. Например, последовательность { 0, 0, 1, 2, 3 } может соответствовать таким числам: 132, 12300, 2301, 1032 и т. д. 4. Вычисление степенной суммы При исходном числе N, порядок которого не превышает 18 знаков, достаточно использовать примитивный тип long, поскольку даже максимально возможная степенная сумма в этом случае будет около 2,7*10^18, и, следовательно, не превысит максимально возможного значения для типа long (примерно 9,2*10^18). Если исходное число N содержит 19 знаков, то при вычислении степенной суммы возможен выход за пределы диапазона значений long, что приведёт к искажению результата (в некоторых случаях результат может быть даже отрицательным). Эту проблему можно разрешить двумя способами. Первый способ – математически точный, но более ресурсоёмкий. Он заключается в использовании класса BigInteger при выполнении вычислений для 19-значных чисел. Второй способ более быстрый, он использует следующее свойство: при прибавлении к Long.MAX_VALUE значения, не превышающего Long.MAX_VALUE, получим отрицательное значение (выход за пределы диапазона long). Таким образом, если в процессе вычисления степенной суммы возникает отрицательное значение, то проверяемое число может быть отброшено как неподходящее.
Павел32 уровень, Харьков
19 May, 10:57
5. Сохранение найденных чисел Армстронга Найденные числа помещаются в множество TreeSet, что позволяет исключить нежелательные дубликаты, возникающие в процессе поиска, а также отсортировать числа по возрастанию. 6. Результаты выполнения программы Код выполнялся на процессоре Intel Core i5-3570 с тактовой частотой 3,7 ГГц. Тесты проводились для диапазона натуральных чисел с верхней границей Long.MAX_VALUE. Версия 1 (с частичным использованием BigInteger): выполнение в 1 поток – 12 с, 12 Мб памяти; выполнение в 2 потока – 6,5 с, 20 Мб памяти; выполнение в 4 потока – 5 с, 35 Мб памяти. Версия 2 (без использования BigInteger): выполнение в 1 поток – 3 с, 8 Мб памяти; выполнение в 2 потока – 1,7 с, 13 Мб памяти; выполнение в 4 потока – 1,2 с, 20 Мб памяти.
Valery Lvov20 уровень, Москва
4 June, 11:17
Павел, третий день мечусь между оптимизацией перебора и твоим массивом...Прошу помощи, если ты еще не забыл эту задачу. все ячейки массива инициализируются значением 9. Затем проводится уменьшение на 1 значения в [0] элементе массива до тех пор, пока это значение не достигнет 0. Тогда аналогичным образом уменьшается значение элемента с индексом [1] и так далее. Мне кажется, ошибка в описании алгоритма. Судя по цитате выше, мы никогда не получим некоторые комбинации, например, очень интересующую нас {1,3,5}. Реализовав перебор по массиву, я получаю лишь 255 155 055 если есть желание - может, дашь в личку посмотреть, как организован этот цикл у тебя?
Павел32 уровень, Харьков
4 June, 13:04
Благодарю за замечание, описание исправил.