Как с помощью циркуля и линейки. Основные задачи на построение

Муниципальное бюджетное общеобразовательное учреждение

средняя общеобразовательная школа №34 с углубленным изучением отдельных предметов

МАН, физико-математическая секция

«Геометрические построения с помощью циркуля и линейки»

Выполнила: ученица 7 «А» класса

Батищева Виктория

Руководитель: Колтовская В.В.

Воронеж, 2013

3. Построение угла равного данному.

Проведем произвольную окружность с центром в вершине А данного угла (рис.3). Пусть В и С - точки пересечения окружности со сторонами угла. Радиусом АВ проведем окружность с центром в точке О-начальной точке данной полупрямой. Точку пересечения этой окружности с данной полупрямой обозначим С 1 . Опишем окружность с центром С 1 и Рис.3

радиусом ВС. Точка В 1 пересечения построенных окружностей в указанной полуплоскости лежит на стороне искомого угла.

6. Построение перпендикулярных прямых.

Проводим окружность с произвольным радиусом r с центром в точке O рис.6. Окружность пересекает прямую в точках A и B. Из точек A и B проводим окружности с радиусом AB. Пусть тоска С – точка пересечения этих окружностей. Точки А и В мы получили на первом шаге, при построении окружности с произвольным радиусом.

Искомая прямая проходит через точки С и О.

Рис.6

Известные задачи

1. Задача Брахмагупты

Построить вписанный четырехугольник по четырем его сторонам. Одно из решений использует окружность Аполлония. Решим задачу Аполлония, используя аналогию между трехокружником и треугольником. Как мы находим окружность, вписанную в треугольник: строим точку пересечения биссектрис, опускаем из нее перпендикуляры на стороны треугольника, основания перпендикуляров (точки пересечения перпендикуляра со стороной, на которую он опущен) и дают нам три точки, лежащие на искомой окружности. Проводим окружность через эти три точки – решение готово. Точно также мы поступим с задачей Аполлония.

2. Задача Аполлония

Построить с помощью циркуля и линейки окружность, касающуюся трех данных окружностей. По легенде, задача сформулирована Аполлонием Пергским примерно в 220 г. до н. э. в книге «Касания», которая была потеряна, но была восстановлена в 1600 г. Франсуа Виетом, «галльским Аполлонием», как его называли современники.

Если ни одна из заданных окружностей не лежит внутри другой, то эта задача имеет 8 существенно различных решений.

Построение правильных многоугольников.

П

равильный (или равносторонний ) треугольник - это правильный многоугольник с тремя сторонами, первый из правильных многоугольников. Все стороны правильного треугольника равны между собой, а все углы равны 60°. Чтобы построить равносторонний треугольник нужно разделить окружность на 3 равные части. Для этого необходимо провести дугу радиусом R этой окружности лишь из одного конца диаметра, получим первое и второе деление. Третье деление находится на противоположном конце диаметра. Соединив эти точки, получим равносторонний треугольник.

Правильный шестиугольник можно построить с помощью циркуля и линейки. Ниже приведён метод построения через деление окружности на 6 частей. Используем равенство сторон правильного шестиугольника радиусу описанной окружности. Из противоположных концов одного из диаметров окружности описываем дуги радиусом R. Точки пересечения этих дуг с заданной окружностью разделят её на 6 равных частей. Последовательно соединив найденные точки, получают правильный шестиугольник.

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

П
равильный пятиугольник может быть построен с помощью циркуля и линейки, или вписыванием его в заданную окружность, или построением на основе заданной стороны. Этот процесс описан Евклидом в его «Началах» около 300 года до н. э.

Вот один из методов построения правильного пятиугольника в заданной окружности:

Постройте окружность, в которую будет вписан пятиугольник и обозначьте её центр как O . (Это зелёная окружность на схеме справа).

Выберите на окружности точку A , которая будет одной из вершин пятиугольника. Постройте прямую через O и A .

Постройте прямую перпендикулярно прямой OA , проходящую через точку O . Обозначьте одно её пересечение с окружностью, как точку B .

Постройте точку C посередине между O и B .

