Функция для словаря, которая возвращает наибольший ключ - int

@way2thesky · Регистрация: 12.02.2021

Студворк — интернет-сервис помощи студентам

Здравствуйте, я только начинаю изучать Python и столкнулся с вот такой сложно для меня задачей:

Написать функцию которая в качестве аргумента принимает словарь, в котором в качестве ключей — числа int, а в качестве значений — либо словарь, с такой же структурой, либо None. Функция должна вернуть максимально большое число находящееся в этой структуре на произвольной глубине.

Напишите два решения этой задачи - одно с использованием рекурсии, другое - без использования рекурсии

я написал, но это какая то бессмыслица

Python
1
2
3
4
5
6
7
8
def max_key_in_dict(a):
    keys = []
    for i in a:
         if a[i] is not None:
            keys.append(max_key_in_dict(a[i]))
    else:
        keys.append(i)
        return max(keys)

@Viktorrus · 13.03.2021, 22:42

Сообщение от Catstail

dfs использует стек. Очередь использует bfs.

Я не в курсе этих обозначений. Просто у питона внутренний механизм рекурсии использует стек. Питон сохраняет промежуточные состояния функции в стеке, и возвращает эти состояния в обратном порядке при раскручивании рекурсии назад. Этот механизм можно создать вручную с помощью стека. Это будет аналог механизма рекурсии, который использует питон, но будет работать медленнее, чем встроенная рекурсия питона. Но возится с этим у меня нет никакого желания.
P.S. Стек это тоже очередь, но которая работает по принципу, "последний пришел, первый ушел".

@Arsegg · 14.03.2021, 07:21

Сообщение от Catstail

- dfs использует стек.

Верное замечание.

Что-то вроде:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def maxKeyRecursive(dict_):
    max_ = max(dict_.keys())
    for value in dict_.values():
        if value is not None and (result := maxKeyRecursive(value)) > max_:
            max_ = result
    return max_
    
def maxKeyIterative(dict_):
    max_ = max(dict_.keys())
    stack = [dict_]
    while stack:
        current = stack.pop()
        if current is None:
            continue
        if (result := max(current.keys())) > max_:
            max_ = result
        stack.extend(current.values())
    return max_
    
d = {2:{3:{5:{7:{12:{27 : {45 : {2:{3:{5:{7:{12:{27 : {145 : None}}}}}}}}}}}}},
     3:{3:{5:{7:{12:{27 : {45 : {2:{3:{5:{7:{12:{27 : {245 : None}}}}}}}}}}}}},
     5:{3:{5:{7:{12:{27 : {445 : {2:{3:{5:{7:{12:{27 : {45 : None}}}}}}}}}}}}}}
assert maxKeyRecursive(d) == 445
assert maxKeyIterative(d) == 445

/upd

Не по теме:

Сообщение от Viktorrus

Стек это тоже очередь

Даже близко не очередь. Кипу книг вы тоже считаете очередью?

@AlexMarkov · 14.03.2021, 08:00

Сообщение от Viktorrus

Ваш пример не соответствует условию. У Вас в качестве значений встречаются строки, что по условию не должно быть. В качестве значений могут быть только словари или None.

Не согласен.
"в котором в качестве ключей — числа int, а в качестве значений — либо словарь, с такой же структурой, либо None."
Словарь с такой же структурой без указания крайнего значения. В моем случае - крайнее значение строка.

Сообщение от way2thesky

к сожалению ни одно из выше указанных примеров, не верны, на 10 из 100

Медвежья услуга, возьмите учебник по алгоритмам и прочитайте, что такое обход в глубину(dfs). Решайте сами - так смысла нет.

@Viktorrus · 14.03.2021, 11:45

Не по теме:

Сообщение от Arsegg

Кипу книг вы тоже считаете очередью?

