Двоичное дерево поиска, или BST, — это структура данных, предназначенная для работы с упорядоченными множествами. Свойство дерева: если мы находимся в вершине с ключом k, то в левом поддереве находятся только ключи, которые строго меньше k, а в правом — строго больше. Описание методов, реализованных в классе BinarySearchTree: метод add(): если дерево пустое, то говорим, … Continue reading
Обратная польская нотация
Передо мной стояли задачи: перевести выражение в обратную польскую нотацию; посчитать значение выражения. Также я реализовала унарный минус, деление и функции cube(), sqrt(), pow10(). Выражение Обратная польская нотация Результат 15 * -(3 — 4) 15 3 4 — u- * 15 sqrt(4) + (8 * 0.5) 4 sqrt 8 0.5 * + 6 -cube(-3) 3 … Continue reading
Segmented Array
Задача Необходимо реализовать некоторую коллекцию индексированных данных некоторого типа T, выглядящую как несколько необычный массив. Вместо операции присваивания значения элементу массива в нём имеется операция присваивания одинаковых значений всем элементам для некоторого диапазона индексов. Также и операции поиска минимума и максимума должны работать для некоторого диапазона значений индексов. При написании класса, реализующего данный интерфейс необходимо … Continue reading
Двоичное дерево поиска
Задача Реализовать структуру «Двоичное дерево поиска» в соответствии с этим шаблоном. Решение По моему субъективному мнению, тут следует привести более ли менее детальное описание только операций вставки и удаления вершины. Операция вставки Пусть у нас есть вершина с ключом [latex]key[/latex] и дерево [latex]T[/latex], в которое нам нужно вставить нашу вершину. Сразу у нас есть ссылка … Continue reading
Java Collections Framework: Map. Частотный словарь.
Задача 1: Получив на входе корпус языка (огромный набор атрибутированных текстов на каком-нибудь языке) построить частотный словарь. Знаки препинания, скобки, кавычки и числа должны быть удалены. Слова, содержащие в себе не буквенные символы, игнорируются целиком. Задача 2: При автоматическом переводе необходимо из нескольких слов выбрать наиболее употребительное. Необходимо построить эффективную реализацию функции, которая для данного … Continue reading
BigSegmentedArray by Tolia
Мне предоставили реализовать класс, который наследует SegmentedArray и характеризуется следующим: принимает большой массив частые запросы get(), min(); Поскольку команда set задает значение на интервале, я решил сделать «дерево отрезков». Которое устроено как бинарное дерево относительно индекса (в задании большое количество запросов get(), следовательно будет быстрее искать элемент по индексу), имея в себе левый и правые концы … Continue reading
Binary Tree Search
Код реализация Бинарного дерева на Java для задания из Word of Week. Саму идею дерева и теоретический алгоритм можно почитать в Википедии. Отличается от реализации на C++ тем, что в Java мы не обращаемся к адресам узлам явно, сравнение происходит через компаратор и сам класс при создании имеет свои особенности от C++. Для работы самого … Continue reading
Задача жестянщика
Задание: Из круга радиуса [latex]r[/latex] вырезан прямоугольник, большая сторона которого равна [latex]a[/latex]. Найти максимальный радиус круга, который можно вырезать из полученного прямоугольника. Тесты: [latex]a[/latex] [latex]R[/latex] [latex]r[/latex] 4 2 3.8729835 2 [latex]2 \sqrt{2}[/latex] 1.4142135 5 5 4.3301272
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
import java.util.*; import java.lang.*; import java.math.*; class asdasd { public static void main (String[] args) throws java.lang.Exception { //r^2=rmax^2+(a/2)^2 Scanner in=new Scanner(System.in); float a,r; System.out.println("r:"); r=in.nextFloat(); System.out.println("a:"); a=in.nextFloat(); calc(r,a); } static void calc(float x, float y){ System.out.println("res: "+(float) Math.sqrt(Math.pow(x, 2)-Math.pow(y/2, 2))); } } |
BitSegmentedArray
Мне предоставили реализовать класс, который наследует SegmentedArray и характеризуется следующим: принимает большой массив элементы массива — 0 и 1 частые запросы get() и set() Чтобы была возможность хранить очень большой массив, я решила построить класс с помощью битовых операций. Это было возможно, так как элемент моего массива — это 0 и 1, и любое число … Continue reading
Java Collections Framework: Map. Частотный словарь.
Задача 1: Получив на входе корпус языка (огромный набор атрибутированных текстов на каком-нибудь языке) построить частотный словарь. Знаки препинания, скобки, кавычки и числа должны быть удалены. Слова, содержащие в себе не буквенные символы, игнорируются целиком. Задача 2: При автоматическом переводе необходимо из нескольких слов выбрать наиболее употребительное. Необходимо построить эффективную реализацию функции, которая для данного … Continue reading