OOP_csharp_2
.pdf
Рис.1.1. Демонстрация операций с классом Fraction.
1.4. Быстрая сортировка массива дробей
Тип Fraction может использоваться в качестве подставляемого вместо обобщенного типа данных при генерации функций и классов на основе обобщений. Приведем пример использования обобщения функции быстрой сортировки для массива дробей. В сгенерированном методе с типом Fraction требуется организовать сравнение двух дробей. Для этого класс Fraction должен раскрывать интерфейс IComparable и иметь метод сравнения дробей CompareTo().
class Fraction : IComparable
{ |
|
|
int sign; |
// знак дроби (+ или -) |
|
int intPart; |
// целая часть |
дроби |
int numerator; |
// числитель дроби |
|
int denominator; |
// знаменатель |
дроби |
// метод сравнения двух дробей public int CompareTo(object ob)
{
if (this < (ob as Fraction)) return -1; if (this > (ob as Fraction)) return 1; return 0;
}
. . .
}
20
Определим обобщенный метод быстрой сортировки, указав ограничение на использование в качестве обобщенных типов только тех, которые раскрывают интерфейс IComparable. Пусть этот метод является статическим для главного класса приложения Program.
class Program
{
static void QuickSort<T>(T [] m, int l, int r) where T: IComparable
{
if(l == r) return;
int i = l, j = r;
//выбирается элемент, делящий массив на две части
T selected = m[l];
//осуществляется поиск и перестановка элементов, меньших
//выбранного, с конца массива и больших выбранного
//с начала массива.
while(i != j)
{
while(m[j].CompareTo(selected) >= 0 && j > i) j--;
if(j > i)
{
m[i] = m[j];
while(m[i].CompareTo(selected) <= 0 && i < j) i++;
m[j] = m[i];
}
}
//выбранный элемент устанавливается на надлежащее место m[i] = selected;
//если существуют элементы слева от выбранного,
//сортируем эту часть массива
if(l <= i-1) QuickSort(m, l, i-1);
//то же проводится с правой частью массива,
//если она существует
if( i+1 < r)
QuickSort(m , i+1, r);
}
static void Main(string[] args)
{
Fraction[] a = { new Fraction(4,2,3,1), new Fraction(1,6,5,-1), new Fraction(0,2,7,1), new Fraction(10,2,3,-1), new Fraction(2,13,20,1),
21
new Fraction(0,1),
new Fraction(1,1,3,1), new Fraction(2,5,7,-1), new Fraction(4,8,2,-1), new Fraction(4,1,3,-1)};
for (int i = 0; i < a.Length; i++) Console.Write(a[i]+" ");
Console.WriteLine();
//генерация и вызов функции быстрой сортировки
//для массива дробей
QuickSort(a, 0, 9);
for (int i = 0; i < a.Length; i++) Console.Write(""+a[i]+" ");
Console.WriteLine();
. . .
}
Это же обобщение можно применять и для массива чисел типов int, double, а также для массивов, элементами которых являются объекты классов (пользовательских или библиотечных), которые раскрывают интерфейс IComparable.
Задания для самостоятельной работы
1.Дополнить класс Fraction перегруженными арифметическими операциями, в которых один из операндов является вещественным числом.
2.Дополнить класс Fraction перегруженными операциями сравнения для дробей и вещественных чисел.
3.Дополнить класс Fraction перегруженным конструктором, осуществляющим преобразование вещественного числа к типу Fraction. Предполагается, что дробная часть вещественного числа содержит до 10 знаков после запятой.
4.Разработать класс «Комплексное число». Определить в нем конструктор, перегрузить арифметические операции, операции сравнения, операцию преобразования в строку и статический метод получения комплексного числа из строки.
5.Разработать класс «Комплексное число в тригонометрической форме». Определить в нем конструктор, перегрузить арифметические операции,
22
операции сравнения, операцию преобразования в строку и статический метод получения комплексного числа из строки.
6.Разработать класс «Комплексное число», в котором данные хранятся в двух видах: алгебраической и тригонометрической формах. Определить в нем конструкторы и деструктор, перегрузить арифметические операции, операции сравнения, операцию преобразования в строку и статический метод получения комплексного числа из строки, написать методы преобразования числа из одной формы в другую. Протестировать все возможности класса.
7.Разработать класс «Дата». Определить в нем конструкторы и деструктор, перегрузить операцию добавления к дате заданного количества дней, операцию вычитания двух дат, операции сравнения и операцию преобразования в символьную строку, а также статический метод получения даты из строки.
8.Разработать класс «Время». Определить в нем конструкторы и деструктор, перегрузить операцию добавления к времени заданного количества минут, операцию вычитания двух моментов времени, операцию преобразования в символьную строку и метод получения момента времени из строки.
9.Разработать класс «Прямоугольник». Определить в нем конструкторы и деструктор, перегрузить операцию пересечения прямоугольников
(операция “*”), операцию вычисления площади прямоугольника операции сравнения (по площади), операцию преобразования в символьную строку и метод получения объекта-прямоугольника из строки.
10.Разработать класс «Треугольник». Определить в нем конструкторы и деструктор, перегрузить операцию преобразования в вещественное число (площадь треугольника), операцию проверки включения точки в треугольник, операции сравнения треугольников (по площади), операцию преобразования в символьную строку и метод получения объекта-треугольника из строки.
23
2. Методы решения уравнений
Решим следующую математическую задачу. Требуется найти корень уравнения вида f(x) = 0 на отрезке [a, b] с точностью (точность по функционалу), т.е. нужно найти точку x [a, b], для которой выполняется неравенство | f (x)| ≤ .
Для решения этой задачи существует целый ряд различных методов, самыми известными из которых являются метод деления отрезка пополам, метод хорд и метод касательных.
Для применения этих методов необходимо, чтобы:
1)функция f (x) являлась непрерывной,
2)значения функции f(x) на концах отрезка имели противоположные знаки (тогда гарантируется, что корень на отрезке существует);
3)для метода касательных обязательно требуется, чтобы функция f(x) была выпуклой или вогнутой на отрезке.
Все три метода нахождения корня основываются на единой процедуре.
1.Некоторым образом выбирается точка с [a, b].
2.Выбирается один из отрезков [a, с] или [с, b], на котором далее будет производиться поиск корня. Должен быть выбран тот из отрезков, на котором в точках-концах функция принимает значения различных знаков:
если f (a)* f (c) < 0, то b = с, иначе a = с .
3. Если на новом отрезке | f (a)| ≤ , то a – приближенное значение корня. Если же | f (b)| ≤ , то b – приближенное значение корня.
Отличия метода деления отрезка пополам, метода хорд и метода касательных заключаются в реализации пункта 1 указанной процедуры. Так, метод деления отрезка пополам выбирает в качестве точки c середину отрезка [a, b], метод хорд – точку пересечения отрезка, соединяющего точки (a, f(a)) и (b, f(b)), с осью абсцисс, метод касательных – точку пересечения одной из касательных к графику функции f(x), построенных в точках a и b, с осью абсцисс (выбирается та из точек пересечения, которая принадлежит отрезку [a, b]).
На рис. 2.1 изображены варианты выбора следующего отрезка, на котором будет осуществлен поиск корня, когда точка c определена методом хорд. На рис. 2.1 а приведено изменение левого конца отрезка (на следующей итерации точку a перенесем в точку x), на рис. 2.1 б – правого (точку b перенесем в точку x).
24
Рис. 2.1. Демонстрация одной итерации метода хорд.
При решении этой задачи будем использовать делегаты. Напомним, что делегаты – это классы, которые предназначены для хранения информации о каких-либо методах с одинаковым прототипом. Объект делегата становится псевдонимом хранимого метода (ссылкой на него). Как и любой объект, делегат можно передавать в функцию как параметр, он может являться полем класса или возвращаемым значением функции. Делегат также можно использовать для вызова хранимого метода в тот момент, когда это станет необходимо.
Создадим класс Solver, который будет решать уравнение. Пусть этот класс будет содержать только один открытый статический метод RootEquation() для решения уравнения. Остальные методы – методы определения точки-середины отрезка (GetX1()), точки пересечения хорды (GetX2()), и точки пересечения касательной с осью абсцисс (GetX3()), будут закрытыми, т.е. будут играть служебную роль. Выбор метода решения будет осуществляться случайным образом в статическом конструкторе.
Такая структура класса предусматривает использование делегатов в двух ситуациях:
1) Делегаты часто используются в качестве параметров других методов. В нашем случае уравнение будет задано посредством определения функции f(x). Для хранения информации о том, как ее вычислять, создадим делегат:
25
// делегат для представления математической функции delegate double Function(double x);
Экземпляр данного делегата может хранить информацию о любом методе, который получает в качестве параметра и возвращает вещественное число, например, таким методом может быть статический метод Sin() класса Math.
Таким образом, метод RootEquation() может получить указание как вычислять функцию f(x) с помощью параметра типа указанного делегата.
2) Второй случай использования делегатов – настройка алгоритма решения задачи. Как уже было сказано, все три метода поиска корня основываются на единой процедуре, которая отличается только реализацией одного шага – выбора точки, разбивающей отрезок на два. Для реализации этого шага создадим в классе Solver три различных метода, информацию о которых будет хранить экземпляр следующего делегата:
// делегат для определения точки деления исходного отрезка delegate double PointIn (Function f, double a, double b);
В классе Solver данный экземпляр будем хранить в виде статического поля method и инициализируем его в статическом конструкторе:
class Solver
{
// делегат для определения точки деления отрезка static PointIn method;
// статический конструктор static Solver()
{
// инициализация генератора случайных чисел
Random r = new Random(); int q = r.Next(300)%3; switch (q)
{
case 0:
// инициализация делегата функцией GetX1 method = GetX1; Console.WriteLine("Выбран метод деления
отрезка пополам");
break;
26
case 1:
// инициализация делегата функцией GetX2 method = GetX2; Console.WriteLine("Выбран метод хорд"); break;
case 2:
// инициализация делегата функцией GetX3 method = GetX3;
Console.WriteLine("Выбран метод касательных"); break;
}
}
// получение середины отрезка
static double GetX1(Function f, double a, double b)
{
return (a + b) / 2;
}
//получение точки пересечения хорды с осью OX static double GetX2(Function f, double a, double b)
{
return a - f(a) * (b - a) / (f(b) - f(a));
}
//получение точки пересечения касательной с осью OX static double GetX3(Function f, double a, double b)
{
//приближенное вычисление производной в точке a double fa = (f(a + 0.001) - f(a)) / 0.001;
if (fa != 0)
{
//получение точки пересечения касательной
//с осью абсцисс
double c = a - f(a) / fa;
//если точка c принадлежит отрезку,
//выбираем ее
if (a <= c && c <= b) return c;
}
// приближенное вычисление производной в точке b double fb = (f(b + 0.001) - f(b)) / 0.001;
if (fb != 0)
{
//получение точки пересечения касательной
//с осью абсцисс
double c = b - f(b) / fb; if (a <= c && c <= b)
return c;
}
27
//функция не удовлетворяет тем свойствам,
//которые гарантируют существование корня throw new Exception("Возможно, на этом
отрезке корней нет");
}
. . .
}
Для решения уравнения достаточно иметь только одну функцию, которая реализует общую процедуру всех методов решения уравнений. Реализация пункта 1 процедуры в этой функции осуществляется посредством вызова через делегат method именно того метода деления отрезка, который был выбран при инициализации класса Solver. В указанном далее коде использование делегатов выделено.
//метод решения уравнения
//1 параметр – делегат функции, которая определяет уравнение,
//2, 3 параметры - концы отрезка,
//4 параметр - точность решения
static public double RootEquation(Function f, double a, double b, double eps)
{
//корень гарантировано существует,
//если на концах отрезка
//функция принимает значения различных знаков. if(f(a) * f(b) > 0)
throw new Exception("Возможно, на этом отрезке корней нет");
//цикл метода - вычисления продолжается до тех пор,
//пока на одном из концов отрезка не будет получено
//значение функции с заданной точностью
while(Math.Abs(f(a))>eps && Math.Abs(f(b))>eps)
{
//поиск точки деления отрезка - вызов делегата double c = method(f,a,b);
//если найденная точка - корень, это решение if(f(c) == 0)
return c;
//выбор следующего отрезка
if(f(a)*f(c) < 0) b = c;
else
a = c;
}
// выбор приближенного значения корня if(Math.Abs(f(a))<=eps )
return a; else
return b;
}
28
Использование разработанного класса для приближенного решения квадратного уравнения x2 – 2x – 5 = 0 может быть таким:
class Program
{
// функция определения уравнения static double func(double x)
{
return x * x - 2 * x - 5;
}
static void Main(string[] args)
{
Console.WriteLine("Введите отрезок"); Console.WriteLine("Введите a");
double a = double.Parse(Console.ReadLine()); Console.WriteLine("Введите b");
double b = double.Parse(Console.ReadLine()); Console.WriteLine("Введите точность решения"); double eps = double.Parse(Console.ReadLine()); try
{
// вызов метода решения уравнения
Console.WriteLine("Корень = {0}",
Solver.RootEquation(func, a, b, eps));
}
catch (Exception e)
{
Console.WriteLine(e.Message);
}
}
}
Рис 2.2. Демонстрация работы программы при выборе метода деления отрезка пополам
29