Царям

Задача интересна, но времени у меня сейчас нет, а что это за практическая задача? Да, про деревья подробнее можно? Двоичные деревья тоже разные бывают.

брутфорсом )

А не слишком ли много деревьев даже для маленьких n чтобы решить задачу практически на существующем железе? Или дело в том, что они очень разреженные?

Просто хочу природу понять и масштабы этих чисел. На какие n рассчитывать с практической точки зрения? У деревьев есть особенности, они не спроста такие разреженные?

в каждом листе — плюс бесконечность.

Т.е. элементы в дереве у тебя никак полезно не упорядочнены и приплёл его сюда ради красного словца? Обычный поиск перебором, линейно от кол-ва всех узлов.

n от четырех до, скажем, тридцати. В деревьях может быть много нулей. Есть процедура последовательной генерации каждого дерева.

приплел его сюда ради красного словца

Как минимум тут возможен перебор с возвратом.

что это за практическая задача

Связана с расположением ректификационных колонн

про деревья подробнее

Это все, что известно о деревьях.

в каждом листе — плюс бесконечность

Эм, дерево не отсортировано?

Как минимум тут возможен перебор с возвратом

в твоей постановке невозможен.

peregrine, vertexua, mashina

Прошу прощения, есть уточнение. Каждое поддерево с корнем равным корню данного дерева есть встречается как корневое поддерево еще в как минимум (n - m - 1)! деревьях.

То есть имеются деревья с одинаковыми префиксами с точностью до вершин, предшествующих листьям.

Нет

Мы можем не перебирать все вершины дерева, если одна из них меньше известного максимума.

Мы можем не перебирать все вершины дерева, если одна из них меньше известного максимума.

у тебя дерево это просто неупорядочненное мн-во, не можешь так делать.

Ну вот кто так дает задачу?

Во-первых, терминология.

высота каждого дерева n-2, каждое дерево имеет n-1 вершин и n листьев.

лист - вершина без потомков. Вершин не может быть меньше, чем листьев.

Во-вторых, в формулировке много ненужного хлама.

Нужно было сказать проще: есть (n-2)! списка по n-1 число, найти список с наибольшим минимальным числом.

Можем. Если в первом дереве минимум, скажем, 5, а во втором мы встретили 4, то второе дерево можно уже не просматривать.

Пока такие рассуждения.

Чтобы найти минимальный элемент дерева, надо просмотреть все его вершины. Иначе никак, раз нам не заданы никакие ограничения на деревья. Размер дерева небольшой, пофиг как обходить, хоть рекурсией, хоть имитацией, хоть в ширину.

Чтобы найти максимальный элемент среди всех деревьев, надо, без отсутствия дополнительных ограничений опять же, перебрать все деревья. Ибо иначе никак. Собственно запоминать нам нужно только найденный максимум на текущий момент, поэтому берём очередное дерево, ищем в нём минимум, если в процессе поиска минимума наткнулись на число, меньшее текущего максимума среди минимумов, сразу отбрасываем это дерево и приступаем к следующему. Если не наткнулись, значит нашли новый максимум, запоминаем и опять же двигаемся дальше.

И короче никак не сделаешь.

Уточнение прочитал, но пока не понимаю, чем оно может помочь. По-моему ничем, но надо ещё подумать.

Вершин не может быть меньше, чем листьев.

Ещё как может. Его дерево это ~ связанный список.

Можем. Если в первом дереве минимум, скажем, 5, а во втором мы встретили 4, то второе дерево можно уже не просматривать.

Ты сейчас взял и дополнил его дерево какими-то своими любимыми свойствами которых в условии нет.

научишься формулировать задачи - вернись, мы всё простим :-)

---

с хрена там деревья, какие деревья, сбалансированы/нет, почему у них в листьях +бесконечность, откуда она там взялась, максимум среди каких элементов нужен? среди рядовых узлов чтоли, тех которые не корень, не лист, а не пойми что? что у вас является «минимальным элементом(ами)» дерева, если в листьях бесконечнсть..

