Category Archive: Java

Дополнение числа ведущими нулями на Java

Всегда хотелось найти быстрый и короткий способ дополнить число ведущими нулями.
Например, часто возникает необходимость вывести последовательность 1,2,3,…,10 в таком виде: 01,02,03,…,10. И сегодня я нашел здесь такой способ.

Рассмотрим, этот способ на примере следующей задачи: выведем все числа от 1 до 100, дополнив числа до длины равной трем, т.е. 001,002,003,…,099,100.

public class LeadingZero {
	public static void main(String[] args) {
		for (int i = 1; i <= 100; i++) {
			System.out.println(zero("" + i));
		}
	}
	static String zero(String value){
		return ("000" + value).substring(value.length());
	}
}

«000» — это шаблон, который мы присоединяем спереди к цифрам числа, но т.к. шаблон уже содержим максимальное кол-во символов, то мы должны проигнорировать первые нули в кол-ве равному избытку, т.е. кол-ву символов в исходном числе, и тогда мы получим искомое число с ведущими нулями заданной длины. Со своей задачей прекрасно справляется функция substring, которая берет часть строки от заданной позиции и до конца строки.
leading_zero_illustration
Также необходимо учитывать, что число может выйти за пределы шаблона.
Вывод программы будет следующим:

001
002
003
...
009
010
011
...
098
099
100

Набор методов для маршалинга и анмаршалинга

При создании и обращении к веб-сервисам в большинстве случаем мы можем забыть и не знать о маршалинге и анмаршалинге (демаршалинге). Но бывают интеграции, где каким-то текстовым полем передается XML-ка. Вот тут нужно с одной стороны уметь делать маршалинг, а с другой анмаршалинг. Предлагаю набор методов для проведения данных операций:

import javax.xml.bind.*;
import java.io.File;
import java.io.StringReader;
import java.io.StringWriter;
 
/**
 * Набор методов для маршалинга и анмаршалинга
 */
public class XmlUtils {
 
	/**
	 * Маршалинг в строку
	 * @param t объект
	 * @param <T> тип объекта
	 * @return XML в виде строки
	 * @throws JAXBException
	 */
	public static<T> String marshalRoot(T t) throws JAXBException {
		JAXBContext context = JAXBContext.newInstance(t.getClass());
		Marshaller marshaller = context.createMarshaller();
		marshaller.setProperty(Marshaller.JAXB_FORMATTED_OUTPUT,true);
		marshaller.setProperty(Marshaller.JAXB_ENCODING, "UTF-8");
		StringWriter sw = new StringWriter();
		marshaller.marshal(t,sw);
		return sw.toString();
	}
 
	/**
	 * Маршалинг в файл
	 * @param t объект
	 * @param file файл
	 */
	public static<T> void marshalRoot(T t,File file){
		marshal(t,file,false);
	}
 
	/**
	 * Маршалинг в файл с возможностью вывода в консоль
	 * @param t объект
	 * @param file файл
	 * @param isAddToLog делать вывод в консоль или нет
	 */
	public static<T> void marshal(T t,File file,boolean isAddToLog){
		String filePath = file.getAbsolutePath();
		try {
			JAXBContext jaxbContext = JAXBContext.newInstance(t.getClass());
			Marshaller marshaller = jaxbContext.createMarshaller();
			marshaller.setProperty(Marshaller.JAXB_FORMATTED_OUTPUT,true);
			marshaller.marshal(t,file);
			if(isAddToLog){
				marshaller.marshal(t,System.out);
			}
		} catch (JAXBException e) {
			System.out.println("Не удалось сбросить xml в файл: " + filePath);
			e.printStackTrace();
		}
		System.out.println("Xml saved to: " + filePath);
	}
 
	/**
	 * Анмаршалинг (Демаршалинг) XML в объект
	 * @param xml входной XML
	 * @param _class класс объекта, который ходит получить
	 * @return объект
	 * @throws JAXBException
	 */
	@SuppressWarnings("unchecked")
	public static <T> T unmarshall(String xml,Class<T> _class) throws JAXBException {
		JAXBContext context = JAXBContext.newInstance(_class);
		Unmarshaller unmarshaller = context.createUnmarshaller();
		JAXBElement<T> element = (JAXBElement<T>)unmarshaller.unmarshal(new StringReader(xml));
		return element.getValue();
	}
 
	/**
	 * Анмаршалинг XML root-элемента (@XmlRootElement) в объект
	 * @param xml входной XML
	 * @param _class класс объекта, который ходит получить
	 * @return объект
	 * @throws JAXBException
	 */
	@SuppressWarnings("unchecked")
	public static <T> T unmarshallRoot(String xml,Class<T> _class) throws JAXBException{
		JAXBContext context = JAXBContext.newInstance(_class);
		Unmarshaller unmarshaller = context.createUnmarshaller();
		return (T)unmarshaller.unmarshal(new StringReader(xml));
	}
 
 
}

Удаленный дебаг в IntelliJ IDEA (на примере JBoss EAP)