Кипа книг не упорядочена. Поэтому она не очередь. А вот стек упорядочен. Любая последовательность является очередью. Но очередь стека, в отличие от обычной очереди, где, кто первый пришел, тот первым и ушел, использует правило, "кто последний пришел, тот первым ушел". И при этом такой обратный порядок очереди не нарушается. Любая очередь отличается именно порядком.
Но замечу, что вести дискуссию можно только если определения понятий обоих сторон совпадают. В противном случае это не дискуссия, а базар.
В моем понятии очередь это упорядоченная последовательность, в которой определено кто участвует (в чем либо) первый и кто стоит за кем. В очереди по умолчанию, тот кто стоит на первой позиции (первый пришел) тот и используется первым (первым ушел). В очереди в виде стека кто стоит последним (последний пришел) тот первым используется (первый ушел). При этом соблюдается последовательность, кто за кем стоит.
https://ru.wikipedia.org/wiki/... 0%B4%D1%8C
"Очередь — определённый порядок в следовании или в движении чего-либо или кого-либо. "
https://ru.wikipedia.org/wiki/... 0%B5%D0%BA
Для Вас очередь, это более узкое понятие, где кроме упорядочения, так же используется принцип "первый пришел, первый ушел".
Для меня очередь не принимает во внимание, кто первым пришел. Важно кто в какой последовательности уходит.
Например существует очередь поступления патронов в затвор автомата из магазина. Там патрон который был вставлен последним в магазин, используется первым. То есть действует принцип стека. При этом патроны в магазине используются в порядке очереди.
В общем Вы можете считать стек не очередью, а я считаю очередью, так как объекты из стека используются в строгой очередности.
Так как наши определения очереди не совпадают, то вести дальнейшую дискуссию не имеет смысла. Каждый остается при своем мнении.
Удачи.:)

@eaa · 14.03.2021, 11:54

значит я правильно решил?! а то по примерам что то не проходило и удалил.

Python
1
2
3
4
5
6
7
8
9
from math import inf
def max_dict_key(dct):
    res = -inf
    for k, v in dct.items():
        if type(v) == dict:
            res = max(max_dict_key(v), k)
        else:
            res = max(res, k)
    return res

какие входные данные?

@Viktorrus · 14.03.2021, 11:56

Сообщение от AlexMarkov

Словарь с такой же структурой без указания крайнего значения.

Понятие крайнего значения, это расплывчатое понятие, если оно четко не описано. В условии нет описания крайних значений, поэтому для меня слова

Сообщение от way2thesky

с такой же структурой,

воспринимаются как

Сообщение от way2thesky

либо словарь,

Сообщение от way2thesky

либо None

Но коль уж пошли такие дискуссии об условии задачи, то из этого можно сделать вывод, что условие задачи не достаточно четкое.

@AlexMarkov · 14.03.2021, 13:40

Сообщение от Viktorrus

P.S. Стек это тоже очередь, но которая работает по принципу, "последний пришел, первый ушел"

На днях повторно смотрел лекции, там так же Стек называют очередью LIFO.

@Viktorrus · 14.03.2021, 23:00

Сообщение от AlexMarkov

На днях повторно смотрел лекции, там так же Стек называют очередью LIFO.

Я понял, почему возникают разные мнения о стеке. Дело в том, что если очередь "первый пришел, первый ушел" всегда остается очередью. А вот стек может себя вести как очередь состаящая из двух очередей разнесенных по времени. Это очередь заполнения стека и очередь выхода элементов из стека. Но стек может и не являться очередью, когда заполнение стека и выход элементов из стека совмещены по времени. В этом случае нарушается последовательность (очередь) выхода из стека.
Но если рассматривать стек рекурсии в питоне, то заполнение стека при рекурсии и забор элементов из стека разнесены по времени. И поэтому элементы из стека возвращаются поочередно в соответствии с их очередью в стеке но в обратном порядке в отличие от заполнения. Отсюда можно говорить о стеке при рекурсии питона как об очереди. Если бы эта очередь нарушалась, то рекурсия не работала бы.

@AlexMarkov · 16.03.2021, 19:01

