БИБЛИОТЕЧКА «ПЕРВОГО СЕНТЯБРЯ»
Серия «Информатика»
Выпуск 23
Д.М. Златопольский
ЗАМЕЧАТЕЛЬНЫЕ КРИВЫЕ
Москва
Чистые пруды
2008

УДК 372.800.2
ББК 74.263.2
3-67
Обш&ремштсерт'ЧЛн+оршсгюсГ-.СЛОстровежшй
На обложке — кривая Гильберта.
Златопол^скяЙ ДЛИ.
3-67 Замечательные кривые / Д.М. Златопольскнй. - М.: Чистые пруды,
2008. - 32 с. (Библиотечка "Первого сентября'*, серия "Информатика".
Вып. 23).
ISBN 978-5-9667-0485-8
В брошюре приведена методика разработки программ, изображающих на экране
три замечательные кривые (кривую Гильберта, кривую Серпнмского и кривую
дракона). Подготовка таких программ может быть предложена учащимся при выполнении
мини-проектов по программированию. Используете* школьный алгоритмический
язык. Русский синтаксис этого языка делает приведенные программы понятными
и легко переносимыми на любой другой язык программирования.
УДК 372.800.2
ББК 74.263.2
Учебное издание
ЗЛАТОПОЛЬСКНЙ Дмитрий Михайлович
ЗАМЕЧАТЕЛЬНЫЕ КРИВЫЕ
Редактор С.Л. Островский
Корректор ЕЛ. Володина
Компьютерная верстка НИ. Пропекая
Свидетельство о регистрации СМИ ПИ № ФС77-19078 от 08.12.2004 г.
Подписано в печать 17.06.2008.
Формат 60х90'/|(|. Гарнитура "Тайме". Печать офсетная. Печ. л. 2,0.
Заказ -1795. Тираж - 6400 экз.
ООО "Чистые пруды", ул.-Киевская, 24, Москва, I21165
Тел. D99) 249-28-77, http://www.lseptember.ra
Отпечатало с готовых диапозитивов в филиале ГУЛ МО "КТ" "Раменская типография"
Сафоновский пр., д. 1, г. Раменское, МО, 140100
Тел. D95) 377-07-83. E-mail: ramentip@maii.ru
ISBN 978-5-9667-0485-8
© ООО "Чистые пруды", 2008

ПРЕДИСЛОВИЕ
Рисунок, представленный на обложке настоящей брошюры, называется
"кривая Гильберта", а показанный на рис. 1 — "кривая Серпинского".
Рис.1
Эти кривые связаны с любопытным понятием теории функций, а
именно — всюду плотными кривыми. Кривая на плоскости.называется всюду
плотной в некоторой области, если она проходит через любую сколь угодно
малую окрестность каждой точки этой области. Несколько упрощенно можно
считать, что всюду плотные кривые целиком заполняют указанную область.
Известные математики Давид Гильберт и Вацлав Серпинский (Серпиньский)
построили примеры всюду плотных кривых. Хотя эти примеры различны,
схема получения соответствующих кривых одинакова. По определенному
правилу строятся кривые (соответственно Гильберта и Серпинского) первого,
второго,..., л-ro порядка, вписанные в заданный квадрат. При
неограниченном возрастании п они стремятся к некоторой предельной кривой, которая
является всюду плотной в заданном квадрате.
Еще одно интересное изображение показано на рис. 2. На нем
представлена линия, которую можно получить следующим образом. Возьмем длинную
полоску бумаги и сложим ее пополам, а затем развернем на 90°. Если смотреть
на полоску сбоку, то получится ломаная линия из двух перпендикулярных
участков (см. рис. 3d). Теперь сложим полоску пополам дважды и также
дважды развернем на 90° так, как это показано на рис. 36. Получим ломаную
линию уже из четырех отрезков, причем угол между смежными отрезками
составляет 90°. Наконец, если сложение и разворачивание полоски
осуществить три раза, то в результате получится фигура, представленная на рис. Зв.
Продолжая этот процесс, можно получить кривую, аналогичную той,
которая показана на рис. 2 (прямые углы у линии на этом рисунке скруглены).
Попробуйте проследить за всеми поворотами линии, и вы поймете, почему
3

эту причудливую кривую называют "кривой дракона. Способ построения
подсказывает, что она не имеет самопересечений даже при неограниченном
увеличении количества перегибов бумажки.
в)
Рис.3
' Кривая дракона в популярной литературе впервые была описана в 1967 году в журнале
"Scientific American". Заметка о ней появилась в колонке "Математические игры", которую
вел выдающийся американский популяризатор науки Мартин Гарднер. Первоначально
использовалось полное название кривой — "дракон Хартера — Хейтуэя", которое ей дал
основатель компьютерной фрактальной геометрии Бенуа Мандельброт, чьим именем названо
знаменитое множество. В дальнейшем стали говорить просто о кривой дракона.
4

Методика разработки программ, изображающих на экране три
перечисленные замечательные кривые (кривую Гильберта, кривую Серпинского и
кривую дракона), приведена ниже. Но, прежде чем описывать эту методику,
заметим, что при построении кривых используется такой прием
программирования, как рекурсия. Поэтому сначала — о ней.
РЕКУРСИЯ
Рекурсией (от лат. recursio — возвращение) называют ситуацию в
программе, когда процедура или функция вызывает в качестве вспомогательной
саму себя. Дело в том, что иногда, разрабатывая программу, удается свести
исходную задачу к более простым задачам. Среди них может оказаться
и первоначальная задача, но в упрощенной форме. Например, поскольку
факториал натурального числа п (обозначаемый и!) равен 1 • 2 • 3 • ... • и, то
можем записать, что и! = (и - 1)! ¦ п. Это значит, что вычисление значения
функции F(n), определяющей факториал натурального числа п, сводится к
вычислению F(n - 1) и умножению результата на п:
алг цел Факториал(арг цел п)
нач
зиач := Факториал(п - 1) * п |Рекурсивный вызов
Iфункции Факториал
|знач - значение функции
кон
На самом деле функция Факториал оформлена не по правилам2 — в
таком виде она приведена исключительно с целью показать использование
рекурсии. При использовании рекурсии необходимо, чтобы рекурсивные
вызовы осуществлялись только по условию, которое когда-то станет ложным.
В случае расчета факториала рекурсивная (вызывающая саму себя в качестве
вспомогательной) функция должна быть оформлена так:
алг цал Факториал(арг цел п)
нач
если п > 1
то
I Рекурсивный вызов функции Факториал
знач := Факториал(п - 1) * п
иначе
знач := 1
все
кон
2 Поэтому при выполнении программы появится сообщение об ошибке.
5