C через точку A . Обозначьте её пересечение с прямой OB (внутри первоначальной окружности) как точку D .

Проведите окружность с центром в A через точку D, пересечение данной окружности с оригинальной (зелёной окружностью) обозначьте как точки E и F .

Проведите окружность с центром в E через точку A G .

Проведите окружность с центром в F через точку A . Обозначьте её другое пересечение с первоначальной окружностью как точку H .

Постройте правильный пятиугольник AEGHF .

Неразрешимые задачи

Следующие три задачи на построение были поставлены ещё в античности:

Трисекция угла - разбить произвольный угол на три равные части.

Иначе говоря, необходимо построить трисектрисы угла - лучи, делящие угол на три равные части. П. Л. Ванцель доказал в 1837 году, что задача разрешима только тогда, когда например, трисекция осуществима для углов α = 360°/n при условии, что целое число n не делится на 3. Тем не менее, в прессе время от времени публикуются (неверные) способы осуществления трисекции угла циркулем и линейкой.

Удвоение куба - классическая античная задача на построение циркулем и линейкой ребра куба, объём которого вдвое больше объёма заданного куба.

В современных обозначениях, задача сводится к решению уравнения . Всё сводится к проблеме построения отрезка длиной . П. Ванцель доказал в 1837 году, что эта задача не может быть решена с помощью циркуля и линейки.

Квадратура круга - задача, заключающаяся в нахождении построения с помощью циркуля и линейки квадрата, равновеликого по площади данному кругу .

Как известно, с помощью циркуля и линейки можно выполнить все 4 арифметических действия и извлечение квадратного корня; отсюда следует, что квадратура круга возможна в том и только в том случае, если с помощью конечного числа таких действий можно построить отрезок длины π. Таким образом, неразрешимость этой задачи следует из неалгебраичности (трансцендентности) числа π, которая была доказана в 1882 году Линдеманом.

Другая известная неразрешимая с помощью циркуля и линейки задача - построение треугольника по трём заданным длинам биссектрис .

Причём эта задача остаётся неразрешимой даже при наличии трисектора.

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

А ЗНАЕТЕ ЛИ ВЫ, ЧТО...

(из истории геометрических построений)

Когда-то в построение правильных многоугольников вкладывали мистический смысл.

Так, пифагорейцы, последователи религиозно-философского учения, основанного Пифагором, и жившие в древней Греции (V I-I V вв. до н. э.), приняли в качестве знака своего союза звездчатый многоугольник, образованный диагоналями правильного пятиугольника.

Правила строгого геометрического построения некоторых правильных многоугольников изложены в книге «Начала» древнегреческого математика Евклида, жившего в III в. до н.э. Для выполнения этих построений Евклид предлагал пользоваться только линейкой и циркулем, который в то время был без шарнирного устройства соединения ножек (такое ограничение в инструментах было непреложным требованием античной математики).

Правильные многоугольники нашли широкое применение и в античной астрономии. Если Евклида построение этих фигур интересовало с точки зрения математики, то для древнегреческого астронома Клавдия Птолемея (около 90 - 160 г. н. э.) оно оказалось необходимым как вспомогательное средство при решении астрономических задач. Так, в 1-й книге «Альмагесты» вся десятая глава посвящена построению правильных пяти- и десятиугольников.

Однако помимо чисто научных трудов, построение правильных многоугольников было неотъемлемой частью книг для строителей, ремесленников, художников. Умение изображать эти фигуры издавна требовалось и в архитектуре, и в ювелирном деле, и в изобразительном искусстве.

В «Десяти книгах о зодчестве» римского архитектора Витрувия (жившего примерно в 63 -14 гг. до н. э.) говорится, что городские стены должны иметь в плане вид правильного многоугольника, а башни крепости «следует делать круглыми или многоугольными, ибо четырехугольник скорее разрушается осадными орудиями».

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

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

Правильный шестиугольник явился предметом специального исследования великого немецкого астронома и математика Иоганна Кеплера (1571-1630), о котором он рассказывает в своей книге «Новогодний подарок, или о шестиугольных снежинках». Рассуждал о причинах того, почему снежинки имеют шестиугольную форму, он отмечает, в частности, следующее: «...плоскость можно покрыть без зазоров лишь следующими фигурами: равносторонними треугольниками, квадратами и правильными шестиугольниками. Среди этих фигур правильный шестиугольник покрывает наибольшую площадь»

