Поиск i-го элемента в массиве
Есть произвольный массив x[] из n элементов (нумерация начинается с нуля, для определённости будем считать, что элементы - целые числа).
Отсортирем массив. i-й элемент в нём это то, что нам надо.
Но полная сортировка массива весьма ресурсозатратна, можно ли решить данную задачу более оптимально? Не сортируя массив целиком/явным образом?
Например, самый первый элемент отсортированного массива (с индексом 0(ноль)) - это просто минимальный элемент исходнго массива и ищется он элементарно за один проход
// int[] x - исходный неотсортированный массив, длины n
int minX = x[0];
for (int i = n - 1; i > 0; i--) minX = Math.min(minX, x[i]);
( Далее... )
Post A Comment | в избранное | рассказать другу | ссылка
Другая "популярная" задача - это замена переменной в полиноме. Есть полином
p(t) = p0 + p1 t + p2 t^2 +... и хотим перенести ноль в точку t0: q(s) = p(t0 + s) = q0 + q1 s + q2 s^2 +... Решается опять же элементарно при помощи формулы Тейлора: q(s) = p(t0 + s) = p(t0) + p'(t0) s + p"(t0) s^2 / 2 + ...
q0 = p(t0)
q1 = p'(t0)
q2 = p"(t0) / 2
... Таким образом, при наличии функции, которая вычисляет значие n-ой производной полинома в заданной точке, задача замены переменной имеет предельно простое програмное решение. Использование. Замена переменной - это первый шаг в "аналитическом" решнии уравнений 3-й и 4-й степени, когда мы приводим уравнение к "угнетённому" (depressed) виду: t0 выбирается так чтобы после замены переменной обнулился (n - 1)-ый коэффициент полинома. Решатель уравнений 4-ой степени в свою очередь нужен, чтобы быстро и точно найти точки пересечения двух кривых Безье 2-го порядка. А находить пересечения кривых необходимо для выполнения теоретико множественных операций (объединение, пересечение, вычитание и т.п.) с фигурами на плоскости, заданными своими границами (как это было описано ранее). (Пример: чтобы получить 2D-месяц надо взять круг и вычесть из него другой круг)
Post A Comment | в избранное | рассказать другу | ссылка
Краткое введение.
1. Кривые Безье - основа копмьютерной 2D графики: фигуры на плоскости задаются не уравнением (например круг: x^2 + y^2 <= r^2), а своей границей, которая описывается в виде последовательности кривых безье 1-го (это просто отрезок), 2-го или 3-го порядка. Так круг можно представить в виде набора из 4-х кривых 3-го порядка одна кривая на каждую четверть круга (получается хорошая апроксимация, такое предаставление круга используется в Java2D) или 8-и кривых второго порядка (Такое представление используется во флэшэ, это менее точная апроксимация, которую, впрочем, легко улучшить увеличив количество кривых). Кривая Безье задайтся последлвательностью точек, первая и последняя точка - это точки начала и конца кривой, вторая и предпоследняя определяют направлние кривой (касательные к ней) в начале и конце соответсвенно - это геометрический смысл описания кривых в форме Безье.
2. Если необходимо найти точки пересечения двух кривых или расстояние от точки до кривой или вычислить длину кривой, то гораздо удобнее работать с полиномиальным представлением кривой Безье.
Задача такая: есть кривая безье 2-го порядка:
p(t) = p1 (1-t)^2 + 2 p2 (1-t)t + p3 t^2 Надо превести её к полиномиальному виду: p(t) = q0 + q1 t + q2 t^2 Т.е. надо тупо открыть скобки, в лоб открывать скобки во-первых влом, а во-вторых геморойно. Тут то нам и приходит на помощь формула Тейлора: p(t) = p(0) + p'(0) t + p"(0) t^2 / 2
p(0) = p1 = q1
p'(t) = -2 p1 (1-t) + 2 p2 (1-2t) + 2 p3 * t = 2 (p2 - p1) + 2 (p1 - 2 p2 + p3) t
p'(0) = 2 (p2 - p1) = q1
p"(t) = 2 (p1 - 2 p2 + p3) = p"(0) = 2 q2 В итоге получаем: q0 = p1
q1 = 2 (p2 - p1)
q2 = (p1 - 2 p2 + p3) p(t) = p1 + 2 (p2 - p1) t + (p1 - 2 p2 + p3) t^2 Впрочем, случай кривых вторго порядка не слишком нагляден, но уже для кривых 3-го порядка: p(t) = p1 (1-t)^3 + 3 p2 (1-t)^2 t + 3 p3 (1-t) t^2 + p4 t^3 описанный подход упращает процесс открытия скобок более чем значительно.
Post A Comment | в избранное | рассказать другу | ссылка
|
![[info]](http://l-stat.livejournal.com/img/userinfo.gif){kind=small}