Иными словами, при некоторых значениях параметра рекурсивной
функции рекурсия использоваться не должна.
Вот еще задача* "Разработать функцию для расчета k-го члена
последовательности Фибоначчи (последовательность Фибоначчи образуют числа
1, 1, 2, 3, 5, 8, 13,...)".
Сначала попробуйте создать такую функцию, не применяя
рекурсию. Если вы готовы это сделать, то не смотрите на приведенный далее
вариант:
•Hsdii XiH9A3tre иипкнХв1Ээт1Гэс1и 'хнэиэие— tradutradu
:Ххнэиэ1ге XwoHffadshO иипкнХнюэтСэаи 'хнэиэие — tradu
:и1эоня1/Э1В801Гэи'зоц хнэиэге иимэваихиьэовс! ион1ГэAэьо — dario
:ганиьи1гэа antnoiXlteiro пнвяоеяичшэи
КОХ
dsbo =: мт
da^o =: tradu
tradu =: tradutradu
tradutradu + tradu =: daho
j - >( off j »o т жив Si
X =: tradutradu
X =: tradu
t 'tradutradu 'tradu 'daho vS5 ь«м
(>( 555 оЗв)диф trmfa лгп
Быстро ли вы получили требуемую функцию? А теперь посмотрите, как
прост и логичен рекурсивный вариант функции:
алг нал Фиб(арг цел к)
нач
•ели к > 2
то
I Рекурсивный вызов функции Фиб
аиач : = Фиб(к - 2) + Фиб(к - 1)
иначе
анач : = 1
асе
КОН
Большое число задач с использованием рекурсии приведено в статье [1]
и в книге [2].
Рекурсия может быть также применена при построении графических
изображений, например, таких, как нарис. 4 и 5.
6

bJbk
^v
<
>
V
Рис.4
Рис.5
div(xb
div(xa
div(xa
+
+
+
xc,
xc,
xb,
2);
2);
2);
УР
yq
yr
:= div(yb +
:= div(ya +
:= div(ya +
yc,
yc,
yb,
2)
2)
2)
Картинка на рис. 4 получена так. В треугольнике проводятся все средние
линии. Тем самым он разбивается на 4 треугольника. К трем из них,
примыкающим к вершинам первоначального треугольника, применяются те же
действия (рекурсия!). Рекурсивная процедура Треугольник, в которой это
реализуется, имеет вид:
аяг Треугольник («рг цел ха, уа, xb, yb, хс, ус, п)
мая дал хр, ур, xq, yq, xr, yr
•оли n > 0 |Порядок фигуры
то
IКоординаты середин сторон треугольника
хр
xq
хр
поз(хр, ур)
IРисуем средние линии
линия(xq, yq)
линия(хг, yr)
линия(хр, ур)
I Рекурсивно вызываем процедуру Треугольник
Треугольник(ха, уа, xr, yr, xq, yq, n - 1) |для каждой
Треугольник(хЬ, yb, хр, ур, xr, yr, п - 1) |из трех
Треугольник(хс, ус, xq, yq, хр, ур, п - 1) |сторон
ее
кон
— где div — функция, возвращающая результат целочисленного деления
своего первого аргумента на второй. В других языках программирования
используется не функция, а специальная операция.
Основная часть программы:
алг Множество_ треугольников
нач цел п, ха, уа, xb, yb, хс, ус, Нэкр, Вэкр
I I Устанавливаем графический режим работы монитора
| видеоA7)
7

Нэкр := 480 |Высота экрана в этом режиме
Вэкр := 640 |Ширина экрана
IКоординаты вершин самого большого треугольника
хс := 0; ус := 0
xb := Вэкр; yb := Нэкр
ха := 0; уа := Нэкр
поз(ха, уа)
I Рисуем самый большой треугольник
линия(xb, yb)
линия(хс, ус)
линия(ха, уа)
п := 6
I Начинаем рисовать внутренние треугольники
Треугольник(ха, уа, xb, yb, хс, ус, п)
кон
Изображение на рис. 5 получено следующим образом. На каждой из
сторон внутреннего (самого большого) квадрата нарисованы 3 стороны малого
квадрата, на каждой из сторон которого также изображены 3 стороны еще
меньшего квадрата и т.д. Процедура, которая выполняет соответствующие
действия на некотором отрезке с координатами концов xa, уа, xb,yb, может
быть оформлена следующим образом:
«яг Сторона(арг цтл ха,
хач дал хр, ур, xq, yq,
Ixp, ур, xq, yq, xr, yr, xs, ys - координаты вершин
I малого квадрата
n - 0
то
линия(xb, yb)
уа, xb,
xr, yr,
yb, n, вед k)
xs, уз, dx, dy
dx := цел @.5 * A - k) * (xb - xa))
dy := цел@.5 * A - k) * (yb - ya))
Ik — коэффициент уменьшения размера квадратов
I Координаты фигуры, изображаемой на отрезке ab:
хр := ха + dx; ур := уа + dy
xs := xb - dx; ys := yb - dy
xq := xp + (ys - yp); yq := yp - (xs - xp)
xr : = xq + (xs - xp); yr := yq + (ys - yp)
линия(xp, yp) |К началу малого квадрата
I Рекурсивное использование процедуры Сторона
Сторона (хр, ур, xq, yq, n - 1, k)
Сторона (xq, yq, xr, yr, n - 1, k)
Сторона (xr, yr, xs, ys, n - 1, k)
линия(xb, yb) IК концу отрезка
mam
кок
8