0дним из наиболее известных ученых, занимавшихся геометрическими построениями, был великий немецкий художник и математик Альбрехт Дюрер (1471 -1528), который посвятил им значительную часть своей книги «Руководства...». Он предложил правила построения правильных многоугольников с 3. 4, 5... 16-ю сторонами. Методы деления окружности, предложенные Дюрером, не универсальны, в каждом конкретном случае используется индивидуальный прием.

Дюрер применял методы построения правильных многоугольников в художественной практике, например, при создании разного рода орнаментов и узоров для паркета. Наброски таких узоров были сделаны им во время поездки в Нидерланды, где паркетные полы встречались во многих домах.

Дюрер составлял орнаменты из правильных многоугольников, которые соединены в кольца (кольца из шести равносторонних треугольников, четырех четырехугольников, трех или шести шестиугольников, четырнадцати семиугольников, четырех восьмиугольников).

Заключение

Итак, геометрические построения - это способ решения задачи, при котором ответ получают графическим путем. Построения выполняют чертежными инструментами при максимальной точности и аккуратности работы, так как от этого зависит правильность решения.

Благодаря этой работе я познакомилась с историей возникновения циркуля, подробнее познакомилась с правилами выполнения геометрических построений, получила новые знания и применила их на практике.
Решение задач на построение циркулем и линейкой – полезное времяпровождение, позволяющее по-новому посмотреть на известные свойства геометрических фигур и их элементов. В данной работе рассмотрены наиболее актуальные задачи, связанные с геометрическими построениями с помощью циркуля и линейки. Рассмотрены основные задачи и даны их решения. Приведенные задачи имеют значительный практический интерес, закрепляют полученные знания по геометрии и могут использоваться для практических работ.
Таким образом, цель работы достигнута, поставленные задачи выполнены.

Энциклопедичный YouTube

1 / 5

Построения циркулем и линейкой, часть 1.

1 Простейшие построения циркулем и линейкой

Science show. Выпуск 19. Циркуль и линейка

Геометрия - Построение правильного треугольника

Геометрия - Построение восьмиугольника

Субтитры

Примеры

Задача на бисекцию . С помощью циркуля и линейки разбить данный отрезок AB на две равные части. Одно из решений показано на рисунке:

• Циркулем проводим окружности с центром в точках A и B радиусом AB .
• Находим точки пересечения P и Q двух построенных окружностей (дуг).
• По линейке проводим отрезок или линию, проходящую через точки P и Q .
• Находим искомую середину отрезка AB - точку пересечения AB и PQ .

Формальное определение

В задачах на построение рассматриваются множество следующих объектов: все точки плоскости, все прямые плоскости и все окружности плоскости. В условиях задачи изначально задается (считается построенными) некоторое множество объектов. К множеству построенных объектов разрешается добавлять (строить):

1. произвольную точку;
2. произвольную точку на заданной прямой;
3. произвольную точку на заданной окружности;
4. точку пересечения двух заданных прямых;
5. точки пересечения/касания заданной прямой и заданной окружности;
6. точки пересечения/касания двух заданных окружностей;
7. произвольную прямую, проходящую через заданную точку
8. прямую, проходящую через две заданные точки;
9. произвольную окружность с центром в заданной точке
10. произвольную окружность с радиусом, равным расстоянию между двумя заданными точками.
11. окружность с центром в заданной точке и с радиусом, равным расстоянию между двумя заданными точками.

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

Решение задачи на построение содержит в себе три существенные части:

1. Описание способа построения заданного множества.
2. Доказательство того, что множество, построенное описанным способом, действительно находится в заданном соотношении с исходным множеством. Обычно доказательство построения производится как обычное доказательство теоремы, опирающееся на аксиомы и другие доказанные теоремы.
3. Анализ описанного способа построения на предмет его применимости к разным вариантам начальных условий, а также на предмет единственности или неединственности решения, получаемого описанным способом.