Использование локальной или удаленной отладки может очень помочь и сэкономить время.

По умолчанию удаленная отладка в JBoss отключена, для ее активации нужно внести изменения в конфигурационный файл %EAP_HOME%/bin/standalone.conf.

  1. Найдите и раскомментируйте следующую строку:
    JAVA_OPTS="$JAVA_OPTS -agentlib:jdwp=transport=dt_socket,address=8787,server=y,suspend=n"
    

    Видно, что мы задействовали порт 8787.

  2. Перегрузите JBoss
  3. Осталось настроить IDEA
    Зайдите в меню Run и выберите пункт Edit configurations…:
    remote_debug_1

    В открывшемся окне Run/Debug configurations выберите пункт Remote:
    remote_debug_2

    Придумайте название для данной конфигурации (поле Name), пропишите адрес(Host) и порт(Port) JBoss’а, на котором включена удаленная отладка. Нажмите OK:
    remote_debug_3
    В качестве адреса можно указать localhost.

  4. Теперь попробуем подключаться к работающему JBoss’у, для этого выберите в списке созданную конфигурацию и нажмите «зеленого жучка», как на картинке:
    remote_debug_4
    При успешном подключении в консоли IDEA вы увидите следующее сообщение:

    Connected to the target VM, address: '10.1.0.50:8787', transport: 'socket'
    
  5. Далее мы можем расставить необходимые breakpoint’ы, где необходимо приостановить код и просмотреть содержимое переменных:
    remote_debug_5
    Вот так в IntelliJ IDEA выглядит отображение содержимого переменных — это очень удобно:
    remote_debug_6

  6. Для навигации по исполняемому коду вам помогут следующие кнопки:
    remote_debug_9
    Одна из самых полезных — Step Over(перешагнуть), вызывается нажатием функциональной клавиши F8.

  7. Также IntelliJ IDEA предоставляет некоторые возможности по горячей замене классов (Hot Swap). Например, вы можете что-то изменить внутри метода, нажать на кнопку Make Project, и все изменные классы будут перегружены:
    remote_debug_7
    Если изменения несовместимы с горячей заменой, то вам будет сообщено о невозможности замены классов.

  8. И последнее — для выхода из режима отладки нажмите кнопку Stop:
    remote_debug_8
    В консоли появиться сообщение об отсоединении от сервера:

    Disconnected from the target VM, address: '10.1.0.50:8787', transport: 'socket
    

Правильная разбивка строки функцией split (Java)

Часто при парсинге данных мы разбиваем строку по разделителю. Один из способов — это использование функции split(regex), где regex — это регулярное выражение. Разобъем следующую строку на части:

Java World|0123456|false

Очень часто разделителем выступает вертикальная черта |, т.к. в функция split принимает регулярное выражение, а символ | (pipe) используется в регулярных выражениях для задания условия «или», то этот символ нужно экранировать. Разбить строку можно следующим кодом:

"Java World|0123456|false".split("\\|")

На первый взгляд кажется, что все будет работать без проблем. Возможно, это будет и так, но допустим вам попадется строка, в которой разделитель стоит в конце строки:

Java World|0123456|

Если разбить эту строку:

"Java World|0123456|".split("\\|")

Вы в своем коде можете ожидать массив из трех элементов: «Java World», «0123456», «».
Но массив будет содержать два элемента: «Java World», «0123456», потому что разделитель, стоящий в конце строки игнорируется.
Для того, чтобы последний разделитель не игнорировался нужно в функцию split, передать вторым параметром -1.
У split есть еще одна сигнатура вида: split(regex,limit), где параметр limit означает максимальное кол-во элементов в итоговом массиве. Примеры использования:

"Java World|0123456|".split("\\|",1)
//вернет одну строку, игнорируя разделители: "Java World|0123456|"
"Java World|0123456|".split("\\|",2)
//вернет две строки, игнорируя все разделители, кроме первого: "Java World", "0123456|"
"Java World|0123456|".split("\\|",5)
//вернет три строки - максимально возможное разбиение строки,
//хотя мы пытались разбить строку на 5 частей: "Java World", "0123456", ""

На самом деле метод split(regex) вызывает split(regex,0), т.е. limit равен 0, и функция ведет себя так, как описано в начале статьи.
Если передать параметр limit, равный -1 (или любое отрицательное число), то разделитель в конце строки не игнорируется:

"Java World|0123456|".split("\\|",-1)
//вернет три строки: "Java World", "0123456" и ""

Заключение:
На практике очень часто приходится пользоваться split(regex), но не нужно забывать и про split(regex,-1).
Что касается использования split(regex,limit) при limit > 0, то я не представляю, где это может пригодиться, и, думаю, используется это очень редко.

Выгрузка простых чисел

Простые числа длины 1
Простые числа длины 2
Простые числа длины 3
Простые числа длины 4
Простые числа длины 5
Простые числа длины 6
Простые числа длины 7 (первые 10 тысяч чисел)
Простые числа длины 8 (первые 10 тысяч чисел)
Простые числа длины 9 (первые 10 тысяч чисел)

