[торможу] Алгоритм отрисовки дерева
или переформулируй или нарисуй, я прочитал четыре раза и не понял.
ну ты что-то такое совсем хитрое хочешь, только какой-то итеративный упаковщик такое нарисует. =)
можно скажем потребовать что каждое подерево вписывается в прямоугольник
и рекурсивно расчитывать размеры прямоугольников и отрисовывать
можно скажем потребовать что каждое подерево вписывается в прямоугольник
и рекурсивно расчитывать размеры прямоугольников и отрисовывать
уже рассчитываю, но не клеится чего-то
сколько проходов?
и компактность по ширине или высоте?
и компактность по ширине или высоте?
в смысле проходов?
компактность по ширине.
компактность по ширине.
в смысле проходов?проходов по дереву
можно, например, размышлять, как отрисовать такое в один проход
типа да. в один проход.
рекурсия (алгоритм для поддерева, находимся в узле):
рисуем узел
рисуем левое поддерево
сдвигаемся по высоте на высоту левого поддерева + дельта и рисуем правое поддерево
рисуем узел
рисуем левое поддерево
сдвигаемся по высоте на высоту левого поддерева + дельта и рисуем правое поддерево
Наверное, надо всюду левое заменить на правое ?
Еще интересно добиться минимальности по высоте (среди всех деревьев, минимальных по ширине).
Еще интересно добиться минимальности по высоте (среди всех деревьев, минимальных по ширине).
Наверное, надо всюду левое заменить на правое ?точно. я перепутал их потому, что мысленно иду от корня, а там на развилке то, что идет в право - левое поддерево, а что вниз - правое
спасибо
Еще интересно добиться минимальности по высоте (среди всех деревьев, минимальных по ширине).
+1
в общем, что-то реализовалось и этого пока хватит.
конечно, можно и дальше компактифицировать, но тут нужно сложную теорию вкладывать
конечно, можно и дальше компактифицировать, но тут нужно сложную теорию вкладывать
боюсь эта штука в общем случае вполне может оказаться NP-полной
угу. как и большинство задач на упаковку/расстановку
да, недавно доказали что тетрис NP-полон =)
А неочевидно? =)
ну давай докажи, сведи какую-нить NPC к тетрису.
как я понял фигурки и ширина стакана фиксированы стандартными, так что сведение явно нетривиальное.
как я понял фигурки и ширина стакана фиксированы стандартными, так что сведение явно нетривиальное.
Окей.
Раз пошла такая пьянка, будь добр - сформулируй задачу "Тетрис".
Раз пошла такая пьянка, будь добр - сформулируй задачу "Тетрис".
а нет, там ешё можно задавать начальное состояние стакана и заузить его, так что всё не так сложно.
http://www.liacs.nl/~kosters/tetris/tot.pdf
http://www.liacs.nl/~kosters/tetris/tot.pdf
прочитай в статье правила, а доказательство не читай =)
Посмотрел =) Конкретно люди заморочились
Я, просто, честно говоря, немного о другом думал и вот там сводимость была бы очень простой...
Я, просто, честно говоря, немного о другом думал и вот там сводимость была бы очень простой...
Оставить комментарий
yolki
у каждого узла 4 направляющих - up/down/left/rightдерево растёт вниз и вправо.
как бы его на плоскости изобразить, чтобы компактно, без наложения узлов, без пересечения дуг и чтобы вправо-вниз было именно вправо и вниз