Известные задачи

Другая известная и неразрешимая с помощью циркуля и линейки задача - построение треугольника по трём заданным длинам биссектрис . Интересно, что эта задача остаётся неразрешимой даже при наличии инструмента, выполняющего трисекцию угла .

Допустимые отрезки для построения с помощью циркуля и линейки

С помощью этих инструментов возможно построение отрезка, который по длине:

Для построения отрезка с длиной численно равной произведению, частному и квадратному корню из длин заданных отрезков необходимо задание на плоскости построения единичного отрезка (то есть отрезка длины 1). Извлечение корней из отрезков с иными натуральными степенями, не являющимися степенью числа 2, невозможны с помощью циркуля и линейки. Так, например, невозможно при помощи циркуля и линейки из единичного отрезка построить отрезок длиной . Из этого факта, в частности, следует неразрешимость задачи об удвоении куба.

Возможные и невозможные построения

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

Поэтому удобно говорить о построении числа - графического решения уравнения определенного типа.

Исходя из возможных построений отрезков возможны следующие построения:

• Построение решений линейных уравнений .
• Построение решений уравнений, сводящихся к решениям квадратных уравнений .

Иначе говоря, возможно строить лишь отрезки, равные арифметическим выражениям с использованием квадратного корня из исходных чисел (заданных длин отрезков).

Важно отметить, что существенно, что решение должно выражаться при помощи квадратных корней, а не радикалов произвольной степени. Если даже алгебраическое уравнение имеет решение в радикалах, то из этого не следует возможность построения циркулем и линейкой отрезка, равного его решению. Простейшее такое уравнение: x 3 − 2 = 0 , {\displaystyle x^{3}-2=0,} связанное со знаменитой задачей на удвоение куба, сводящаяся к этому кубическому уравнению. Как было сказано выше, решение этого уравнения ( 2 3 {\displaystyle {\sqrt[{3}]{2}}} ) невозможно построить циркулем и линейкой.

Возможность построить правильный 17-угольник следует из выражения для косинуса центрального угла его стороны:

Вариации и обобщения

• Построения с помощью одного циркуля. По теореме Мора - Маскерони с помощью одного циркуля можно построить любую фигуру, которую можно построить циркулем и линейкой. При этом прямая считается построенной, если на ней заданы две точки.
• Построения с помощью одной линейки. Очевидно, что с помощью одной линейки можно проводить только проективно-инвариантные построения. В частности,
  • невозможно даже разбить отрезок на две равные части,
  • также невозможно найти центр данной окружности.