Генерация Java-классов Web-сервиса по WSDL

Допустим, у вас есть WSDL и вы хотите написать либо сам веб-сервис, либо клиента для сервиса. Для этого по WSDL нужно сгенерировать Java-классы с помощью утилиты wsimport, входящую в состав JDK.
Стоит отметить, что сгенерированный код может использовать и на сервере, и на клиенте.
Создайте новую папку и положите в нее вашу WSDL и всё, что к ней относится (это может быть другие WSDL или XSD). Увидеть все, что импортирует ваша основная WSDL можно в теге import. Например:

<xsd:import namespace="http://www.kesh.kz/blog/v1" 
schemaLocation="http://123.45.678.90:8080/kesh/example.xsd"/>

В данном примере следует заменить интернет адрес XSD на локальный:

<xsd:import namespace="http://www.kesh.kz/blog/v1" 
schemaLocation="example.xsd"/>

Разумеется, файл example.xsd должен лежать c WSDL в одной директории.
Теперь напишем скрипт для генерирования классов. Рассмотрим сперва Windows-версию скрипта, а потом Linux-версию.

Скрипт для Windows
Создайте файл w-gen.bat в любом текстовом редакторе и скопируйте в него следующий код:

cls
set GEN_DIR=kz
rmdir %GEN_DIR% /s/q
"%JAVA_HOME%/bin/wsimport" -keep -Xnocompile -p kz.kesh.blog.v1 myBlog.wsdl
pause

cls — очистка консоли
GEN_DIR — директория пакета верхнего уровня
rmdir — полное удаление директории
wsimport — утилита для генерации Java-классов из WSDL
keep — сохраняет сгенерированные файлы
Xnocompile — не компилирует сгенерированные Java-файлы
kz.kesh.blog.v1 — имя пакета, в котором будет сгенерированые классы
myBlog.wsdl — наша WSDL
pause — пауза, чтобы консольное окно сразу не закрылось

Данный скрипт генерирует *.java файлы, но вы можете немного переработать скрипт и генерировать скопилированные файлы *.class. Так же вы можете доработать упаковку файлов и WSDL в jar. Например:

"%JAVA_HOME%/bin/jar" cf keskBlog.jar kz

jar — стандартная утилита из JDK для создания jar-файлов
cf — создает новый архив с указанным именем
keskBlog.jar — имя вашего jar-файла
kz — директория, которая упаковывается в jar, она соответствует названию верхнего пакета

Скрипт для Linux
Создайте файл w-gen.sh:

#!/bin/bash
GEN_DIR="kz"
rm -r $GEN_DIR
wsimport -keep -Xnocompile -p kz.kesh.blog.v1 myBlog.wsdl

Не забудьте дать скрипту права на выполенение:

chmod +x w-gen.sh

#!/bin/bash — обязательная строчка для bash-скриптов
GEN_DIR — директория пакета верхнего уровня
rm — рекурсивное удаление директории
wsimport — утилита для генерации Java-классов из WSDL
keep — сохраняет сгенерированные файлы
Xnocompile — не компилирует сгенерированные Java-файлы
kz.kesh.blog.v1 — имя пакета, в котором будет сгенерированы классы
myBlog.wsdl — наша WSDL

Вложенный тернарный поиск с золотым сечением

Определение тернарного поиска можно найти в Википедии. Также описание алгоритма можно найти здесь.
Реализация у тернарного поиска несложная, давайте убедимся в этом на примере следующей задачи:

triangle_find_alpha

Имеется прямоугольный треугольник, у которого гипотенуза равна 100 сантиметрам.
Нужно вычислить при каком угле α площадь треугольника будет максимальна.

Хотя данную задачу можно решать другими способами, но для учебных целей решим ее тернарным поиском.
Для начала нужно убедиться, что эту задачу вообще можно решить тернарным поиском. Убедимся в унимодальности нашей функции, т.е. на заданном интервале у функции должен быть один экстремум (максимальное или минимальное значение функции на заданном интервале).
Мы будем перебирать углы от 0° до 90°, т.е. наш интервал поиска от 0 до 90. При возрастании угла, начиная от 0°, площадь треугольника строго возрастает, затем при приближении к углу 90° площадь треугольнига строго уменьшается, т.е. у нас есть максимальное значение функции на данном интервале, а значит выполняется унимодальность функции, и мы можем применить тернарный поиск.
Как работает тернарный поиск.
Сначала интервал разбивается на три части, отсюда и название «тернарный» (Ternary переводится как тройной или троичный). На следующем шаге отсеивается участок, в котором точно нет решения, затем снова отрезок разбивается на три части, и это повторяется до тех пор, пока не будет достугнута необходимая точность результата.
Классический способ разбиения — это разбиение на три равные части части:
ternary_equal
Фрагмент кода, обеспечивающий равенство отрезков Lm1 = m1m2 = m2R:

double m1 = l + (r - l) / 3;
double m2 = r - (r - l) / 3;

