Возникла тут небольшая задачка - сделать (на паскале, но это совершенно не важно) программу, рисующую кривую Пеано. Что это за кривая, я примерно себе представлял, но смутно, поэтому пришлось обратиться к Википедии за подробностями.
Всю историю пересказывать не стану, тем более, что я её не знаю. В XVIII-XIX веках активно развивался аналитический аппарат теории функций на волне успехов дифференциального и интегрального исчисления, уточнялись базовые понятия, в том числе дело дошло и до понятия кривой. Появилась надежда, что любую непрерывную функцию можно представить при помощи рядов Фурье, потом коварный Дюбуа-Реймон эту надежду похоронил, потом Кантор, поправ существующий в матанализе инструментарий, построил понятие кривой средствами теории множеств... Как пишет Рыбников в "Истории математики", кривых снова оказалось больше, чем формул. В 1882 году Жордан дал определение кривой как совокупность точек плоскости с координатами (x(t), y(t)), где x и y - непрерывные функции от параметра t на некотором отрезке. А в 1890 году Пеано подарил миру плоскую кривую, которая, подпадая под определение Жордана, заполнила собой некоторый квадрат целиком.
Строится кривая довольно интересно. Исходный квадрат разбивается на квадратики, и по определенным правилам выясняется, из какого квадратика в какой смежный квадратик кривая переходит. Затем каждый из этих квадратиков дробится дальше, и уже для этих субквадратиков выясняется, из какого в какой переходит кривая, и так далее, до бесконечности. То есть, всю кривую никто не видел, но картинки, соответствующие каким-то начальным итерациям такого построения, хорошо известны.
При виде этой картинки возникает закономерный вопрос: а чё так сложно-то? Нельзя, что ли, было просто заштриховать и не мучиться?
Оказывается, нет, нельзя. Дело в том, что кривая Пеано не просто заполняет единичный квадрат, но делает это непрерывно. Смысл тут такой. Если взять любую точку квадрата, то найдётся содержащий эту точку маленький квадратик, который точно таким же образом, как и большой квадрат, будет под завязку заполнен некоторым участком кривой Пеано. Грубо говоря, некоторой окрестности из образа (квадратику) должна соответствовать некоторая окрестность из прообраза (кусочек кривой). Короче говоря, кривая Пеано обладает свойством самоподобия, и это важно для непрерывности.
В теории всё хорошо, но как же алгоритмизовать построение этой кривой? Ну, то есть, не всей кривой (что мы, серый квадрат не нарисуем? 8-), но какой-нибудь из этих промежуточных итераций. Понятно, что, поскольку самоподобие, то алгоритм должен быть рекурсивным. Также понятно, что этот рекурсивный алгоритм должен иметь дело с квадратом, нарезанным на кусочки, и заполнять некую матрицу переходов от кусочка к кусочку.
Какому правилу должен подчиняться размер этой матрицы? Если посмотреть на первую итерацию, то выглядит она так:
Как видим, весь путь в этом простейшем случае можно уместить в матрицу 3x3. Следовательно, если мы вознамеримся заполнять матрицу 3ⁿх3ⁿ, то дробя её на девять квадратов, а каждый - в свою очередь, на девять и т.п., сведём всё к случаю 3х3 и выйдем из рекурсии.
Ну, а уж имея представление, как должен быть устроен алгоритм заполнения матрицы переходов, и какого размера должна быть эта матрица (степень тройки), не составит труда сделать реализацию на любом языке программирования:
Сама реализация получилась не очень интересная - просто много кропотливой работы по правильному обходу девяти квадратиков - но если кого-то заинтересует, исходный текст программы на Free Pascal лежит тут.
Ну и, напоследок пара слов ещё об одной кривой, обладающей свойствами, аналогичными кривой Пеано, и упомянутой в Википедии. Это кривая Гильберта. Строится она также рекурсивно, только исходный квадрат требуется превращать не в 3ⁿх3ⁿ матрицу, а в 2ⁿх2ⁿ.
Исходный текст программы на Free Pascal для построения кривой Гильберта лежит тут.