• при наличии на плоскости заранее проведённой окружности с отмеченным центром с одной линейкой можно провести те же построения, что и циркулем и линейкой (

Если вполне естественно, что с допущением большего разнообразия инструментов оказывается возможным решать более обширное множество задач на построение, то можно было бы предвидеть, что, напротив, при ограничениях, налагаемых на инструменты, класс разрешимых задач будет суживаться. Тем более замечательным нужно считать открытие, сделанное итальянцем Маскерони (1750-1800): все геометрические построения, выполнимые с помощью циркуля и линейки, могут быть выполнены с помощью одного только циркуля. Следует, конечно, оговорить, что провести на самом деле прямую линию через две данные точки без линейки невозможно, так что это основное построение не покрывается теорией Маскерони. Вместо того приходится считать, что прямая задана, если заданы две ее точки. Но с помощью одного лишь циркуля удается найти точку пересечения двух прямых, заданных таким образом, или точку пересечения прямой с окружностью.

Вероятно, простейшим примером построения Маскерони является удвоение данного отрезка Решение было уже дано на стр. 185. Далее, на стр. 186 мы научились делить данный отрезок пополам. Посмотрим теперь, как разделить пополам дугу окружности с центром О. Вот описание этого построения. Радиусом проводим две дуги с центрами От точки О откладываем на этих дугах две такие дуги и что Затем находим точку пересечения дуги с центром Р и радиусом и дуги с центром и радиусом Наконец, взяв в качестве радиуса отрезок опишем дугу с центром Р или до пересечения с дугой точка пересечения и является искомой средней точкой дуги Доказательство предоставляем читателю в качестве упражнения.

Рис. 48. Пересечение окружности и прямой, не проходящей через центр

Было бы невозможно доказать основное утверждение Маскерони, указывая для каждого построения, выполнимого с помощью циркуля и линейки, как его можно выполнить с помощью одного циркуля: ведь возможных построений бесчисленное множество. Но мы достигнем той же цели, если установим, что каждое из следующих основных построений выполнимо с помощью одного циркуля:

1. Провести окружность, если заданы центр и радиус.

2. Найти точки пересечения двух окружностей.

3. Найти точки пересечения прямой и окружности.

4. Найти точку пересечения двух прямых.

Любое геометрическое построение (в обычном смысле, с допущением циркуля и линейки) составляется из выполнения конечной последовательности этих элементарных построений. Что первые два из них выполнимы с помощью одного циркуля, ясно непосредственно. Более трудные построения 3 и 4 выполняются с использованием свойств инверсии, рассмотренных в предыдущем пункте.

Обратимся к построению 3: найдем точки пересечения данной окружности С с прямой, проходящей через данные точки Проведем дуги с центрами и радиусами, соответственно равными и кроме точки О, они пересекутся в точке Р. Затем построим точку обратную точке Р относительно окружности С (см. построение, описанное на стр. 186). Наконец, проведем окружность с центром и радиусом (она непременно пересечется с С): его точки пересечения с окружностью С и будут искомыми. Для доказательства достаточно установить, что каждая из точек находится на одинаковых расстояниях от (что касается точек то аналогичное их свойство сразу вытекает из построения). Действительно, Достаточно сослаться на то обстоятельство, что точка, обратная точке отстоит от точек на расстояние, равное радиусу окружности С (см. стр. 184). Стоит отметить, что окружность, проходящая через точки является обратной прямой в инверсии относительно круга С, так как эта окружность и прямая пересекаются

Рис. 49. Пересечение окружности и прямой, проходящей через центр

с С в одних и тех же точках. (При инверсии точки основной окружности остаются неподвижными.)

Указанное построение невыполнимо только в том случае, если прямая проходит через центр С. Но тогда точки пересечения могут быть найдены посредством построения, описанного на стр. 188, как получающихся, когда мы проводим произвольную окружность с центром В, пересекающуюся с С в точках Метод проведения окружности, обратной прямой, соединяющей две данные точки, немедленно дает и построение, решающее задачу 4. Пусть прямые даны точками (рис. 50).

Рис. 50. Пересечение двух прямых

Проведем произвольную окружность С и с помощью указанного выше метода построим окружности, обратные прямым и Эти окружности пересекаются в точке О и еще в одной точке Точка X, обратная точке и есть искомая точка пересечения: как ее построить - уже было разъяснено выше. Что X есть искомая точка, это ясно из того факта, что есть единственная точка, обратная точке, одновременно принадлежащей обеим прямым и следовательно, точка X, обратная должна лежать одновременно и на и на

Этими двумя построениями заканчивается доказательство эквивалентности между построениями Маскерони, при которых разрешается пользоваться только циркулем, и обыкновенными геометрическими построениями с циркулем и линейкой.

Мы не заботились об изяществе решения отдельных проблем, нами здесь рассмотренных, так как нашей целью было выяснить внутренний смысл построений Маскерони. Но в качестве примера мы еще укажем построение правильного пятиугольника; точнее говоря, речь идет о нахождении каких-то пяти точек на окружности, которые могут служить вершинами правильного вписанного пятиугольника.

Пусть А - произвольная точка на окружности К. Так как сторона правильного вписанного шестиугольника равна радиусу круга, то не представит труда отложить на К такие точки что

Данная статья написана по материалам одного из разделов книги Седжвика, Уэйна и Дондеро "Программирование на языке Python", уже упоминавшейся ранее . Называется этот раздел "Системы итерационных функций", и в нём описано построение различных изображений, таких как треугольник Серпиньского, папоротник Барнсли и некоторых других, с помощью достаточно несложного алгоритма, который, к тому же, ещё и с лёгкостью реализуется.

Начну я с описания данного алгоритма. Я буду использовать математическую терминологию, в том числе, и ту, которую авторы книги, в ходе своего повествования, не задействуют. Сугубо математический взгляд на алгоритмы облегчает мне их понимание, да и излагать их с помощью математического языка мне достаточно удобно.

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

За теоретической частью статьи будет следовать практическая, описывающая реализацию алгоритма на языке C99. Поскольку результатами работы программы будут являться изображения, мы будем использовать в программе графическую библиотеку pgraph , предполагая, что читатель, хотя бы в общих чертах, с ней знаком.

Итак, переходим к теоретической части нашего повествования.

Итерационные функции и случайные последовательности

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

Зададим 2 последовательности, x n n = 1 ∞ и y n n = 1 ∞ , с помощью следующих рекуррентных формул:

X n = f x n - 1 , y n - 1 , n ∈ ℕ , y n = g x n - 1 , y n - 1 , n ∈ ℕ .

Поясним, что x 0 и y 0 - это некоторые заранее заданные числа, а f (x , y ) и g (x , y ) - это некоторые функции двух переменных, называемые итерационными . Сам процесс вычисления очередного члена той или иной последовательности через такие функции будем называть итерациями , а приведённый выше набор рекуррентных формул - итерационной схемой.

Рекурсивный способ задания последовательностей, скорее всего, хорошо знаком читателю, если он изучал математику в вузе. Несколько необычным может показаться "перекрёстный" способ вычисления членов последовательностей, при котором для вычисления n -го члена каждой из двух последовательностей нужен не только n − 1-й член той же последовательности, но и n − 1-й член другой.

А теперь рассмотрим схему построения членов двух последовательностей, использующую не одну пару итерационных функций, а m пар. Каждая из этих функций будет линейной по обеим переменным, а также будет содержать аддитивную константу. Более конкретно, функции будут иметь вид:

F k x , y = a k x + b k y + c k g k x , y = d k x + e k y + h k , k = 0 , 1 , … , m - 1 .

Для каждого n , начиная с 1, будет случайным образом выбираться число от 0 до m − 1, и при вычислении x n и y n в рекуррентных формулах будет использоваться пара итерационных функций, индексы которых равны данному случайному числу. Отметим, что случайные числа, "появляющиеся" перед каждой итерацией, не обязаны быть равновероятными. Однако для разных шагов вероятность появления конкретного фиксированного числа одна и та же.

Давайте теперь сформулируем сказанное на строгом математическом языке. Рассмотрим последовательность дискретных независимых в совокупности случайных величин T n = 1 ∞ , распределённых по одному и тому же закону. А именно: каждая случайная величина принимает значения 0, 1, …, m − 1 с соответствующими вероятностями p 0 , p 1 , …, p m -1 .

Теперь последовательности, x n n = 1 ∞ и y n n = 1 ∞ зададим с помощью следующей итерационной схемы:

X n = f T n x n - 1 , y n - 1 , n ∈ ℕ , y n = g T n x n - 1 , y n - 1 , n ∈ ℕ .

Как и ранее, x 0 и y 0 - это некоторые заранее заданные числа.

Таким образом, каждая из последовательностей является случайной, т. е. её члены - это случайные величины. Однако, каждую из этих последовательностей можно "реализовать", т. е. вычислить все её члены (разумеется, таких реализаций будет бесконечно много).

Зададимся главным вопросом данного раздела. А какое же отношение изображения, которые мы собираемся строить, имеют к этой паре случайных последовательностей? Очень простое. Построим реализацию этих двух последовательностей. Для каждого натурального n пару (x n , y n ) можно рассматривать как координаты точки, заданной в декартовой прямоугольной системе координат на плоскости. Так вот, изображение, соответствующее некоторой паре реализованных последовательностей, представляет собой геометрическое место всех таких точек на плоскости.

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

Добавим, что при построении изображений на компьютере, мы, разумеется, будем выполнять лишь конечное (но достаточно большое) число итераций.

О генерации псевдослучайных чисел

При написании программы мы столкнёмся с необходимостью генерировать псевдослучайные числа, распределённые, вообще говоря, не равномерно, а по заранее заданному закону. В то же самое время, мы будем располагать лишь программным генератором псевдослучайных чисел, равномерно распределённых на промежутке . Как из второго распределения получить первое?

Переведём задачу в математическую плоскость. Пусть имеется непрерывная случайная величина U , распределённая равномерно на отрезке . Зададимся целью построить дискретную случайную величину T как функцию от U , таким образом, чтобы T принимала значения 0, 1, …, m − 1 с соответствующими вероятностями p 0 , p 1 , …, p m -1 .

Решить поставленную задачу весьма просто. Введём в рассмотрение суммы вероятностей

Если верхний предел суммирования по i меньше нижнего, то такую сумму по определению будем полагать равной 0.

Т выразим через U следующим образом:

T = 0 , если U ∈ s 0 , s 1 , 1 , если U ∈ s 1 , s 2 , 2 , если U ∈ s 2 , s 3 , … … … … … … , … … … … … … , m - 1 , если U ∈ s m - 1 , 1 .

Очевидно, случайная величина T распределена по требуемому нами закону. Заметим, что, по сути, Т - это номер промежутка, в который попадает случайная величина U (при условии, что промежутки мы нумеруем числами от 0 до m − 1 в порядке возрастания их левых границ).

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

А теперь можно переходить к написанию программы.

Структура программы

Программа состоит из файла main.c и файлов, образующих графическую библиотеку pgraph. Содержимое файла main.c начинается со следующей директивы, подключающей графическую библиотеку:

Далее в файле содержатся описания глобальных константных переменных и константных массивов. За ними - определения функций get_random_value() и main() . Первая из них генерирует псевдослучайные числа, а вторая выполняет основную работу по построению изображений.

Глобальные константные переменные и константные массивы

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

Ниже приводятся описания данных констант и массивов.

• n - количество итераций;
• w - ширина изображения в пикселях;
• h - высота изображения в пикселях;
• xc - абсцисса начала новой системы координат в старой системе;
• yc - ордината начала новой системы координат в старой системе;
• l - длина в пикселях отрезка, параллельного одной из осей координат, имеющего в новой системе координат единичную длину;
• m - количество пар итерационных функций, т. е. число m ;
• s - одномерный массив размера m , содержащий суммы вероятностей случайных величин T n (k -й элемент массива содержит s k );
• f - двухмерный массив, состоящий из m f k (x , y k , 0), (k , 1), (k , 2) содержат числа a k , b k , c k соответственно, где 0 ≤ k ≤ m − 1);
• g - двухмерный массив, состоящий из m "строк" и 3-х "столбцов", содержащий константы, задействованные в функциях g k (x , y ) (элементы массива с индексами (k , 0), (k , 1), (k , 2) содержат числа d k , e k , h k соответственно, где 0 ≤ k ≤ m − 1).

