Что это?
Треугольник Серпинского
Треугольник Серпинского — один из известнейших фракталов, его построение — одна из первых лабораторных работ на рекурсию по соответствующим дисциплинам во многих ВУЗах. Выглядит фрактал следующим образом:
Треугольник Паскаля
Треугольник Паскаля — бесконечная таблица биномиальных коэффициентов, имеющая треугольную форму. В этом треугольнике на вершине и по бокам стоят единицы. Каждое число равно сумме двух расположенных над ним чисел. Строки треугольника симметричны относительно вертикальной оси.
И что с того?
Есть в треугольнике Паскаля интересная особенность. Он отображает вышеупомянутый фрактал своими числами. Если долго всматриваться в бездну, бездна начинает всматриваться в тебя значения, то можно увидеть, что чётные и нечетные числа располагаются группами, ибо есть одно негласное всем известное правило: четное+нечетное=нечетное, четное+четное=четное, нечетное+нечетное=четное.
Что ж, меньше слов, больше дела. Сделаем вывод немного нагляднее. Людям, не интересующимся программной реализацией следующий абзац будет неинтересен.
Я взял старый алгоритм расчета-вывода треугольника Паскаля и преобразовал его таким образом, что вместо значения чисел выводится остаток от его деления на 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_INn";
open (STREAM_OUT, '>> 1.html');# || die "Can't open STREAM_OUTn";
$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
Автор: 19N4T0V