Основная часть программы:
ус, Ь, Нэкр, Вэкр,
Картинка
нач ц»л п, хс,
видеоA7)
Нэкр := 480 |Высота экрана
Вэкр := 640 |Ширина экрана
хс := div(B3Kp, 2); ус := div(H3Kp,
Ь := 100
= 0.4
ус - Ь)
УС
ус
ус
УС
п := 5; к
поз(хс - Ь,
Сторона(хс
Сторона(хс
Сторона(хс
Сторона(хс
КОК
Ь,
Ь,
Ь,
Ь,
I Точка,
- Ь, хс
- Ь,
t- Ь,
Ь Ь,
хс
хс
хс
2)
которой начинается рисунок
Ь,
Ь,
Ь,
Ь,
ус
ус
ус
ус
ь,
Ь,
Ь,
ь,
к)
к)
к)
к)
КРИВАЯ ГИЛЬБЕРТА
Кривая Гильберта первого порядка, обозначаемая #,\ похожа на
изображение буквы П, вычерченной в виде трех сторон квадрата, как показано
на рис. 6а.
3 С
в, &i
П U
Ci <*i
а)
d% в1
U
potior
Р Lji-I^
с, а,
б)
MJ3
в)
Рис. б. Кривые Гильберта первого, второго и третьего порядков
На рис. 66 изображена кривая Гильберта второго порядка Нг Видно, что
она состоит из кривых Я,, ориентированных в разные стороны (вниз, вправо
и вверх). Кривые Я,, составляющие кривую Я2, соединены тремя отрезками
прямых, называемых связками (на рис. 66 они вычерчены более тонкими
линиями). В действительности эти отрезки должны иметь одинаковую
толщину с другими линиями, тонкими они показаны единственно с целью
демонстрации способа получения Нг из Я,.
Аналогично фигуру Я, (рис. бе) можно рассматривать как состоящую
из четырех кривых Я2 (ориентированных в разные стороны) и трех связок.
' Использована латинская буква Я, с которой начинается фамилия ученого — автора
кривой (Hilbert).

Заметим, что отрезки, образующие линию #,, можно рассматривать как
связки, соединяющие 4 точки — кривые Гильберта нулевого порядка.
Таким образом, кривую Гильберта i-го порядка Н. можно получить из
четырех кривых Ht _,, ориентированных в разные стороны, и трех связок.
Это означает, что для ее изображения можно использовать рекурсию. Если
процедуры рисования кривых Я, ориентированных вверх, вниз, влево и
вправо, обозначить соответственно Heeepx(i), Нвнизф, Нвлевоф и Henpaeo(i),
а процедуры рисования связок—стрелками, то можно составить следующие
рекурсивные схемы построения этих кривых:
| Нвверхф'. Нвправф - 1); f; Heeepx(i - 1); —>; Heeepx(i - 1); [;
НвлевоЦ -1);
91
-
Henpaeo(i): Heeepx(i - 1); —»; Henpaeo(i - 1); f; Henpaedi - 1); •
НвнизЦ- 1);
[Нвнизфг. НвлевоЦ-1% 1;НвнизA- 1); *-%H«maHi- 1); |; HenpaeoQ- 1);
I Нвяевсф. НвтаЦ - X% «-; НвлевсЦ - IX i; НвдевоЦ -1); —>; HeeepxQ -1).
Например, процедура Наверх может быть оформлена следующим образом:
тяг Нвверх(«рг пля 1)
S
•олк i > О4
22
НвправоЦ - 1)
ЛинияВверх
НвверхЦ - 1)
ЛинияВправо
Наверх(i - 1)
ЛинияВниз
НвяевоЦ - 1)
ЪтлЛ1тияВщзх,ЛинияВправо,ЛшшяВлево,ЛшшяВниз—процедуры
рисования связок между i^BHMH,Hanpa^ieHHbixcc<yrBeTCTBeHHOBBqjx,raipeB0v влево и
вниз. Построеяиеэтюсеаиокудобно выполнятьс использованием команды, которая
на школьном алгоритмическом языке называется ведаяср. Ее формат
вектор(а, Ь)
В результате выполнения этой команды проводятся, линия из текущей
позиции (хО, уО) в точку с координатами (хО + а,уО + ft); текущая позиция
4 Напомним, что рекурсивные вызовы процедур и функций должны осуществляться
по условию, которое когда-то обязательно станет ложным.
10

переносится в последнюю точку. В языках Паскаль и Си аналогом этой
команды является процедура Linerel, а в Бейсике — модификация команды
LINE: LINE -STEP (о, b), где а, Ь — приращения координат.
Если длину элементарного отрезка прямых в кривых Я, обозначить через
А, то с учетом сказанного процедуры рисования связок примут вид:
алг ЛинияВверх
м
вектор@, -h)
ЛинияВправо
векторШ, 0)
ком
ЛинияВлево
I вектор(-п, 0)
шяг ЛинияВниз
WW
I вектор@, h)
кои
Аналогично можно оформить процедуры рисования кривых Гильберта,
ориентированных вниз, влево и вправо:
«яг Нвниз(арг цел i)
мч
•ояи i > 0
52
НвлевоЦ - 1)
ЛинияВниз
Нвниз(i - 1)
ЛинияВлево
НвнизЦ - 1)
ЛинияВверх
Направо(i - 1)
НвнизД - 1)-
ЛинияВлево
АвлевоA - 1)
11

ЛинияВниз
НвлевоЦ - 1)
ЛинияВправо
НвверхЦ - 1)
¦оо
кои
алг Направо(арг цал i)
кач
•оли i > О
то
НвверхЦ - 1)
ЛинияВправо
Направо(i - 1)
ЛинияВверх
НвправоЦ.- 1)
ЛинияВлево
НвнизA - 1)
»еа
кои
Обратим внимание на то, что в приведенных процедурах рисования кривых
Гильберта используется так называемая "косвенная рекурсия"—ситуация, когда
процедура вызывает себя как вспомогательную не только непосредственно, а
также и через другую процедуру [1,2]5.
Квадрат, в который вписывается кривая Гильберта, будем называть
опорным, длину его стороны (в пикселях) обозначим через Л. Обсудим теперь
вопрос определения значения величины А в зависимости от порядка кривой /.
Из рис. 3 видно, что при / = 2 длина элементарного отрезка линии в три раза
меньше стороны опорного квадрата, при i=3—в семь раз. Отсюда получаем,
что коэффициенты уменьшения для этих элементарных отрезков в фигурах
Я,, Нг, Н},.„ образуют ряд чисел 1,3,7,..., тоест%в общем случае коэффициент
уменьшения для фигуры #у может быть вычислен по формуле 2'- 1.
Естественно расположить изображаемую кривую Гильберта по центру
экрана. Для этого надо найти координаты х0, у0 начальной точки кривой.
Проанализировав приведенные выше процедуры, можно убедиться, что
при ориентации кривой вверх и влево она начинается с левой нижней точки
опорного квадрата, т.е.
х0 = Хц - Л/2; уп = Уц + А/2,
а в остальных случаях — с правой верхней точки опорного квадрата, т.е. в
этих случаях
х0 = Хц + А/2; у0=Уц- А/2.
5 См. также приведенные ранее схемы построения кривых Гильберта.
12

