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

  • 20
  • Недоступна
Ура, задачи на алгоритмы! Их очень любят резиденты планеты Линейный Хаос. И вы должны любить, по крайней мере, до того момента, как пройдёте пару-тройку собеседований. Итак, у вас есть число из некоторого количества чисел. Нужно найти все числа меньше N, которые удовлетворили бы некоторому критерию (о нём узнаете в самой задаче!).
Вы не можете решать эту задачу, т.к. не залогинены.
Комментарии (686)
  • популярные
  • новые
  • старые
Для того, чтобы оставить комментарий Вы должны авторизоваться
Sergey Paleny
Уровень 25, Ставрополь, Россия
вчера, 15:04
Легендарного Павла так и не нашёл, но всё равно спасибо ему))) Решил благодаря остальным комментаторам. Хочу объединить прочитанное: 1 - возьмите из комментов список нужных цифр (числа Армстронга) и с ними сравнивайте свои цифры; 2 - не перебирайте все цифры подряд от 0 до N - выходит долго и валидатор не принимает... З.ы. моё решение с N = Long.Max_Value выдаёт требуемый список за: memory 368 time = 0
Вадим
Уровень 39, Минск, Belarus
6 августа, 10:08
У кого не принимает по последнему пункту "Метод getNumbers должен возвращать массив чисел удовлетворяющих условию задачи", то возможно, как это было у меня, ваш алгоритм не проходит по лимиту памяти. Долго сверял свой вывод при всех возможных входных значениях, а оказалось что просто надо код немного оптимизировать, чтобы меньше памяти кушал. И ещё это походу шутка от разарабов, но в исходном коде задачи память зачем-то выводится в килобитах. Чтобы нормально чекать лимит, надо ещё и вкурить как вывод переделать в мегабайты 🙄
proxylunae
Уровень 41, Russian Federation
19 июля, 17:21
Решил задачу меньше чем за 10 секунд, как и указано в требованиях, но не понял как узнать сколько памяти выделил мой мозг. 🤔🤔🤔🤔
4MVX
Уровень 36, 134340 Pluto, Германия
19 июля, 09:06
ставь лайк,если решил за 10 секунд
Lyokha Blagodatskikh
Уровень 30, Ural, Russian Federation
7 августа, 15:24
я условия то минут 15 только понять пытался ))))))
aelir1
Уровень 23
17 июля, 21:22
Невероятно горит. Написал двольно быстрое, хоть и явно не идеальное решение, уходит 6 секунд на 10^9, то есть на расчёт 31 числа армстронга от начала. Вывод совпадает с выводом "эталонного" решения от javarush. Но валидатор не принимает!
Alexandr Vlasov
Уровень 23, Москва
29 июня, 09:43
Что не так? [1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407] memory 368 time = 0 [1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407, 1634, 8208, 9474, 54748, 92727, 93084, 548834] memory 368 Process finished with exit code 0
AhanSere специалист тех поддержки в в сфере 1с
24 июня, 07:36
Эта задача дает п**** вашим мозгам знатно, но это полезно - можно узнать или вспомнить много полезного, понять, "пощупать" скорость работы java и различных методов и подходов в ситуации обработки большого количества данных. Павлу респект, он все верно объяснил, поэтому не буду много писать, поделюсь некоторыми моментами и ошибками, с которыми столкнулся я
AhanSere специалист тех поддержки в в сфере 1с
24 июня, 08:32
В отличие от (похоже) устоявшегося тут решения забивать массив девятками и понижать, я сделал в готовом решении наоборот, генерировал такой ряд начиная с нуля и увеличивая его: ... 7777 7778 7779 7780 7788 7789 7790 7799 7800 7880 7888 7889 7890 7899 7900 7990 7999 8000 ... это на мой взгляд, то же самое только в другом порядке, поэтому разницы нет мне было так удобней т.к. всегда сохранялась оригинальная длина массива (длина числа) - степень, в которую нужно возводить цифры и не нужно отбрасывать нули при проверке, просто каждый раз беру из матрицы элемент с индексами - сама цифра и длина массива Как разбить long в массив правильно и быстро (без string'а) - не нашел, может плохо искал (подскажите, если знаете) - написал такой метод сам (беру остатки от деления на 10)
AhanSere специалист тех поддержки в в сфере 1с
24 июня, 09:11
Некоторые ошибки, которые я допускал по незнанию/лени разбираться: - Главная ошибка - конечно в начале не допер в чем суть и начал перебирать все числа, потом прочитал в интернете, что многие из них равнозначны, тут до меня дошло и решение задачи началось. Остальное - дело техники - В некоторых местах, боясь переполнения брал double, но не учел, что он (как и float) округляет числа (после 15 вроде символа) - получалось в конце длинного числа не ...75807, а ...76000, что искажало результат. На самом же деле double вовсе не нужен, как и Biginteger, можно все решить только в long, а он считается хорошо, без таких "сюрпризов" - Сначала использовал не матрицу готовых чисел, возведенных в степень, а каждый раз метод Math.pow - Для подсчета матрицы использовал Math.pow, потом переписал на ручной подсчет - Вначале использовал не массив цифр, а целое число (long), для которого прописал функцию, которая увеличивала бы его каждый раз на нужное значение, чтобы отсеивать не нужные числа - Для разбиения числа в массив использовал String и его split - позже от String совсем отказался, написал функцию, которая правильно увеличивает число прямо в виде массива - Вначале для каждого действия написал отдельный метод, но потом решил смешать почти все в одном - это позволило избавиться от некоторых лишних действий и преобразований, связанных с передачей переменных в эти методы, позволило сразу использовать некоторые данные, которые были получены ранее, хоть код и стал менее читаемым - Делал инкремент моего числа в начале цикла, а не в конце, поэтому подсчет начинался с 1, а не с 0. Не знаю точно, повлияло ли это на валидатор (не выяснял), но это изменение было в числе последних, после которых решение прошло проверку - При разбиении числа в массив я увеличивал размер массива каждый раз на 1 при необходимости, но ИМХО это долго, особенно при том, что это действие повторяется много раз. В результате я стал вначале вычислять нужную длину массива и затем сразу создавать его, а потом наполнять
Дмитрий Студент в мгу(вмк)/мфюа
14 июля, 14:39
Что за комментарии ПАВЛА вы все обсуждаете, немогу найти их
AhanSere специалист тех поддержки в в сфере 1с
24 июня, 07:29
Вот правильный вывод на Long.MAX_VALUE, если кому надо (время выполнения у вас может, конечно, отличаться, в зависимости от обстоятельств) [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 686 time = 2
Сонмониус
Уровень 39, Харьков, Ukraine
22 июня, 12:35
Сделал файл с числами армстронга (их всего 88, и все уже вычислены, в интернете можно найти список и скопировать). При вызове метода, getNumbers, этот список скачивается из файла, и преобразуется в массив строк через стринг.сплит. Входящее значение сравнивается с элементами массива. До тех пор, пока элемент массива преобразованный к значению long, не будет больше пришедшего на вход N, каждый элемент сохраняется в новый список. Работает вроде все корректно, но валидатор ругается) По использованию памяти, в 10 с копейками раз лучше программа получилась, чем первый вариант, где каждое число раскладывалось, возводилось в степень и т.д, время вообще по нулям показывает. Вообще отображение проверки один в один, как при запуске предложенного джавараш варианта, по длине кода и того меньше, причем раза в два. Хз, что не нравится валидатору, меня такое решение устроило, пойду дальше.
Artem Trainee в Deutsche Telekom
17 июня, 20:01
кто-нибудь может объяснить задание?