Двоичное дерево фрактал

25

Сегодняшняя задача состоит в том, чтобы нарисовать бинарное дерево таким красивым ascii-art, как этот пример:

                               /\
                              /  \
                             /    \
                            /      \
                           /        \
                          /          \
                         /            \
                        /              \
                       /                \
                      /                  \
                     /                    \
                    /                      \
                   /                        \
                  /                          \
                 /                            \
                /                              \
               /\                              /\
              /  \                            /  \
             /    \                          /    \
            /      \                        /      \
           /        \                      /        \
          /          \                    /          \
         /            \                  /            \
        /              \                /              \
       /\              /\              /\              /\
      /  \            /  \            /  \            /  \
     /    \          /    \          /    \          /    \
    /      \        /      \        /      \        /      \
   /\      /\      /\      /\      /\      /\      /\      /\
  /  \    /  \    /  \    /  \    /  \    /  \    /  \    /  \
 /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\

Вам будет дано положительное целое число в качестве входных данных. Этот вход - высота дерева . Приведенный выше пример имеет высоту шесть.

Вы можете отправить либо полную программу, либо функцию, и вы можете использовать любой из наших методов ввода-вывода по умолчанию . Например, будет разрешено печатать дерево, возвращать строку с символами новой строки, возвращать массив двумерных символов, сохранять дерево в файл и т. Д.

Пробелы на каждой строке разрешены.

Вот несколько примеров входов и их соответствующих выходов:

1:
/\

2:
 /\
/\/\

3:
   /\
  /  \
 /\  /\
/\/\/\/\

4:
       /\
      /  \
     /    \
    /      \
   /\      /\
  /  \    /  \
 /\  /\  /\  /\
/\/\/\/\/\/\/\/\

5:
               /\
              /  \
             /    \
            /      \
           /        \
          /          \
         /            \
        /              \
       /\              /\
      /  \            /  \
     /    \          /    \
    /      \        /      \
   /\      /\      /\      /\
  /  \    /  \    /  \    /  \
 /\  /\  /\  /\  /\  /\  /\  /\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\

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

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

Удачного игры в гольф!

code-golf string ascii-art fractal DJMcMayhem
источник
Могут ли быть завершающие пробелы, чтобы сделать все строки одинаковой длины?
xnor
@xnor Да, все в порядке.
DJMcMayhem

Ответы:

5

Python 2, 77 байт

S=s=i=2**input()
while s:print S/s*('/'+' '*(s-i)+'\\').center(s);i-=2;s/=s/i

Печать с пробелами, заканчивающимися ошибкой.

Я взял этот код из своей заявки на вызов, который я поставил на Anarchy Golf , плюс однобайтовое улучшение, найденное xsot. Кодовое значение 128 было изменено на 2**input().

Идея состоит в том, что каждая строка вывода представляет собой сегмент, скопированный один или несколько раз. Половина после входного разбиения имеет одну копию каждого сегмента, четверть после следующего разбиения имеет две копии и т. Д. До последней строки с множеством сегментов /\.

Каждый сегмент имел /и \, с промежутками между ними, а также снаружи, чтобы заполнить до нужной длины. Внешнее дополнение сделано с center.

Переменная sотслеживает текущее значение каждого сегмента, а количество сегментов S/sтаково, что общая ширина равна ширине дерева S. Номер строки iведет обратный отсчет на 2, и когда значение sравно половине, происходит разделение, и ширина сегмента уменьшается вдвое. Это делается с помощью выражения s/=s/i. Когда iдостигает 0, это дает ошибку, которая завершает программу.

Поскольку anagolf разрешает только отправку программ, я не исследовал возможность рекурсивной функции, которая, я думаю, скорее всего короче.

XNOR
источник
4

V , 32 байта

é\é/À­ñLyPÄlx$X>>îò^llÄlxxbPò
|

Попробуйте онлайн!

HexDump:

00000000: e95c e92f c0ad f116 4c79 50c4 6c78 2458  .\./....LyP.lx$X
00000010: 3e3e eef2 5e6c 6cc4 6c78 7862 50f2 0a7c  >>..^ll.lxxbP..|
DJMcMayhem
источник
4

