Треугольник Серпинского и треугольник Паскаля

    Что это?


    Треугольник Серпинского

    Треугольник Серпинского — один из известнейших фракталов, его построение — одна из первых лабораторных работ на рекурсию по соответствующим дисциплинам во многих ВУЗах. Выглядит фрактал следующим образом:
    image

    Треугольник Паскаля

    Треугольник Паскаля — бесконечная таблица биномиальных коэффициентов, имеющая треугольную форму. В этом треугольнике на вершине и по бокам стоят единицы. Каждое число равно сумме двух расположенных над ним чисел. Строки треугольника симметричны относительно вертикальной оси.
    image

    И что с того?


    Есть в треугольнике Паскаля интересная особенность. Он отображает вышеупомянутый фрактал своими числами. Если долго всматриваться в бездну, бездна начинает всматриваться в тебя значения, то можно увидеть, что чётные и нечетные числа располагаются группами, ибо есть одно негласное всем известное правило: четное+нечетное=нечетное, четное+четное=четное, нечетное+нечетное=четное.

    Что ж, меньше слов, больше дела. Сделаем вывод немного нагляднее. Людям, не интересующимся программной реализацией следующий абзац будет неинтересен.

    Я взял старый алгоритм расчета-вывода треугольника Паскаля и преобразовал его таким образом, что вместо значения чисел выводится остаток от его деления на 2. Стало быть, четные теперь стали нулями, нечетные — единицами. Сам код прилагаю ниже
    #include <iostream>
    using namespace std;
    
    double Cnk(int N,int K)
    {
      return ((N<K)?0:((K==0)?1:((N-K+1)/double(K)*Cnk(N,K-1))));
    }
    
    
    int main()
    {
      int n=10;
      
      for(int j=0; j<= n; j++) 
      {
    	  for (int i=0; i <=j ; i++)
    	  
          cout<<(static_cast<int>(Cnk(j,i)))%2<<" ";
          cout<<"\n";
      }
      return 0;
    }
    

    Для пущей наглядности я разукрасил вывод следующим способом: вывод программы перенаправляется в файл, откуда по завершению выполнения первой, перл своими регэкспами заменяет единицы на красные буквы О, нули — на синие. Код скрипта ниже:
    #! perl -w
    
    open (STREAM_IN, '1.txt');# || die "Can't open STREAM_IN\n";
    open (STREAM_OUT, '>> 1.html');# || die "Can't open STREAM_OUT\n";
    $ss='<br>';
    while ($curr = <STREAM_IN>)
    {	
        chomp($curr);
        $curr=~s/1/<font color="red">O<\/font>/g;
        $curr=~s/0/<font color="blue">O<\/font>/g;
        $curr=~s/-//g;
        $out = $curr.$ss;
        print (STREAM_OUT $out);
    };
    close STREAM_IN;
    close STREAM_OUT;
    

    Из исходника видно, что смотреть мы будем html. Почему? Из соображений простоты. Только дерево DOM неверное получается. Исправим это скриптом на BASH и автоматизируем всё вышеописанное:
    #!/bin/bash
    g++ ~/serp.cpp;
    ~/a.out > ~/1.txt;
    echo '
    <html>
    <head>
    <title>TRIANGLE</title>
    </head>
    <body>
    <center>' > ~/1.html;
    perl ~/s.pl;
    echo '</center>
    </body>
    </html>' >> ~/1.html
    

    Итак, мы компилируем исходник на плюсах, его вывод уходит в текстовичок, баш «эхает» в html на перезапись началом дерева DOM, после чего текстовичок берет перл-скрипт, переделывает его в разноцветную html-версию, дополняет htmlку, после чего любезный БАШ снова завершает формирование дерева. Запускаем, смотрим:

    Подчеркнем и сравним с оригиналом

    PROFIT
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 50

      +19
      PROFIT

      В чем?
        +44
        мне теперь не так скучно
        +5
        Сколько разных языков программирования используется для такой простой задачи…
          0
          «Я тебя слепила из того, что было». Просто были исходники для некоторых задач на разных языках. А башем, как всегда, стравливаю их.
            +2
            Десяток строк JavaScript заменила бы всю это мешанину скриптов и компилируемых исходников в универсальное веб-решение для любых платформ, и можно было бы даже ссылку на демо дать.
            ЗЫ. Хотел прикрепить код, да jsfiddle не отвечает.
              +12
              Поддерживаю. Ради интереса набросал грубую демку: arthur.ho.ua/uploads/pascal.html
              Там еще забавные мотивы получаются, если брать остатки от деления не на 2, а на 3 или больше.
                0
                А так же интересные закономерности когда брать простые и не простые делители.
                  +1
                  Шикарно!
                    +2
                    Еще интересней, если вместо кружков делать цветные треугольники, как в оригинале
                      +5
                      Хорошая идея. Обновил демку.
                        0
                        А в <pre> обернуть не пробовали? Мне кажется, должно выглядеть лучше.
                          0
                          pre сохраняет форматирование. А нужно центровать
                            0
                            Если в <pre> оборачивать отдельно каждую строку, а все их поместить в <div> с text-align: center, то будет работать.
                              0
                              Остается только придумать зачем
                                0
                                Для красоты =)
                                  +3
                                  Для красоты, я бы лучше line-height: 0.88; сделал.
                                    0
                                    И это можно, да.
                                      +2
                                      Сделал.
                                        +5
                                        31 / 2 / 0.5
                                        Мне кажется, «канонический» вариант.
                                          +1
                                          Ага, удачная комбинация у вас получилась. Только с интерлиньяжем там неоднозначно — в разных шрифтах треугольники имеют разную высоту относительно строки. У меня, например, с DejaVu Serif наилучшая картинка где-то около 0,68.
                                            +1
                                            Я ниже писал про порождающие последовательности, вот вспомнил как на них посмотреть, думаю отписавшимся в этой ветке будет интересно.

                                            Надо на вольфрамальфа вбить текст rule X — где Х номер
                                            например интересные последовательности из его (автора вольфрамальфа) книжки:

                                            rule 1

                                            rule 30

                                            rule 90
                              0
                              А что должно улучшиться? Я попробовал с <pre> — у меня вроде ничего не изменилось.
                                0
                                По идее pre предполагает использование моноширного шрифта. Но т. к. используется один символ, смысла в нём мало.
                              +4
                              В оригинале ▲ используется. (CTRL+SHIFT+u25b2)
                          +3
                          0
                          Некошерно!
                          Надо было на… Pascal'e написать!
                          :-)))
                        –1
                        Людям, не интересующимся программной реализацией следующий абзац будет неинтересен.

                        Обычно эта фраза обозначает, что в начале или в конце статьи был разбор сложного алгоритма, практическое применение.
                        Ну или просто крутая технологичная демка, которую дадут пощупать своими руками, еще и исходник приложат.
                        Здесь же этого нет.
                        P.S. Ну и можно было по человечески метод Cnk(int,int) написать, смотреть же невозможно.
                          +1
                          У вас что-то странный код на плюсах. Запустил у себя и вот, что получил.
                          1
                          1 1
                          1 0 1
                          1 1 1 0
                          1 0 0 1 0
                          1 1 0 0 1 1
                          1 0 1 1 0 0 0
                          1 1 1 1 1 1 0 0
                          1 0 0 0 0 0 0 0 1
                          1 1 0 0 0 0 0 1 0 0
                          1 0 1 1 1 1 1 1 0 1 0

                          На правом ребре не единицы. Поправте, чтоли.
                            0
                            Ну, из результатов, представленных выше, видно, что G++ не согласен с Вашим компилятором. Я отлаживал в своем.
                              0
                              Перед преобразованием к int прибавьте 0.5 — может помочь…
                              +3
                              Трифорс?)
                                +1
                                Он самый)
                                0
                                Вы как-то смело предположили, что при дальнейших расчётах и дальше будет похоже на треугольник Серпинского.
                                  0
                                  Это не мое предположение, это факт. Только методика дальнейшего расчета другая немного будет.
                                  +2
                                  Вообще есть хорошая лекция про порождающие последовательности от создателя wolframalpha.
                                    +1
                                    И занимательная книженция «New Kind of Science» от него же.
                                      0
                                      Вот не могу только ее найти, ссылку на лекцию не кинете?
                                    +2
                                    А вот если бы вы как то резюмировали это все дело, пояснили что-ли, тогда еще и мне было бы не так скучно.
                                      +2
                                      «Можно заменить четные красненькими, а нечетные синенькими, смотрите, как весело!» — это все, что я хотел сказать
                                      +1
                                      В этом объекте интересное другое: неинтуитивые значения различных размерностей.
                                        +2
                                        На вкладке «Игра в пенис с…» написано? Хм…
                                        0
                                        Писал рекурсивное рисование фракталов в универе в качестве хобби, вот бы нас этому учили тогда =)

                                        Про рекурсию только вскользь упоминали )

                                        А реализация у Вас, конечно, адовая, если уж начали на плюсах, можно было б и весь html им выводить.
                                          –2
                                          И даже без use strict, ты смотри-ка
                                            0
                                            с++, perl, bash — зачем?
                                            Dancer, Mojolicious же!
                                              +2
                                              Главное в жизни это разнообразие!
                                              Я бы добавил ещё надстройку на Коболе.
                                                0
                                                Я хотел еще что-нибудь на паскале написать, но Лазарус отвалился :)
                                                  0
                                                  Ты бы мог не компилить! Главное же написать!
                                          • UFO just landed and posted this here
                                              0
                                              Более подробное исследование треугольника Паскаля: arbuz.uz/u_treug.html

                                              Only users with full accounts can post comments. Log in, please.