При сравнении значений функций в точках m1 и m2 у нас возможно три варианта:
1) Мы сдвигаем область поиска вправо, т.е. l становится равным m1 (l = m1);
2) Мы сдвигаем область поиска влево, т.е. r становится равным m2 (r = m2);
3) При равенстве значений функции в обеих точках, мы сдвигаем область поиска с обеих сторон, т.е. l становиться равным m1 (l = m1), а r становиться равным m2 (r = m2)

Рассмотрим данные случаи на примере поиска максимального значения.
1) Если f(m1) < f(m2), возможно два случая: когда максимальное значение лежит в центральной части или в правой части, а значит левую часть можно отбросить. Максимальное значение обозначено зеленой точкой.
ternary_max_large
2) Если f(m1) > f(m2), аналогично имеется только два случая, когда максимальное значение лежит в центральной или левой части, а значит правую часть можно отбросить.
ternary_max_less
3) Если f(m1) = f(m2), то возможен только один вариант, при котором максимальное значение находится в центральной части, а значит левую и правую части можно отбросить.
ternary_max_equal
Последний вариант, когда f(m1) = f(m2), в целях облегчения алгоритма можно заменить либо на этот случай f(m1) < f(m2), либо на этот f(m1) > f(m2). В скорости из-за этого, конечно же, мы чуть-чуть проиграем, но выиграем в скорости реализации алгоритма и компактности кода.
После каждого шага алгоритма от исходной области поиска остается 2/3, т.е. не самая большая скорость сходимости. Можно повысить скорость сходимости, если выбирать точки m1 и m2 ближе друг другу, правда при этом теряется точность. Повышение скорости сходимости может потребоваться в случае, когда вычисление функции f(x) занимает много времени и нужно минимизировать кол-во вызовов этой функции.
Очень хорошо при выборе точек m1 и m2 воспользоваться пропорциями золотого сечения. Если тернарный поиск использует пропорции золотого сечения, то это один в один Метод золотого сечения.


Золотое сечение — это такое разбиение целого на две части, при котором отношение большего к меньшему равно отношению целого к большему


Это отношение постоянно и равно примерно 1,618, обозначается как φ и называется золотым числом:
phi
Для вычисления точек m1 и m2, разбивающих область поиска золотым сечением, воспользуемся следующими формулами:
m1_phi

m2_phi

В процентном соотношении длины отрезков lm1 и lm2 приблизительно равны 38,2% и 61,8% от длины отрезка lr.
Благодаря свойствам золотого сечения точка m1 делит отрезок lm2 в пропорциях золотого сечения, а точка m2 делит отрезок m1r также в пропорциях золотого сечения.
golden_section_search
И так мы видим, что сходимость золотого сечения будет 0,618, что лучше сходимости в случае разбиения области поиска на равные части, где сходимость у нас была 2/3 (0,66).
А теперь вернемся к решению задачи… Исходный код решения задачи на Java:

import static java.lang.Math.*;
 
public class angle {
 
	public static void main(String[] args) {
		double l = 0;
		double r = 90;
		double EPS = 1e-6;//точность 0.000001
		double hypo = 100;//гипотенуза
		while(r - l >= EPS){//повторяем цикл пока не достигнем требуемой точности
			double m1 = l + (r - l) / 3;
			double m2 = r - (r - l) / 3;
			if(f(hypo,m1) < f(hypo,m2)){
				l = m1;
			}else{
				r = m2;
			}
		}
		System.out.println((l + r) / 2);//результат 44.99999993498489
	}
 
	//функция расчета площади треугольника по гипотенузе и углу
	static double f(double hypo,double alpha){
		alpha = toRadians(alpha);
		return 0.5 * hypo * hypo * cos(alpha) * sin(alpha);
	}
 
}

Т.е. при угле в 44.999999° (45°) достигается максимальная площадь треугольника. В качестве ответа можно было взять значение из переменной l или r, это возможно благодаря достижению заданной точности результата, также можно взять их середину (l + r) / 2, как в рассмотренном выше коде.

Задача на вложенный тернарный поиск
В качестве примера применения вложенного тернарного поиска возьмем задачу «Футбольные ворота». С условием задачи можно ознакомиться здесь или здесь.
Найти максимальную площадь ворот можно, подобрав углы для палок α и β:
football_gate
Сперва мы находим углы α1 и α2, которые разбивают область поиска на три равные части (в данной задачи можно не использовать золотое сечение). Далее для угла α1 с помощью вложенного тернарного поиска ищем угол β1, при котором площадь фигуры максимальна, аналогично, для угла α2 находим подходящий угол β2.
alpha_beta
Найдя пары углов α1 и β1; α2 и β2, вычисляем площадь S1 и S2 соответственно. Можно использовать следующую формулу вычисления площади, где a и b — длины палок:

S = 0.5 * a * a * cos(alpha) * sin(alpha) +
0.5 * b * b * cos(beta) * sin(beta) +
a * b * sin(alpha) * cos(beta)