Все переменные имеют тип int , а базовым типом всех массивов является double .

Поясним, что под "старой" системой координат подразумевается та, которая определена в библиотеке pgraph. Построения всех изображений будут вестись в новой системе, полученной из старой параллельным переносом (сдвиги по осям абсцисс и ординат равны соответственно x c и y c ) и "сжатием" в l раз. Таким образом, точка, имеющая в новой системе координаты (x , y ), в старой будет иметь координаты (x l + x c , y l + y c ). Излишне, думаю, пояснять, что за хранение чисел x c , y c и l ответственны константные переменные xc , yc и l соответственно.

Для хранения чисел x 0 и y 0 переменные не выделяются, поскольку во всех случаях построения изображений в качестве этих чисел берутся нули.

Генерация псевдослучайных чисел: функция get_random_value()

Функция get_random_value() при каждом обращении к ней генерирует псевдослучайное целое число в диапазоне от 0 до m − 1 в соответствии с описанной ранее схемой . Вот код этой функции:

Получаем с помощью стандартной библиотечной функции rand() псевдослучайное число в диапазоне от 0 до значения макроса RAND_MAX , делим полученный результат на это значение и присваиваем частное переменной r (стр. 3). Теперь в r хранится число, принадлежащее отрезку . Его приближённо можно считать значением случайной величины, равномерно распределённой на этом отрезке.

