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

  • 20
  • Недоступна
Ура, задачи на алгоритмы! Их очень любят резиденты планеты Линейный Хаос. И вы должны любить, по крайней мере, до того момента, как пройдёте пару-тройку собеседований. Итак, у вас есть число из некоторого количества чисел. Нужно найти все числа меньше N, которые удовлетворили бы некоторому критерию (о нём узнаете в самой задаче!).
Вы не можете решать эту задачу, т.к. не залогинены.
Комментарии (524)
  • популярные
  • новые
  • старые
Для того, чтобы оставить комментарий вы должны авторизоваться
Yura Moskalevich 23 уровень, Mogilev
19 февраля, 17:41
Если кому-то это поможет лучше понять условие задачи мы ищем число Армстронга.число Армстронга
Anonymous #2489173 23 уровень
17 февраля, 06:50
Напоминает задачки со школьной олимпиады)
Михаил 23 уровень, Саратов
14 февраля, 19:32
Ох. Два дня решал, забывая про обеды. На правильный путь наставили комментарии Павла. На потоки пока ни чего не распускал, в голове каша, в IDE - говнокод, пока и не представляю как это сделать.
Андрей 22 уровень, Киев
9 февраля, 18:18
Заумная задача свелась к перебору массива))
Андрей Овчаренко 25 уровень, Москва
7 февраля, 21:37
что означает ошибка по четвёртому пункту "Метод getNumbers должен возвращать массив чисел удовлетворяющих условию задачи." ? вывод:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407]
memory 718
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]
memory 1026
time = 3
Андрей 24 уровень, Москва Expert
2 февраля, 21:52
Вот как бы решил и локально получаю такие показатели:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407]
memory 556
time = 0
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407, 1634, 8208, 9474, 54748, 92727, 93084, 548834]
memory 6481
time = 0
Но что-то очкую кормить этим "валю"...
Андрей 24 уровень, Москва Expert
3 февраля, 19:09
"Валя" меня послал нахрен, говорит "Что-то опасное ты творишь!", "А отсортировал?" и "А если исключения?". Перелопатил свой код в методе и получил такой уже результат:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407]
memory 446
time = 0
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407, 1634, 8208, 9474, 54748, 92727, 93084, 548834]
memory 1836
time = 0
Ну что ж, пробуем ver.1.0.1...
Андрей 24 уровень, Москва Expert
3 февраля, 21:54
Новый варинат выдал это 🤔
OutOfMemoryError
Я всё ещё пытаюсь решить через Stream...
Андрей 24 уровень, Москва Expert
6 февраля, 20:33
Я того рот труба шатал! 4 дня и просто жестя с писюардом переписыванием решения. Наивно начал полностью с Stream API, выражение которого в итоге сократилось тупо до получения long[] из List<Long> для возвращения в main(). Core i3-3120M 2.50GHz без распараллеливания выдало:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407, 1634, 8208, 9474]
memory 446
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]
memory 476
time = 0
На скрине видно, что второй тест запускался на
System.out.println(Arrays.toString(getNumbers(10_000_000_000L)));
Но всё равно я что-то делаю не так, как оказалось. Видимо нет в массиве нуля и таки допустил числа >= N. Дрочим голову дальше...
Андрей 24 уровень, Москва Expert
6 февраля, 20:40
UPD: Решение было в добавлении метода Stream.filter(l -> l < N) с указанной лямбдой в цепочку вызовов методов Stream API, ну и в появлении цифры 0 в массив чисел (спойлер - не помог ноль). Результат:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407]
memory 446
time = 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]
memory 476
time = 0
Тут в тест не стал особо большой long кидать, тк этот момент уже не влияет на результат: Но всё равно чего-то не хватает, не пойму только чего 🤷‍♂️
Е К 23 уровень, Краснодар
1 февраля, 12:28
Топчик в рейтинге "Самый труднорождённый алгоритм". Но даже когда родил - остаётся ещё беспощадный, но где-то справедливый валидатор. Неделя жизни в итоге я 6307й с характеристиками за которые не стыдно(вот она мощь рекурсии):
memory 2192
time = 4
Что помогло в процессе творческих мук: 1. Комменты Павел Безумный учёный в самых популярных 2. Готовое решение от JR(каюсь посмотрел). Но так и не смог разобраться до конца как там всё устроено(решил не терять на это время). Однако в процессе разбора пришло осознание, что алгоритм составления комбинации чисел для последующего анализа (пункт 2 у Павла) лучше всего выполнить с помощью рекурсии. 3. пункт 2 у Павла - ядро задачи. После его выполнения остальное это дело техники. Однако столкнулся с непониманием валидатора. Очень помог такой тест в майне:
long[] result = getNumbers(Long.MAX_VALUE);
 long[] result1 = getNumbers(100l);
 System.out.println(Arrays.toString(result));
 System.out.println(Arrays.toString(result1));
4. Проверка входящего параметра обязательно должна быть именно такого вида N < 0. Это был последний рубеж, перед которым уже готов был послать на хрен валидатора и эту задачу вместе взятых запрос разработчикам о помощи в поиске косяка. Но с помощью комментов к запросам в разделе помощь выяснился этот мелкий, но важный для вали аспект. Дорогу осилит идущий! Не останавливайтесь, упорство вознаграждается приятным ощущением кайфа. Сам не смог бы себе забыть\простить, что не справился и пропустил эту задачу. Это как переступить через себя.... Желаю всем страждущим удачи!
Клим 24 уровень
29 января, 21:38
Может кому поможет. Массив генерации степеней размещать не в теле main()
Артур 20 уровень, Москва
24 января, 20:42
Вроде как решил, числа показывает правильные. Но вероятно не самым оптимальным образом, на больших числах в заданное время не укладываюсь, однако при проверке по таймауту не отваливается. Но и валидатор упрямится, говорит массив чисел не тот (числа сверял с википедией), кто-то с таким сталкивался?
Kes Чайник в Банк
26 января, 00:55
В популярных комментах есть список всех чисел.
Артур 20 уровень, Москва
26 января, 20:39
Ну, список найти не проблема, вопрос немного в другом. Бывает валидатор ругается на действительно рабочий код (впрочем, бывает и обратное когда какой-то хитрый случай входных данных не учел). Вот не пойму какой случай у меня сейчас. На вид числа совпадают с эталонным списком, валидатор не принимает. Видимо надо все-таки посидеть еще над оптимизацией
Валентин 22 уровень, Москва
17 января, 15:19
Андрей 24 уровень, Москва Expert
2 февраля, 21:30
Случаем не на Stream API делал?