Pull to refresh

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

Reading time 2 min
Views 66K

Что это?


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

Треугольник Серпинского — один из известнейших фракталов, его построение — одна из первых лабораторных работ на рекурсию по соответствующим дисциплинам во многих ВУЗах. Выглядит фрактал следующим образом:
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
Tags:
Hubs:
+20
Comments 50
Comments Comments 50

Articles