---

я так думаю, что ответ : «коммунизм минус пол.электрофикации»

Ещё как может. Его дерево это ~ связанный список.

Не может. Каждый лист - вершина. Множество листьев - подмножество множества вершин.

Ты сейчас взял и дополнил его дерево какими-то своими любимыми свойствами которых в условии нет.

Да ничего не дополнял. Давай так, у тебя есть два множества A и B. Тебе нужно найти max{min A, min B}. Пусть, ты вычислил min A и нашел какой-то элемент b из множества B такой, что b < min A. Тогда дальше множество B ты можешь не просматривать. max{min A, min B} = min A

с хрена там деревья

Потому что она так поставлена.

сбалансированы/нет

Нет

почему у них в листьях +бесконечность, откуда она там взялась

Потому что это такое свойство этих деревьев

максимум среди каких элементов нужен

Максимум среди минимумов по каждому дереву. Минимум ищется среди всех узлов дерева. В вершинах тоже есть числа.

что у вас является «минимальным элементом(ами)» дерева, если в листьях бесконечнсть

Читай чуть выше.

лист - вершина без потомков

Ну да, n-1 ветвлений и n листьев

списка

Чуть выше есть уточнение про префиксы

Дополню задачу таким образом.

Каждое дерево характеризуется двумя числами натуральными: n и m. Для всех деревьев в оригинальной постановке m = n - 1. Число всех возможных корней равно n * m. Для двух непосредственных потомков корня n1 + n2 = n. Создание каждого непосредственного потомка уменьшает m на единицу. И так узлы строятся до тех пор, пока ni не будет равно единице. Все дерево строится до тех пор, пока m не равно нулю.

Имхо, в задаче поиска совершенно не обязательно следовать в лоб древовидной логической организации данных. Поскольку в памяти всё это, так или иначе, валяется в виде списков, а в условии задачи никак не отмечена упорядоченность двоичных деревьев, задача может быть сведена к поиску в списках.
Для ускорения именно поиска, в функциях сохранения/получения данных этих деревьев можно было бы предусмотреть, чтобы данные сохранялись в отсортированные линейные списки, а в деревьях хранились лишь индексы из этих списков.
Тогда решение сводится, например, к сбору первых (наименьших) значений из списков каждого дерева и выбора среди них максимума.

Все данные вычисляемы и по памяти тоже хотелось бы в ограничения влезть

58! = 2,...e+78

все в машину

высота каждого дерева n-2, каждое дерево имеет n-1 вершин и n листьев.

Это вообще как?

Деревья двоичные, высота каждого дерева n-2, каждое дерево имеет n-1 вершин и n листьев.

нарисуй пример для n=4

Необходимо придумать эффективный алгоритм поиска максимума среди минимальных элементов каждого дерева

при чем тут эти деревья? они ничем не помогут. или тебе задали придумать алгоритм с использованием деревьев с таким свойством?

Все данные вычисляемы и по памяти тоже хотелось бы в ограничения влезть

ты считаешь, что об этом в постановке задачи можно было не упоминать? формулу в студию

если деревья вычисляемы, use math, luke. и math - это не std::math, а то, что, как известно, не нужно программистам.

Это в частном случае. Мне интересно общее решение. Дополнительные ограничения я указал тут: Царям (комментарий)

К тому же, у меня эта задача (частная) уже решена, решена перебором с возвратом, и пока это единственный доступный для меня алгоритм. Однако, я пока еще не доказал, что он наилучший.

я так и не смог понять постановку задачи. Можно еще раз? Только теперь корректно.

Интересно, но времени нет.

постановку задачи. Можно еще раз? Только теперь корректно

кастаните плз, когда будет

Проблема в том, что я ее формулировал вчера в полусонном состоянии :)

Сейчас попробую.

Есть натуральное число n > 2. Можно считать, что все практические значения n лежат в интервале [5, 30].

Есть не менее (2n-2)! деревьев. О деревьях известно следующее:

• Каждый узел дерева содержит неотрицательное вещественное число
• Каждый лист содержит плюс бесконечность
• Деревья бинарные, в них есть n листьев и n-1 вершина (здесь я буду называть вершиной узел, не являющийся листом, для простоты)
• Высота дерева равна n-1
• О способе построения деревьев известно следующее:
  • Каждый узел может быть охарактеризован двумя натуральными числами: p и q
  • q — глобальная величина
  • Число возможных различных значений в узле равно p*q
  • Для любого листа p = 1
  • Два узла с равными значениями p и q (попарно) равны только тогда, если равны пути от корня до этих узлов и равны соответствующие p и q для всех узлов этих путей
  • Для корня p = n, q = n-1
  • Для непосредственных потомков узла (обозначим их характеристические числа через p1, q1, p2, q2) p1 + p2 = p. А q вычисляет в следующем алгоритме q--, q1 = q, q--, q2 = q

Необходимо найти максимальный среди минимальных элементов каждого дерева.

Кастую :)

...

Опять ерунда какая-то

Связана с расположением ректификационных колонн

Напиши нормально что нужно сделать с колоннами, а не морочь голову своими деревьями

Есть натуральное число n > 2. Можно считать, что все практические значения n лежат в интервале [5, 30].

Есть не менее (2n-2)! деревьев

62! деревьев? где они есть? если мы рассматриваем все такие деревья, сколько бы их ни было, так и пиши

Загнал условия в пролог, понятия не имею, как он ищет

Деревья бинарные, в них есть n листьев и n-1 вершина (здесь я буду называть вершиной узел, не являющийся листом, для простоты)

Высота дерева равна n-1

хм. так тогда это фактически связанный список с присобаченным где-нибудь посередине _одним_ листом. Ты уверен, то дал сейчас правильное определение того, что ты хочешь?

Деревья бинарные, в них есть n листьев и n-1 вершина (здесь я буду называть вершиной узел, не являющийся листом, для простоты)
Высота дерева равна n-1
Есть натуральное число n > 2

нарисуй такое дерево для n=3

Необходимо найти максимальный среди минимальных элементов каждого дерева.

как определено отношение порядка на множестве узлов?

Предположим, что они просто где-то лежат

В том смысле, что минимальное из тех вещественных чисел, что сопоставлены с каждым узлом

    A
   / \
  B   C
     / \
    D   E

Это если мы считаем, что высота листа равна нулю, а не единице

Это если мы считаем, что высота листа равна нулю, а не единице

это какая-то жесть. почему нельзя дать ТЗ в общеизвестных терминах?

ерунда

Конкретнее

что нужно сделать с колоннами

Там будет такая куча деталей, которую никто не переварит за разумное время

Эм, вообще-то, такое определение высоты дерева довольно распространено. Да хоть в википедии даже

Эм, вообще-то, такое определение высоты дерева довольно распространено

в совокупности с остальными «определениями» это делает понимание ТЗ окончательно невозможным.

Да хоть в википедии даже

специально сходил, посмотрел. Нет, в википедии таки определно как и везде - максимально длинный путь между корнем и вершиной.

То есть? Это общепринятое понятие высоты дерева. Что там еще не ясно?

// алсо, Вирт [Алгоритмы и структуры данных, ДМК, 2011, с. 191] вообще смешивает понятия высоты и глубины. Впрочем его определение высоты эквивалентно моему.

Статья «Tree (data structure)», раздел «Terminology».

The height of a node is the length of the longest downward path to a leaf from that node. The height of the root is the height of the tree. The depth of a node is the length of the path to its root (i.e., its root path). This is commonly needed in the manipulation of the various self-balancing trees, AVL Trees in particular. The root node has depth zero, leaf nodes have height zero, and a tree with only a single node (hence both a root and leaf) has depth and height zero. Conventionally, an empty tree (tree with no nodes, if such are allowed) has depth and height −1.