«Алгоритмы сортировки и их программа»

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

Программный продукт GRAPHIC позволяет строить и сохранять графики любых функций одной переменной. Продукт разработан на языке программирования Мicrosoft Visual C++ 6.0 с использованием объектно-ориентированной методологии. Диалог пользователя с программой, а именно введение параметров, осуществляется посредством диалоговых окон программы. Диапазон вводимых значений программно ограничен, с целью недопущения некорректной работы или возникновения ошибки.

Общая блок-схема алгоритма

Общая блок схема алгоритма программы GRAPHIC:

2. Нарисуйте коническое сечение из его полиномиального уравнения в C#
В зависимости от типа конического сечения и его ориентации это может привести к следующим пяти ситуациям:
private void DrawConicSection(Graphics gr,
float A, float B, float C, float D, float E, float F)
{
float xmin = 0;
float xmax = xmin + picGraph.ClientSize.Width;

for (float x = xmin; x < xmax; x++)

{
float y = G1(x, A, B, C, D, E, F, -1f);
if (IsNumber(y))
{
xmin = x;
break;
}
}

for (float x = xmax; x > xmin; x--)

{
float y = G1(x, A, B, C, D, E, F, -1f);
if (IsNumber(y))
{
xmax = x;
break;
}
}
List
ln_points = new List
();
float xmid1 = xmax;
for (float x = xmin; x < xmax; x++)
{
float y = G1(x, A, B, C, D, E, F, -1f);
if (!IsNumber(y))
{
xmid1 = x - 1;
break;
}
ln_points.Add(new PointF(x, y));
}
List
lp_points = new List
();
for (float x = xmid1; x >= xmin; x--)
{
float y = G1(x, A, B, C, D, E, F, +1f);
if (IsNumber(y)) lp_points.Add(new PointF(x, y));
}
List
rp_points = new List
();
List
rn_points = new List
();
float xmid2 = xmax;
if (xmid1 < xmax)
{
for (float x = xmax; x > xmid1; x--)
{
float y = G1(x, A, B, C, D, E, F, +1f);
if (!IsNumber(y))
{
xmid2 = x + 1;
break;
}
rp_points.Add(new PointF(x, y));
}
for (float x = xmid2; x <= xmax; x++)
{
float y = G1(x, A, B, C, D, E, F, -1f);
if (IsNumber(y)) rn_points.Add(new PointF(x, y));
}
}
if (xmin > 0) lp_points.Add(ln_points[0]);

if (xmid1 < picGraph.ClientSize.Width) ln_points.Add(lp_points[0]);

if (rp_points.Count > 0)

{
rp_points.Add(rn_points[0]);

if (xmax < picGraph.ClientSize.Width) rn_points.Add(rp_points[0]);

}

using (Pen thick_pen = new Pen(Color.Red, 2))

{
thick_pen.Color = Color.Red;
if (ln_points.Count > 1)
gr.DrawLines(thick_pen, ln_points.ToArray());

thick_pen.Color = Color.Green;

if (lp_points.Count > 1)
gr.DrawLines(thick_pen, lp_points.ToArray());

thick_pen.Color = Color.Blue;

if (rp_points.Count > 1)
gr.DrawLines(thick_pen, rp_points.ToArray());

thick_pen.Color = Color.Orange;

if (rn_points.Count > 1)
gr.DrawLines(thick_pen, rn_points.ToArray());
}
}

Метод начинается с поиска наименьшего и наибольшего значений координаты X в PictureBox, для которого определена функция G1. Например, уравнения эллипса определены только в ограниченном диапазоне значений координат X (и Y). (Кривая не доходит до левого и правого краев PictureBox.) Метод находит минимальное определенное значение X, перебирая значения от 0 до ширины PictureBox, пока не найдет определенное значение для G1. Затем он находит максимальное определенное значение X, перебирая значения от ширины PictureBox до 0, пока не найдет определенное значение для G1.