Поясним, что значение макроса RAND_MAX , в нашем случае (т. е. в случае использования компилятора MinGW64 версии 4.9.2 для 64-битных систем) равно 32767.

Теперь, с помощью линейного поиска, задействующего цикл while , ищем индекс наибольшего элемента массива s , не превосходящего значение r , увеличенный на единицу, и сохраняем его в переменной c (см. стр. 4-6). Отметим, что в случае, если значение r - нулевое, цикл не выполняется ни разу, а переменная с сохраняет единичное значение (см. стр. 4).

Значение, возвращаемое функцией, можно приближённо рассматривать как значение случайной величины T , описанной в упомянутом выше разделе.

Генерация изображения: функция main()

А вот и код функции main() :

Создаём изображение с заданными размерами (стр. 3). Выделяем память под переменные x и y , в которых будут храниться текущие члены последовательностей, и инициализируем их нулями (стр. 4). Напомню, что в качестве чисел x 0 и y 0 , участвующих в вычислении первых членов каждой из последовательностей, берутся нули.

Вычисляем в цикле for первые n членов каждой последовательности (стр. 5-13). Получаем сначала псевдослучайное число и записываем его в r (стр. 7). Далее вычисляем текущие значения членов обеих последовательностей, помещая их во временные переменные x1 и y1 (стр. 8, 9). При вычислении используем константы, фигурирующие в итерационных функциях и хранящиеся в массивах f и g . Выбор той или иной пары наборов коэффициентов (а значит, пары итерационных функций) зависит от значения r , использующегося в качестве первых индексов участвующих в вычислениях элементов массивов.