Сообщение от Viktorrus

P.S. Стек это тоже очередь, но которая работает по принципу, "последний пришел, первый ушел".

Сообщение от Arsegg

Даже близко не очередь. Кипу книг вы тоже считаете очередью?

Меня заинтересовала Ваша дискуссия относительно терминологии структур данных, а именно, о стеках и очередях. Вооружившись первым томиком «Искусства программирования» Дональда Кнута и пониманием того, что настоящий программист работает не с кодом, а со структурами данных, решил посмотреть, что думает автор в своей фундаментальной монографии с его гипотетическим компьютером «MIX-ассемблер». В главе 2 автор называет структуры данных информационными структурами, одна из частей главы так и называется «стеки, очереди и деки».
Думаю, оригинальный текст физико-математической монографии признанной в 1999 году одной из лучших монографий мира будет более авторитетным, чем таблицы памяти моей

Стеки и очереди автор называет линейными списками, в которых операции вставки, удаления и доступа к значениям чаще всего выполняются в первом или последнем узле.

“““
...текст с определением линейных списков и списком возможных операций…
Стек — это линейный список, в котором все операции вставки и удаления ( и, как правило, операции доступа к данным) выполняются только на одном из концов списка.
Очередь или односторонняя очередь — это линейный список, в котором все операции вставки выполняются на одном из концов списка, а все операции удаления (и, как правило, операции доступа к данным) — на другом.
….текст с определением деков…
МНЕНИЕ АВТОРА ИЛИ РЕДАКТОРА!!!(ОРИГИНАЛЬНЫЙ ТЕКСТ НЕ НАШЕЛ)
В некоторых дисциплинах слово «очередь» используется в более широком смысле, например, при описании любого типа списка, для которого выполняются операции вставки и удаления. Тогда упомянутые выше особые случаи следует характеризовать как разные «правила упорядочения» (или «очередности обслуживания»). В этой книге термин «очередь» предполагается использовать только в узком смысле, по аналогии с обычной упорядоченной очередью людей, ожидающих обслуживания.
...текст с описанием модели работы стека
Многие исследователи независимо пришли к выводу о важности стеков и очередей, а потому присвоили им иные собственные имена. Так, стеки часто называют магазинными списками (push-down lists), реверсивными хранилищами (reversion storages), магазинами (cellars), вложенными хранилищами (nesting stores), кучами(piles), дисциплинами обслуживния в обратном порядке (last-in-first-out lists-LIFO lists) и даже флюгерными списками (yo-yo lists). Очереди часто называют циклическими хранилищами (circular stores) или дисциплинами обслуживания в порядке поступления (first-in-first-out lists — FIFO lists). Термины «LIFO» и «FIFO» многие годы употреблялись бухгалтерами для обозначения метода оценки и продажи товаров. ….
““

и так далее если Вам интересно можете прочитать главу 2 Том 1...
Важен или нет, данный вопрос? Решать Вам, Платон говорил, что ошибки начинаются с неправильных понятий, Аристотель, что с неправильных суждений. Искусство программирования это еще и правильная структуризация собственных мыслей в процессе выполнения поставленной задачи. Так как мой возраст не позволяет идти методом индукции в данной предметной области, развитие современных информационных систем получило свое начало еще с середины прошлого века. В своем размышлении на языке Python могу идти только от общего к частному.
«Реальная» реализация стека и очереди получили свою истинную суть только на первых этапах развития компьютерных и других логико-математических систем и моделей. В настоящее время мы пользуемся в основном абстрагированными типами данных или структурами данных с дополнительным слоем абстракции над другой абстракцией.
На данном этапе развития и в дальнейшей работе, скорее всего, что бы мы не называли стеком или очередью, все определения или будут верны в общем понимании смысла этого слова или не верны в контексте выполняемой задачи.
Не много переформулирую представленную цитату из книги: «Программируйте не думайте ...»

@Arsegg · 16.03.2021, 20:02

Не по теме:

