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