АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Рекурсивный алгоритм

Читайте также:
  1. Вопрос. Канонический рекурсивный фильтр.
  2. Вопрос. Рекурсивный фильтр (БИХ).

ВВЕДЕНИЕ

 

Тема: Разработка программы с рекурсивным алгоритмом.
Кривая Гильберта

 

Техническое задание.

Цель: Создать программу, вычерчивающую кривую Гильберта.
Задачи:

1. Изучить необходимую литературу.

2. Изучить фракталы и их составляющие.

3. Разработать программу на СИ+, которая будет вычеркивать кривую.

Рекурсивный алгоритм.

Рекурсия - метод определения класса объектов или методов предварительным заданием одного или нескольких (обычно простых) его базовых случаев или методов, а затем заданием на их основе правила построения определяемого класса, ссылающегося прямо или косвенно на эти базовые случаи.

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

 

Рекурсивный алгоритм (процедура, функция):

Ø алгоритм называется рекурсивным, если в его определении содержится прямой или косвенный вызов этого же алгоритма;

Ø рекурсивная функция - одно из математических уточнений интуитивного понятия вычислимой функции.

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

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

Шаг рекурсии - это правило, в теле которого обязательно содержится, в качестве подцели, вызов определяемого предиката.

Подпрограмма - все, что находится внутри рекурсивной функции.

Дави́д Ги́льберт - немецкий математик-универсал, внёс значительный вклад в развитие многих областей математики. В 1910—1920-е годы (после смерти Анри Пуанкаре) был признанным мировым лидером математиков. Гильберт разработал широкий спектр фундаментальных идей во многих областях математики, в том числе теорию инвариантов и аксиоматику евклидовой геометрии. Он сформулировал теорию гильбертовых пространств, одной из основ современного функционального анализа.
Давид Гильберт был одним из истинно великих математиков своего времени. Его труды и его вдохновляющая личность ученого оказали глубокое влияние на развитие математических наук вплоть до настоящего времени. Его проникновенная интуиция, его творческая мощь и неповторимая оригинальность математического мышления, широта и разносторонность интересов сделали Гильберта первооткрывателем во многих областях математики. Это была единственная в своем роде личность, глубоко погруженная в свою работу и полностью преданная науке, учитель и руководитель самого высокого класса, вдохновляющий и крайне великодушный, не знающий усталости и настойчивый во всех своих устремлениях.

Кривая Гильберта — это непрерывная кривая, заполняющая пространство. Эти кривые также являются фракталами, они самоподобны; если вы увеличите масштаб и внимательно посмотрите на часть кривой более высокого порядка, то вы увидите, что она выглядит так же, как сама кривая.

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

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

 

Вот некоторые кривые Гильберта по возрастанию порядка:


Рис.1

От 1D к 2D

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

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

Замечание. Обратное не всегда верно (что неизбежно при отображении двух измерений на одно измерение). Обязательно будут случаи, когда точки с геометрически близкими координатами будут соответствовать сильно отличающимся значениям на ленте . Тем не менее, за исключением этих случаев, кривые Гильберта также неплохо работают и на обратных отображениях.
Справа вы можете увидеть квадрат, раскрашенный с использованием кривой Гильберта. Цвета, близкие друг к другу на спектре, имеют близкие координаты .

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


1 | 2 | 3 | 4 |

Поиск по сайту:



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