Сравнив полученные площади, мы можем отсеять треть диапазона углов, которые дают маленькую площадь. И повторяем эти шаги до тех пор, пока не достигнем требуемой точности.
Код решения задачи на Java:

import java.io.*;
 
import static java.lang.Math.*;
 
import java.text.DecimalFormat;
import java.text.DecimalFormatSymbols;
import java.util.*;
public class FooballGate {
 
	static int a;//длина 1-ой палки
	static int b;//длина 2-ой палки
	static double EPS = 1e-6;//точность результата
 
	public static void main(String[] args) throws IOException {
		Scanner s = new Scanner(new File("input.txt"));
		s.useLocale(Locale.US);		
		a = s.nextInt();
		b = s.nextInt();
		s.close();
 
		double l = 0;
		double r = 90;
 
		while(r - l >= EPS){
			double m1 = l + (r - l) / 3;
			double m2 = r - (r - l) / 3;
			if(f(m1) < f(m2)){
				l = m1;
			}else{
				r = m2;
			}
		}
 
		double ans = f((l + r) / 2);//результат		
		DecimalFormat df = new DecimalFormat("0.00000000",
				DecimalFormatSymbols.getInstance(Locale.US));
		System.out.println(df.format(ans));//вывод с восемью знаками после запятой
 
	}
 
 
	//функция расчета площади с фиксированным углом alpha,
	//в которой тернарным поиском идет поиск угла beta,
	//при котором площадь максимальна
	static double f(double alpha){
		double l = 0;
		double r = 90;
		while(r - l >= EPS){
			double m1 = l + (r - l) / 3;
			double m2 = r - (r - l) / 3;
			if(f(alpha,l) < f(alpha,r)){
				l = m1;
			}else{
				r = m2;
			}
		}	
		return f(alpha,(l + r) / 2);
	}
 
	//функция расчета площади в зависимости от углов: alpha и beta 
	static double f(double alpha, double beta){
		alpha = toRadians(alpha);
		beta = toRadians(beta);
		return 0.5 * a * a * cos(alpha) * sin(alpha) +
				0.5 * b * b * cos(beta) * sin(beta) +
				a * b * sin(alpha) * cos(beta);
	}
}

Задача на тройную вложенность тернарного поиска с необходимостью применения золотого сечения
Задача называется «Космические спасатели». Ознакомиться с условием задачи можно здесь или здесь.
planets
По условию задачи нам нужно вычислить координаты x,y,z строительства новой спасательной станции, причем расстояние от станции до самой дальней планеты должно быть минимально.
Сперва пробуем подобрать координату x тернарным поиском, но координаты y и z — неизвестны, поэтому зафиксировав некоторые точки x, полученные золотым сечением, мы запускаем вложенные тернарный поиск с фиксированной координатой x для поиска координаты y. Далее внутри поиска y запускаем вложенный тернарный поиск координаты z. Когда мы имеем все три зафиксированные координаты мы можем посчитать расстояния до всех планет и из них определить максимальное расстояние, это расстояние и будет значением функции f(x,y,z).
Т.к. в условии сказано, что количество планет может быть 100, то вычисление функции f(x,y,z) очень затратно по времени. Чтобы программа уложилась во временные рамки, нужно при тернарном поиске разбивать область поиска золотым сечением, а не на равные части. Тем самым у нас повыситься сходимость, т.е. вызовов функции f(x,y,z) станет меньше. Но при золотом сечении теряется точность, поэтому мы увеличим точность с 10-6 до 10-7.
Реализация на Java:

import java.io.*;
import java.text.DecimalFormat;
import java.text.DecimalFormatSymbols;
import java.util.*;
public class SpaceRescuers {
	static int MAX = (int) 1e4;//максимальная граница поиска
	static int MIN = -MAX;//минимальная граница поиска
	static class Point{
		int x;
		int y;
		int z;
		public Point(int x, int y, int z) {
			super();
			this.x = x;
			this.y = y;
			this.z = z;
		}
	}
 
	static class PointD{
		double x;
		double y;
		double z;
		public PointD(double x, double y, double z) {
			super();
			this.x = x;
			this.y = y;
			this.z = z;
		}
 
	}
 
	static Point[] points;
	static double EPS = 1e-7;
	static PointD bestPoint;//лучшая точка
	static double best = Double.MAX_VALUE;//лучшее расстояние (минимальное)
	static double fi = 1 / ((Math.sqrt(5) + 1) / 2);
 
	public static void main(String[] args) throws IOException {
		Scanner s = new Scanner(new File("input.txt"));
		s.useLocale(Locale.US);
		int N = s.nextInt();
		points = new Point[N];
		for(int i = 0; i < N; i++){
			points[i] = new Point(s.nextInt(),s.nextInt(),s.nextInt());
		}
		s.close();
 
		double l = MIN;
		double r = MAX;
		while(r - l > EPS){
			double delta = (r - l) * fi;
			double m1 = r - delta;
			double m2 = l + delta;
			if(f(m1) > f(m2)){
				l = m1;
			}else{
				r = m2;
			}
		}		
		double x = bestPoint.x;
		double y = bestPoint.y;
		double z = bestPoint.z;
		DecimalFormat df = new DecimalFormat("0.000000", 
			DecimalFormatSymbols.getInstance(Locale.US));
		System.out.println(df.format(x) + " " + df.format(y) + " " + 
			df.format(z));
	}
 