Здесь Хц, Уц — координаты центра экрана.
Кроме того, удобно задавать размер опорного квадрата в процентах от
высоты экрана, поскольку она всегда меньше ширины. Эту величину
обозначим к. В программе построения кривой Гильберта ислользуем, помимо
указанных обозначений, еще переменную ориент — число, определяющее
ориентацию кривой (вверх — 1, вниз — 2, влево — 3, вправо — 4).
Вся программа имеет вид:
цвл h |Величину h описываем как глобальную
«яр Кривая _ Гильберта
мая рвя п, хО, уО, А, ориент, Нэкр, Вэкр, ввщ к
¦ Нэкр :- 480 |Высота экрана
Вэкр := 640 |Ширина экрана
|Ввод исходных данных для построения кривой Гильберта
Ж
цшол но, "Введите длину стороны опорного квадрата "
вывод "в % от высоты экрана"
ввоя к
ив при к < 100
вывод нс, "Введите порядок кривой"
ввод п
Ш
вывод не, "Введите ориентацию кривой "
вывод "(вверх - 1, вниз -'2, влево - 3, вправо - 4)"
ввод ориент
кц при (ориент >-•1) и (ориент <= 4)
| Сторона опорного квадрата
А :» цел(Нэкр * к/100)
IДлина элементарного отрезка
h :- div(S, 2 ** n - lN
ГНаходим координаты начальной точки кривой
волк ориент = 1 или ориент «= 3
32
хО := diV(B3>cp, 2) - div(A, 2)
уО :- div(H3Kp, 2) + div(A, 2)
чтшят
хб".:- а!у<Вэкр, 2)+ div(A, 2)
уО :- div(H3Kp, 2)- div(A, 2) ,
все
Устанавливаем графический режим работы экрана
видео A7)
поз(х0, уО) ^Начальная точка кривой
I Рисуем соответствующий вариант кривой Гильберта
6 О функции div см. выше примечание к программе Треугольник. Символы "**" в
школьном алгоритмическом языке обозначают знак операции возведения в степень.
13

выбор
при ориент = 1: Нвверх(п)
ориент = 2: Нвниз(п)
ориент = 3: Нвправо(п)
Нвлево(п)
кон
Чего не хватает в этой программе? Хотелось бы наблюдать
последовательность построения кривой, а для этого в конец процедур Наверх, Нвниз,
Неправо, Нвлево необходимо включить процедуру задержки. Это можно
сделать с помощью так называемого "пустого цикла" [3], а в языке
программирования Паскаль можно использовать также процедуру Delay. Отметим,
что параметр процедуры задержки надо подбирать экспериментально,
поскольку его величина зависит от быстродействия компьютера и порядка
кривой Гильберта.
КРИВАЯ СЕРПИНСКОГО
Кривая Серпинского замечательна тем, что является замкнутой кривой
без самопересечений, всюду плотной в квадрате.
Парис. 7 представлены две кривые Серпинского: первого (рис. la) и
второго (рис. 16) порядков. Обратим внимание на важную особенность кривых
Серпинского: длина горизонтальных и вертикальных отрезков кривых в два
раза больше длины горизонтальных и вертикальных проекций наклонных
отрезков.
в</^>
Рис. 7. Кривые Серпинского первого и второго порядков
Как построить кривую Серпинского? Попытка по аналогии с
алгоритмом построения кривой Гильберта использовать в качестве основного
"строительного блока" кривую S, на рис. la (возможно, без одного ребра)
14

не приведет нас к нужному решению. Кривая Серпинского состоит из
четырех звеньев А В, CD, EF и GH, каждое из которых строится
рекурсивно, соединенных четырьмя отрезками. На рис. 7 эти отрезки обозначены
ВС, DE, FG и НА.
Если процедуры рисования четырех звеньев кривой обозначить
соответственно ЛинияАВ, JIuhuhCD, JIuhmEF и JIuhuhGH, а отрезков ВС,
DE, FG и НА — соответственно OmpBC, OmpDE, OmpFG и ОтрНА, то
фрагмент, относящийся к построению кривой Серпинского (по часовой
стрелке), имеет вид:
ЛинияАВ
ОтрВС
ЛинияСБ
OrpDE
ЛинияЕГ
OTpFG
ЛинияСН
ОтрНА
Напомним, что звенья АВ, CD, EF и GH строятся рекурсивно. Чтобы
получить схемы их построения, проанализируем структуру кривой АгВг на
рис. 16. Можно увидеть, что она состоит из линий, подобных кривым AXBV
CfDr G]HI и А1В1 на рис. la, соединенных отрезками ВгСг и Н2А2, а также
горизонтальным отрезком двойной длины (см. выше), т.е. рекурсивная схема
построения кривой АВ /-го порядка следующая:
AB(l): AB(i - 1); ВС; СЩ - 1); —; GH(i - 1); НА; AB(i - 1)
Соответствующая рекурсивная процедура имеет вид:
•лг ЛинияАВ (арг цта i)
ишч
•ели i > О
«о
ЛинияАВЦ - 1)
ОтрВС
ЛинияСОЦ - 1)
ОтрВосток
ЛинияСНЦ - 1)
ОтрНА
ЛинияАВЦ - 1)
кон
—где ОтрВС, ОтрНА и ОтрВосток—соответственно процедуры рисования
отрезков ВС, НА и отрезка, изображенного на схеме в виде символа "—>".
15