AlexMarkov, несколько раз перечитал ваш пост - не понял смысла сего опуса, но интересно.

По теме: есть такая алгоритмическая задача, как реализовать очередь на 2 стеках, что push(value) и pop() работали в среднем за O(1). Реализацию можно глянуть тут. Если бы стек был бы очередью, то какой смысл реализовывать очередь на очереди? Где логика?
P. S. Стек и очередь - совершенно разные структуры данных. К ним неприменимо отношение is-a. Да, одну из них можно реализовать на основе другой, но не более того.
/upd

Не по теме:

Понимаю еще назвать дек очередью (двусторонней), но блин стек называть очередью - это просто кощунство.

@Viktorrus · 17.03.2021, 00:18

Не по теме:

Вы так и не поняли, что процесс может менять свою организацию (алгоритм) во временном интервале. При рекурсии в питоне заполнение стека ничем не отличается от заполнения обычной очереди. И первый элемент у стека будет первым элементом у обычной очереди. Однако в отличие от обычной очереди при извлечении элементов алгоритм у стека меняется и он превращается в очередь первым элементом которой становится последний пришедший элемент. И освобождается стек в рекурсии у питона строго по очереди. Если бы извлечение из стека было с нарушением очередности, то рекурсия приводила бы к ошибочному результату. А то о чем вы говорите, это использование стека в процессах, где чередуются поступления в стек и извлечения из стека. В таком стеке не существует очереди. Хотя если применить дифференциал, то в каждый момент времени (во временной точке) существуют две относящиеся к этой временной точке очереди, которые в следующий момент времени могут изменится или нет. Это аналогично прямой на плоскости. Прямая линия имеет постоянный угол наклона к оси. Кривая непрерывная линия имеет также угол наклона в каждой точке, но этот угол постоянно меняется и вычисляется в каждой точке производной. Однако если мы возьмем ломанную кривую, состоящую из двух прямолинейных отрезков, то получим два участка, у которых будут разные углы наклона, но каждый из двух кусков этой ломанной является прямым отрезком. Стек в рекурсии питона ведет себя аналогично, он сохраняет структуру одной очереди при заполнении и структуру другой очереди при извлечении. Этим такой стек отличается от стека хаотично получающего элементы и хаотично их извлекая. Там можно говорить только о хаотично возникающих очередях привязанных к конкретным моментам времени.
Это как разница между школьной математикой и высшей математикой в институте, где изучают матанализ.
Так, все, надо взять себя в руки и на этом закончить.
Всем удачи.:)

@Arsegg · 17.03.2021, 10:02

Не по теме:

Viktorrus, прочтите, пожалуйста, курс по алгоритмам, например, хоть "Грокаем алгоритмы" Бхаргавы. Очень больно читать ваши умозаключения. Просто есть общепризнанные определения и понятия. Если каждый будет говорить на своем языке: получится как с Вавилонской башней...
P. S. Вы сильно путаете начинающих, которые без критического осмысления, возьмут ваши идеи на вооружение.

@Viktorrus · 17.03.2021, 12:42

Не по теме:

Сообщение от Arsegg

прочтите, пожалуйста, курс по алгоритмам, например, хоть "Грокаем алгоритмы" Бхаргавы.

Что же такое, когда это закончится? Я прочту только после того, как Вы прочтете трактат Бурбаки по основам математики, хотя бы первую книгу, "Теория множеств", и потом расскажите, что Вы оттуда поняли.:) Так как все алгоритмы строятся на математических моделях. А в этом трактате в первой части "Метаматематика" формируются математические понятия с нуля.
Тогда и поговорим.:)
Всем другим, кто это читает, хочу предупредить, Если я не буду больше отвечать, это не значит что я признаю , что я неправ, а просто считаю, что пытаться что то объяснить, когда тебя не понимают, теряет смысл.
А объяснять работу с питоном , тем кому мое мнение интересно, я буду продолжать. Благо у меня есть опыт преподавания в школе математики и в институте информатики.

@AlexMarkov · 17.03.2021, 20:13

Сообщение от Viktorrus

Вы так и не поняли, что процесс может менять свою организацию (алгоритм) во временном интервале.

А почему Вы так решили, ваша мысль ясна.

Сообщение от Arsegg

прочтите, пожалуйста, курс по алгоритмам, например, хоть "Грокаем алгоритмы" Бхаргавы

После Бхарвы посоветовал бы прочитать материал из данной книги, много интересного об эффективности применяемых алгоритмов,
асимптотиках, разъясняется, что же все таки такое О большое, наихудшие, наилучшие и средние случаи:
Хайнеман, Джордж, Пояяис, Гэри, Сеяков, Стэнли.Алгоритмы. Справочник с примерами на С, C++, Java и Python.

Сообщение от Arsegg

Если каждый будет говорить на своем языке: получится как с Вавилонской башней...

Ха, припомнилась одна фраза приписываемая Гете: Математики как французы всё, что вы им говорите, они переводят на свой язык,
и это тотчас же становится чем-то совершенно иным. На самом деле, каждый математик другому математику точно такой же француз.

Сообщение от Viktorrus

Всем другим, кто это читает, хочу предупредить, Если я не буду больше отвечать, это не значит что я признаю , что я неправ, а просто считаю, что пытаться что то объяснить, когда тебя не понимают, теряет смысл.
А объяснять работу с питоном , тем кому мое мнение интересно, я буду продолжать. Благо у меня есть опыт преподавания в школе математики и в институте информатики.

Я не математик ну было очень интересно... узнать о структурах данных применяемых при рекурсии в языке Python...

А вот мысль заголовка "Не по теме" мне не ясна...все по теме, решение любой задачи требует соответствующих умозаключений.

@Arsegg · 17.03.2021, 20:25

Не по теме:

Сообщение от AlexMarkov

А вот мысль заголовка "Не по теме" мне не ясна...

Беседа давно себя исчерпала. Начиналась с dfs рекурсивной и итеративной версий, закончилась ~~за упокой~~ очередями. Хотя тут очереди вообще не к месту, т. к. в dfs используется стек - тут уже не важно, явно или не явно (стек вызовов функций). Ясное дело, что вопрос очередей - совсем не относится к обсуждаемому предмету.

Новые блоги и статьи Все статьи Все блоги /
интеграция AnyLogic с самописным REST API и переход на Odoo anaschu 03.07.2026 Успешная интеграция AnyLogic с самописным REST API и переход на промышленную Odoo WMS Сегодня проделал огромный путь от простой симуляции физических процессов до построения полноценной. . .	Поиск всех путей на ориентированном графе. Linux dcc0 02.07.2026 Переработка старого кода из моей статьи. Через несколько переработок от PHP кода к C89 (надеюсь, 89). Но довольно запутанно получилось. Код для Linux. Но если убрать time и то, что с ним. . .	Сам себя обучал rest api anaschu 02.07.2026 Педагогический лайфхак: Почему чистый REST API для ученика намного круче, чем готовые библиотеки Когда мы отказались от капризного JAR-файла AnyLogic и переписали код на стандартный HttpClient,. . .	rest api anylogic - выполнение модели на своём русском сайте anaschu 02.07.2026 Как подружиться с AnyLogic Cloud API, победить провайдеров и развернуться Java-бэкенд в Docker на бесплатном хостинге: Двухдневный лог борьбы Всем привет! Хочу поделиться свежим (и довольно. . .
Где деньги лежат kumehtar 02.07.2026 Это - японская подводная лодка I-52 (тип C2, кодовое имя Momi) вышла из Японии в марте 1944 года с миссией в оккупированную немцами Францию (Лорьян). Это была одна из «Янаги»-миссий по обмену. . .	Krabik для WoW 3.3.5a, многоязычный AmbA 02.07.2026 Допилил бота, думаю что окончательно. Изменения: - добавлена многоязычность - добавлено снятие скриншотов - добавлено поддержание бафов хождения по воде (для жреца, дк и шамана) - и так, по. . .	Алиса нашла кучу ошибок компиляции и запуска в проекте, который без проблем компилировался и запускался))) anaschu 30.06.2026 Я пока посмеюся, но завтра проверю. А вообще интерсно. Дал алисе файл, в котором точно нет ошибок компиляции и запуска, и попросил их найти. Нашла кучу))) Критические ошибки, мешающие компиляции и. . .	сукцессия 16. Общий обзор, в основном что бы другие ии поняли anaschu 29.06.2026 # Передаточный документ: модель микоризной сукцессии (для нового чата) Этот документ предназначен для того, чтобы новый чат Claude мог продолжить работу без необходимости заново разбираться в. . .