	//опредение минимального расстояния при фиксированной координате x
	static double f(double x){
		double l = MIN;
		double r = MAX;
		while(r - l > EPS){
			double delta = (r - l) * fi;
			double m1 = r - delta;
			double m2 = l + delta;
			if(f(x,m1) > f(x,m2)){
				l = m1;
			}else{
				r = m2;
			}
		}
		return f(x,(l + r) / 2);
	}
 
	//определение минимального расстояния при фиксированных координатах x и y
	static double f(double x,double y){
		double l = MIN;
		double r = MAX;
		while(r - l > EPS){
			double delta = (r - l) * fi;
			double m1 = r - delta;
			double m2 = l + delta;
			if(f(x,y,m1) > f(x,y,m2)){
				l = m1;
			}else{
				r = m2;
			}
		}
		return f(x,y,(l + r) / 2);
	}
 
	//определение минимального расстояния при фиксированных координатах x,y и z
	static double f(double x,double y,double z){
		double max = 0;
		for(int i = 0; i < points.length; i++){
			Point p = points[i];			
			double s = 
					(p.x - x) * (p.x - x) + 
					(p.y - y) * (p.y - y) + 
					(p.z - z) * (p.z - z);
			max = Math.max(max, s);
		}
		if(max < best){
			best = max;
			bestPoint = new PointD(x,y,z);
		}
		return max;
	}
 
}

Обратите внимание на некоторые места в коде:

  1. Мы рассчитываем не φ, а 1/φ, чтобы дальше в вычислениях использовать умножение, а не деление, т.к. умножение работает быстрее;
    static double fi = 1 / ((Math.sqrt(5) + 1) / 2);
    double delta = (r - l) * fi;
    double m1 = r - delta;
    double m2 = l + delta;
  2. В первых двух задачах мы рассматривали поиск максимального значения, а данной задаче нас интересует минимально значение, поэтому в условном операторе меняется условие:
    if(f(m1) > f(m2)){
    	l = m1;
    }else{
    	r = m2;
    }
  3. Обратите внимание, что при расчете расстояния извлечение квадратного корня опущено.
    double s = 
    	(p.x - x) * (p.x - x) + 
    	(p.y - y) * (p.y - y) + 
    	(p.z - z) * (p.z - z);

    Извлечение квадратног корня — очень затратная операция. Сравнивать расстояния можно и без извлечения корня, а если бы потребовалось узнать самое минимальное расстояние, то корень можно было бы извлечь в самом конце.

Перебор всех возможных вариантов

В данной статье будет рассмотрено два алгоритма перебора всех возможных вариантов.

Для начала придумаем задачу, на примере которой будем рассматривать алгоритмы.
Пусть у нас имеется множество S, состоящее из 4-х элементов: * + /, и наша задача — перебрать все возможные комбинации из 3-х элементов, используя элементы множества S. Причем, выбираемые элементы могут повторяться. Например: «+*+».

Первый алгоритм

Сопоставим каждому элементу число, начиная с 0.
* — 0
— 1
+ — 2
/ — 3

Можно догадаться, что нужно перебрать элементы от 0 0 0 до 3 3 3:
0 0 0
0 0 1
0 0 2
0 0 3
0 1 0
0 0 1


3 2 3
3 3 0
3 3 1
3 3 2
3 3 3

Всего получится 64 варианта (4 * 4 * 4 = 64)

Далее нужно провести обратную операцию, сопоставив числу элемент множества S.
Например, набору 2 0 2 соответствует +*+

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

Реализация:

char abc[] = new char[]{'*','-','+','/'};//множество допустимых символов
int size = 3;//кол-во элементов
int arr[] = new int[size];//массив для хранения текущего варианта множества
outer: while(true){//вечный цикл
 
	//вывод варианта множества на экран
	for(int ndx : arr){
		System.out.print(abc[ndx]);
	}
	System.out.println();
 
	int i = size - 1;//ставим курсов в самую правую ячейку
	while(arr[i] == abc.length - 1){//движемся влево, если ячейка переполнена
		arr[i] = 0;//записываем в ячейку 0, т.к. идет перенос разряда
		i--;//сдвиг влево
		//если перенос влево невозможен, значит перебор закончен
		if(i < 0)break outer;
	}
	arr[i]++;//увеличиваем значение ячейки на единицу
}

В результате программа выведет все 64 варианта:

***
**-
**+
**/
*-*
*--
...
...
/++
/+/
//*
//-
//+
///