Переписываем вычисленные текущие значения в переменные x и y (стр. 10, 11). Координаты точки, содержащиеся в этих переменных, переводим в координаты исходной системы координат, округляем до целых и наносим точку с результирующими координатами на изображение чёрным цветом (стр. 12).

По завершении цикла сохраняем сформированное изображение в файле "out.bmp" (стр. 14) и освобождаем занимаемую изображением память (стр. 15). На этом работа функции завершается.

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

Треугольник Серпиньского представляет собой множество точек, получаемого из всех точек некоторого исходного равностороннего треугольника следующим образом. Треугольник разбивается тремя средними линиями на 4 треугольника, после чего "центральный" треугольник удаляется. Далее c каждым из оставшихся трёх равносторонних треугольников выполняется та же операция. Наконец, то же самое мы делаем с получившимися девятью равносторонними треугольниками.

Продолжая описанные операции до бесконечности, удаляем, в итоге, из исходного треугольника бесконечное число равносторонних треугольников, сумма площадей которых равна площади исходного. Оставшиеся точки образуют линию, называемую треугольником Серпиньского , играющую важную роль в теории множеств.

В книге Седжвика и других авторов предлагается следующий способ построения изображения треугольника Серпиньского. Рассмотрим 3 точки на плоскости, являющиеся вершинами равностороннего треугольника, например, точки с координатами 0 , 0 , 0 , 1 , 1 / 2 , 3 / 2 в декартовой прямоугольной системе координат. Выбираем наугад (с равными вероятностями) одну из трёх вершин треугольника и строим точку, делящую отрезок, соединяющий вершину с координатами 0 , 0 и выбранную наугад вершину, пополам. Это первая точка нашего изображения.

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

Нам потребуются 3 пары итерационных функций. Их индексы 0, 1, 2 должны выбираться с вероятностями 1/3, 1/3, 1/3 соответственно. Сами итерационные функции приведены ниже.

F 0 x , y = 1 / 2 x , g 0 x , y = 1 / 2 y , f 1 x , y = 1 / 2 x + 1 / 2 , g 1 x , y = 1 / 2 y , f 2 x , y = 1 / 2 x + 1 / 4 , g 2 x , y = 1 / 2 y + 3 / 4 .

Теперь давайте вставим в нашу программу описания глобальных константных переменных и константных массивов, соответствующие данным вероятностям и данным итерационным функциям. Но для начала определим макрос TRIANGLE , поместив в файл main.с после инструкции #include следующую инструкцию

После инструкции вставляем в файл следующий код: