Класс для работы с геометрическими векторами на плоскости

Задача

Напишите класс для работы с геометрическими векторами на плоскости. Реализуйте максимально возможное количество методов.

Тесты

x1 y1 x2 y2 x3 y3 x4 y4 Ск. пр. Угол
4 4 61 12 44 65 21 51 -1423 2.7342438697918836

Код

 

Описание решения

Переменные x1,y1,x2,y2 являются координатами начала и конца вектора, xV и yV — координаты вектора, xM и yM — координаты середины вектора, vL — длина вектора. Реализованы методы для нахождения середины вектора, длины вектора, умножения вектора на число, сложения векторов, скалярного произведения векторов и нахождения угла между векторами.

Код можно просмотреть на сайте ideone

Класс изменяемых рациональных дробей

Задача

Напишите класс для работы с изменяемыми (mutable) рациональными дробями, подготовьте для него интерфейс.

Тесты

Входные данные: четыре целых числа — числитель и знаменатель дроби F1, числитель и знаменатель  дроби F2

Выходные данные: результаты сравнения, сложения, вычитания, умножения, деления дробей F1 и F2

Входные данные Дробь F1 Дробь F2 Сравнение F1 и F2 F1+F2 F1-F2 F1*F2 F1/F2
1 1 2 2 3 1/2 2/3 1/2<2/3 7/6 -1/6 1/3 3/4
2 4 16 3 -5 1/4 -3/5 1/4>-3/5 -7/20 17/20 -3/20 -5/12
3 1 7 2 14 1/7 1/7 1/7=1/7 2/7 0/1 1/49 1/1
4 2 4 0 4 1/2 0/1 1/2>0/1 1/2 1/2 0/1 Error

Код

Код доступен на ideone

Пояснение

Класс Arithmetics содержит метод для вычисления НОД  public static int gcd(int a, int b).