Второй алгоритм
Для начала посчитаем сколько всего возможных комбинаций, это число равно n ^ k, где n — это размер алфавита (кол-во допустимых символов), а k — кол-во элементов в комбинации.
Для нашего множества S, состоящего из *,,+ и /, n равно 4. И т.к. нужно перебрать все комбинации из трех элементов, то k равно 3.
Получаем: n ^ k = 4 ^ 3 = 64.
В итоге мы должны получить 64 комбинации.
Вот если бы существовал способ преобразования номера комбинации в элементы комбинации.
И такой способ существует: для этого нужно номер комбинации преобразовать в k-значное число в системе счисления по основанию n.
Первой комбинации будет соответствовать число 0, а последней 63.
Перебирая числа от 0 до 63, нам нужно каждое число преобразовать в число в систему счисления по основанию 4. Для получения разрядов числа нужно целочисленно разделить число на 1, 4, 16 (т.е. n^0, n^1, n^2) и результат взять по модулю n.
Пример: для числа 57 при k = 3 и n = 4
(57 / 1) % 4 = 57 % 4 = 1 (-)
(57 / 4) % 4 = 14 % 4 = 2 (+)
(57 / 16) % 4 = 3 % 4 = 3 (/)
Т.е. комбинации под номером 57 соответствует комбинация -+/

char abc[] = new char[]{'*','-','+','/'};//множество допустимых символов (алфавит)
int N = abc.length;//N - размер алфавита
int K = 3;//кол-во элементов в комбинации
 
int pow[] = new int[K + 1];//массив для степеней числа N: N^0, N^1, .., N^K   
pow[0] = 1;
for (int i = 1; i <= K; i++) {//вычисляем степени числа N
	pow[i] = pow[i - 1] * N
}
 
//перебираем все номера комбинаций
for (int i = 0; i < pow[K]; i++) {
	char arr[] = new char[K];
	//вычисляем элементы комбинации
	for (int j = 0; j < K; j++) {
		//каждый элемент получаем из массива abc по индексу,
		//индекс - это число в системе счисления по основанию N (0..N-1)
		//в соответствующем разряде j (от 0 до K-1 включительно)
		arr[j] = abc[(i / pow[j]) % N];
	}
	//вывод в консоль
	for(char ch : arr){
		System.out.print(ch);
	}
	System.out.println();
}

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

0 ***
1 -**
2 +**
3 /**
4 *-*
.....
57 -+/
58 ++/
59 /+/
60 *//
61 -//
62 +//
63 ///

В данном алгоритме перебор идет как бы слева направо, но это не важно, т.к. мы перебираем все комбинации.

Перебор всех подмножеств заданного множества (Java)

Пусть дано множество, состоящее из четырех элементов: {a,b,c,d}.
Необходимо перебрать все возможные подмножества данного множества:
1) {} — пустое множество
2) {a}
3) {b}
4) {a,b}
5) {c}
6) {a,c}
7) {b,c}
8) {a,b,c}
9) {d}
10) {a,d}
11) {b,d}
12) {a,b,d}
13) {c,d}
14) {a,c,d}
15) {b,c,d}
16) {a,b,c,d}

Причем подмножества {a,b} и {b,a} считаются одним и тем же подмножеством.

Данную задачу будем решать с использованием битовых масок и битовых операций.
Сразу приведу реализацию:

char arr[] = new char[]{'a','b','c','d'};
int N = arr.length;
for (int mask = 0; mask < (1 << N); mask++) {//перебор масок			
	for (int j = 0; j < N; j++) {//перебор индексов массива
		if((mask & (1 << j)) != 0){//поиск индекса в маске
			System.out.print(arr[j] + " ");//вывод элемента
		}
	}
	System.out.println();//перевод строки для вывод следующего подмножества
}

А теперь пояснения.
1 << N — побитовый сдвиг единицы на N позиций влево.
В двоичном виде единица выглядит так 00000001. В нашем случае N = 4.
После сдвига на 4 позиции влево появится новое число, двоичный вид которого 00010000. Теперь, если вычесть из этого числа единицу получим: 00001111. Если опустить ведущие нули, то получим 1111. Четыре единицы — это состояние, когда в подмножество попадают все элементы, 0000 — пустое множество, 1010 — подмножество состоит из первого и третьего элемента множества (нумерация с нуля, отсчет ведется справа) и т.д.
Т.е. мы перебираем числа, двоичное представление которых от 0000 до 1111.

После того как мы получили маску (mask), необходимо узнать в каких позициях стоят единицы. Проверять будем следующим образом.
Например, на каком-то шаге цикла программы маска равна 1100, мы перебираем все позиции путем сдвига единицы: 0001, 0010, 0100 и 1000. Для проверки воспользуемся операцией побитового И (если в одинаковых позициях стоят единицы, то результат единица, иначе ноль). В Java обозначается как &
В нашем случае:
1100 & 0001 = 0000
1100 & 0010 = 0000
1100 & 0100 = 0100
1100 & 1000 = 1000
Т.е. если в итоге получилось число отличное от нуля, то включаем элемент в множество.
0100 — включаем в множество элемент с индексом 2
1000 — включаем в множество элемент с индексом 3
Нумерация с нуля и справа.
Результат работы программы (первая строка пустая — это пустое множество):


