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

  • 20
  • Недоступна
Ура, задачи на алгоритмы! Их очень любят резиденты планеты Линейный Хаос. И вы должны любить, по крайней мере, до того момента, как пройдёте пару-тройку собеседований. Итак, у вас есть число из некоторого количества чисел. Нужно найти все числа меньше N, которые удовлетворили бы некоторому критерию (о нём узнаете в самой задаче!).
Вы не можете решать эту задачу, т.к. не залогинены.
Комментарии (460)
  • популярные
  • новые
  • старые
Для того, чтобы оставить комментарий вы должны авторизоваться
Sergey22 уровень, Ярославль
пятница, 13:30
Кто еще не намучился с решением, не читайте!!! Задача на поиск чисел Армстронга в заданном диапазоне от 0 (не включая) до N. Поэтому решал ее не тратя время на вычисление этих самых чисел, а взяв массив уже вычисленных чисел в заданном пределе. Если же Ваша цель, все таки реализовать оптимальный алгоритм нахождения этих самых чисел, то Вам этот способ решения не подойдет или подойдет, но только после заполнения того же самого списка из вычисленных чисел Вашим алгоритмом. Так как в качестве входящего параметра мы используем тип long, то максимальное число знаков у нас будет равно 19 (Long.MAX_VALUE = 9223372036854775807). 1) Создаем массив типа long и в соответствии с таблицей инициализируем его, переписывая в него через запятую все числа Армстронга, включая 19 строку. 2) Создаем новый список, например типа ArrayList и через цикл, заполняем его последовательно всеми числами из ранее созданного массива, если число из массива меньше чем число N. 3) Создаем новый массив long [] result размером равным размеру заполненного списка. 4) Через цикл переписываем в массив все числа из списка и возвращаем result.
Иван Линник27 уровень, Краматорск
22 сентября, 17:02
Очень рад что решил эту задачу. Потратил на неё неадекватно огромное количество времени, рыдал, злился, забывал есть. Но когда решил получил море удовольствия. Правда без комментариев ниже наверное бы не справился. Есть совершенно не очевидные и мудрёные вещи. Всем спасибо кто пишет умные комменты. В итоге: 100 строк решения, 2-4 кб и 2,5 сек для максимального значения. PS 4е условие ругалось, но пропустило когда добавил проверку на выход за пределы диапазона long.
Romul22 уровень
понедельник, 07:04
Привет. Можешь помочь? Я не совсем понимаю алгоритм перебора значений. В чем его мысль. Хочу решить самостоятельно, поэтому мне не код нужен, а на словах суть. Вдруг ты сможешь объяснить, буду благодарен. Вначале я подумал, что мысль алгоритма в следующем: есть число например 546. Комбинаций трехзначных цифр из этих 3!, соответственно можно найти степенную сумму одного числа, затем для этого числа найти все комбинации и для них уже не вычислять степенную сумму и это использовать. Но находить комбинации 19разрядного числа это не есть быстрое нахождения чисел Армстронга. Ну и вообщем до меня до сих пор не доходит эта идея(
Иван Линник27 уровень, Краматорск
понедельник, 18:28
Чтобы не пересчитывать лишние комбинации нужно упорядочить цифры по возрастанию или убыванию ("456" или "654"). Не нужно находить комбинации 19разрядного числа. А чтобы не пропустить некоторые числа нужно добавлять нули. Так меняется степень в которую возводятся цифры. Например нужно проверить "0456" и "00456" и так до 19 разрядов. Для этого числа нужно найти сумму произведений и проверить является ли это число числом Армстронга. Самое интересное это организовать алгоритм который находит все уникальные комбинации. В комментах все подробно расписано у Павла, за что ему большое спасибо. Чтобы было проще написать всю эту конструкцию - разбивай на методы.
kate krivikh41 уровень, Москва
18 сентября, 13:48
Хорошая задачка. Читайте комменты ниже. Я застряла на следующем: 1. Если не принимает 4 пункт, при этом на Long.MAX_VALUE выполняется секунд за 10, этого мало. Надо, чтобы выполнялось за 7. 2. Проверяйте для N <= 0. 3. И продублирую повыше чуть: не сравнивайте цифры в числах (135 и 153 и т.п.) через стримы и т.п. - очень долго.
Owpk24 уровень, Иркутск
5 сентября, 05:54
https://github.com/sorokod/Armstrong - решение, 1ч поиска на 35 символов в числе, 6 секунд на Long.MAX_VALUE
Сергей26 уровень
23 августа, 15:08
Решил в лоб. Во входящее число сразу сунул Long.MAX_VALUE. Ждал часа три и вырубил нафиг не дождавшись. 😂
ram097341 уровень, Набережные Челны
20 августа, 20:16
Странно что этот король задач стоит так мало :)
Шамиль22 уровень, Кисловодск
19 августа, 15:08
🤪😜👍
Arseniy Zhuck26 уровень
11 августа, 06:49
Классная задача, так как сам долго мучался, решил написать, что мне помогло. Собственно, подход в лоб не работает в принципе, читайте про числа Армстронга, поймите, какие числа нужно перебрать. Далее нужно сгенерить все такие числа. Сгенерить мне помогла дискретная математика, пришлось вспомнить что такое сочетания и сочетания с повторениями, так как эти значения всегда можно в онлайн калькуляторе посмотреть и сравнить количество сгенеренных массивов с количеством сочетаний, должны совпадать. Для реализации можно рекурсия, но слишком много памяти жрет, можно перебор в цикле, тут можно легко с индексами запутаться. Я составил первый массив из нулей, а дальше функцию, которая получает следующий массив, то есть после 02339 - 02344 соотвественно, все элементы в массиве сразу получаются упорядоченными, тем самым повторы сразу исключены. Далее в зависимости от количества нулей нахожу возможные суммы, например в указанном чисел сумму для 4 и 5 степеней. и проверяю полученные числа. не знаю, нужен ли был массив степеней цифр, но он был готов еще на первых этапах. Главное в этом массиве не пользоваться power, возникают ошибки округления. Просто надо подумать, что следующая степень это предыдущая умножить на число. Никакие другие подходы у меня не проходили по времени. Да и еще проверяйте программу на 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 407 time = 5
wan-derer.ru25 уровень, Москва
11 сентября, 11:27
Ноль не надо включать в последовательность?
Arseniy Zhuck26 уровень
12 сентября, 15:36
Реализовать логику метода getNumbers, который должен среди натуральных чисел меньше N (long) находить все числа, удовлетворяющие следующему критерию: на основе этого условия не надо, ноль не натуральное
wan-derer.ru25 уровень, Москва
12 сентября, 17:55
Что-то у меня не принимает: ни с нулём, ни без нуля. Пишет "не хватает или есть лишние", хотя списку соответствует...
dolcom22 уровень, Самара
15 сентября, 20:15
Бро, сочетания с повторениями и без повторений - это тебе не дискретная математика, это комбинаторика 😄
Arseniy Zhuck26 уровень
22 сентября, 12:26
А комбинаторика раздел чего?))
dolcom22 уровень, Самара
22 сентября, 15:19
Хмм! Ты прав! Но я с комбинаторикой столкнулся только в теории вероятностей 🤔
Dator23 уровень, Киев
28 июля, 16:16
Потратил больше времени чем обычно. Сначала думал что должно работать с теми числами которые были заложены в тест. На практике - вплоть до
Long.MAX_VALUE
Для последующих любителей таких упражнений: В комментах есть ссылка на статью про числа армстронга. Будет полезна для начала. Но самое главное - проблема в том как вы мыслите. Не в стрингах, не в коллекциях.. хотя без них быстрее намного. Главная проблема в количестве чисел, которые вы будете проверять. И тут на помощь приходит математика примерно 3-5 класса школы. От перемены мест слагаемых, сумма не изменяется. Удачи)
Ivan D25 уровень
24 июля, 11:43
Я решал задачу несколько недель! Я ее решил! УРА! Огромная благодарность пользователю Павел за помощь! Ниже в комментариях можно найти его план решения, который очень Вам поможет.
Ivan D25 уровень
24 июля, 11:44
[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 548 time = 3 [1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407, 1634, 8208, 9474, 54748, 92727, 93084, 548834] memory 869 time = 0 Process finished with exit code 0