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

  • 11
  • Недоступна
Ура, задачи на алгоритмы! Их очень любят резиденты планеты Линейный Хаос. И вы должны любить, по крайней мере, до того момента, как пройдёте пару-тройку собеседований. Итак, у вас есть число из некоторого количества чисел. Нужно найти все числа меньше N, которые удовлетворили бы некоторому критерию (о нём узнаете в самой задаче!).
Вы не можете решать эту задачу, т.к. не залогинены.
Комментарии (184)
  • популярные
  • новые
  • старые
Для того, что бы оставить комментарий вы должны авторизоваться
Vadim Krant22 уровень, Москва
позавчера, 20:01
Написал я код программы, прямые вычисления, Integer.MAX_VALUE у меня даже вкладывалось в отведённый заданием временной интервал времени и объём программы в ОЗУ. Но на числе Long.MAX_VALUE я немного завис, точнее совсем завис, на пару часов, но список я получил :) Я несколько раз пытался скормить валидатору код решения, но пришлось включить запасной вариант. Как показала практика проще было сделать предрасчёт, сохранить его, а потом восстановить в виде константы прямо в процедуре (дальше уже всё очень просто). Может быть как великий оптимизатор кода я не состоялся, но на мой взгляд решение такое гораздо оптимальнее к ресурсам и времени чем код который на лету считает эти числа.
Sasha S25 уровень, Киев
15 декабря 2018, 22:41
Не просто капец, а тотальне знищення мозгу, 2 дня. Трохи підівчив алгоритми)) Я своїми силами спромігся тільки для 10000000 з 25 секунд до 2,5секунд. Дальше мій неокріплий мозок(прочитав нижче з коментарів)) ) не був готовий до придумання рекурсій)) як виявилося він не був готовий для робирання майже готового рішення (https://github.com/shamily/ArmstrongNumbers) ((. Думаю що вернусь сюда мабуть на відпусті або вже після закінчення курсу. Задачу рішив трошки нечесно, ну впринципі як сказати мені ще треба десь цілий тиждень сидіти щоб її рішити чисно і я вирішив не видумувати ровер а просто зайти з кінця, взяти готові числа і циклом перевіряти. Я рахую що мені треба більше досвіді на цю задачу а видающихся матиматичних здібностей чи логіки в мене нема так як і часу. В принципі JAVA, MAVEN з нуля ніхто не пише, навіть мало хто може написати))
Дмитрий26 уровень
14 декабря 2018, 10:51
Интересная задача, решал 2 дня, узнал много нового. Сначала попробовал решить в лоб элементарным перебором, даже для Integer.MAX_VALUE было очень долго. Далее, немного пошерстив интернет, стало ясно что сумма степеней 153 и 351 одинакова, соответственно достаточно посчитать ее один раз, а остальные варианты исключить. Переделал программу используя регулярки для исключения лишних итераций и BigInteger для расчета сумм. Для Integer.MAX_VALUE результат считался достаточно быстро, но Long.MAX_VALUE все еще был недостижим. Переделал с регулярок на массивы. Стало лучше для Long.MAX_VALUE находилось за 30 сек, но все равно многовато. Ну и, наконец, заменив BigInteger на long добился времени 3.7 сек. Итого с 11 попытки. В принципе можно еще ускорить распараллелив вычисления.
DancingShaman23 уровень
7 декабря 2018, 08:44
Не так сейчас много времени, чтобы учиться, а так бы хотелось по-больше разобраться с задачей. Решил в ЛОБ, но слишком долго работало, потом тупо использовать готовый лист констант, с ним задача решается за 5 минут.
urydmi23 уровень, Новосибирск
20 ноября 2018, 20:49
Кому как, а лично у меня эта задача вызвала только боль. В итоге бросил заходить на джавараш в сентябре - задача отбила желание обучаться вообще, чувствую себя тупым чурбаном просто. Ребят, подскажите как решить, бился недели две, ничего не получается.
Сергей31 уровень, Нижний Новгород
27 ноября 2018, 22:32
Тут расписан алгоритм нахождения чисел армстронга(а они нам и нужны) https://acmp.ru/article.asp?id_text=198, его реализация позволяет рассчитать необходимые числа где то за 25 секунд, если не заморачиваться с оптимизацией. А далее хардкодим полученный массив в метод getNumbers(long N) и возвращаем его часть, в зависимости от N.
urydmi23 уровень, Новосибирск
6 декабря 2018, 05:29
решение через хардкод не интересует
Alex P31 уровень
18 ноября 2018, 09:33
Let's think... In order to optimize calculations, we can reduce exponentials operations and results covered by some combinatory combinations. like ab~ba, abc~acb~bac~cab~bca~cba etc... We can store optimized results in XYZ matrix: x{0-9} - numbers in the decimal system. y{1-18} - for results of exponentiations for 18 bases (number of symbols in Long.MAX_V). z - for combinatory data. (We also can share matrix operations to threads) The good question is the nature of the combinatory type algorithm. Would it be good enough... It's a complex task...
Victoria Sedletskaya32 уровень, Одесса
15 ноября 2018, 19:36
уже "Всего эту задачу решили 4137 учеников." одна из проверок потратилась на то, что числа в массиве были не строго меньше заданного числа, а <= Время работы алгоритма для максимального лонг у меня получалось от 8 до 12 секунд, не смотря на это валидатор принял (фух) мне кажется, за такие задачи надо больше материи давать :-) хотя, опыт бесценен
Pavel Soros23 уровень
8 ноября 2018, 17:42
Сохраните в массив все возможные числа Армстронга в диапазоне Long.MAX_VALUE (их всего 50). Затем сравнивайте эти числа с переданным значением. Всё что меньше кладите в возвращаемый методом getNumber() массив. Это не очень честно. Но кто сказал что так нельзя. Валидатор принимает.
JamesBean25 уровень, Новосибирск
8 ноября 2018, 16:03
Супер задача. Кучу времени потратил на нее, испробовал несколько вариантов. Но оказалось, что больше всего времени боролся с собственной глупостью - не чистил static переменную :-( - валидатор ругался, не принимал.
Bogdan Yushkov32 уровень, Екатеринбург
8 ноября 2018, 16:08
Подскажи пожалуйста, как ты это сделал?)
JamesBean25 уровень, Новосибирск
8 ноября 2018, 16:21
Написал коммент в вашем вопросе на обсуждение
Bogdan Yushkov32 уровень, Екатеринбург
8 ноября 2018, 16:23
Спасибо)
JamesBean25 уровень, Новосибирск
8 ноября 2018, 16:26
Удачи, надеюсь поможет. Сам я потратил 4 дня :-)
pca17323 уровень
19 сентября 2018, 17:09
Здравствуйте! Не понятно для какого N должно быть < 10 c. ?
Максим27 уровень
22 сентября 2018, 21:00
Для Long.MAX_VALUE