a 
b 
a b 
c 
a c 
b c 
a b c 
d 
a d 
b d 
a b d 
c d 
a c d 
b c d 
a b c d 

В данной реализации мы хранили маски в типе int.
(1 << 30) равно 1 073 741 824 Безопасное значение N для типа int: 30. Свыше 30 будет переполнение переменных типа int, поэтому нужно использовать long.
При N > 30 перебор будет ощутимо все медленнее и медленнее.

Если будете делать реализацию с long, то при сдвиге единицы нужно писать так:

1L << j

Т.е. нужно к единице приписать L, и тогда результат операции будет long, в противном случае будет int с переполнением.

Замена и удаление повторяющихся символов в строке

В данной статье будет рассмотрена замена и удаление повторяющихся символов в строке с помощью регулярных выражений Java.
Заменять и удалять повторяющиеся символы будет через функции замены класса String.
У класса String есть четыре метода для замены символов. Вот их сигнатуры:

  1. replace(char oldChar, char newChar):String
  2. replace(CharSequence target, CharSequence replacement):String
  3. replaceAll(String regex,String replacement):String
  4. replaceFirst(String regex,String replacement):String

Первые два метода в нашем случае не пригодятся, т.к. они нужны для замены одного символа (char) на другой символ или последовательности символов (CharSequence) на другую последовательность. CharSequence — это интерфейс, который реализуют классы: String, StringBuilder и StringBuffer.
Остановимся на двух последних методах: replaceAll и replaceFirst. Оба метода первым параметром принимают регулярное выражение (regex), а вторым параметром текст замены (replacement). replaceAll— заменяет все совпадения, а replaceFirst заменяет только первое совпадение. В данной статье будет использоваться только replaceAll.

  1. Представим себе следующую задачу: требуется удалить из строки все стоящие рядом два одинаковых символа. Например, из строки «keeshh» должна в итоге получиться строка «ks»
    String text = "keeshh";
    String result = text.replaceAll("([a-z])\\1", "");
    System.out.println(result);//"ks"

    replaceAll — функция для замены всех совпадений
    [a-z] — выражение говорит о том, что на этом месте должен быть символ в диапазоне от a до z.
    () — круглые скобки означают группировку, сослаться на которую можно по номеру, причем нумерация начинается с единицы
    \1 — указывает на то, что в этом месте должен быть такой же текст, как в группировке под номером 1. Обратный слэш «\» необходимо экранировать, поэтому в выражении два слэша «\\»

  2. После удаление двух повторных символов, могут снова образоваться повторные символы.
    Например, если в строке «keeshhs» заменить два подряд повторяющихся символа, то получится «kss», но подстроку «ss» также можно удалить. Поместим описанный выше код в цикл, который будет повторяться до тех пор, пока не будут заменены все повторные символы. В данной реализации будем пытаться удалять повторения, пока меняется (укорачивается) длина строки

    String text = "keeshhs";
    int len;		
    do{
    	len = text.length();//сохраняем длину строки
    	text = text.replaceAll("([a-z])\\1", "");
    }while(len != text.length());//сравниваем новую длину строки с сохраненной длиной
    System.out.println(text);//"k"
  3. Рассмотрим следующий пример. Нужно удалить все повторяющиеся подряд символы.
    Например, для строки «keeeshh» результат должен быть «ks». Реализация:

    String text = "keeeeshh";
    text = text.replaceAll("([a-z])\\1+", "");
    System.out.println(text);//"ks"
    

    Как вы, наверное, заметили после единички добавился символ +. Плюс в регулярных означает, что предшествующий плюсу символ или группировка должна встретиться от одного раза и более. Можно также включить этот код в цикл, чтобы снова заменить появившиеся повторения.

  4. Теперь рассмотрим замену. Задача: имеется строка, необходимо из двух подряд идущих одинаковых символов оставить только один.
    Пример: из строки «kkeesshh» получится строка «kesh».
    Реализация:

    String text = "kkeesshh";
    text = text.replaceAll("([a-z])\\1", "$1");
    System.out.println(text);//"kesh"

    Для замены мы использовали выражение $1, которое говорит о том, что текст, соответствующий регулярному выражению, необходимо заменить на текст, соответствующий группировке с номером 1. В нашем случае группировка с номером — это текст, соответствующий шаблону [a-z].
    Можно переписать код, используя группу с номером 2 для замены:

    String text = "kkeesshh";
    text = text.replaceAll("([a-z])(\\1)", "$2");
    System.out.println(text);//"kesh"

    Вторая группа соответствует шаблону \\1

  5. И напоследок заменим в строке все подряд повторяющиеся символы одним символом.
    Например, строка «keeeeessshh» преобразуется в «kesh».
    Реализация:

    String text = "keeeeessshh";
    text = text.replaceAll("([a-z])\\1+", "$1");
    System.out.println(text);//"kesh"

Использование регулярных выражений позволяет писать более компактный код и, возможно, сэкономить время на наборе кода, если хорошо освоить регулярные выражения.