@Arsegg 3582 / 2182 / 571 Регистрация: 02.09.2015 Сообщений: 5,510
	16.03.2021, 20:02
	Не по теме: AlexMarkov, несколько раз перечитал ваш пост - не понял смысла сего опуса, но интересно. По теме: есть такая алгоритмическая задача, как реализовать очередь на 2 стеках, что `push(value)` и `pop()` работали в среднем за O(1). Реализацию можно глянуть тут. Если бы стек был бы очередью, то какой смысл реализовывать очередь на очереди? Где логика? P. S. Стек и очередь - совершенно разные структуры данных. К ним неприменимо отношение `is-a`. Да, одну из них можно реализовать на основе другой, но не более того. /upd Не по теме: Понимаю еще назвать дек очередью (двусторонней), но блин стек называть очередью - это просто кощунство. 1

@Viktorrus
	17.03.2021, 00:18
	Не по теме: Вы так и не поняли, что процесс может менять свою организацию (алгоритм) во временном интервале. При рекурсии в питоне заполнение стека ничем не отличается от заполнения обычной очереди. И первый элемент у стека будет первым элементом у обычной очереди. Однако в отличие от обычной очереди при извлечении элементов алгоритм у стека меняется и он превращается в очередь первым элементом которой становится последний пришедший элемент. И освобождается стек в рекурсии у питона строго по очереди. Если бы извлечение из стека было с нарушением очередности, то рекурсия приводила бы к ошибочному результату. А то о чем вы говорите, это использование стека в процессах, где чередуются поступления в стек и извлечения из стека. В таком стеке не существует очереди. Хотя если применить дифференциал, то в каждый момент времени (во временной точке) существуют две относящиеся к этой временной точке очереди, которые в следующий момент времени могут изменится или нет. Это аналогично прямой на плоскости. Прямая линия имеет постоянный угол наклона к оси. Кривая непрерывная линия имеет также угол наклона в каждой точке, но этот угол постоянно меняется и вычисляется в каждой точке производной. Однако если мы возьмем ломанную кривую, состоящую из двух прямолинейных отрезков, то получим два участка, у которых будут разные углы наклона, но каждый из двух кусков этой ломанной является прямым отрезком. Стек в рекурсии питона ведет себя аналогично, он сохраняет структуру одной очереди при заполнении и структуру другой очереди при извлечении. Этим такой стек отличается от стека хаотично получающего элементы и хаотично их извлекая. Там можно говорить только о хаотично возникающих очередях привязанных к конкретным моментам времени. Это как разница между школьной математикой и высшей математикой в институте, где изучают матанализ. Так, все, надо взять себя в руки и на этом закончить. Всем удачи.:) 0

@Arsegg
	17.03.2021, 10:02
	Не по теме: Viktorrus, прочтите, пожалуйста, курс по алгоритмам, например, хоть "Грокаем алгоритмы" Бхаргавы. Очень больно читать ваши умозаключения. Просто есть общепризнанные определения и понятия. Если каждый будет говорить на своем языке: получится как с Вавилонской башней... P. S. Вы сильно путаете начинающих, которые без критического осмысления, возьмут ваши идеи на вооружение. 0