Что это?
Треугольник Серпинского
Треугольник Серпинского — один из известнейших фракталов, его построение — одна из первых лабораторных работ на рекурсию по соответствующим дисциплинам во многих ВУЗах. Выглядит фрактал следующим образом:
Треугольник Паскаля
Треугольник Паскаля — бесконечная таблица биномиальных коэффициентов, имеющая треугольную форму. В этом треугольнике на вершине и по бокам стоят единицы. Каждое число равно сумме двух расположенных над ним чисел. Строки треугольника симметричны относительно вертикальной оси.
И что с того?
Есть в треугольнике Паскаля интересная особенность. Он отображает вышеупомянутый фрактал своими числами. Если долго всматриваться в бездну, бездна начинает всматриваться в тебя значения, то можно увидеть, что чётные и нечетные числа располагаются группами, ибо есть одно негласное всем известное правило: четное+нечетное=нечетное, четное+четное=четное, нечетное+нечетное=четное.
Что ж, меньше слов, больше дела. Сделаем вывод немного нагляднее. Людям, не интересующимся программной реализацией следующий абзац будет неинтересен.
Я взял старый алгоритм расчета-вывода треугольника Паскаля и преобразовал его таким образом, что вместо значения чисел выводится остаток от его деления на 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
ссылка на оригинал статьи http://habrahabr.ru/post/167817/