Холст , 11 байт

/║╶╷［ｌ＼；∔↔║

Попробуй это здесь!

Объяснение:

/║          push `/\` ("/" palindromized so this is a Canvas object)
  ╶╷[       repeat input-1 times
     l        get the width of the ToS
      \       create a diagonal that long
       ;∔     prepend that to the item below
         ↔    reverse the thing horizontally
          ║   and palindromize it horizontally
dzaima
источник
3

Haskell , 140 138 135 байтов

e n=[1..n]>>" "
n!f=(e n++).(++e n)<$>f
f 0=[]
f n=1!f(n-1)++['/':e(2*n-2)++"\\"]
b n|n<2=f 1|t<-b$n-1,m<-2^(n-2)=m!f m++zipWith(++)t t

Попробуйте онлайн! Call with b 5, возвращает список строк.

Довольно использование печати:

*Main> putStr . unlines $ b 5
               /\
              /  \
             /    \
            /      \
           /        \
          /          \
         /            \
        /              \
       /\              /\
      /  \            /  \
     /    \          /    \
    /      \        /      \
   /\      /\      /\      /\
  /  \    /  \    /  \    /  \
 /\  /\  /\  /\  /\  /\  /\  /\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\

(некоторые) Объяснение:

  • e nгенерирует строку nпробелов
  • n!fподушечки каждая строка в списке строк fс nпробелами слева и справа
  • f nрисует «пик» в nпо 2nпрямоугольнику
  • b n рисует двоичное дерево, объединяя два меньших дерева и центрируя новый пик над ними

Редактировать: -3 байта благодаря Zgarb!

Laikoni
источник
Я думаю 1!f(n-1)и m!f mстоит сэкономить пару байтов.
Згарб
@Zgarb Спасибо за указание, эти правила приоритета иногда путают.
Лайкони
2

J , 49 43 42 байта

' /\'{~(|.,-)"1@(=@i.@#,-)^:(<:`(,:@,&*-))

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

объяснение

Сначала я строю матрицу значений -1, 0 и 1, повторяя вспомогательный глагол, а затем заменяю числа на символы. Вспомогательный глагол создает правую половину следующей итерации, а затем отражает ее по горизонтали, чтобы получить остальное. В следующем объяснении ,конкатенация двухмерных массивов по вертикали и одномерных массивов по горизонтали.

