Проект Эйлера 4 задача (наибольшее произведение-палиндром) позволила не только познакомиться и отработать новые конструкции языка java, но и попрактиковаться в работе с git, создать локальный репозиторий с кодом программы, отправить изменения на удаленный репозиторий (в GitHub) и склонировать код на удаленный сервер, где затем скомпилировать и запустить программу. Онлайн-калькулятор для проверки вычислений и правильный ответ на задачу прилагаются.
Число-палиндром с обеих сторон (справа налево и слева направо) читается одинаково. Самое большое число-палиндром, полученное умножением двух двузначных чисел - 9009 = 91 * 99. Найдите самый большой палиндром, полученный умножением двух трехзначных чисел.
В программу можно передать параметр, указывающий разрядность множителей, среди произведений которых нужно искать палиндром. Например, если мы ищем палиндром среди произведений двузначных чисел, то передаем программе 2 через параметры командной строки:
Программу можно запускать также и без параметров:
В этом случае программа вычисляет максимальный палиндром двух трехзначных чисел (согласно условиям 4 задачи Эйлера).
Весь исходный код программы находится в одном файле. Класс Solution служит для получения пользовательского ввода, содержит метод main(), а также статические методы необходимые для вычислений.
public class Solution {
public static void main(String[] args) {
int digits = (args.length > 0) ? (Integer.parseInt(args[0])) : (3);
int max = (int) Math.pow(10, digits) - 1;
int min = (int) Math.pow(10, digits - 1);
int answer = 0;
int fact1 = max;
while (answer < fact1 * fact1) {
for (int fact2 = fact1; fact2 > min; fact2--) {
if (isPalindrome(fact1 * fact2)) {
answer = Math.max(fact1 * fact2, answer);
break;
}
}
fact1--;
}
System.out.println("The largest palindrome between " + min +
" and " + max + " is " + answer);
}
Программа перебирает множители fact1 и fact2 в цикле от максимально возможного значения (max = 999 для трехзначных чисел), к минимальному (min = 100). Если их произведение является палиндромом и числом большим, чем уже записанный ответ, его значение (answer) обновляется.
Поскольку перебор множителей идет от большего к меньшему, то первый найденный при переборе fact2 палиндром является максимальным и перебор fact2 прерывается (все следующие произведения fact1 * fact2 будут заведомо меньше). Перебор начинается заново уже при новом значении fact1.
По этой же причине прекращается перебор первого множителя fact1, как только его квадрат превысит последний полученный ответ answer - все возможные последующие палиндромы заведомо меньше.
Метод invert принимает положительное натуральное число (например, 123456), превращает его в строку ("123456"), инвертирует ее ("654321") и и преобразует обратно в число (654321), которое и возвращает.
public static int invert(int number) {
String stringNumber = String.valueOf(number);
stringNumber = new StringBuilder(stringNumber).reverse().toString();
return Integer.parseInt(stringNumber);
}
Метод isPalindrome принимает натуральное число и возвращает true, если оно является палиндромом. Для этого он использует вышеописанный метод invert. Если число равно инвертированному самому себе - оно палиндром.
public static boolean isPalindrome(int number) {
return number == invert(number);
}
Продолжаю работать с удаленным сервером и начну внедрять в работу git. Создаю локальный git-репозиторий с кодом программы, отправлю изменения (git push) на удаленный репозиторий (в GitHub) и склонирую (git clone) код на мой vps-сервер. После чего уже соберу и запущу программу из консоли через ssh соединение.
В данный момент структура проекта имеет следующий вид:
project-euler/
problem-4/
src/
Solution.java
Инициализирую git репозиторий в корневой папке проекта (project-euler/):
Небольшая "шпаргалка" по командам git:
Добавляю файл с кодом для отслеживания:
Делаю "коммит":
Правильно написать "коммит" поможет статья:
Создаю репозиторий на GitHub, после чего добавляю его:
Отправляю изменения в ветку main удаленного репозитория (origin):
Подключаюсь через ssh к удаленному vps-серверу.
Как это сделать было описано ранее:
Клонирую код из удаленного репозитория на сервер:
Компилирую файлы с исходным кодом (из папки problem-4):
Вопросы компиляции java-кода подробно описаны в статье:
Запускаю скомпилированный файл и получаю искомый ответ:
java -cp bin/ Solution 3 The largest palindrome between 100 and 999 is 906609
В этой программе применил несколько новых конструкций языка java: