Тут не так слово "только" в определении. Чтобы число было простым, у него не должно быть никаких делителей, кроме единицы и себя. А тут проверили, что число на них делится, а другие делители просто проигнорировали
Идея для книги хорошая и очень полезная для начинающих, но меня немного смущают некоторые фразы.
В этом лабиринте между любыми двумя точками (например, между входом и выходом) есть только один путь. Такие лабиринты могут быть представлены ориентированным ациклическим графом (DAG).
С одной стороны это утверждение верно, однако меня оно очень сильно нервирует. Если в графе есть только один путь между каждой парой вершин, то такой граф называется в первую очередь деревом. Более того, любой лабиринт является неориентированным графом по построению, хотя в ходе решения его и можно преобразовать в ориентированный для удобства. То есть можно сказать что-то на уровне "такой граф является деревом, давайте подвесим его за точку начала и тогда мы можем превратить полученное корневое дерево в ориентированный ациклический граф", но напрямую заключить, что из единственности пути следует, что граф является DAGом - это сильно.
if y + 1 < HEIGHT and maze[y + 1][x] in (EMPTY, EXIT) and \
str(x) + ',' + str(y + 1) not in visited:
# РЕКУРСИВНЫЙ СЛУЧАЙ
if solveMaze(maze, x, y + 1, visited):
return True # БАЗОВЫЙ СЛУЧАЙ
Еще меня немного смущает, что внутри рекурсивного случая откуда-то возник базовый случай. Тут я вполне допускаю, что просто отличается терминология какая-то, однако обычно базовым случаем называется любое состояние рекурсии, из которого не происходит новых рекурсивных вызовов. То есть в данной функции базой рекурсии является условие
if maze[y][x] == EXIT:
return True # Выход найден, возвращаем значение True
А все остальное - это рекурсивные случаи.
И напоследок хочу отметить совершенно ложное утверждение:
Вы можете отредактировать строку лабиринта самостоятельно, однако помните, что алгоритм прохождения лабиринта сработает только при отсутствии в нем замкнутых маршрутов.
Алгоритм, который был реализован выше, вообще говоря называется поиском в глубину. Единственное отличие от классической реализации заключается в том, что тут мы работаем с неявным графом, но от этого по сути ничего не поменялось. Этот алгоритм не имеет никаких требований к графу, так что даже при наличии в графе циклов, он будет работать абсолютно так же, как и для деревьев. Это происходит как раз благодаря списку visited, который содержит все посещенные вершины, чтобы мы не могли зайти в них еще раз. Единственное отличие будет заключаться в том, что среди всех путей на выход алгоритм найдет не кратчайший, а произвольный, но учитывая тот факт, что про длину пути в отрывке не было ни слова, я думаю, это несущественные детали.
Кстати, говоря о visited, не могу не отметить полнейшую неэффективность использования списка в качестве коллекции тут. Нам нужно постоянно проверять элементы на вхождение и гораздо лучше и удобнее использовать тут какое-нибудь множество вместо простого массива. Также я все еще не понимаю, почему в качестве элементов этого списка используется строка, которая вычисляется по численным координатам - гораздо удобнее хранить пару чисел.
В общем идея хорошая, но редактора, который понимает о чем идет речь, стоило бы приставить к этой книжке перед публикацией. В любом случае, как я понял, данная статья является лишь отрывком из книги, которая является переводом с английского, так что не уверен, зачем я вообще расписывал выше ее промашки - очевидно, никто не станет их исправлять, как минимум до следующего издания (и тогда их будут исправлять явно не согласно комментариям с хабра).
Зашел в посты и сразу же увидел пост, в котором продолжение ушло в комментарии. Раз уж началось такое, то может сразу и цепочки постов из твиттера взять?
Я не считаю равноправной, но учитывая, сколько статей пишется за день, никто особо не расстроится, если для написания статьи надо будет сделать еще один клик в выборе формата. Убрать написание постов под тот же карандаш, что и статьи, это действительно хорошая идея, как мне кажется.
А как это так получилось, что в пятой задаче решение за куб внезапно оказалось верным при ограничениях 10^5? Конечно, есть шанс, что магия срезов оптимизировала этот код до квадрата, но даже так оно не должно работать ну никак за адекватное время.
Бинарный поиск тут не сработает. Точнее он не поможет считать быстро. Если мы даже ограничим количество огненных клеток, внутри поиска пути все равно придется хранить в состоянии количество пройденных огненных клеток.
Если честно, я не понимаю, с чем мучился автор статьи в первой задачи. Кто-нибудь может сказать, почему нельзя было просто сделать веса ребер парами? Тогда обычный алгоритм Дейкстры искал бы самый кратчайший путь, а среди таких он бы искал путь с наименьшим количеством огненных клеток. Ну или веса в паре можно перевернуть и тогда он бы искал путь с минимальным количеством огня, а среди таких выбирал бы самый короткий. Я до конца не понял, какой из этих вариантов нужен был автору.
Потому что теорема об обезьянах действительно является доказанной теоремой. Она хоть и схожа с гипотезой о нормальности пи, но все-таки представляет собой совершенно другую вещь.
Я понимаю, о чем вы говорите, но опять же вы просто не желаете принять мою точку зрения во внимание.
Как мне кажется, нужно отличать реальные страницы и их представление в голове. Первые неотделимы от листов и соответственно всегда идут попарно. Вторые являются образом, они интересны только тогда, когда на них что-то есть, и таких страниц вполне может буть нечетное число, ведь последняя пустая страница не несет полезной информации, а значит в нашем представлении книги будет отсутствовать.
Чтобы почувствовать это более точно, можно вспомнить, что мы живем в век цифровых технологий, и книги у нас тоже бывают электронными. Конкретно в моей читалке книга читается не разворотами, а страницами, причем каждая страница соответствует одному листу (экрану). И очевидно, что зачастую у меня в книге получается нечетное количество страниц.
Конечно, данный пример может показаться некорректным в данном обсуждении, так как мы выше говорили о типографии, но я считаю, что он отлично показывает, насколько вольно можно относиться к понятию "страница". А наличие этой вольности говорит, что нужно коммуницировать друг с другом, как минимум для того, чтобы договориться об общей терминологии. В бизнесе отказ без попытки настроить контакт с покупателем - это довольно плохая привычка, которая является серьезным конкурентным недостатком.
Кроме того, не могу не заметить, что в описаниях книг в интернет-магазинах в том числе используется нечетное число страниц (например, https://www.labirint.ru/books/851120/), что говорит о том, что данный факт не является чем-то из ряда вон, а скорее наоборот его можно назвать общественной нормой.
Прочитал половину вашей с автором дискуссии, но так и не понял, почему же нельзя сделать 61 страницу. Это ведь просто разница точек зрения. Меня, как заказчика, волнует только текст, который будет напечатан, и этого текста будет ровно 61 страница. Типографию, в которую я обращаюсь, волнует еще и количество бумаги которое уйдет, это будет 31 или еще немного больше листов. В чем проблема войти в мое положение и просто уточнить, что будет напечатано на одну страницу больше, но последняя страница будет пустой?
Ваш категорический отказ приведет к тому, что я просто уйду в соседнюю типографию, где люди готовы говорить с клиентом.
Так и не понял, по какому именно маршруту идут сборщики после вашей обработки их листа. Просто после каждого предмета жадно идут к ближайшему (с точки зрения вашей "близости") невзятому продукту и берут его?
Но если переменная some_arg имеет, например, тип int (неизменяемый тип), то в функцию передается именно значение переменной, а не ссылка на неё.
def foo(value):
print(id(value))
value += 1
print(id(value))
a = 1000
print(id(a)) # 1588669723440
foo(a) # 1588669723440 1588669722640
print(id(a)) # 1588669723440
Как показывает эксперимент, неизменяемые типы вполне себе передаются по ссылке. Кажется, будто они передаются по значению, потому что они не мутабельны и при изменении внутри функции создается новый объект.
Я просто не понимаю, почему все так боятся вакцинироваться, если не верят в эпидемию. Так же как и от болезни, у меня нет близких, получивших осложнений от прививки, а санкции по отношению к антипрививочникам все растут и растут, поэтому логично просто подчиниться и не париться, разве нет?
Спасибо за создание и анализ конкретной модели — многие вокруг говорят, основываясь на чистых убеждениях и статистике, но мало кто пытается абстрагироваться от реальных данных и изучить ситуацию в вакууме. И отдельное спасибо за мемные «Советы».
Просто ужасная. Во-первых база фраз будет очень небольшая (даже десяти миллионов не набрать), из-за чего роботы ее скопируют вмиг, а во-вторых не все люди учились в нашей русской школе или помнят, что там в ней было. В итоге получаем, что боты будут входить в 99% случаев, а люди возможно даже в меньшем.
Ну так если вам нравятся, то и решайте их на leetcode)
Они созданы, чтобы проверять знание кандидатом базового синтаксиса. Конечно, немного думалка тоже проверяется, но алго-думалка с обычной не совсем коррелирует и даже скорее совсем не коррелирует.
Тут не так слово "только" в определении. Чтобы число было простым, у него не должно быть никаких делителей, кроме единицы и себя. А тут проверили, что число на них делится, а другие делители просто проигнорировали
Пример может и правильный, но фраза совсем некорректная. Перестановка слагаемых - это не ассоциативность, а коммутативность, не стоит путать людей.
Идея для книги хорошая и очень полезная для начинающих, но меня немного смущают некоторые фразы.
С одной стороны это утверждение верно, однако меня оно очень сильно нервирует. Если в графе есть только один путь между каждой парой вершин, то такой граф называется в первую очередь деревом. Более того, любой лабиринт является неориентированным графом по построению, хотя в ходе решения его и можно преобразовать в ориентированный для удобства. То есть можно сказать что-то на уровне "такой граф является деревом, давайте подвесим его за точку начала и тогда мы можем превратить полученное корневое дерево в ориентированный ациклический граф", но напрямую заключить, что из единственности пути следует, что граф является DAGом - это сильно.
Еще меня немного смущает, что внутри рекурсивного случая откуда-то возник базовый случай. Тут я вполне допускаю, что просто отличается терминология какая-то, однако обычно базовым случаем называется любое состояние рекурсии, из которого не происходит новых рекурсивных вызовов. То есть в данной функции базой рекурсии является условие
А все остальное - это рекурсивные случаи.
И напоследок хочу отметить совершенно ложное утверждение:
Алгоритм, который был реализован выше, вообще говоря называется поиском в глубину. Единственное отличие от классической реализации заключается в том, что тут мы работаем с неявным графом, но от этого по сути ничего не поменялось. Этот алгоритм не имеет никаких требований к графу, так что даже при наличии в графе циклов, он будет работать абсолютно так же, как и для деревьев. Это происходит как раз благодаря списку visited, который содержит все посещенные вершины, чтобы мы не могли зайти в них еще раз. Единственное отличие будет заключаться в том, что среди всех путей на выход алгоритм найдет не кратчайший, а произвольный, но учитывая тот факт, что про длину пути в отрывке не было ни слова, я думаю, это несущественные детали.
Кстати, говоря о visited, не могу не отметить полнейшую неэффективность использования списка в качестве коллекции тут. Нам нужно постоянно проверять элементы на вхождение и гораздо лучше и удобнее использовать тут какое-нибудь множество вместо простого массива. Также я все еще не понимаю, почему в качестве элементов этого списка используется строка, которая вычисляется по численным координатам - гораздо удобнее хранить пару чисел.
В общем идея хорошая, но редактора, который понимает о чем идет речь, стоило бы приставить к этой книжке перед публикацией. В любом случае, как я понял, данная статья является лишь отрывком из книги, которая является переводом с английского, так что не уверен, зачем я вообще расписывал выше ее промашки - очевидно, никто не станет их исправлять, как минимум до следующего издания (и тогда их будут исправлять явно не согласно комментариям с хабра).
Зашел в посты и сразу же увидел пост, в котором продолжение ушло в комментарии. Раз уж началось такое, то может сразу и цепочки постов из твиттера взять?
Я не считаю равноправной, но учитывая, сколько статей пишется за день, никто особо не расстроится, если для написания статьи надо будет сделать еще один клик в выборе формата. Убрать написание постов под тот же карандаш, что и статьи, это действительно хорошая идея, как мне кажется.
А как это так получилось, что в пятой задаче решение за куб внезапно оказалось верным при ограничениях 10^5? Конечно, есть шанс, что магия срезов оптимизировала этот код до квадрата, но даже так оно не должно работать ну никак за адекватное время.
Бинарный поиск тут не сработает. Точнее он не поможет считать быстро. Если мы даже ограничим количество огненных клеток, внутри поиска пути все равно придется хранить в состоянии количество пройденных огненных клеток.
Если честно, я не понимаю, с чем мучился автор статьи в первой задачи. Кто-нибудь может сказать, почему нельзя было просто сделать веса ребер парами? Тогда обычный алгоритм Дейкстры искал бы самый кратчайший путь, а среди таких он бы искал путь с наименьшим количеством огненных клеток. Ну или веса в паре можно перевернуть и тогда он бы искал путь с минимальным количеством огня, а среди таких выбирал бы самый короткий. Я до конца не понял, какой из этих вариантов нужен был автору.
Потому что теорема об обезьянах действительно является доказанной теоремой. Она хоть и схожа с гипотезой о нормальности пи, но все-таки представляет собой совершенно другую вещь.
Теперь вашу позицию понял, спасибо за пояснение.
Я понимаю, о чем вы говорите, но опять же вы просто не желаете принять мою точку зрения во внимание.
Как мне кажется, нужно отличать реальные страницы и их представление в голове. Первые неотделимы от листов и соответственно всегда идут попарно. Вторые являются образом, они интересны только тогда, когда на них что-то есть, и таких страниц вполне может буть нечетное число, ведь последняя пустая страница не несет полезной информации, а значит в нашем представлении книги будет отсутствовать.
Чтобы почувствовать это более точно, можно вспомнить, что мы живем в век цифровых технологий, и книги у нас тоже бывают электронными. Конкретно в моей читалке книга читается не разворотами, а страницами, причем каждая страница соответствует одному листу (экрану). И очевидно, что зачастую у меня в книге получается нечетное количество страниц.
Конечно, данный пример может показаться некорректным в данном обсуждении, так как мы выше говорили о типографии, но я считаю, что он отлично показывает, насколько вольно можно относиться к понятию "страница". А наличие этой вольности говорит, что нужно коммуницировать друг с другом, как минимум для того, чтобы договориться об общей терминологии. В бизнесе отказ без попытки настроить контакт с покупателем - это довольно плохая привычка, которая является серьезным конкурентным недостатком.
Кроме того, не могу не заметить, что в описаниях книг в интернет-магазинах в том числе используется нечетное число страниц (например, https://www.labirint.ru/books/851120/), что говорит о том, что данный факт не является чем-то из ряда вон, а скорее наоборот его можно назвать общественной нормой.
Прочитал половину вашей с автором дискуссии, но так и не понял, почему же нельзя сделать 61 страницу. Это ведь просто разница точек зрения. Меня, как заказчика, волнует только текст, который будет напечатан, и этого текста будет ровно 61 страница. Типографию, в которую я обращаюсь, волнует еще и количество бумаги которое уйдет, это будет 31 или еще немного больше листов. В чем проблема войти в мое положение и просто уточнить, что будет напечатано на одну страницу больше, но последняя страница будет пустой?
Ваш категорический отказ приведет к тому, что я просто уйду в соседнюю типографию, где люди готовы говорить с клиентом.
Так и не понял, по какому именно маршруту идут сборщики после вашей обработки их листа. Просто после каждого предмета жадно идут к ближайшему (с точки зрения вашей "близости") невзятому продукту и берут его?
Как показывает эксперимент, неизменяемые типы вполне себе передаются по ссылке. Кажется, будто они передаются по значению, потому что они не мутабельны и при изменении внутри функции создается новый объект.
Блин, а что за игра-то?
Они созданы, чтобы проверять знание кандидатом базового синтаксиса. Конечно, немного думалка тоже проверяется, но алго-думалка с обычной не совсем коррелирует и даже скорее совсем не коррелирует.