Авторское решение задачи строит фрактал при помощи рекурсивной функции. Пусть a - квадратная матрица размера nk × nk для записи результата. Напишем функцию fractal(x, y, k), которая заполняет квадратную часть матрицы с левым верхним углом (x, y) и длиной стороны nk, рисуя в ней фрактал с глубиной k. В случае если k = 0 выводим точку. В противном случае требуется разбить имеющуюся часть матрицы на n2 квадратов размера nk - 1 × nk - 1 и заполнить их в соответствии с шаблоном. Если соответствующий символ в шаблоне ''*'', то нужно весь квадрат заполнить символами ''*'', иначе запустить fractal(x1, y1, k-1), где (x1, y1) - координаты левого верхнего угла нового квадрата.
Более простое в реализации решение предлагает kdalex (http://mirror.codeforces.com/blog/entry/764). Переберем все клетки (x, y). Если для какого-то c = nd, 0 ≤ d < k клетка ((x/c)%n, (y/c)%n) шаблона черная, что и (x, y) - черная, иначе (x, y) - белая. Нетрудно видеть, что если при d = k - 1 клетка ((x/c)%n, (y/c)%n) черная, то получается, что наша клетка (x, y) попала в черный квадрат на первом шаге алгоритма. Если ((x/c)%n, (y/c)%n) черная при d = k - 2, то на втором шаге и т.д.
Комментарии (0)