Аналогично можно получить схемы построения кривых CD, EF и GH:
CDQ): СЩ - 1); DE; EF(i - 1); |; AB{i - 1); ВС; CD(i - 1)
EF{i): EF{i - 1); FG; GH(i - 1); <-; СЩ - 1); DE; EF(i - 1)
GH(i): GH(i - 1); HA; AB(i - 1); |; Щ/ - 1); FG; GH(i - 1)
Рекурсивные процедуры их построения:
алг ЛинияСР(арг цал i)
нач
•ели 1 > О
то
ЛинияСОЦ - 1)
OTpDE
ЛинияЕГЦ - 1)
ОтрЮг
ЛинияАВЦ - 1)
ОтрВС
ЛинияСОЦ - 1)
аса
кон
аяг ЛинияЕГ(*рг цал i)
иач
¦ели i > О
то
ЛинияЕГA - 1)
OTpFG
ЛинияСНЦ - 1)
ОтрЗапад
ЛинияСОЦ - 1)
OTpDE
ЛинияЕГЦ - 1)
аса
кои
алг ЛинияСН(арг дм i)
нач
•оли i > О
то
ЛинияСНЦ - 1)
ОтрНА
ЛинияАВЦ - 1)
ОтрСевер
ЛинияЕЕЦ - 1)
OTpFG
ЛинияСНЦ - 1)
аса
кои
16

Длину горизонтальной и вертикальной проекций наклонных отрезков
кривой обозначим h и учтем, что горизонтальные и вертикальные отрезки
имеют длину 2А (см. выше). Тогда процедуры рисования отрезков, показанных
на схемах в виде символов "—>", "|", "f", "«—", можно оформить с
использованием уже известной нам команды вектор так:
алг ОтрВосток
нач
| вектор{2 * h, 0)
кои
алг ОтрЮг
нач
| вектор@, 2 * h)
кон
ОтрСевер
I вектор@, -2 * h)
кои
алг ОтрЗапад
иач
I вектор(-2 * h, 0)
кои
Процедуры рисования наклонных отрезков OmpBC, OmpDE, OmpFG,
ОтрНА имеют вид:
алг ОтрВС
иач
I вектор(h, h)
кои
алг ОтрРЕ
Iвектор(-Ь, h)
кои
алг OTpFG
иач
I вектор(-11, -h)
кон
алг ОтрНА
иач
I вектор(h, -h)
кон
Как и в случае кривой Гильберта, кривую Серпинского будем вписывать в
некоторый "опорный" квадрат экрана, длину его стороны обозначим Л. Если
мы хотим вписать в этот квадрат кривую Серпинского /-го порядка, то нам
17

необходимо найти соответствующее значение параметра Л, определяющего
положение и размеры всех отрезков кривой. Для нахождения зависимости
h от А и i придется привлечь геометрию и алгебру.
Выше показано, что кривая Серпинского порядка i состоит из
центрального квадрата со срезанными углами, а к каждому срезу примыкает кривая
Серпинского порядка (г - 1) — см. рис. 7. С учетом этого изобразим рис. 8.
Проведем главную диагональ опорного квадрата, соединяющую левую
верхнюю вершину Г; с правой нижней Тп/. Она пересечет кривую порядка
/ в точках Сы и С^, а линии среза центрального квадрата — в точках Кы и
Krd. Назовем отрезок, соединяющий точки Сы и Crd> диагональю кривой
Серпинского, его длину обозначим 5,, кроме того, введем относительную
длину диагонали кривой Серпинского S = 8/й. Расстояние между точками
Кы и /^обозначим через р. Выполнив несложные геометрические
выкладки, найдем,чтор - Поскольку отрезки [Сы, К J и [С^, KJ являются
диагоналями кривых Серпинского порядка i - 1, то 8. = 28. , +р или в
относительных величинах:
причем из рассмотрения кривой первого порядка следует, что S0=v2 .
Ряд значений 5.приведен в табл. 1:
Таблица 1
Порядок кривой
S,
0
4г
1
5>?
2
13>/2
3
29>/2
4
...
Нам понадобится не относительная длина диагонали кривой Серпинского
¦У, а величина/. , которую назовем коэффициентом диагонали кривой
Серпинского. Ряд значений этого коэффициента приведен в табл. 2:
Таблица 2
Порядок кривой
*,
0
1
1
5
2
13
3
29
4
...
Из уравнения С") с учетом нижней строки приведенной табл. 2 можно
получить:
Z, = 2Z_, + 3>/2,(**)
причем Z0= 1. Отсюда следует, что коэффициенты Zi — натуральные числа.
Уравнение (**) позволяет найти (используя, например, рекурсию7) Z, для
любого /.
7 Можно также не использовать рекурсию, а провести расчет непосредственно по
рекуррентной формуле (**). Соответствующая функция приведена в Приложении.
18

Рис.8
Из того же рис. 8 видно, что диагональ опорного квадрата D^
выражается через диагональ кривой Серпинского соотношением: D ш 8я + V2A.
Выражая 8я через ?я, а эту величину через ZK, получаем: D^ = h(Zn +1) Л.
С другой стороны, как известно, D^=Л V2. Приравнивая эти два выражения
для D , находим искомую величину я:
Расчет коэффициента Zn (коэффициента длины диагонали кривой
Серпинского порядка л), необходимого для определения л, можно провести,
например, с помощью рекурсивной функции PacvemZ:
«яр уля Расчетг(«?р цел п)
¦и
•сяк п - О
| то
19

:= 1
I Рекурсивный вызов функции
ми := 2 * Расчетг(п - 1) + 3
Immw - значение функции Расчетг
После этих выкладок легко найти положение начальной точки кривой
Серпинского Г0: она расположена правее точки Ты на величину h. В свою
очередь, координаты этой точки можно вычислить, если учесть, что опорный
квадрат расположен по центру экрана:
Xau=Xc-m;Yllu = Yc-AI2
Вся программа построения кривой Серпинского заданного порядка п
имеет вид:
цвл h | глобальная переменная
алг Кривая Серпинского
ивч ц«л п, хО, уО, Xlu, Ylu, Нэкр, Вэкр, A, Z, »«щ к
Нэкр := 480 IВысота экрана
Вэкр := 640 |Ширина экрана
IВводим исходные данные для построения
| кривой Серпинского
•3
вывод нс, "Введите длину стороны опорного квадрата "
вывод, "в % от высоты экрана"
мол к
иц при к < 100
вывод не, "Введите порядок кривой"
ввод п
I Сторона опорного квадрата
А := цел(Нэкр * к/100)
коэффициент диагонали кривой Серпинского
Z := Расчетг(п)
I Проекция наклонного отрезка
h := цел(А/(г + 1))
IКоординаты левой верхней
Iточки опорного квадрата
Xlu := div(B3Kp, 2) - div(A, 2)
Ylu := div(H3Kp, 2) - div(A, 2)
IКоординаты начальной точки кривой
уО := Ylu
хО := Xlu + h
видео A7)
поз(х0, уО)
20

ЛинияАВ(п)
ОтрВС
ЛинияСР(п)
OTpDE
ЛинияЕГ(п)
OTpFG
ЛинияСН(п)
ОтрНА
кон
Как и при построении кривой Гильберта, в этой программе не хватает
задержки, позволяющей проследить процесс построения кривой. Добавьте
соответствующую процедуру в программу самостоятельно.
КРИВАЯ ДРАКОНА
Разработку программы построения кривой дракона начнем с того, что
будем наблюдать ход ломаных линий на рис. Зв, начиная с отрезка 1, и на
каждом углу следить, поворачивается отрезок на 90° вправо (по часовой
стрелке) или влево (против часовой стрелки). Присвоим код 1 повороту влево
и код 3 повороту вправо и обозначим код для отрезка с номером / через K(i).
Из рис. Зв видно, что
Щ) = 1; КB) = 1; Щ) = 3; КD) = 1; *E) = 1; КF) = 3; КA) = 3.
Задача заключается в том, чтобы найти правило выбора направления
поворота (влево или вправо) в конце отрезка с номером /(/=1,2,...).
Если рассмотреть ломаные, аналогичные представленной на рис. Зв, но
состоящие из 16,32 и т.д. отрезков, и проанализировать зависимость
направления поворота от номера отрезка, то можно установить, что значение K(i)
определяется следующим образом:
K(i) = K(i div 2), если / четное;
Щ) = i mod 4, если / нечетное,
где div — целочисленное деление, a mod — операция определения остатка.
Внимательный читатель конечно же обнаружил рекурсивный характер
расчета значения Щ). С учетом этого расчет Щ) может быть проведен с
помощью рекурсивной функции, имеющей вид:
алг цел К(арг цел i)
нтч
•ели mod(i, 2) = 0
до
I мм := K(div(i, 2)) |Рекурсивный вызов функции
21

