Практические Мацука. Основы программирования на. Net и Java
 Скачать 131.13 Kb.
|
|
Тема: двоичный поиск Цель: двоичный поиск Задача: Напишите метод, который проверяет, входит ли в массив заданный элемент или нет. Используйте перебор и двоичный поиск для решения этой задачи. Сравните время выполнения обоих решений для больших массивов (например, 100000000 элементов). Решение: /* Просто перебираем, пока не найдет. Если ничего не найдём, вернём -1 */ public static int bruteForce(double[] array, double key) { for (int i = 0; i < array.length; i++) { if (array[i] == key) return i; } return -1; } /* Двоичный поиск */ public static int binarySearchRecursively(double[] sortedArray, double key) { return binarySearchRecursively(sortedArray, key, 0, sortedArray.length); } /** * Вспомогательный метод для {@link #binarySearchRecursively(double[], double)} * * Будем делить отрезок пополам, но не копировать, а просто "сдвигать границы", * и вызывать этот же метод рекурсивно. Для этого используем low и high * * @param sortedArray сортированный массив * @param key искомое значение * @param low от какого значения ищем * @param high до какого значения ищем * @return индекс элемента */ private static int binarySearchRecursively (double[] sortedArray, double key, int low, int high) { int middle = (low + high) / 2; // середина if (high < low) { // больше делить нечего return -1; } if (key == sortedArray[middle]) { // если нашёлся return middle; } else if (key < sortedArray[middle]) { // ищем в левой половине return binarySearchRecursively( sortedArray, key, low, middle - 1); } else { return binarySearchRecursively( // ищем в правой половине sortedArray, key, middle + 1, high); } } // Вспомогательный метод для тестов private static double[] generateRandomArray(int length) { double[] array = new double[length]; for (int i = 0; i < array.length; i++) { array[i] = Math.random(); } return array; } public static void main(String[] args) { double[] array = generateRandomArray(100000000); Arrays.sort(array); // нужно сначала отсортировать /* Строго говоря, измерять время выполнения так не совсем корректно, лучше использовать benchmarks см. https://habr.com/ru/post/349914/ Но масштаб будет понятен */ long time = System.currentTimeMillis(); // текущее время, unix-time bruteForce(array, 0.5); System.out.println(System.currentTimeMillis() - time); time = System.currentTimeMillis(); binarySearchRecursively(array, 0.5); System.out.println(System.currentTimeMillis() - time); } Практическая 3.1. Тема: найти корень уравнения Цель: найти корень уравнения Задача: Найдите корень уравнения cos(x^5) + x^4 - 345.3 * x - 23 = 0 на отрезке [0; 10] с точностью по x не хуже, чем 0.001. Известно, что на этом промежутке корень единственный. Используйте для этого метод деления отрезка пополам (и рекурсию). Решение: // вспомогательный метод public static double func(double x){ return Math.cos(Math.pow(x, 5)) + Math.pow(x, 4) - 345.3 * x - 23; } // решить уравнение public static double solve(double start, double end){ if(end - start <= 0.001){ return start; } double x = start + (end - start) / 2; if(func(start) * func(x) > 0){ return solve(x, end); } else { return solve(start, x); } } public static void main(String[] args) { System.out.println(solve(0, 10)); } Замечание: если мы хотим добиться нужной точности не по x, по y, то условие в методе следует переписать: if(Math.abs(func(start)- func(end)) <= 0.001){ return start; } Маленькая хитрость: учитывая, что множество значений double конечно (есть два соседних значения, между которыми нет ни одного значения double), условие выхода из рекурсии переписать так: double x = start + (end - start) / 2; if(x == end || x == start){ return x; } Таким образом получим максимальную точность, которую вообще можно получить, используя этот подход. Наследование Практическая 4.0. Тема: реализовать иерархию классов, описывающую трёхмерные фигуры Цель: реализовать иерархию классов, описывающую трёхмерные фигуры Задача: Реализуйте иерархию классов:  Класс Box является контейнером, он можем содержать в себе другие фигуры. Метод add() принимает на вход Shape. Нужно добавлять новые фигуры до тех пор, пока для них хватаем места в Box (будем считать только объём, игнорируя форму. Допустим, мы переливаем жидкость). Если места для добавления новой фигуры не хватает, то метод должен вернуть false. Решение: class Shape { private double volume; public Shape(double volume) { this.volume = volume; } public double getVolume() { return volume; } } class SolidOfRevolution extends Shape { private double radius; public SolidOfRevolution(double volume, double radius) { super(volume); this.radius = radius; } public double getRadius() { return radius; } } class Ball extends SolidOfRevolution { // конкретный класс public Ball(double radius) { super(Math.PI * Math.pow(radius, 3) * 4 / 3, radius); } } class Cylinder extends SolidOfRevolution { // конкретный класс private double height; public Cylinder(double radius, double height) { super(Math.PI * radius * radius * height, radius); this.height = height; } } class Pyramid extends Shape{ private double height; private double s; // площадь основания public Pyramid(double height, double s) { super(height * s * 4 / 3); this.height = height; this.s = s; } } class Box extends Shape { private ArrayList private double available; public Box(double available) { super(available); this.available = available; } public boolean add(Shape shape) { if (available >= shape.getVolume()) { shapes.add(shape); available -= shape.getVolume(); return true; } else { return false; } } } public class Main { public static void main(String[] args) { Ball ball = new Ball(4.5); Cylinder cylyinder = new Cylinder(2, 2); Pyramid pyramid = new Pyramid(100, 100); Box box = new Box(1000); System.out.println(box.add(ball)); // ok System.out.println(box.add(cylyinder)); // ok System.out.println(box.add(pyramid)); // failed } } Чтобы к этой задаче не возвращаться, далее описывается еще несколько вариаций этой задачи. Практическая 4.1. Тема: реализовать иерархию классов, описывающую трёхмерные фигуры — 2 Цель: реализовать иерархию классов, описывающую трёхмерные фигуры — 2 Задача: Реализуйте ту же иерархию классов, но сделав некоторые классы абстрактными. Решение: abstract class Shape { public abstract double getVolume(); } abstract class SolidOfRevolution extends Shape { protected double radius; public SolidOfRevolution(double radius) { this.radius = radius; } public double getRadius() { return radius; } } class Ball extends SolidOfRevolution { // конкретный класс @Override public double getVolume() { return Math.PI * Math.pow(radius, 3) * 4 / 3; } public Ball(double radius) { super(radius); } } class Cylinder extends SolidOfRevolution { // конкретный класс private double height; public Cylinder(double radius, double height) { super(radius); this.height = height; } @Override public double getVolume() { return Math.PI * radius * radius * height; } } class Pyramid extends Shape { private double height; private double s; // площадь основания public Pyramid(double height, double s) { this.height = height; this.s = s; } @Override public double getVolume() { return height * s * 4 / 3; } } class Box extends Shape { private ArrayList private double available; private double volume; public Box(double available) { this.available = available; this.volume = available; } public boolean add(Shape shape) { if (available >= shape.getVolume()) { shapes.add(shape); available -= shape.getVolume(); return true; } else { return false; } } @Override public double getVolume() { return volume; } } public class Main { public static void main(String[] args) { Ball ball = new Ball(4.5); Cylinder cylyinder = new Cylinder(2, 2); Pyramid pyramid = new Pyramid(100, 100); Box box = new Box(1000); System.out.println(box.add(ball)); // ok System.out.println(box.add(cylyinder)); // ok System.out.println(box.add(pyramid)); // failed } } Практическая_4.2._Тема'>Практическая 4.2. Тема: реализовать иерархию классов, описывающую трёхмерные фигуры — 3 Цель: реализовать иерархию классов, описывающую трёхмерные фигуры — 3 Задача: Реализуйте ту же иерархию классов, но использовав интерфейсы. Решение: interface Shape extends Comparable double getVolume(); @Override default int compareTo(Shape other) { return Double.compare(getVolume(), other.getVolume()); } } abstract class SolidOfRevolution implements Shape { protected double radius; public SolidOfRevolution(double radius) { this.radius = radius; } public double getRadius() { return radius; } } class Ball extends SolidOfRevolution { // конкретный класс @Override public double getVolume() { return Math.PI * Math.pow(radius, 3) * 4 / 3; } public Ball(double radius) { super(radius); } } class Cylinder extends SolidOfRevolution { // конкретный класс private double height; public Cylinder(double radius, double height) { super(radius); this.height = height; } @Override public double getVolume() { return Math.PI * radius * radius * height; } } class Pyramid implements Shape { private double height; private double s; // площадь основания public Pyramid(double height, double s) { this.height = height; this.s = s; } @Override public double getVolume() { return height * s * 4 / 3; } } class Box implements Shape { private ArrayList private double available; private double volume; public Box(double available) { this.available = available; this.volume = available; } public boolean add(Shape shape) { if (available >= shape.getVolume()) { shapes.add(shape); available -= shape.getVolume(); return true; } else { return false; } } @Override public double getVolume() { return volume; } public ArrayList return shapes; } } public class Main { public static void main(String[] args) { Ball ball = new Ball(4.5); Cylinder cylyinder = new Cylinder(2, 2); Pyramid pyramid = new Pyramid(100, 100); Box box = new Box(1000); System.out.println(box.add(ball)); // ok System.out.println(box.add(cylyinder)); // ok System.out.println(box.add(pyramid)); // failed // Sorting: ArrayList Collections.sort(shapes); // sorted by Volume! } } Абстрактные классы и интерфейсы Практическая 6.0. Тема; конвертер температур Цель; конвертер температур Задача: Напишите класс BaseConverter для конвертации из градусов по Цельсию в Кельвины, Фаренгейты, и так далее. У класса должен быть метод convert, который и делает конвертацию. Решение: interface Converter { double getConvertedValue(double baseValue); } class CelsiusConverter implements Converter { @Override public double getConvertedValue(double baseValue) { return baseValue; } } class KelvinConverter implements Converter { @Override public double getConvertedValue(double baseValue) { return baseValue + 273.15; } } class FahrenheitConverter implements Converter { @Override public double getConvertedValue(double baseValue) { return 1.8 * baseValue + 32; } } public class Main { public static void main(String[] args) { double temperature = 23.5; System.out.println("t = " + new CelsiusConverter().getConvertedValue(temperature)); System.out.println("t = " + new KelvinConverter().getConvertedValue(temperature)); System.out.println("t = " + new FahrenheitConverter().getConvertedValue(temperature)); } } Дополнительно можно попросить реализовать фабричный метод, как-то так: interface Converter { double getConvertedValue(double baseValue); public static Converter getInstance(){ Locale locale = Locale.getDefault(); String[] fahrenheitCountries = {"BS", "US", "BZ", "KY", "PW"}; boolean isFahrenheitCountry = Arrays.asList(fahrenheitCountries).contains(locale.getCountry()); if(isFahrenheitCountry){ return new FahrenheitConverter(); } else { return new CelsiusConverter(); } } } Практическая 6.1. Тема: Stringbuilder с поддержкой операции undo Цель: Stringbuilder с поддержкой операции undo Задача: Напишите свой класс StringBuilder с поддержкой операции undo. Для этого делегируйте все методы стандартному StringBuilder, а в собственном классе храните список всех операций для выполнения undo(). Это будет реализацией шаблона «Команда». Решение: /** * StringBuilder с поддержкой операции undo * java.lang.StringBuilder — класс с модификатором final, * поэтому нет наследования, используем делегирование. */ class UndoableStringBuilder { private interface Action{ void undo(); } private class DeleteAction implements Action{ private int size; public DeleteAction(int size) { this.size = size; } public void undo(){ stringBuilder.delete( stringBuilder.length() - size, stringBuilder.length()); } } private StringBuilder stringBuilder; // делегат /** * операции, обратные к выполненным. * То есть при вызове append, в стек помещается * операция "delete". При вызове undo() она * будет выполнена. */ private Stack // конструктор public UndoableStringBuilder() { stringBuilder = new StringBuilder(); } /** see {@link java.lang.AbstractStringBuilder#reverse()} После того, как сделан reverse(), добавляем в стек операций обратную — тоже reverse(). Далее таким же образом. */ public UndoableStringBuilder reverse() { stringBuilder.reverse(); Action action = new Action(){ public void undo() { stringBuilder.reverse(); } }; actions.add(action); return this; } public UndoableStringBuilder append(String str) { stringBuilder.append(str); Action action = new Action(){ public void undo() { stringBuilder.delete( stringBuilder.length() - str.length() -1, stringBuilder.length()); } }; actions.add(action); return this; } // ..... остальные перегруженые методы append пишутся аналогично (см. выше)...... public UndoableStringBuilder appendCodePoint(int codePoint) { int lenghtBefore = stringBuilder.length(); stringBuilder.appendCodePoint(codePoint); actions.add(new DeleteAction(stringBuilder.length() - lenghtBefore)); return this; } public UndoableStringBuilder delete(int start, int end) { String deleted = stringBuilder.substring(start, end); stringBuilder.delete(start, end); actions.add(() -> stringBuilder.insert(start, deleted)); return this; } public UndoableStringBuilder deleteCharAt(int index) { char deleted = stringBuilder.charAt(index); stringBuilder.deleteCharAt(index); actions.add(() -> stringBuilder.insert(index, deleted)); return this; } public UndoableStringBuilder replace(int start, int end, String str) { String deleted = stringBuilder.substring(start, end); stringBuilder.replace(start, end, str); actions.add(() -> stringBuilder.replace(start, end, deleted)); return this; } public UndoableStringBuilder insert(int index, char[] str, int offset, int len) { stringBuilder.insert(index, str, offset, len); actions.add(() -> stringBuilder.delete(index, len)); return this; } public UndoableStringBuilder insert(int offset, String str) { stringBuilder.insert(offset, str); actions.add(() -> stringBuilder.delete(offset, str.length())); return this; } // ..... остальные перегруженные методы insert пишутся аналогично (см. выше)...... public void undo(){ if(!actions.isEmpty()){ actions.pop().undo(); } } public String toString() { return stringBuilder.toString(); } } Практическая 6.2. |