Это еще просто и понятно. Вот когда башен не 3, а N...
И вместо кружков башни.
И тестовое на 1 час.
Вот так бог мир и создавал
Не пизди, проэкт был реализован за неделю точнее за 6 рабочих дней +1 выходной.
сразу слать нахуй такое тестовое
потому что это тест на АНТИ ITшника
и вот почему:
айтишники работают с чужим кодом днями неделями и месяцами в КОМАНДЕ.
а не кодят тривиальное нахуй некому не нужное гавно с нуля в одиночку за пол часа В ОДИНОЧКУ.
если долбаёбам не жить не быть нужно покодить на leetcode (извиняюсь за мат) дипломотично предложить открыть чужое решение и доработать вдвоём, там куча задач схожих, взять одну решённую и доработать до другой. вот как надо пользоваться leetcode-ом (извиняюсь за мат).
потому что это тест на АНТИ ITшника
и вот почему:
айтишники работают с чужим кодом днями неделями и месяцами в КОМАНДЕ.
а не кодят тривиальное нахуй некому не нужное гавно с нуля в одиночку за пол часа В ОДИНОЧКУ.
если долбаёбам не жить не быть нужно покодить на leetcode (извиняюсь за мат) дипломотично предложить открыть чужое решение и доработать вдвоём, там куча задач схожих, взять одну решённую и доработать до другой. вот как надо пользоваться leetcode-ом (извиняюсь за мат).
А что не так?
Я конечно, фотошоп, а не программист, но кажется шутка про алгоритмы сортировки.
Ханойские башни
У меня пошли флешбеки из Легенд Кирандии 2. И в случае с этой головоломкой - нихуя не приятные
И в КОТОРе, вроде в гробнице ситхов
А что не так?
Не уверен, что многие с этим сталкивались. Кроме того, когда учились в универе. Потому что есть куча готовых решений, нужно только воспользоваться. Хотя я тоже не тру программист, и говорю со своей колокольни.
У меня в школе они были. Я ненавидел информатику.
Я на паскале писал программу для этого
Давно на ютубе смотрел видео про программиста который учил ИИ, (аватар в виде монитора с телом человека в толстовке), так вот у него половина решений задач сводилась к:
"-Хм ИИ не хочет преследовать этот самолет. Спизжу я вот этот кусок кода.
-Хм теперь ИИ не видит препятствия, опа вот и ещё кусок"
"-Хм ИИ не хочет преследовать этот самолет. Спизжу я вот этот кусок кода.
-Хм теперь ИИ не видит препятствия, опа вот и ещё кусок"
Ага именно он
Проблема такого подхода в том, что это ведёт к полному непониманию того как твой код работает. А как следствие при возникновении какой-либо ошибки ты потратишь гораздо больше времени и сил на то, чтобы просто эту ошибку выявить, не говоря уже о том, чтобы её устранить. Так что, готовые решения это конечно хорошо, но знать как работает код и уметь его писать с нуля - это тоже надо уметь.
Так а никто и не станет тебе платить на рабочем месте за долгое и вдумчивое изучение внутренностей готового решения. Всем надо здесь и сейчас, а если проблемы и появятся, то решать их будут тогда, когда они появятся.
Глупо выделять тонну времени на оптимизацию для какого-то специфического случая, который не факт, что вообще произойдет.
Глупо выделять тонну времени на оптимизацию для какого-то специфического случая, который не факт, что вообще произойдет.
так никто и не заплатит тебе за продукт который не будет работать или на отладку которого придётся угробить ещё чёрт знает сколько времени, потому что он нужен к установленному сроку.
Я это больше к тому, что люди которые полагаются исключительно на готовые решения зачастую грешат тем, что забивают на самообразование, уповая на то, что какой-то другой Васян уже написал готовое решение для их задачи, даже если это решение проблемы другого готового решения. И ведь такие люди реально существуют. Мне как минимум известно два таких.
Я это больше к тому, что люди которые полагаются исключительно на готовые решения зачастую грешат тем, что забивают на самообразование, уповая на то, что какой-то другой Васян уже написал готовое решение для их задачи, даже если это решение проблемы другого готового решения. И ведь такие люди реально существуют. Мне как минимум известно два таких.
Заплатит. И еще как заплатит.
Есть целые компании, которые держатся на рынке 10+ лет тупо тем, что предлагают заказчикам низкие цены и набирают себе в штат веб-макак после курсов, далее через полгода скидывают всю ответственность на них, выбрасывают и находят новых.
>так никто и не заплатит тебе за продукт который не будет работать или на отладку которого придётся угробить ещё чёрт знает сколько времени
Ха ха.
Ха ха.
Но если речь идёт о таких базовых вещах, как сортировка массива, то зачем изобретать велосипед? Самообразование это, конечно, хорошо, но ни у кого ни за что не хватит времени изучить как реализованы все алгоритмы.
Вот нихуя вообще. Я прекрасно знаю как мой код работает. На всё есть чёткие спецификации. Я идеально знаю как будет работать мой код в соответствие с этими спецификациями.
Библиотечная функция сортирует. Сортирует всегда так, как указано, с более-менее оптимальной сложностью. Абсолютно поебать какой там алгоритм под капотом. Мне достаточно в принципе знать о существований классов сложности, ничего более.
Если я столкнусь с узким местом или странным поведением, только тогда я начну забираться в конкретные алгоритмы. И заберусь, и изучу. Но не раньше, в моей голове и так мусора хватает.
Библиотечная функция сортирует. Сортирует всегда так, как указано, с более-менее оптимальной сложностью. Абсолютно поебать какой там алгоритм под капотом. Мне достаточно в принципе знать о существований классов сложности, ничего более.
Если я столкнусь с узким местом или странным поведением, только тогда я начну забираться в конкретные алгоритмы. И заберусь, и изучу. Но не раньше, в моей голове и так мусора хватает.
Это не про алгоритмы сортировки, они здесь не подойдут. Просто придумать и реализовать оптимальный алгоритм будет ооочень непросто.
ханойские башни. задача: сложить из блинов одну пирамидку. ограничение: сверху на блин можно положить только меньший по размеру блин.
если на 3 шеста 3 блина, то тривиально. если больше блинов, то складываешь минипирамидку из трех блинов как обычно, потом представялешь эту минипирамдку как "один наименьший блин", и проделываешь те же шаги с ней и еще двумя блинами. только чтобы ее переместить на другой шест, нужно проделать шаги из предыдущего раза. получается, каждый раз ты сортируешь 3 блина, за один из которых принимаем отсортированную минипирамидку. но чем больше в ней блинов, тем больше шагов нужно, чтобы ее саму переместить на другой шест
если на 3 шеста 3 блина, то тривиально. если больше блинов, то складываешь минипирамидку из трех блинов как обычно, потом представялешь эту минипирамдку как "один наименьший блин", и проделываешь те же шаги с ней и еще двумя блинами. только чтобы ее переместить на другой шест, нужно проделать шаги из предыдущего раза. получается, каждый раз ты сортируешь 3 блина, за один из которых принимаем отсортированную минипирамидку. но чем больше в ней блинов, тем больше шагов нужно, чтобы ее саму переместить на другой шест
Да тут с любым числом блинов решение тривиально, через рекурсию.
Не, это классическая задача для изучения рекурсивных алгоритмов
Это известная задача про ханойские башни. Ее часто используют для демонстрации рекурсии и иногда динамического программирования. Сложные запутанные темы, в общем-то.
Надо глянуть на ютабчике.
И как иллюстрация комбинаторного взрыва
Был забавный фантастический рассказ, как астронавт был на какой-то исследуемой планете взят в плен разумными существами, типа эволюционировавших горилл. Там все общество было помешано на играх, и перед казнью приговоренный мог предложить сыграть в любую игру. А если предложит новую - вообще здорово, вся планета смотрит это по ТВ и радуется. Он спрашивает: мол, если выиграю - отпустите? Нет, просто будешь жить, пока игра продолжается.
Ну, он и предложил им новую игру - вот это самое. Ханойские башни. Ему говорят: Ну, как-то странно выглядит, но все же новая игра, давайте попробуем. Сели играть - а игра все не кончается. Вроде и в обмане не уличить - прогресс какой-то есть, но... Обезьяний профессор рассчитал, что это займет 1000+ лет, и измученный астронавт по многу часов в день все играл с этими обезьянами. Дождался, дожил - прилетела спасательная экспедиция, всем дала дюлей и освободила его.
Вот тако
Ну, он и предложил им новую игру - вот это самое. Ханойские башни. Ему говорят: Ну, как-то странно выглядит, но все же новая игра, давайте попробуем. Сели играть - а игра все не кончается. Вроде и в обмане не уличить - прогресс какой-то есть, но... Обезьяний профессор рассчитал, что это займет 1000+ лет, и измученный астронавт по многу часов в день все играл с этими обезьянами. Дождался, дожил - прилетела спасательная экспедиция, всем дала дюлей и освободила его.
Вот тако
Там была "модефицированная" ханойская башня: стержнев 3, а дисков гораздо больше. Впрочем, вот и сам рассказ:
Не модифицированная, а обычная, на n дисков.
Добавление каждого нового диска увеличивает число шагов вдвое.
Автор игры, Эдуард Люка, сочинил легенду, что в каком-то восточном монастыре монахи решают эту задачу с 64 дисками, и когда закончат, наступит конец света. Впрочем, нам он не грозит, потому что надо сделать всего-то 2^64-1 ходов, то есть даже если монахи херачат по диску в секунду (что уже слишком оптимистично), то это у них займёт 585 миллиардов лет.
Добавление каждого нового диска увеличивает число шагов вдвое.
Автор игры, Эдуард Люка, сочинил легенду, что в каком-то восточном монастыре монахи решают эту задачу с 64 дисками, и когда закончат, наступит конец света. Впрочем, нам он не грозит, потому что надо сделать всего-то 2^64-1 ходов, то есть даже если монахи херачат по диску в секунду (что уже слишком оптимистично), то это у них займёт 585 миллиардов лет.
Решите эту задачку когда часть "бубликов" сделаны изо льда и тают со временем, цвета у "бубликов" с другой стороны (которую не видно на фото) не совпадают, а верх у стержней запаян
1. Дождаться, пока лишние растают
2 ...
3. PROFIT
2 ...
3. PROFIT
Это если только ледяные стояли на нужных местах
Но вообще интересная задача где решением является просто "ждать пока само не встанет как надо"
Но вообще интересная задача где решением является просто "ждать пока само не встанет как надо"
В условии сказано, что не все из них ледяные. Но это логично: если они все равно растают, то нет смысла вообще их куда-либо двигать. Пусть растают и не мешают манипулировать остальными
Ну, если задача сосчитать шаги, то всё не так уж плохо, типичное рекурсивное решение с (O(n), где n - количество блинов в пирамидке), со случаями:
n = 1: return 1
n = 2: return 3
Остальные: return 2 * Hanoi(n - 1) + 1
Можно добавить tail recursion для уменьшения потребления памяти с O(n) до O(1)
Если же выдать именно шаги, то тут тоже всё просто: нам пиздец, ибо кол-во шагов в любом случае будет 2^n и времени и памяти. То есть, на 10 блинов нужно 2^10 = 1024, или грубо 1000 шагов. На 40 блинов это уже будет триллион шагов.
n = 1: return 1
n = 2: return 3
Остальные: return 2 * Hanoi(n - 1) + 1
Можно добавить tail recursion для уменьшения потребления памяти с O(n) до O(1)
Если же выдать именно шаги, то тут тоже всё просто: нам пиздец, ибо кол-во шагов в любом случае будет 2^n и времени и памяти. То есть, на 10 блинов нужно 2^10 = 1024, или грубо 1000 шагов. На 40 блинов это уже будет триллион шагов.
ПыСы: это нихера не просто, я просто поехал кукухой на этой теме, ибо скоро очередной собес
Не знаю, выглядит как классическое динамическое программирование.
Типа переместить башню высотой n - это как переместить верхние n-1 на временный столбик, переместить нижнюю плиту, переместить n-1 со временного столбика на перемещенную нижнюю плиту. Переместил, замемоизировал, вот и весь алгоритм.
Типа переместить башню высотой n - это как переместить верхние n-1 на временный столбик, переместить нижнюю плиту, переместить n-1 со временного столбика на перемещенную нижнюю плиту. Переместил, замемоизировал, вот и весь алгоритм.
Как-то заумно количество считается. Можно же просто 2**n - 1 подсчитать. Битовым сдвигом вообще за 2 действия будет.
Это уже дальнейшая оптимизация. Все решения работают и достаточно быстры по моей части. Как по твоей - виднее тебе
Ну странно же, если есть явная формула, да еще и считающаяся элементарно, городить рекурсию!
Если ты сразу увидел формулу, поздравляю. Я нет, и привёл первое решение, что попалось на ум.
Не из вредности, а интереса ради: как решишь факториал?
Не из вредности, а интереса ради: как решишь факториал?
У факториала формулы, к сожалению, нет. Так что придется циклом. Правда, если он часть какой-нибудь комбинаторной задачи, где на самом деле нужны сочетания или еще что-то, то там есть варианты.
> кол-во шагов в любом случае будет 2^n и времени и памяти
Кстати, есть и другие задачи, которые так же решаются, хотя на первый взгляд ничего общего.
Например, игра 2048. Если мы не будем заканчивать игру на числе 2048, а продолжим объединять числа и дальше (ну и поле тоже увеличим), то игра реально может стать бесконечной, ибо достижение каждой следующей плитки занимает вдвое больше времени, чем предыдущей. Для плитки 2048 надо минимум 1023 хода (а фактически больше), для 4096 надо 2047 ходов, для 65536 надо 32767 ходов и т.д.
Кстати, есть и другие задачи, которые так же решаются, хотя на первый взгляд ничего общего.
Например, игра 2048. Если мы не будем заканчивать игру на числе 2048, а продолжим объединять числа и дальше (ну и поле тоже увеличим), то игра реально может стать бесконечной, ибо достижение каждой следующей плитки занимает вдвое больше времени, чем предыдущей. Для плитки 2048 надо минимум 1023 хода (а фактически больше), для 4096 надо 2047 ходов, для 65536 надо 32767 ходов и т.д.
Было такое задание в школе в д/з в 7м классе, нагуглил ответы по заданию, налил в код бесполезной воды для объема, вывод сделал просто условием, после ввода количества блинов, если введено 2 - печатать ответ "x", 3 - "y", 4 - "z". Было палево, т.к. никто кроме меня не предоставил работающий код , и мне сказали объяснять свой алгоритм другим.
Тут же крайне простой алгоритм: чётный диск кладётся только на нечётный, а нечётный, соответственно, только на чётный. Ну и, естественно, диск кладётся только на диск меньшего диаметра или пустой стержень.
О, да... Помню, помню.
Дальше уровни все злее.
Чтобы написать коммент, необходимо залогиниться