Блог Дмитрия Сошникова

про технологии и человеческое счастье

Магия треугольника Серпинского в функциональном стиле

Сегодня мы поговорим про замечательную геометрическую фигуру: треугольник Серпинского. Это фрактальная самоподобная структура, которая однако очень проста в построении.

image

Алгоритм построения треугольника таков:

  • Задаем координаты трех вершин-аттракторов (x1,y1), (x2,y2) и (x3,y3)
  • Выбираем некоторую точку (x,y) внутри треугольника
  • Повторяем много раз:
    • Ставим точку с координатами (x,y)
    • Выбираем случайным образом одну из вершин (xi,yi)
    • Вычисляем координаты новой точки по формуле ((x+xi)/2,(y+yi)/2)

Такой алгоритм легко реализовать на любом языке программирования, однако его реализация на функциональных языках имеет ряд интересных моментов. В частности, для вычисления координат всех точек треугольника мы используем концепцию корекурсии.

В соответствии с этим, мы реализуем функцию sierpinski, которая будет возвращать бесконечную последовательность координат точек треугольника:

let sierpinski (p1,p2,p3) =
   let rec sierpinski' pt =
      seq {
        let p = pick [p1;p2;p3]
        let pt' = mid pt p
        yield pt'
        yield! sierpinski' pt'
      }
   sierpinski' (mid3 p1 p2 p3)

В этом определении мы используем вспомогательную вложенную рекурсивную функцию sierpinski’, которая в качестве аргумента передает координаты текущей точки pt. Координаты вершин p1,p2,p3 в данном случае являются внешними по отношению к этой функции. Далее мы выбираем одну из вершин случайным образом, вычисляем координаты очередной точки, “возвращаем” (с помощью yield) эти координаты, и затем рекурсивно возвращаем бесконечный остаток списка, который получается из рекурсивного вызова. Затем чтобы сформировать результат мы вызываем sierpinsky’, передавая ему в качестве начальной точки среднюю точку, вычисленную из координат вершин.

Для вычисления средних точек мы определим следуюшие вспомогательные функции:

let mid (x1,y1) (x2,y2) = (x1+x2)/2,(y1+y2)/2
let mid3 (x1,y1) (x2,y2) (x3,y3) = (x1+x2+x3)/3,(y1+y2+y3)/2

Для выбора вершины случайным образом мы используем немного нефукнциональный подход, который зато позволяет быстро получить требуемую функциональность:

let Rnd = new Random()
let pick (L:'t list) = L.[Rnd.Next(0,Seq.length L)]

В завершение остаётся лишь построить полученный треугольник. Для этого можем использовать стандартную библиотеку FSharp.Charting:

sierpinski ((0,0),(300,600),(600,0)) |> Seq.take 5000 |> Chart.FastPoint

Вот какой получился результат:

image

Весь исходный код можно найти здесь: http://fssnip.net/ta.

В качестве самостоятельного упражнения, попробуйте в качестве эксперимента модифицировать функцию sieprinski, чтобы она могла принимать произвольное число вершин. И посмотрите, будет ли сохраняться фрактальное свойство для квадратов, шестиугольников и т.д. Буду рад видеть результаты ваших экспериментов в комментариях!

Add a comment

Как научить ребенка программировать

Если у вас, как и у меня, есть дети – то вас наверняка волнует вопрос, как воспитать в них творческое начало, сделать их заинтересованными активными членами общества. Огромная роль в этом принадлежит родителям, которым для достижения результата приходится вкладывать очень много любви, своей креативности, терпения и усилий. Но как всегда на помощь могут прийти информационные технологии – ведь они способны усиливать любое правильное (и неправильное) начинание, делая процесс намного более эффективным.

Использованию информационных технологиях применительно к развитию детей посвящен мой новый курс на Microsoft Virtual Academy, под кодовым названием “Как научить ребенка программировать”. На самом деле речь пойдет не только о программировании – в этом курсе я постарался описать известные мне технологии Майкрософт, которые могут вдохновить ребенка на творчество.

Этот курс предназначен для родителей, которые ищут различные способы занять своих детей творчеством. Мы видим, что дети с удовольствием берут в руки компьютер, и важно дать им правильные творческие инструменты, чтобы они воспринимали компьютер не как поставщика развлекательного контента (наравне с телевизором), а как инструмент для творчества. На самом деле детям нравится творить (этим в основном объясняется популярность Minecraft), и важно направить их в правильное русло.

Среди технологий, о которых рассказывается в курсе – технологии для исследования мира (Bing Maps, Worldwide Telescope), для коллективного творчества (Photosynth, Image Composite Editor и др.). Я также уделяю особое внимание вопросу мотивации детей, и рассказываю о своем опыте работы с детскими коллективами как преподавателя детского лагеря ЮНИО-Р, одного из идеологов часа кода в России и детского трека Microsoft AppDay, лектора и ведущего мастер-классов в Компьютерии.

Особое внимание конечно уделяется именно обучению программированию. На мой взгляд, важнее всего увлечь ребенка на первых этапах процесса, поэтому предлагается использовать инструменты быстрого создания игровых миров Kodu Game Lab и Project Spark. Ну а потом уже подключаются различные “традиционные” инструменты – от увлекательного введения в C#, до возможного пути Small Basic –> Visual Basic и функционального программирования на F#.

Конечно, приведенный подход не является единственно правильным, и может кому-то показаться дискуссионным. Если у вас возникают какие-то свои мысли, или вы хотите поделиться своим опытом и пообсуждать вопросы обучения детей – я с удовольствием это сделаю в комментариях к этому посту, вконтакте или в твиттере.

Надеюсь, этот курс будет полезен и интересен – по крайней мере об интересе к этой теме говорят полные залы на моих докладах на конференциях DevCon и ряде других. Приятного просмотра!

Add a comment