Затем метод перебирает функцию G1 для ее положительных и отрицательных корней. Сначала он перебирает увеличивающиеся значения X, начиная со значения xmin и используя отрицательный корень. Может случиться одно из двух.
Во-первых, функция G1 может быть определена до тех пор, пока x не достигнет максимального значения координаты X xmax. Это происходит для гиперболы, открывающейся вверх/вниз, и параболы, открывающейся вверх. (Этого не происходит для параболы, открывающейся вниз, потому что в этом случае используется положительный корень в функции G1, а код еще не дошел до этого случая.)
Во-вторых, функция G1 может быть неопределенной для некоторого значения x. Это происходит для эллипса и левой/правой открывающейся гиперболы. В этом случае код сохраняет координату X, которая дала последнее определенное значение, в переменной xmid1 и выходит из цикла.
Поскольку метод перебирает координаты X, он сохраняет точки функции в списке ln_points («ln» означает «левое отрицательное значение»).
Наиболее поучительная ситуация для размышлений — это случай гиперболы открытия влево/вправо. В этом случае xmid1 дает координату X самой правой точки красной кривой в левой половине гиперболы.
Найдя точки для отрицательного корня слева от кривой, метод перебирает значения координат X, начиная с xmid1 и уменьшаясь до xmin, на этот раз находя точки с положительным корнем из G1. На этот раз метод сохраняет точки функции в списке lp_points («lp» означает Left Positive).
Если кривая представляет собой эллипс, гиперболу, открывающуюся вверх/вниз, параболу, открывающуюся вверх, или параболу, открывающуюся вниз, то захваченные до сих пор точки покрывают всю кривую. Оставшийся случай - гипербола открытия слева/справа. В этом случае xmid1 меньше xmax, и метод должен найти правую половину кривой.
Код использует положительный корень из G1, перебирая координаты X, начиная с xmax и уменьшая их, пока не найдет неопределенное значение. Затем он возвращается от этой точки к точкам записи xmax, созданным с использованием отрицательного корня G1.



Последний шаг в нахождении точек пересечения двух эллипсов (или конических сечений вообще) — использование метода Ньютона для нахождения корней некоторых разностных уравнений. Метод Ньютона работает так: вы начинаете с координаты X. Вы оцениваете функцию и ее производную для этого значения X, чтобы найти прямую, касательную кривой уравнения. Вы определяете, где касательная пересекает ось X, и используете эту точку пересечения в качестве новой оценки того, где находится корень. Вы повторяете этот шаг несколько раз, пока рассматриваемая точка не окажется достаточно близко к корню.
На картинке справа показан процесс. Точка x0 является начальным предположением для корня. Вы находите касательную и определяете, где она пересекает ось X в точке x1. Точка x1 становится следующим предположением значения корня.

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

К сожалению, такая ситуация довольно часто возникает с разностными кривыми, используемыми для нахождения точек пересечения конических сечений. Если вы посмотрите на разностные кривые на картинке вверху этого поста, вы увидите, что красная кривая имеет именно такую ​​форму. Оранжевая кривая имеет довольно маленькую вторую производную, поэтому метод Ньютона может найти этот корень, но может не найти корень в месте пересечения красной кривой с осью X.

Альтернативой методу Ньютона является бинарное деление. Здесь вы выбираете две координаты X x0 и x1, которые, по вашему мнению, окружают корень уравнения. Вы оцениваете функцию в этих координатах x. Если между ними лежит корень, то значение одной из этих координат должно быть положительным, а другой отрицательным. Если это так, то вы вычисляете x2 = (x0 + x1)/2 в середине других точек и оцениваете функцию там. Затем вы повторяете процесс, используя среднюю точку и любое из исходных значений, лежащее на противоположной стороне линии y = 0. На рисунке справа F(x0) < 0 и F(x1) > 0, поэтому между этими точками должен быть корень. Для средней точки F(x2) > 0, поэтому корень лежит между x0 и x2.

Вы повторяете этот процесс до тех пор, пока значение функции в рассматриваемых точках не станет достаточно близко к 0.