Ужасы нашего городка
Feb. 13th, 2021 12:23 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
elglinМне несколько раз с интервалом от месяцев до лет снился сон на одну и ту же тему, что я второй раз учусь у себя на факе. При этом я осознаю, что учусь второй раз, и, вроде как, непонятно, зачем, но вот учусь. Ну и мысли (все во сне), что как же я сессию сдавать буду, у меня же работа, отпрашиваться надо будет и все такое.
Это я, собственно, к чему. Есть некая девочка, назовем ее Х. (нет, не Хуанита). Девочка учится на программистском факультете. Девочке я до того пытался нести в мозг матан и алгебру, их она сдала.
А вот теперь она попросила помочь с пересдачей по погромированию. Я сначала машинально (девочка позвонила аккурат между двумя нервными совещаниями) попросил прислать все задачи и вопросы, и только потом отметил, что на дворе не то, что февраль, а середина его, и сессия закончилась не только сама, но и вместе с пересдачами. Сталбыть, девочка не то, что с хвостом, а в одном шаге от пресловутого компота.
Ну ладно, слава яйцам, у нее не Паскаль, который я бы без методички не вспомнил (хотя у меня на нем написан один курсач - не мой, и одна лаба - не моя), а старый добрый Це. Ну на Це мы могем, и у нас, естественно, есть муха гэцеце (прольем скупую слезу над безвременно почившим ваткомом, а какой был в свои годы компилятор, какой был слон, какой был слон).
Понятное дело, что ничего эпичного там не было - немного очень простой строковой работы, набившие оскомину фибоначчи и немного работы со связным списком и деревьями (рекурсия, омномном). Ну, короче, один вечер после реально упоротой трудовой недели - могу, значит, еще, на первом курсе учиться.
Девочка то ли гнет дерево не по себе, то ли не познала мантру, что ИТ - это ноулайферство, но в консерватории надо что-то менять. Не мое, впрочем, дело ее жизни учить.
Но фиг с ней, с девочкой, там был интересный вопрос, который я в полубессознанке сделал через жопу, а хотелось красиво. Есть у нас два отсортированных бинарных дерева, нам надо найти мощность пересечения, и нам даже гарантируют, что элементы внутри каждого дерева уникальны.
Вариант через жопу - это пройти одно дерево насквозь и поискать каждый элемент в другом. Были бы это два массива, я бы параллельно по ним прошелся и за один проход все нашел.
Но это деревья, и по условиям задачи (структура данных задана жестко) указателя вверх у нас нет, только налево и направо. В этой ситуации я знаю, как сделать параллельный обход, имея два стека. Но у меня не плюсы, где я взял бы стек из STL и горя не знал, а голая сишка. Писать на автопилоте динамический стек поверх связного списка - ну, это так себе затея в первом часу ночи.
А есть ли более кошерный вариант? Теория-то уверенно говорит, что дерево в глубину без стека не обходится.
Надумал я сейчас только извращенный вариант провязывать стек вызовов указателями (чтобы невозбранно ходить в предыдущие стекфреймы), глубину стека держать как максимум глубин погружения в оба дерева - по сути, эмулируя второй стек на стеке вызовов. При этом что при погружении, что при разматывании то и дело придется "переключать" реальный и эмулируемый стеки. Как-то слишком сложно и кулхацкерски.
Это я, собственно, к чему. Есть некая девочка, назовем ее Х. (нет, не Хуанита). Девочка учится на программистском факультете. Девочке я до того пытался нести в мозг матан и алгебру, их она сдала.
А вот теперь она попросила помочь с пересдачей по погромированию. Я сначала машинально (девочка позвонила аккурат между двумя нервными совещаниями) попросил прислать все задачи и вопросы, и только потом отметил, что на дворе не то, что февраль, а середина его, и сессия закончилась не только сама, но и вместе с пересдачами. Сталбыть, девочка не то, что с хвостом, а в одном шаге от пресловутого компота.
Ну ладно, слава яйцам, у нее не Паскаль, который я бы без методички не вспомнил (хотя у меня на нем написан один курсач - не мой, и одна лаба - не моя), а старый добрый Це. Ну на Це мы могем, и у нас, естественно, есть муха гэцеце (прольем скупую слезу над безвременно почившим ваткомом, а какой был в свои годы компилятор, какой был слон, какой был слон).
Понятное дело, что ничего эпичного там не было - немного очень простой строковой работы, набившие оскомину фибоначчи и немного работы со связным списком и деревьями (рекурсия, омномном). Ну, короче, один вечер после реально упоротой трудовой недели - могу, значит, еще, на первом курсе учиться.
Девочка то ли гнет дерево не по себе, то ли не познала мантру, что ИТ - это ноулайферство, но в консерватории надо что-то менять. Не мое, впрочем, дело ее жизни учить.
Но фиг с ней, с девочкой, там был интересный вопрос, который я в полубессознанке сделал через жопу, а хотелось красиво. Есть у нас два отсортированных бинарных дерева, нам надо найти мощность пересечения, и нам даже гарантируют, что элементы внутри каждого дерева уникальны.
Вариант через жопу - это пройти одно дерево насквозь и поискать каждый элемент в другом. Были бы это два массива, я бы параллельно по ним прошелся и за один проход все нашел.
Но это деревья, и по условиям задачи (структура данных задана жестко) указателя вверх у нас нет, только налево и направо. В этой ситуации я знаю, как сделать параллельный обход, имея два стека. Но у меня не плюсы, где я взял бы стек из STL и горя не знал, а голая сишка. Писать на автопилоте динамический стек поверх связного списка - ну, это так себе затея в первом часу ночи.
А есть ли более кошерный вариант? Теория-то уверенно говорит, что дерево в глубину без стека не обходится.
Надумал я сейчас только извращенный вариант провязывать стек вызовов указателями (чтобы невозбранно ходить в предыдущие стекфреймы), глубину стека держать как максимум глубин погружения в оба дерева - по сути, эмулируя второй стек на стеке вызовов. При этом что при погружении, что при разматывании то и дело придется "переключать" реальный и эмулируемый стеки. Как-то слишком сложно и кулхацкерски.
(no subject)
Date: 2021-02-13 03:30 pm (UTC)О, кстати да, по принципу mergesort. У меня только не получилось забацать такой алгоритм.
(no subject)
Date: 2021-02-13 07:29 pm (UTC)while(runner1 && runner2){
if(runner1->x == runner2->x) count++;
if(runner1->x <= runner2->x) runner1 = tree1.next(runner1); else runner2 = tree2.next(runner2);
}
Все сводится к реализации метода next(). Алгоритмически он тривиален: если можем уйти направо, идем направо один шаг, потом налево до упора; если не можем, идем вверх, пока не появляется поворот направо; если дошли до корня, а поворота все нет, то уходим на NULL. Если у нас в структуре дерева есть указатель вверх, это решается без стека.
Если нет, то для похода вверх нам нужна вся история текущего пути от корня дерева в стеке. Для обхода двух деревьев параллельно нужно два стека. Естественный обход дерева через рекурсию держит стек обхода дерева в стеке вызовов.
Эмуляция, которую я придумал на идеологическом уровне, следующая:
1) В каждый рекурсивный вызов мы прокидываем два указателя на элемент дерева, один из которых может быть NULL. Так мы строим два параллельных стека.
2) Дополнительно мы по ссылке передаем указатель на указатель из предыдушего вызова. По сути у нас связный список (который годно эмулирует стек) - который весь лежит в стеке вызовов.
3) Дополнительно у нас есть "глобальные" указатели на голову каждого списка (=вершину стека) и, скорее всего, еще сколько-то глобального состояния, которые мы все по указателю таскаем между вызовами.
4) Если нам надо пойти вниз в дереве, куда мы погрузились глубже, мы проваливаемся на еще один уровень рекурсии. Если надо пойти вниз в другом дереве, манипулируем вторым связным списком (все элементы уже есть).
5) Аналогично, если надо всплыть в более глубоком дереве, мы всплываем на один уровень, сохранив что-то при необходимости в глобальном состоянии; если надо всплыть в более мелком, то манипулируем вторым списком.
Получается очень глючно, багопотенциально и все такое, но мы таким макаром получаем эмуляцию стека на стеке вызовов, а динамическое управление памятью перекладываем, как и в случае наивного рекурсивного обхода дерева, на стек вызовов. Но это уже черная магия.
(no subject)
Date: 2021-02-13 09:47 pm (UTC)Было бы мило написать все это рекурсивно. Держать пару, ((t1, state1), (t2, state2)), и вычислять, что передать вглубь.