' /\'{~(|.,-)"1@(=@i.@#,-)^:(<:`(,:@,&*-))  Input is n.
                          ^:(            )  Iterate this verb
                             <:             n-1 times
                               `(       )   starting from
                                    ,&*-    the array 1 -1 (actually sign(n), sign(-n))
                                 ,:@        shaped into a 1x2 matrix:
                                             Previous iteration is y.
                      #                      Take height of y,
                   i.@                       turn into range
                 =@                          and form array of self-equality.
                                             This results in the identity
                                             matrix with same height as y.
                       ,-                    Concatenate with -y, pad with 0s.
       (    )"1@(        )                   Then do to every row:
        |.,-                                 Concatenate reversal to negation.
' /\'{~                                     Finally index entry-wise into string.
Zgarb
источник
1

JavaScript (ES6), 105 байт

f=n=>n<2?"/\\":" "+f(n-1).split`/`[0].replace(/|/g,"$`$'$'/$`$`\\$'$'$` \n")+f(n-1).replace(/.*/g,"$&$&")

Работает путем рекурсивного построения результата из базового варианта /\. Нижняя половина - это просто предыдущий случай с дублированием каждой строки. Верхняя половина была немного хитрее; похоже, что вы хотите взять предыдущий случай и оставить только две стороны, но вам также нужно беспокоиться о заполнении строк для удвоения ширины, поэтому вместо этого я использую магию регулярных выражений. Взяв начальные пробелы из предыдущего случая и разделив их в каждой точке, я могу рассмотреть пробелы до и после этой точки. При каждом совпадении пробелы до увеличения на 1 и пробелы после уменьшения на 1; это может быть использовано для позиционирования /и\в правильных местах. Новые строки и отступы также добавляются здесь; это берет на себя все отступы, кроме завершающего пробела в каждой строке и начального пробела в первой строке, которые я должен добавить вручную. (Ведущие пробелы в последующих строках взяты из совпадающей строки).

Нил
источник
1

Древесный уголь , 12 байт

ＦＮ«→↗⌈Ｘ²⊖ι‖Ｍ

Попробуйте онлайн! Ссылка на подробную версию кода. Объяснение:

 Ｎ              Input as a number
Ｆ «             Loop over implicit range
   →            Move right (because mirroring moves the cursor)
         ι      Current index
        ⊖       Decremented
      Ｘ²        Power of 2
     ⌈          Ceiling
    ↗           Draw diagonal line
          ‖Ｍ    Mirror image

Длина линии составляет 1, 1, 2, 4, 8 ... 2 ^ (N-2), таким образом, неуклюжий расчет.

Нил
источник
0

Пакет, 218 байт

@echo off
set/a"n=1<<%1"
set s=set t=
%s%/\
set l=for /l %%i in (2,1,%n%)do call
%l% %s% %%t%% 
%l%:l
:l
echo %t%
set/an-=1,m=n^&n-1
%s%%t: /=/ %
%s%%t:\ = \%
if %m% neq 0 exit/b
%s%%t:/ =/\%
%s%%t: \=/\%

Примечание: строка 6 заканчивается пробелом. Работает, перемещая ветви влево и вправо соответственно каждый раз, за ​​исключением строк, которые находятся на расстоянии 2 n от конца, и в этом случае ветви вместо этого разветвляются.

Нил
источник
0

Haxe, 181 байт

function g(n):String return(n-=2)==-1?"/\\":[for(y in 0...1<<n)[for(x in 0...4<<n)x+y+1==2<<n?"/":x-y==2<<n?"\\":" "].join("")].concat([for(y in g(n+1).split("\n"))y+y]).join("\n");

Или с некоторыми дополнительными пробелами:

function g(n):String
  return
    (n -= 2) == -1
    ? "/\\"
    : [ for (y in 0...1 << n)
        [ for (x in 0...4 << n)
          x + y + 1 == 2 << n
          ? "/"
          : x - y == 2 << n
            ? "\\"
            : " "
        ].join("")
      ].concat([ for (y in g(n + 1).split("\n"))
        y + y
      ]).join("\n");

Некоторое время я работал над решением, которое сначала создавало массив пространственных символов правильного размера, а затем итеративно помещал раздвоенные пути все ниже и ниже (и более плотно на каждой итерации). Осталось 230+ байтов. Подход здесь в значительной степени похож на подход @ Laikoni's Haskell. Я не мог сойти с рук, не имея :String, потому что Haxe не достаточно умен, чтобы определить, что тип возвращаемого значения всегда будет String.

Это только функция, вот полная программа для тестирования:

class Main {
    public static function main(){
        function g(n):String return(n-=2)==-1?"/\\":[for(y in 0...1<<n)[for(x in 0...4<<n)x+y+1==2<<n?"/":x-y==2<<n?"\\":" "].join("")].concat([for(y in g(n+1).split("\n"))y+y]).join("\n");
        Sys.println(g(Std.parseInt(Sys.args()[0])));
    }
}

Поместите вышесказанное в Main.hx, скомпилируйте haxe -main Main.hx -neko frac.nи протестируйте с neko frac.n 4(замените 4в нужном порядке).

Аурел Белый
источник
0

PHP, 188 байт

Онлайн версия

function f($l,$r=0,$m=1){global$a;for(;$i<$l;$i++)$i<$l/2?$a[$i+$r]=str_repeat(str_pad("/".str_pad("",2*$i)."\\",2*$l," ",2),$m):f($l/2^0,$r+$l/2,2*$m);}f(2**$argv[1]/2);echo join("\n",$a);

расширенный

function f($l,$r=0,$m=1){
global$a;    
for(;$i<$l;$i++)    
$i<$l/2
    ?$a[$i+$r]=str_repeat(str_pad("/".str_pad("",2*$i)."\\",2*$l," ",2),$m)
    :f($l/2^0,$r+$l/2,2*$m);
}
f(2**$argv[1]/2);
echo join("\n",$a);
Йорг Хюльсерманн
источник