Класс  Fraction  предназначен для работы с изменяемыми дробями. Его методы предосталяют возможность выполнять такие действия с дробью:

  • получить значение числителя (метод public int getNumerator()) и знаменателя (метод public int getDenominator());
  • задать значение (методы  public void setValue() с различными параметрами) числителем и знаменателем (параметры  int n, int d, целым числом (параметр  int n) или другой дробью (параметр  Fraction f);
  • прибавить, отнять, умножить на, разделить на дробь или целое число (методы  public void  add(), substract(), multiply()divide() с параметрами  Fraction f или int n;
  • сравнить с другой дробью (методы  public boolean equals() и  public int compareTo();
  • получить строковое представление дроби (метод  public String toString().

Класс для хранения матриц

Задача

Напишите класс для хранения матриц и реализуйте основные операции работы с ними.

Тесты

Операция Входная матрица А Входная   матрица В Результат
 1 Транспони-рования 33 34 12
33 19 10
12 14 17
84 24 51
43 71 21
33 33 12 84 43
34 19 14 24 71
12 10 17 51 21
 2 Сложения -1   1   -1
1   -1   1
-1   1   -1
1   -1   1
-1    1  -1
1   -1   1
0   0   0
0   0   0
0   0   0
 3 Вычитания -1   1   -1
1   -1   1
-1   1   -1
1   -1   1
-1    1  -1
1   -1   1
-2   2   -2
2   -2   2
-2   2   -2
 4 Умножения 33  34  12
33  19  10
12  14  17
84  24  51
43  71  21
10  11  34  55
33  45  17  81
45  63  12  16
1992 2649 1844 4761
1407 1848 1565 3514
1347  1833 850 2066
3927 5217 3876 7380
3718 4991 2921 8452

Решение

Проверить работу кода можно в облаке по ссылке — Ideone.

Пояснения

Класс  Matrix  имеет следующие поля:  n, m  — размеры основной матрицы, и сама матрица  mainMatrix , представлена в виде двумерного массива целочисленного типа. Также данный класс имеет два конструктора: первый из которых принимает как параметры размеры создаваемой матрицы public Matrix(int n, int m) , второй же принимает как параметр двумерный массив(матрицу)  public Matrix(int [][] paramMatrix) .

Данный класс имеет следующие методы:

  1. public int getElement(int n, int m)  — метод для получения элемента матрицы по индексам;
  2. public void setElement(int n, int m, int value)  — метод задания элемента по индексам;
  3. public int getVerticalLength() — метод получения количества строк в матрице;
  4. public int getHorizontalLength()  — метод получения количества столбцов в матрице;
  5. public void fillRandomValues()  — метод заполнения матрицы рандомными значениями;
  6. public void displayMatrix()  — метод вывода матрицы;
  7. public static int[][] transpone(int[][] paramMatrix)  — метод транспонирования матрицы, с двумерным массивом как параметр;
  8. public static Matrix transpone(Matrix paramMatrix)  — метод транспонирования матрицы, с объектом класса  Matrix , как параметр;
  9. public static Matrix add(Matrix first, Matrix second)  — метод нахождения суммы двух матриц;
  10. public static Matrix subtract (Matrix first, Matrix second)  — метод вычитания одной матрицы из другой;
  11. public static Matrix multiply (Matrix first, Matrix second)  — метод произведения двух матриц.

Для последних трех методов был написан псевдокласс NotEqualLengthsOfMatrixException  наследник класса  Exception , чтобы при несовпадении размеров заданных матриц генерировать исключительную ситуацию.

Класс рациональных дробей

Задача

Напишите класс для работы с не изменяемыми (immutable) рациональными дробями используя статические методы.

Код

Код на Ideone.

Тест

Входящие данные Операция Выходящие данные
4/5

1/2

проверка равенства false
4/5

1/2

2/5

сравнение по равенству дроби и произведения двух других true
2/5

1/2

сложение 9/10
4/5

1/2

вычитание 3/10
4/5

1/2

вычитание -3/10
2/5

1/2

умножение 1/5
4/5

1/2

деление 8/5
4/5

1/2

сравнение 4/5 > 1/2
4/5

1/2

сравнение 1/2 > 2/5
4/5

1/2

2/5

сравнение дроби и произведения двух других 2/5 = 2/5

 

Class Matrix

Задача:

Напишите класс для хранения матриц и реализуйте основные операции работы с ними.

Тесты:

Исходные данные Операция Результат
1.  

A:                            B:

-9  1  0                      1  0  0

4   1   1                     0  2  0

-2   2  -1                    0  0  1

 

+ -8 1 0
4 3 1
-2 2 0
2. -10 1 0
4 -1 1
-2 2 -2
3. * -9 2 0
4 2 1
-2 4 -1
4. -9 1 0
4 1 1
-2 2 -1
transposition -9 4 -2
1 1 2
0 1 -1

Решение на Ideone

Класс комплексных чисел

Задача.

Напишите класс для хранения комплексных чисел и реализуйте основные операции работы с ними.

Тесты.

Исходные числа Операция Результат
z1 = 2 + 3i

z2 = -1 + 2i

+ 1.0 + 5.0i
3.0 + i
* -8.0 + i
/ 0.8 — 1.4i
3 + 4i  2.0 + i,

-2.0 -i

-1 + 2i pow -3.0 — 4.0i

Код программы

Ссылка на Ideone.

Векторы

Задача. Написать класс для работы с геометрическими векторами на плоскости. Реализовать максимально возможное количество методов.
Определение. Вектор — это направленный отрезок, то есть отрезок, имеющий длину и определенное направление. Графически вектора изображаются в виде направленных отрезков прямой определенной длины.

Код программы:

Описание класса:

Формулы

Длина вектора
|\vec{a}| = \sqrt{x^2+y^2}

Умножения вектора на число
\lambda \vec{a} = \left\{ \lambda x; \lambda y \right\}

Проекция вектора на вектор
{}_{\vec{b}}\vec{a} = \frac{\vec{a}\cdot\vec{b}}{|\vec{b}|}.

Основная программа

Ход выполнения

При выполнении происходит проверка функций класса: логических, арифметических, построения объектов, функции строкового отображения объекта.

Вывод программы

Ссылки

Код программы на Ideone

Quaternion

Условие

Кватернионы (от лат. quaterni, по четыре) — система гиперкомплексных чисел, образующая векторное пространство размерностью четыре над полем вещественных чисел. Обычно обозначаются символом H. Предложены Уильямом Гамильтоном в 1843 году.
Кватернионы удобны для описания изометрий трёх- и четырёхмерного евклидовых пространств, и поэтому получили широкое распространение в механике. Также их используют в вычислительной математике, например, при создании трёхмерной графики.
Источник: Кватернионы — Википедия.

Код на Java:

Описание класса:

Стандартное определение

Кватернионы можно определить как формальную сумму a + bi + cj + dk, где a, b, c, d — вещественные числа, а i, j, k — мнимые единицы со следующим свойством: i2 = j2 = k2 = ijk = −1.
Таким образом, таблица умножения базисных кватернионов — 1, i, j, k — выглядит так:

× 1 i j k
1 1 i j k
i i -1 k -j
j j -k -1 i
k k j -1 -1

Сопряжение

Для кватерниона q сопряжённым называется:
conj(q) = a - bi - cj - dk

Модуль

Так же, как и для комплексных чисел,
abs(q) = sqrt(q*conj(q)) = sqrt(a^2 + b^2 + c^2 + d^2)
называется модулем q.

Обращение умножения (деление)

Кватернион, обратный по умножению к q, вычисляется так:
q^-1 = conj(q)/abs(q)^2.

Основная программа:

Ход выполнения

При выполнении происходит проверка функций класса: логических, арифметических, построения объектов, производных от исходного (таких, как сопряженное и обратное значение), функции строкового отображения объекта.

Вывод программы:

Ссылки:

Рабочий код для тестирования на Ideone.com: Ideone.com

BST – Двоичные деревья поиска

Задача

Разработать класс, реализующий функциональность дерева двоичного поиска.

Ссылка на условие http://java.mazurok.com/word-of-week/bst

Тесты

input output
put S 11.11 Ok
put E 22.22 Ok
put A 33.33 Ok
put R 44.44 Ok
put H 55.55 Ok
put C 66.66 Ok
put X 77.77 Ok
put M 88.88 Ok
size 8
min (A->33.33)/2
max (X->77.77)/1
print L0: (S->11.11)/8
.L1: (E->22.22)/6
..L2: (A->33.33)/2
…L3: (C->66.66)/1
..L2: (R->44.44)/3
…L3: (H->55.55)/2
….L4: (M->88.88)/1
.L1: (X->77.77)/1
delete E Ok
size 7
min (A->33.33)/2
max (X->77.77)/1
print L0: (S->11.11)/7
.L1: (H->55.55)/5
..L2: (A->33.33)/2
…L3: (C->66.66)/1
..L2: (R->44.44)/2
…L3: (M->88.88)/1
.L1: (X->77.77)/1
exit N/A

Критерий тестирования

В ходе тестирования мы добавляем 8 ключей с уникальными значениями. Затем мы определяем размер, минимальный и максимальный узлы, а также распечатываем все дерево, чтобы убедится, что оно имеет ожидаемою конфигурацию. Затем мы удаляем 1 ключ с серединным значением и повторяем вышеперечисленные операции, чтобы увидеть ожидаемые изменения в дереве.

Формат вывода:

Команды min и max выводят одиночный узел в следующем формате: (ключ->значение)/кол-во узлов

Команда print выводит дерево по уровням, каждая строчка имеет следующий формат: уровень: (ключ->значение)/кол-во узлов

Структура программы

Код программы состоит из следующих элементов, объединенных в пакет odessa.uni.imem.maxim:

  1. Класс CountingBST, реализующий функциональность дерева двоичного поиска с подсчетом количества узлов в дереве
  2. Класс CountingBSTTestApp, реализующий тестовое приложение

Класс CountingBST

Все методы разделены на пары — один метод пары приватный, а другой — публичный. Это необходимо для того, чтобы передавать первым аргументом корень дерева, начиная с которого выполняются все операции. Каждый приватный метод содержит первым аргументом узел, начиная с которого будет выполнятся операция. Публичный метод вызывает приватный и передает ему в качестве первого аргумента корень дерева. Это относится к основным операциям на дереве:

  1. put — помещает ключ и значение в дерево
  2. get — извлекает значение по клчу
  3. size — возвращает количество узлов дерева
  4. min — находит узел с минимальным ключом
  5. max — находит узел с максимальным ключом
  6. delete — удаление по Хиббарду ( Coursera presentation )
  7. print — печать дерева

Помимо основных полей, необходимых для BST, узел содержит поле count, в котором содержится количество все узлов поддерева, корнем которого является данный узел, включая сам узел.

Класс CountingBSTTestApp

Данный класс реализует тестовое приложение для класса CountingBST. Он содержит вспомогательные функции ввода и функцию main, содержащую код теста. Он реализует командный интерпритатор, где каждая команда вызывает соответствующий публичный метод тестируемого класса. По-этому тест представляет собой текстовый файл с командами для стандартного потока ввода с консоли.

Ссылка на Ideone: https://ideone.com/b0xrPX

 

Binary Heap (двоичная куча)

В данном отчёте я напишу о структуре данных под названием куча (Heap), а точнее — о её разновидности.

Двоичная куча

Двоичная куча — структура данных, двоичное дерево, для которого выполнены три условия:

  • Значение в любой вершине не меньше чем значение в потомках
  • Расстояние до корня отличается не более чем на один уровень
  • Заполняется слева на право

Зафиксируем операции, которые будем проводить над кучей:

  • Достать максимальный элемент из кучи, не удаляя его
  • Добавить элемент в кучу
  • Создать кучу
  • Отсортировать массив путём превращения его в кучу, а кучи — в отсортированный массив
  • Узнать размер кучи
  • Удалить максимальный элемент из кучи

Описание методов

1. Восстановление свойства кучи

Каждый элемент помещается в конец кучи, потом становится на своё место, соответственно свойств кучи.

Сложность: O(\log(n))

2. Возврат максимального элемента

Возвратить содержимое самой верхней вершины.

Сложность: O(1)

3. Удаление максимального элемента

Меняются местами первая и последняя вершины, после чего последняя вершина запоминается и удаляется, а новая первая вершина проталкивается в кучу, согласно её свойствам.

Сложность: O(\log(n))

4. Пирамидальная сортировка

Достаточно заметить, что в самую первую вершину кучи всегда (по крайней мере, по введённым свойствам) встаёт максимальный элемент. Если каждый раз удалять максимальный элемент — получим отсортированный массив.

Сложность: O(n\log(n))

О реализации

Реализуется структура данных с абстрактным типом данных.  Для хранения вершин будем использовать ArrayList. Для каждой вершины под номером i её левый сын хранится в 2*i+1 вершине, а правый — в 2*i+2 вершине.

Класс содержит следующие методы:

  • Heap() — конструктор
  • shiftUp() — восходящее восстановление свойства кучи
  • shiftDown() — нисходящее восстановление свойства кучи
  • insert() — добавление элемента в кучу
  • delete() — удаление первой вершины
  • size() — размер кучи
  • isEmpty() — проверка на пустоту
  • toString() — преобразование в строку
  • max() — максимальный элемент
  • print() — вывод кучи на экран

Код