иначе
аиач := mod(i, 4)
ВС*
|»иач - значение функции К
коя
Построение очередного отрезка ломаной будем выполнять с
использованием все той же команды вектор. В процедуре ОчерОтр, выполняющей
построение очередного отрезка, представлены 4 варианта направления
перемещения (два направления по горизонтали и два по вертикали). Направление
задается величиной угол. При перемещении вертикально вверх значение этой
величины равно 0, горизонтально влево-90°, вертикально вниз-180° и
горизонтально вправо -270° (т.е. отсчет производится против часовой стрелки от
направления вертикально вверх). Длина отрезка ломаной обозначена а.
алг ОчерОтр (арг нал угол)
нач
аыбор
при угол = 0: вектор@, -а)
при угол = 180: вектор{0, а)
при угол = 270: вектор(а, 0)
при угол = 90: вектор(-а, 0)
Определим закономерности изменения значения у та угол в ходе
построения ломаной. Можно утверждать, что в конце каждого отрезка с номером /
мы должны повернуть на Щ) * 90° влево, поскольку поворот на 90° по
часовой стрелке эквивалентен повороту на 270° влево против часовой стрелки.
Тогда с учетом принятой системы отсчета величины угол ее очередное (после
поворота) значение связано с предыдущим значением зависимостью:
угол = (угол + Щ) * 90) mod 360, A)
где КA) — код направления поворота (см. выше).
С использованием функции К и процедуры ОчерОтр, а также формулы
A) основная часть программы может быть оформлена в виде:
пая а |Величину а описываем как глобальную
алг Ломаная
нач цая п, угол, i
видео A7)
IНачальная точка ломаной
позA90, 276)
|Угол, под которым рисуется первый отрезок
угол := 270
IДлина отрезков ломаной
22

а := 20
вектор (а, 0) | Рисуем первый отрезок
п := 418 (Количество отрезков
IРисуем остальные отрезки линии
мц длж 1 w 1 до п - 1
| угол := тос!((угол + K(i) * 90), 360)
I ОчерОтр(угол)
т
кон
Примечание. Принятые значения координат начальной точки ломаной, а
также длины отрезков обеспечивают размещение на экране всей линии из 418
отрезков.
Как уже говорилось, замечательным свойством полученной линии
является то, что в ней отсутствуют самопересечения (помните о складываемой
полоске бумаги?). Чтобы наглядно продемонстрировать указанную
особенность, можно скруглить все углы или, точнее, заменить их небольшими
отрезками прямых линий (т.е. при этом во всех вершинах ломаной будем
иметь углы 135* вместо 90°). Парис. 2 как раз и представлена такая линия.
Для ее построения уточним приведенную программу. Основные
изменения должны быть внесены в процедуру ОчерОтр. Включим в нее также
рисование "закругления", предшествующего очередному отрезку. Очевидно,
что для вычерчивания этого "закругления" необходимо знать
предшествующее направление перемещения. Информацию о нем будем хранить в
переменной ст_угол. Естественно, что длина вычерчиваемого отрезка в
данном случае уменьшается до a - 2b, где b — длина катета "закругления".
После вычерчивания отрезка и закругления использованное значение станет
значением величины ст_угоп, которое будет использоваться на следующем
шаге рисования нашей кривой.
С учетом этого процедура ОчерОтр оформляется следующим образом:
алг ОчерОтр(арг цал угол, арг р— цел ст_угол)
нач
выбор
при угол = 0:
•сии ст _ угол = 90
то
вектор(-а, -а)
mm
вектор(а, -а)
не»
вектор@, -(а - 2 * Ь))
при угол = 180:
•cam ст _ угол « 90
I —
23

