Category Archive: Java

Разбивка текста на блоки фиксированной длины

Допустим, перед нами стоит задача разбить текст на блоки фиксированной длины. Как пример можно взять строку:
oxxxxooox
и разбить на блоки по три символа:
oxx
xxo
oox
Это можно сделать следующим кодом:
String text = "oxxxxooox";//исходный текст
int portion = 3;//размер блока
int i = 0;
while(i < text.length()){
	System.out.println(text.substring(i,Math.min(i += portion, text.length())));
}
Функция substring вырезает часть строки в диапазоне [beginIndex,endIndex), т.е. начиная с позиции beginIndex включительно и до позиции endIndex (не включая саму позицию endIndex). i += portion - определяет конец текущего блока и одновременно начало следующего. Math.min(i += portion, text.length()) - позволяет определить конец блока и не выйти за пределы самого текста.

Дополнение числа ведущими нулями на 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 с переполнением.