Последний комментарий на тему for (i = 0; i < n; ++i) O(n)
Все до этого - это именно последовательные алгоритмы. Там берется количество операций в первом, во втором и складываются.
Drak Lowell, Очень непонятно написано условие. Уточните, пожалуйста.
"путь, который обойдет каждый граф единижны" - У вас что, несколько графов? Вроде как у вас один граф и в нем важные вершины. Вам надо пройтись по всем waypoint вершинам? Конечная точка не важна, но есть ли фиксированная начальная точка?
Waypoint-ы можно обходить в любом порядке? Можно ли заходить в waypoint несколько раз (допустим, кратчайший путь из B в C лежит уже через обойденную A)? Может ли путь заходить в уже обойденные не waypoint-ы (просто вершины графа)? Насколько у вас большой граф, сколько в нем может быть waypoint-ов?
Для начала нужно определиться - окружность должна точно проходить через точки? Или, как на картинке, точки зашумлены?
Во втором случае возникает вопрос, а какая окружность будет для вас наилучшим приближением. Можно вводить разыне метрики ошибки. Например сумма квадратов разностей квадратов расстояний от центра до точек и квадрата радиуса. Или можно минимизировать максимальный такой квадрат разности.
Играясь с метрикой можно получить более простую или сложную задачу, но ответ может быть разным. Особенно в крайних случаях. Например. если почти все точки лежат на очень маленькой окружности, а одна точка где-то далеко-далеко. Одно решение будет взять окружность через все кроме одной далекой точки. Тут сумма квадратов ошибок будет маленькой. Другое решение будет окружностью, проходящей через центр мелкой окружности и дальнюю точку. Тут максимальная ошибка будет меньше.
beduin01, Вот вам надо понять, как эта лента из структуры получается. Потом взять именно этот код и вместо wirte() сделать там read(). Все.
Судя по тому, что у вас в примере "number" идут подряд, то у вас что-то вроде обхода в ширину, но это нелогичный обход для такой древовидной структуры данных. У вас в примере точно нет опечатки? Если там на самом деле в массиве идет "name", "number", "name", "number", то тогда это обход в глубину и все не так сложно.
По первому вопросу: s[i] - это i-ый символ в строке (считая с 0).
Сравнения там делаются чтобы отделить цифры от букв и от скобок. Вы у себя сморите, что символ один из numers, но можно это сделать сравнениями '0'<=s[i] and s[i] <= '9'. Сравнение строк же происходит посимвольно. Это не идеальный способ в питоне, возможно есть более корректный метод, я не питонист.
ord(s[i]) - ord('0') - должно выдвавть численное значение цифры. Для '7' - должно вернуть 7. Пользуется тем, что цифры идут в алфавите подряд с 0 до 9.
Важно отментить, что мой пример решения не работает с юникодом, а только c ascii текстом. Можно изменить так, чтобы работало не только с английским алфавитом. Для этого надо выделать в тексте только цифры и скобки, а все остальное считать текстом. Т.е. заменить проверку на то, чот символ от 'a' до 'z' проверкой что символ не цифра и не скобка.
Зато мое решение, в отличие от вашего, работает с многозначными числами и "123a" распакует именно как 123 копии "a", а не 1 копию "2" и 3 копии "a".
> Даже мастер-пароли могут украсть во время их ввода и обработки.
Ровно так же можно утащить те самые пароли, которые в этом вопросе и хочется хранить. Таким образом, мастер пароль облегчает жизнь пользователям не создавая дополнительных векторов атак.
Если пользователь расскажет свои пароли кому-то, то это не ваша проблема. Если пароли из вашего приложения утекли, потому что пользователь сидит под админом, то на хабре будет статья "приложение X взломали".
Какой изврат. Любое решение этой задачи будет так или иначе работать с графом. Возможно неявно.
Вы не называйте граф - графом, и будет без графов)
Один хешмап будет по пользователю выдававть список емейлов. Второй - по емейлу список пользователей. Третий - по пользователю или емейлу выдавать выведен ли этот пользователь уже или нет.
Заполните мапы, потом пройдитесь по всем пользователем, и если он еще не выведен, пишите в ответ его логин и запускайте рекурсивную функцию GetAllMails(user). Она первым делом помечает пользователя как выведенного, проходится по списку его имейлов, и если они еще не выведены, выводит их и помечает выведенными. Для каждого добавленного имейла надо вложенным циклом пройтись по списку пользователей. Если пользователь еще не выведен - запуститься рекурсивно.
Фактически, это обход в глубину на двудольном графе, но выглядит, что вы берете всех пользователей с тем же мылом и выводите все их имейлы и берете всех пользователей с такими же имейлами и выводите все их остальные емейлы, и так по кругу, пока все не соберете.
Тут видно, что работает за линейную сложность - GetAllMails может запуститься только один раз от каждого пользователя. Внутри оно один раз проходит список его емейлов. Для каждого емейла ровно один раз, при выводе, будет пройден список всех пользователей с таким мылом.
Андрей Шалыгин, Прям вам в условии и сказано, что должно быть 2 hashmap'a? Если так надо, вы можете использовать их для храниния ребер в графе - для каждого пользоватля выдавать список емейлов и наоборот. Еще нужно будет как-то хранить пометки обойденных вершин. Это еще один хешмап. Если нужно ровно 2 - то один для ребер, второй для пометок.
Единственное решение за линию у этой задачи - это какой-то обход графа, как я вам уже описал.
for (i = 0; i < n; ++i) O(n)Все до этого - это именно последовательные алгоритмы. Там берется количество операций в первом, во втором и складываются.