вектор(-а, а)
иначе
вектор(а, а)
все
вектор@, а - 2 * Ь)
при угол = 270:
если ст _ угол = 0
то
вектор(а, -а)
иначе
вектор(а, а)
все
вектор(а - 2 * Ь, 0)
при угол = 90:
если ст _ угол = 0
то
вектор(-а, -а)
иначе
вектор(-а, а)
все
вектор(-(а - 2 * Ь), 0)
все | Конец команды выбор
ст _ угол := угол
кон
Обращаем внимание на то, что параметр ст_угол, меняющийся в ходе
выполнения процедуры, указан в ее заголовке как параметр-переменная (это
следует учесть в программе на языке Паскаль).
Основная часть программы (ее уже можно назвать "Кривая дракона")
меняется незначительно:
цел а, Ь |0 величине b - см. процедуру ОчерОтр
алг Кривая _ дракона
нач цел п, угол, ст _ угол, i
видеоA7)
а := 20
b := div(a, 5)
позA90 + b, 276)
угол := 270
вектор (а - Ь, 0)
ст _ угол :«= 270
п := 418
НЦ ДЛИ 1 от 1 до п - 1
угол := тос1((угол + K(i) * 90), 360)
Очер0тр(угол, ст_ угол)
кон
И здесь также следует дополнительно включить в программу процедуру
задержки.
24

ЛИТЕРАТУРА
1. Медведькова Н.А. Материалы к урокам по теме "Рекурсивные
алгоритмы" // "Информатика", № 5/2008.
2. Златопольский Д.М Программирование: типовые задачи, алгоритмы,
методы. М.: БИНОМ. Лаборатория знаний, 2007.
3. Школа программирования: Тематический выпуск газеты-вкладки "В
мир информатики" // "Информатика", № 11/2005.
ПРИЛОЖЕНИЕ 1
Великие математики,
именами которых были названы замечательные кривые
ГИЛЬБЕРТ Давид B3.01.1862 — 14.02.1943;
Hilbert David) — немецкий математик, логик,
философ, руководитель одного из основных
центров мировой математической науки первой
трети XX в. — Геттингенской математической
школы,—исследования которого оказали
определяющее влияние на развитие математических
наук. Обладатель престижной
Международной премии имени Лобачевского A904), с
1913 г. — чл.-корр., с 1942 г. — почетный член
Берлинской академии наук; с 1922
г.—иностранный чл.-корр. АН СССР, с 1934 г.—иностранный
почетный член АН СССР. Давид Гильберт
Родился близ Кенигсберга (Велау). Окон- A910 год)
чил Кенигсбергский университет в 1884 году;
с 1893 по 1895 г. — профессор Кенигсбергского университета; с 1895 по
1930 г. — профессор математического факультета Геттингенского
университета. Исследования Гильберта оказали большое влияние на развитие многих
разделов математики, а его деятельность в Геттингенском университете как
профессора в значительной мере содействовала тому, что Геттинген в первой
трети XX века являлся одним из основных мировых научных центров
математической мысли. Свою последнюю лекцию в нем Гильберт прочитал в
1933 году, после чего был вынужден отойти от университетских дел в связи
с преследованиями со стороны идеологов национал-социализма.
Гильберт возглавлял обширную школу, оказавшую сильное влияние на
всю математику и физику прошлого века. Творчество Гильберта охватывало,
по существу, всю математику, он был "математиком-универсалом": его имя
25

встречается во многих разделах современной высшей математики. Ученик
Гильберта и крупный математик Герман Вейль говорил о своем учителе:
"Если он занимался интегральными уравнениями, то они означали для
него все; бросив какой-либо предмет, он отделывался от него полностью
и переходил к другому. Именно таким своеобразным образом он достиг
универсальности".
Диссертации большого числа крупных математиков (среди них Г.Вейль,
Р.Курант) были написаны под его научным руководством.
Одним из самых важных направлений в научном творчестве Гильберта
были основания геометрии A898-1902). Опубликованный им труд
"Основания геометрии" A899) стал основополагающим для исследований в
направлении аксиоматического построения различных геометрий. Гильберт
предложил систему аксиом, необходимую и достаточную для построения
всей геометрии Евклида. Именно система Гильберта стала первым строгим
основанием геометрии Евклида; она содержит 20 аксиом принадлежности,
порядка, конгруэнтности, непрерывности, параллельности. Тогда же
Гильберт провел логическую обработку всей системы этих аксиом, доказал ее
непротиворечивость и полноту (при помощи числовых моделей), а также
независимость групп аксиом.
Аксиоматизация геометрии, выполненная Гильбертом, была совершенно
необходимой в связи с развитием неевклидовых геометрий.
В исследованиях Гильберта по теории интегральных уравнений с
симметричным ядром (составляющих основу современного
функционального анализа) было получено обобщение понятия, векторного евклидова
пространства для случая бесконечного числа измерений — гильбертова
пространства, принадлежащего к числу базисных категорий современной
математики, широко применяемого в исследованиях по теоретической и
математической физике.
В1900 году на I) Международном конгрессе в Париже Гильберт прочитал
ставший знаменитым доклад, в котором указал 23 важнейшие проблемы,
требующие разрешения. Во введении к докладу говорилось о целостном
характере математики как основе всего точного естественно-научного
познания, о математической строгости, о значении для математики "хорошо
поставленной" специальной проблемы. Там же был выдвинут и основной
тезис Гильберта — о разрешимости в широком смысле любой задачи
математики.
Свой доклад он начал словами: "Кто из нас не хотел бы приоткрыть завесу,
за которой скрыто наше будущее, чтобы хоть одним взглядом проникнуть
в предстоящие успехи нашего знания и тайны его развития в ближайшие
столетия?". Уверенность в том, что каждая определенная математическая
проблема непременно должна иметь решение, побудила Гильберта поставить,
например, проблему № 10: "Указать способ, при помощи которого возможно
26

