Привет, Хаброжители! Ранее мы уже анонсировали книгу «Карьера программиста. 6-е издание" Гейлы Лакман Макдауэллы в этом посте. Теперь мы получили электронные права на эту книгу, а значит можем поделиться главой «Java» и предложить решить задачки: 1. Разработайте алгоритм для поиска наименьших К чисел в массиве.
2. Напишите функцию суммирования двух чисел без использования "+" или любых других арифметических операторов.
3. Для двух квадратов на плоскости найдите линию, которая делит эти два квадрата пополам. Предполагается, что верхняя и нижняя стороны квадрата проходят параллельно оси x.
Тем, кто предложит аргументированные решения — мы, с удовольствием, отправим электронную книгу в качестве подарка.
Глава Java
13.1. Как повлияет на наследование объявление конструктора приватным?
РЕШЕНИЕ
Объявление конструктора класса A со спецификатором private гарантирует, что конструктор будет доступен только для того, для кого доступны приватные методы A. Кто еще, кроме A, может обращаться к приватным методам и конструкторам A? Внутренние классы A. Кроме того, если A содержит внутренний класс Q, то и внутренние классы Q тоже смогут к ним обращаться.
Все это напрямую отражается на наследовании, потому что субкласс вызывает конструктор своего родителя. Класс A может использоваться для наследования, но только внутренними классами (его собственными или родительскими).
13.2. Будет ли выполняться блок finally (в коде Java), если оператор return находится внутри try-блока (конструкция try-catch-finally)?
РЕШЕНИЕ
Да, будет. Блок finally выполняется при выходе из блока try. Даже при попытке принудительного выхода из блока try (командой return, continue, break или еще каким-либо образом), блок finally все равно будет выполнен.
Блок finally не выполняется только в экстренных случаях, например:
- виртуальная машина прекратила свою работу во время выполнения блока try/catch;
- поток, который выполнял блок try/catch, был уничтожен.
13.3. В чем разница между final, finally и finalize?
РЕШЕНИЕ
Несмотря на похожие названия, final, finally и finalize имеют разные предназначения. final управляет «изменяемостью» переменной, метода или класса. finally используется в конструкции try/catch, чтобы гарантировать выполнение сегмента кода. Метод finalize() вызывается сборщиком мусора, как только последний решает, что ссылок больше не существует.
Ниже эти ключевые слова рассматриваются более подробно.
final
Назначение команды final может меняться в зависимости от контекста:
- С переменной (примитив): значение переменной не может изменяться.
- С переменной (ссылка): переменная не может указывать ни на какой другой объект в куче.
- С методом: метод не может переопределяться.
- С классом: класс не может субклассироваться.
finally
Необязательный блок finally может располагаться после блоков try или catch. Команды, находящиеся в блоке finally, выполняются всегда (исключение — завершение работы виртуальной машины Java в блоке try). Блок finally предназначен для выполнения завершающих действий, то есть «зачистки». Он выполняется после блоков try и catch, но до возврата управления к исходной точке.
Следующий пример показывает, как это делается:
1 public static String lem() {
2 System.out.println("lem");
3 return "return from lem";
4 }
5
6 public static String foo() {
7 int x = 0;
8 int y = 5;
9 try {
10 System.out.println("start try");
11 int b = y / x;
12 System.out.println("end try");
13 return "returned from try";
14 } catch (Exception ex) {
15 System.out.println("catch");
16 return lem() + " | returned from catch";
17 } finally {
18 System.out.println("finally");
19 }
20 }
21
22 public static void bar() {
23 System.out.println("start bar");
24 String v = foo();
25 System.out.println(v);
26 System.out.println("end bar");
27 }
28
29 public static void main(String[] args) {
30 bar();
31 }
Результат выполнения этого кода выглядит так:
1 start bar
2 start try
3 catch
4 lem
5 finally
6 return from lem | returned from catch
7 end bar
Присмотритесь к строкам 3–5. Блок catch отрабатывает полностью (включая вызов функции в команде return), затем выполняется блок finally, и только после этого функция возвращает управление.
finalize()
Метод finalize() вызывается сборщиком мусора непосредственно перед уничтожением объекта. Таким образом, класс может переопределить метод finalize() из класса Object для реализации нестандартного поведения в процессе уборки мусора.
1 protected void finalize() throws Throwable {
2 /* Закрыть открытые файлы, освободить ресурсы и т. д. */
3 }
13.4. Объясните разницу между шаблонами C++ и обобщениями (generics) в языке Java.
РЕШЕНИЕ
Многие программисты полагают, что шаблон и обобщения — это одно и то же: ведь в обоих случаях можно использовать конструкции вида List. Но то, как и почему каждый из языков достигает нужного эффекта, существенно различается.
Обобщения Java происходят от идеи «стирания типа». Этот метод устраняет параметризацию типов при преобразовании исходного кода в байт-код JVM.
Допустим, имеется следующий Java-код:
1 Vector<String> vector = new Vector<String>();
2 vector.add(new String("hello"));
3 String str = vector.get(0);
Во время компиляции он будет преобразован к виду:
1 Vector vector = new Vector();
2 vector.add(new String("hello"));
3 String str = (String) vector.get(0);
Использование обобщений Java практически не повлияло на функциональность, но сделало код более красивым. Поэтому обобщения Java часто называют «синтаксическим украшением».
С шаблонами C++ дело обстоит совершенно иначе. Шаблоны в C++ по сути представляют собой набор макросов, создающих новую копию шаблонного кода для каждого типа. Это убедительно доказывает тот факт, что экземпляр MyClass не будет использовать статическую переменную совместно с экземпляром MyClass. С другой стороны, два экземпляра MyClass будут совместно использовать статическую переменную.
Чтобы проиллюстрировать этот пример, рассмотрим следующий код:
1 /*** MyClass.h ***/
2 template<class T> class MyClass {
3 public:
4 static int val;
5 MyClass(int v) { val = v; }
6 };
7
8 /*** MyClass.cpp ***/
9 template<typename T>
10 int MyClass<T>::bar;
11
12 template class MyClass<Foo>;
13 template class MyClass<Bar>;
14
15 /*** main.cpp ***/
16 MyClass<Foo> * foo1 = new MyClass<Foo>(10);
17 MyClass<Foo> * foo2 = new MyClass<Foo>(15);
18 MyClass<Bar> * bar1 = new MyClass<Bar>(20);
19 MyClass<Bar> * bar2 = new MyClass<Bar>(35);
20
21 int f1 = foo1->val; // будет равно 15
22 int f2 = foo2->val; // будет равно 15
23 int b1 = bar1->val; // будет равно 35
24 int b2 = bar2->val; // будет равно 35
В Java статические переменные совместно используются экземплярами MyClass независимо от параметров-типов.
У обобщений Java и шаблонов C++ есть и другие отличия:
— Шаблоны С++ могут использовать примитивные типы (например, int). Для обобщений Java это невозможно, они обязаны использовать Integer.
- Java позволяет ограничить параметры обобщения определенным типом. Например, вы можете использовать обобщения для реализации CardDeck и указать, что параметр-тип должен расширять CardGame.
- В C++ можно создать экземпляр параметра-типа, в Java такая возможность отсутствует.
- В Java параметр-тип (Foo в MyClass) не может использоваться для статических методов и переменных, так как это привело бы к их совместному использованию MyClass и MyClass. В C++ это разные классы, поэтому параметр-тип может использоваться для статических методов и переменных.
- В Java все экземпляры MyClass независимо от их типизированных параметров относятся к одному и тому же типу. Параметры-типы «стираются» во время выполнения. В C++ экземпляры с разными параметрами-типами относятся к разным типам.
Помните, что хотя обобщения Java и шаблоны C++ внешне похожи, у них много различий.
13.5. Объясните различия между TreeMap, HashMap и LinkedHashMap. Приведите пример ситуации, в которой каждая из этих коллекций работает лучше других.
РЕШЕНИЕ
Все перечисленные классы коллекций предназначены для хранения ассоциативных пар «ключ/значение» и поддерживают средства перебора ключей. Самое важное различие — гарантии временной сложности и упорядочение ключей.
— HashMap обеспечивает поиск и вставку за время O(1). При переборе ключей порядок их следования фактически непредсказуем. Коллекция реализуется в виде массива связных списков.
- TreeMap обеспечивает поиск и вставку за время O(log N). Ключи упорядочены, поэтому если их перебор должен осуществляться в порядке сортировки, такая возможность существует. Это означает, что ключи должны реализовать интерфейс isComparable. Коллекция TreeMap реализуется в виде красно-черного дерева.
- LinkedHashMap обеспечивает поиск и вставку за время O(1). Ключи упорядочены в порядке вставки. Коллекция реализуется в виде двусвязных блоков.
Представьте, что пустые экземпляры TreeMap, HashMap и LinkedHashMap передаются следующей функции:
1 void insertAndPrint(AbstractMap<Integer, String> map) {
2 int[] array = {1, -1, 0};
3 for (int x : array) {
4 map.put(x, Integer.toString(x));
5 }
6
7 for (int k : map.keySet()) {
8 System.out.print(k + ", ");
9 }
10 }
Результаты для разных коллекций выглядят так:
Очень важно: результаты LinkedListMap и TreeMap должны выглядеть так, как показано выше. Для HashMap в моих тестах выводился результат {0, 1, -1}, но порядок может быть любым. Никаких гарантий на этот счет нет.
Когда упорядочение может понадобиться в реальной ситуации?
- Допустим, вы создаете отображение имен на объекты Person. Время от времени требуется выводить список людей, упорядоченный по имени в алфавитном порядке. TreeMap позволит вам это сделать.
- Класс TreeMap также предоставляет возможность вывести следующие 10 человек для заданного имени, например для реализации кнопки Далее> во многих приложениях.
— Класс LinkedHashMap удобен в тех случаях, когда порядок ключей должен соответствовать порядку вставки. В частности, данная возможность пригодится для организации кэширования, когда потребуется удалить самый старый элемент.
В общем случае рекомендуется использовать HashMap, если только у вас нет веских причин для другого выбора, а именно, если вам потребуется получить ключи в порядке вставки, используйте LinkedListMap. Если ключи должны возвращаться в фактическом/естественном порядке, используйте TreeMap. В остальных случаях класс HashMap, вероятно, подойдет лучше всего: обычно он работает быстрее и эффективнее.
13.6. Объясните, что такое рефлексия (reflection) объектов в Java и для чего она используется.
РЕШЕНИЕ
Рефлексия (или отражение) — механизм получения содержательной информации о классах и объектах Java, а также выполнение следующих операций:
1. Получение информации о методах и полях класса во время выполнения.
2. Создание нового экземпляра класса.
3. Прямое чтение и запись значений полей объекта по ссылке (независимо от модификатора доступа).
Пример использования рефлексии:
1 /* Параметры */
2 Object[] doubleArgs = new Object[] { 4.2, 3.9 };
3
4 /* Получение класса */
5 Class rectangleDefinition = Class.forName("MyProj.Rectangle");
6
7 /* Эквивалентно: Rectangle rectangle = new Rectangle(4.2, 3.9); */
8 Class[] doubleArgsClass = new Class[] {double.class, double.class};
9 Constructor doubleArgsConstructor =
10 rectangleDefinition.getConstructor(doubleArgsClass);
11 Rectangle rectangle = (Rectangle) doubleArgsConstructor.newInstance(doubleArgs);
12
13 /* Эквивалентно: Double area = rectangle.area(); */
14 Method m = rectangleDefinition.getDeclaredMethod("area");
15 Double area = (Double) m.invoke(rectangle);
Этот код эквивалентен следующему:
1 Rectangle rectangle = new Rectangle(4.2, 3.9);
2 Double area = rectangle.area();
Зачем нужна рефлексия
Конечно, в приведенном выше примере рефлексия не кажется необходимой, но в некоторых случаях она очень полезна. Три основных причины для применения рефлексии:
1. Она упрощает наблюдение или управление поведением программы во время выполнения.
2. Она способствует отладке или тестированию программ, поскольку мы получаем прямой доступ к методам, конструкторам и полям.
3. Она позволяет вызывать методы по имени, даже если нам это имя заранее не известно. Например, пользователь может передать имя класса, параметры конструктора и имя метода, а программа использует эту информацию для создания объекта и вызова метода. Выполнение аналогичных операций без рефлексии потребует использования цепочки сложных команд if (если оно вообще возможно).
13.7. Существует класс Country, содержащий методы getContinent() и getPopulation(). Напишите функцию int getPopulation(List countries, String continent), которая вычисляет население заданного континента по списку всех стран и названию континента с использованием лямбда-выражений.
РЕШЕНИЕ
Решение в действительности состоит из двух частей. Сначала нужно сгенерировать список стран (допустим, в Северной Америке), а затем вычислить их общее население.
Без лямбда-выражений это делается достаточно просто.
1 int getPopulation(List<Country> countries, String continent) {
2 int sum = 0;
3 for (Country c : countries) {
4 if (c.getContinent().equals(continent)) {
5 sum += c.getPopulation();
6 }
7 }
8 return sum;
9 }
Чтобы написать реализацию с лямбда-выражениями, разобъем задачу на несколько подзадач.
Сначала мы используем фильтр для получения списка стран заданного континента.
1 Stream<Country> northAmerica = countries.stream().filter(
2 country -> { return country.getContinent().equals(continent);}
3 );
Затем результат преобразуется в список с населениями стран:
1 Stream<Integer> populations = northAmerica.map(
2 c -> c.getPopulation()
3 );
Наконец, общее население вычисляется методом reduce:
1 int population = populations.reduce(0, (a, b) -> a + b);
Следующая функция собирает все подзадачи воедино:
1 int getPopulation(List<Country> countries, String continent) {
2 /* Фильтрация списка стран. */
3 Stream<Country> sublist = countries.stream().filter(
4 country -> { return country.getContinent().equals(continent);}
5 );
6
7 /* Преобразование в список численности населения. */
8 Stream<Integer> populations = sublist.map(
9 c -> c.getPopulation()
10 );
11
12 /* Суммирование списка. */
13 int population = populations.reduce(0, (a, b) -> a + b);
14 return population;
15 }
Также из-за особенностей этой конкретной задачи можно обойтись вообще без фильтра. Операция reduce может содержать логику, которая связывает население стран других континентов с нулем. Таким образом, в сумме вклад других континентов учитываться не будет.
1 int getPopulation(List<Country> countries, String continent) {
2 Stream<Integer> populations = countries.stream().map(
3 c -> c.getContinent().equals(continent) ? c.getPopulation() : 0);
4 return populations.reduce(0, (a, b) -> a + b);
5 }
Лямбда-функции появились в Java 8, и если вы о них не знаете, удивляться не приходится. Зато у вас появляется хороший повод изучить их.
13.8. Напишите функцию List getRandomSubset(List list), возвращающую случайное подмножество произвольного размера. Все подмножества (включая пустое) должны выбираться с одинаковой вероятностью. При написании функции следует использовать лямбда-выражения.
РЕШЕНИЕ
На первый взгляд можно пойти простым путем: выбрать размер подмножества от 0 до N, а затем сгенерировать случайное множество такого размера.
Однако такой подход порождает две проблемы:
1. Вероятностям придется назначать весовые коэффициенты. Если N>1, то количество подмножеств с размером N/2 больше количества подмножеств с размером N (которое, конечно, всегда равно 1).
2. Сгенерировать подмножество ограниченного размера (например, 10) сложнее, чем сгенерировать подмножество произвольного размера.
Вместо того чтобы генерировать подмножество на основании размера, рассмотрим задачу генерирования на основании элементов. (Тот факт, что в задаче предлагается использовать лямбда-выражения, также подсказывает, что искать нужно некоторую форму перебора с обработкой элементов.)
Представьте, что мы перебираем множество {1, 2, 3} для создания подмножества. Должен ли элемент 1 войти в подмножество?
Есть два варианта ответа: «да» и «нет». Вероятностям выбора следует присвоить весовые коэффициенты на основании доли подмножеств, включающих 1. Итак, какая часть подмножества содержит 1?
Для каждого отдельного элемента количество подмножеств, включающих его, равно количеству подмножеств, в которые этот элемент не входит. Рассмотрим следующий пример:
{} {1}
{2} {1, 2}
{3} {1, 3}
{2, 3} {1, 2, 3}
Обратите внимание: подмножества в левом и правом столбце отличаются только вхождением 1. Количество подмножеств в левом и правом столбце одинаково, потому что одно подмножество преобразуется в другое простым добавлением элемента.
Это означает, что для построения случайного подмножества достаточно перебрать список и «бросить монетку» (то есть принять решение с вероятностью 50/50), чтобы решить, должен ли каждый элемент войти в это множество.
Без лямбда-выражений реализация выглядит примерно так:
1 List<Integer> getRandomSubset(List<Integer> list) {
2 List<Integer> subset = new ArrayList<Integer>();
3 Random random = new Random();
4 for (int item : list) {
5 /* Да/нет */
6 if (random.nextBoolean()) {
7 subset.add(item);
8 }
9 }
10 return subset;
11 }
Реализация с лямбда-выражениями:
1 List<Integer> getRandomSubset(List<Integer> list) {
2 Random random = new Random();
3 List<Integer> subset = list.stream().filter(
4 k -> { return random.nextBoolean(); /* Да/нет */
5 }).collect(Collectors.toList());
6 return subset;
7 }
Также можно воспользоваться предикатом (определяемым в классе или функции):
1 Random random = new Random();
2 Predicate<Object> flipCoin = o -> {
3 return random.nextBoolean();
4 };
5
6 List<Integer> getRandomSubset(List<Integer> list) {
7 List<Integer> subset = list.stream().filter(flipCoin).
8 collect(Collectors.toList());
9 return subset;
10 }
Одно из преимуществ этой реализации — возможность применения предиката flipCoin в других местах.
Задачи
Задача 1. Разработайте алгоритм для поиска наименьших K чисел в массиве.
РЕШЕНИЕ
К решению этой задачи можно подходить несколькими разными способами. Мы рассмотрим три варианта: сортировку, max-кучу и алгоритм ранжированного выбора. Некоторые из этих алгоритмов требуют модификации массива. Обсудите этот момент с интервьюером. Впрочем, даже если модификация исходного массива недопустима, ничто не мешает создать копию и модифицировать ее — это не отразится на общей сложности алгоритма.
Решение 1. Сортировка
Мы можем отсортировать элементы по возрастанию, а затем взять первые k элементов.
1 int[] smallestK(int[] array, int k) {
2 if (k <= 0 || k > array.length) {
3 throw new IllegalArgumentException();
4 }
5
6 /* Сортировка массива. */
7 Arrays.sort(array);
8
9 /* Копирование первых k элементов. */
10 int[] smallest = new int[k];
11 for (int i = 0; i < k; i++) {
12 smallest[i] = array[i];
13 }
14 return smallest;
15 }
Временная сложность равна O(n log(n)).
Решение 2. Max-куча
Также для решения задачи можно воспользоваться max-кучей. Сначала создается max-куча (с наибольшим элементом на вершине) для первого миллиона чисел. Затем начинается перебор списка. Каждый элемент, если он меньше корня, вставляется в кучу, после чего удаляется наибольший элемент (которым будет корень). В конце обхода будет получена куча, содержащая миллион наименьших чисел. Этот алгоритм выполняется за время O(n log(m)), где m — количество искомых значений.
1 int[] smallestK(int[] array, int k) {
2 if (k <= 0 || k > array.length) {
3 throw new IllegalArgumentException();
4 }
5
6 PriorityQueue<Integer> heap = getKMaxHeap(array, k);
7 return heapToIntArray(heap);
8 }
9
10 /* Создание кучи из k наименьших элементов. */
11 PriorityQueue<Integer> getKMaxHeap(int[] array, int k) {
12 PriorityQueue<Integer> heap =
13 new PriorityQueue<Integer>(k, new MaxHeapComparator());
14 for (int a : array) {
15 if (heap.size() < k) { // Если осталось место
16 heap.add(a);
17 } else if (a < heap.peek()) { // Куча заполнена, элемент больше
18 heap.poll(); // Удалить корень
19 heap.add(a); // Вставить новый элемент
20 }
21 }
22 return heap;
23 }
24
25 /* Преобразование кучи в целочисленный массив. */
26 int[] heapToIntArray(PriorityQueue<Integer> heap) {
27 int[] array = new int[heap.size()];
28 while (!heap.isEmpty()) {
29 array[heap.size() - 1] = heap.poll();
30 }
31 return array;
32 }
33
34 class MaxHeapComparator implements Comparator<Integer> {
35 public int compare(Integer x, Integer y) {
36 return y - x;
37 }
38 }
Для реализации функциональности кучи в Java используется класс PriorityQueue. По умолчанию он работает как min-куча, в которой на вершине находится наименьший элемент. Чтобы на вершине находился наибольший элемент, достаточно передать другой компаратор.
А вы знаете еще решения?
Задача 2. Напишите функцию суммирования двух чисел без использования «+» или любых других арифметических операторов.
РЕШЕНИЕ
Первое, что приходит в голову в подобных задачах, — поразрядные операции. Почему? Если нельзя использовать оператор «+», то что еще остается? Будем суммировать числа так, как это делают компьютеры!
Теперь нужно поглубже разобраться в том, как работает суммирование. Разберем дополнительный пример и попробуем найти нечто интересное — выявить закономерность, которую можно было бы воспроизвести в коде.
Итак, рассмотрим дополнительную задачу. Для удобства будем использовать десятичную систему счисления. Чтобы просуммировать 759 + 674, мы обычно складываем digit[0] из каждого числа, переносим единицу, затем переходим к digit[1], переносим и т. д. Точно так же можно работать с битами: просуммировать все разряды и при необходимости сделать переносы единиц.
Можно ли упростить алгоритм? Да! Допустим, я хочу разделить «суммирование» и «перенос».
Мне придется проделать следующее.
1. Выполнить операцию 759 + 674, «забыв» о переносе. В результате получится 323.
2. Выполнить операцию 759 + 674, но сделать только переносы (без суммирования разрядов). В результате получится 1110.
3. Теперь нужно сложить результаты первых двух операций (используя тот же механизм, описанный в шагах 1 и 2): 1110 + 323 = 1433.
Теперь вернемся к двоичной системе.
1. Если просуммировать пару двоичных чисел, без учета переноса знака, то i-й бит суммы может быть нулевым, только если i-е биты чисел a и b совпадали (оба имели значение 0 или 1). Это классическая операция XOR.
2. Если суммировать пару чисел, выполняя только перенос, то i-й бит суммы будет равен 1, только если i-1-е биты обоих чисел (a и b) имели значение 1. Это операция AND со сдвигом.
3. Повторять, пока остаются переносы.
Следующий код реализует данный алгоритм.
1 int add(int a, int b) {
2 if (b == 0) return a;
3 int sum = a ^ b; // суммирование без переноса
4 int carry = (a & b) << 1; // перенос без суммирования
5 return add(sum, carry); // повторить с sum + carry
6 }
Также возможна итеративная реализация.
1 int add(int a, int b) {
2 while (b != 0) {
3 int sum = a ^ b; // суммирование без переноса
4 int carry = (a & b) << 1; // перенос без суммирования
5 a = sum;
6 b = carry;
7 }
8 return a;
9 }
Задачи, связанные с реализацией базовых операций (сложение, вычитание), встречаются относительно часто. Чтобы решить такую задачу, нужно досконально разобраться с тем, как обычно выполняется такая операция, а потом реализовать ее заново с учетом поставленных ограничений.
А вы знаете еще решения?
Задача 3. Для двух квадратов на плоскости найдите линию, которая делит эти два квадрата пополам. Предполагается, что верхняя и нижняя стороны квадрата проходят параллельно оси x.
РЕШЕНИЕ
Прежде чем начать, нам нужно подумать, что понимается под «линией». Как будет задаваться линия — углом наклона и точкой пересечения с осью y? Двумя точками на линии? Или под линией на самом деле понимается отрезок, начало и конец которого лежат на сторонах квадратов?
Чтобы задача была более интересной, мы выберем третий вариант — отрезок, начало и конец которого лежат на сторонах квадратов. Находясь на собеседовании, вы можете обсудить данный момент с интервьюером.
Прямая, которая делит два квадрата пополам, должна проходить через их середины. Наклон прямой описывается формулой: slope = (y1 — y2) / (x1 — x2). Этим же принципом можно руководствоваться, чтобы рассчитать начальную и конечную точки отрезка.
В следующем коде предполагается, что начало координат (0, 0) находится в левом верхнем углу.
1 public class Square {
2 ...
3 public Point middle() {
4 return new Point((this.left + this.right) / 2.0,
5 (this.top + this.bottom) / 2.0);
6 }
7
8 /* Возвращает точку, в которой отрезок, соединяющий mid1 и mid2,
9 * пересекает сторону квадрата 1. То есть мы проводим линию из mid2
10 * в mid1 и продолжаем ее до стороны квадрата. */
11 public Point extend(Point mid1, Point mid2, double size) {
12 /* Определение направления, в котором идет линия mid2 -> mid1. */
13 double xdir = mid1.x < mid2.x ? -1 : 1;
14 double ydir = mid1.y < mid2.y ? -1 : 1;
15
16 /* Если у mid1 и mid2 значения x совпадают, при вычислении наклона
17 * произойдет деление на 0. Этот случай обрабатывается отдельно. */
18 if (mid1.x == mid2.x) {
19 return new Point(mid1.x, mid1.y + ydir * size / 2.0);
20 }
21
22 double slope = (mid1.y - mid2.y) / (mid1.x - mid2.x);
23 double x1 = 0;
24 double y1 = 0;
25
26 /* Наклон вычисляется по формуле (y1 - y2) / (x1 - x2).
27 * Примечание: при "крутом" наклоне (>1) конец отрезка
28 * пересечет горизонтальную сторону квадрата. При "пологом"
29 * наклоне (<1) конец отрезка пересечет вертикальную
30 * сторону квадрата. */
31 if (Math.abs(slope) == 1) {
32 x1 = mid1.x + xdir * size / 2.0;
33 y1 = mid1.y + ydir * size / 2.0;
34 } else if (Math.abs(slope) < 1) { // Пологий наклон
35 x1 = mid1.x + xdir * size / 2.0;
36 y1 = slope * (x1 - mid1.x) + mid1.y;
37 } else { // steep slope
38 y1 = mid1.y + ydir * size / 2.0;
39 x1 = (y1 - mid1.y) / slope + mid1.x;
40 }
41 return new Point(x1, y1);
42 }
43
44 public Line cut(Square other) {
45 /* Вычисление точек пересечения линии, соединяющей середины,
46 * со сторонами квадратов. */
47 Point p1 = extend(this.middle(), other.middle(), this.size);
48 Point p2 = extend(this.middle(), other.middle(), -1 * this.size);
49 Point p3 = extend(other.middle(), this.middle(), other.size);
50 Point p4 = extend(other.middle(), this.middle(), -1 * other.size);
51
52 /* Определение начала и конца отрезков. Начальная точка находится
53 * левее остальных (и выше при совпадении), а конечная - правее
54 * остальных (и ниже при совпадении). */
55 Point start = p1;
56 Point end = p1;
57 Point[] points = {p2, p3, p4};
58 for (int i = 0; i < points.length; i++) {
59 if (points[i].x < start.x ||
60 (points[i].x == start.x && points[i].y < start.y)) {
61 start = points[i];
62 } else if (points[i].x > end.x ||
63 (points[i].x == end.x && points[i].y > end.y)) {
64 end = points[i];
65 }
66 }
67
68 return new Line(start, end);
69 }
Основная цель этой задачи — увидеть, насколько вы внимательно относитесь к написанию кода. Очень легко забыть об особых случаях (когда середины квадратов совпадают по какой-либо из осей). Вы должны продумать поведение программы в особых ситуациях прежде, чем начнете писать код. Этот вопрос требует тщательного тестирования.
А вы знаете еще решения?
Свои методы решения задач публикуйте в комментариях, тем, кто предложит конструктивный подход — электронная книга в подарок.
» Более подробно с книгой можно ознакомиться на сайте издательства
» Оглавление
» Отрывок
Для Хаброжителей скидка 25% по купону — Макдауэлл