после конечного числа операций установить, разрешимо ли данное
уравнение в целых рациональных числах". Иначе эта проблема формулируется
так: доказать, что существует алгоритм, который по данному многочлену Р
от л переменных с целыми коэффициентами распознавал бы, имеет уравнение
Р = 0 целочисленные корни или нет. (В 1970 г. Юрий Владимирович Матия-
севич установил, что требуемого алгоритма не существует.)
Еще один пример: Гильберт был настолько уверен, что функции трех
переменных устроены сложнее, чем функции двух переменных, что
высказал такую гипотезу: некоторая конкретная функция трех переменных
непредставима в виде суперпозиции непрерывных функций двух
переменных. (Ее опровергли в 1957 году Колмогоров и Арнольд. Оказалось,
что с помощью только одной, и притом простейшей, функции двух
переменных (х,у) —»х + у и непрерывных функций одной переменной можно
восстановить любую функцию и переменных.)
СЕРПИНСКИЙ Вацлав A4.03.1882 —
21.10.1969) — польский математик; в
1917-1951 гг. — член Академии наук в
Кракове, Президент Варшавского научного
общества A831-1951), с 1952 г. член
Польской АН; член 11 академий наук и научных
обществ. Государственная премия по науке
Польской Народной Республики A949).
Родился Серпинский в Польше (в
Варшаве), которая в тот момент входила в
состав Российской империи.
Интерес к математике и
математические способости у Серпинского появились
очень рано, еще в школе это отмечал его
первый учитель математики. Уже в 1904
году за разработку темы, предложенной
научным руководителем, Варшавский университет присудил ему золотую
медаль. '
В 1904 г. окончил Варшавский университет и работал некоторое время
как школьный учитель математики и физики в школе для девочек в Варшаве.
В 1905 г. принимал участие в забастовке студентов, после чего вынужден
был выехать из Варшавы. Серпинский поступил в докторантуру Ягеллонов-
ского университета в Кракове, посещал лекции по математике, астрономии
и философии. Закончив докторантуру, в 1908-1914 гг. работал во Львовском
университете. За это короткое время издал, помимо многих
научно-исследовательских работ, три книги: Теория иррациональных чисел A910), Основы
теории множеств A912) и Теория чисел A912).
27
Вацлав Серпинский

Свой первый значительный результат в теории множеств Серпинский
получил в 1907 году. С этого момента началась его деятельность в области
теории множеств. Уже в 1909 г. он прочитал свой первый курс лекций,
полностью посвященный теории множеств.
Помимо теории множеств и ее применений к различым отраслям
математики (топологии, теории функций действительной переменной и др.),
Серпинский занимался функциональными рядами, диффереицирумостью
функций, классификациями Бэра. В математике широко известна кривая
"ковер Серпинского" — непрерывная кривая, проходящая через каждую
точку квадрата.
Во время Первой мировой войны Серпинский жил и работал в Москве
и Вятке A914-1918), сблизился с русскими математиками (в первую
очередь с Н.Лузиным). Когда война закончилась, вернулся в Варшаву A919).
Совместно с З.Янишевским и С.Мазуркевичем основал в 1920 г. в Польше
журнал "Fundamenta mathematicae" ("Основы математики"), посвященный
исследованиям в области теории множеств. С 1919 по 1960 г. он профессор
Варшавского университета.
В годы Второй мировой войны Серпинский не прекращал научной
работы и даже преподавал в подпольном университете. За годы войны польская
школа математики понесла огромные потери. Погибли многие преподаватели,
фашисты дотла сожгли варшавскую университетскую библиотеку, которая
содержала несколько тысяч единиц журналов, математических книг и статей.
Почти все выпуски "Fundamenta mathematicae" C2 тома) были полностью
сожжены.
С февраля 1945 г. Серпинский работал в Краковском университете, а
осенью возвратился в Варшаву. В 1952-1957 гг. он был избран вице-президентом
Польской академии наук.
В 1960 г. он ушел со ставки профессора Варшавского университета, но
продолжал вести семинар по теории чисел в польской Академии наук вплоть
до 1967 г. Он также продолжал свою редакционную работу как главный
редактор журнала Acta Arithmetica, который он основал в 1958 г., и в качестве
члена редакционной коллегии журналов Rendiconti del Circolo Matimatico di
Palermo, Composito Matematica и Zentralblatt fiir Mathemalik.
За свою жизнь Вацлав Серпинский удостоился многих почестей, так что
даже упомянуть их все будет невозможно. Вот только некоторые. Он был
награжден почетными учеными степенями университетов Львова A929),
Лимы A930), АмстердамаA931), Софии A939), Праги A947), Вроцлава A947),
Лакхнау A949), Москвы A967); получил Государственную премию по науке
Польской Народной Республики A949).
Серпинский был избран в Географическое общество Лимы A931),
Королевское научное общество Льежа A934), болгарскую Академию наук A936),
Национальную академию Лимы A939), Королевское общество наук Неаполя
28

A939), Академию наук Рима A947), немецкую Академию наук A950),
американскую Академию искусств и наук A959), Парижскую академию A960),
Королевскую голландскую академию A961), Академию наук Брюсселя A961),
Лондонское математическое общество A964), румынскую Академию A965),
Папскую академию наук A967). Внушительный перечень.
Один из студентов Вацлава Серпинского написал о своем учителе: "У
Серпинского было исключительно хорошее здоровье и веселый характер<...>.
Он мог работать при любых условиях<...>. У него был творческий ум и он
любил творческую математику. Он был самым великим и самым
продуктивным из польских математиков".
Всего Серпинский опубликовал более 700 (!) работ, среди которых около
30 университетских учебников и монографий, много научно-популярных
книг. Часть из них переведена и на русский язык.
И в заключение очень хочется привести небольшую цитату из письма
Серпинского к А.Данжуа. Цитату, никакого отношения к математике не
имеющую. Просто жаль, что уже не пишут больше таких писем...
"Дорогой коллега,
Я бесконечно виноват перед Вами из-за моего столь долгого молчания.
Но это вовсе не потому, что я не думал о Вас. Я часто о Вас думаю, но из-за
моих многочисленных дел я был вынужден задержаться с ответом. Кроме
моих обычных занятий (Университет, Fundamenta, Союз преподавателей,
председателем которого я являюсь), новые обязанности и ответственные
дела свалились на меня. <...> "
ПРИЛОЖЕНИЕ 2
Рекуррентная функция расчета коэффициента Расчет!
тяг птл Расчетг(«рг цел 1)
тая утл г, к
z := 1
ИЦ ДЛЯ к О* 1 ДО 1
I z := 2 * z + 3
3
аиач := z
|»иач - значение функции Расчетг
кои
29

СОДЕРЖАНИЕ
Предисловие 3
Рекурсия 5
Кривая Гильберта 9
Кривая Серпинского 14
Кривая Дракона , 21
Литература 25
Приложение 1. Великие математики, именами которых были названы
замечательные кривые ; 25
Приложение 2 29