Проект Эйлера #9: нахождение пифагоровых троек с данной суммы.


Постановка задачи:

Пифагорейский тройня-это набор из трех натуральных чисел, а < Б < C, для которых, А2 + В2 = С2. Дано число n, проверить, если есть какие-тройка Пифагора, для которой A + Б + С = Н.

public class SpecialPythagoreanTriplet {

public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    int t = scan.nextInt();
    int n=0, i=0, j=0, a=0, b=0, c=0;

    while(t!=0) {
        n = scan.nextInt();
        a=0; b=0; c=0;
        for(i=1; i<n; i++)
            for(j=(i+1); j<=n; j++) {
                //These two loops run to take a pair of numbers. j=(i+1) to avoid repetitions in the future.
                if(isSquare((i*i) + (j*j))) //check if a number is a square
                    if(((int)Math.sqrt((i*i)+(j*j)) + i + j) == n) {
                        a = i;
                        b = j;
                        c = (int)Math.sqrt((i*i)+(j*j));
                    }
            }
        if(c==0)
            System.out.println(-1);
        else
            System.out.println(a*b*c);
        t--;
    }
    scan.close();
}

static boolean isSquare(double t) { 
    int a = (int)Math.sqrt(t);
    if(a*a == t)
        return true;
    else
        return false;
}
}

Я работал над этой программой в ProjectEuler и Hackerrank последовательно. Он прекрасно бегал за вход 1000 и поступил на проект Эйлера. Но это дает прекращено из-за тайм-аута ошибки в большинстве случаев в Hackerrank.

Как я могу оптимизировать это больше, чтобы избежать этой ошибки?



Комментарии
2 ответа

Программа завершается из-за тайм-аута из-за высокой сложности время \$о(т*н*н)\$.
Сложности данной программы может быть сокращено до \$О(Т)\ долл препроцесса и сохранение результатов, чтобы избежать повторных вычислений.

Повторные вычисления для нахождения комбинации из двух чисел ( I и J ) можете уменьшения выполнить только один раз, за определенное количество Время 'Н'.

Вот полная реализация в Java:

import java.io.*;
import java.math.*;

public class Solution {

public static void main(String[] args) {
BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
try{

//precomputation
int save[] = new int[3001];

for(int i=1; i<3001; i++){
int iSqr = i*i;
for(int j=i+1; j<3001; j++){

double x = Math.sqrt(iSqr + j*j);
if(x == Math.floor(x)){
int sum = i+j+(int)x;
int product = i*j*(int)x;
if((sum < 3001) && (product > save[sum]))
save[sum] = product;
}
}
}

int t = Integer.parseInt(stdin.readLine());

while(t-- > 0){
int n = Integer.parseInt(stdin.readLine());
if(save[n] == 0)
System.out.println(-1);
else
System.out.println(save[n]);
}
}
catch(Exception e){

}
}
}

4
ответ дан 12 февраля 2018 в 05:02 Источник Поделиться

Реорганизации кода

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

В вашем случае, вы могли бы написать что-то вроде:

import java.util.Scanner;

public class SpecialPythagoreanTriplet {

public static int getProductForPythagoreanTriplerOfPerim(int n)
{
int i=0, j=0, a=0, b=0, c=0;
for(i=1; i<n; i++)
for(j=(i+1); j<=n; j++) {
//These two loops run to take a pair of numbers. j=(i+1) to avoid repetitions in the future.
if(isSquare((i*i) + (j*j))) //check if a number is a square
if(((int)Math.sqrt((i*i)+(j*j)) + i + j) == n) {
a = i;
b = j;
c = (int)Math.sqrt((i*i)+(j*j));
}
}
return (c==0) ? -1 : a*b*c;
}

public static void main(String[] args) {
if (false) // interactive
{
Scanner scan = new Scanner(System.in);
for (int t = scan.nextInt(); t!=0; t--) {
System.out.println(getProductForPythagoreanTriplerOfPerim(scan.nextInt()));
}
scan.close();
}
else // hardcoded
{
System.out.println(getProductForPythagoreanTriplerOfPerim(25) == -1);
System.out.println(getProductForPythagoreanTriplerOfPerim(1000) == 31875000);
System.out.println(getProductForPythagoreanTriplerOfPerim(30000) == 1197129472);
}
}

static boolean isSquare(double t) {
int a = (int)Math.sqrt(t);
if(a*a == t)
return true;
else
return false;
}
}

Улучшение качества кода

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

Вы бы сделать что-то вроде:

public static int getProductForPythagoreanTriplerOfPerim(int n)
{
int a=0, b=0, c=0;
for (int i=1; i<n; i++) {
for (int j=i+1; j<=n; j++) {
//These two loops run to take a pair of numbers. j=(i+1) to avoid repetitions in the future.
int squareCand = i*i + j*j;
if (isSquare(squareCand)) {
int squareRoot = (int)Math.sqrt(squareCand);
if (squareRoot + i + j == n) {
a = i;
b = j;
c = squareRoot;
}
}
}
}
return (c==0) ? -1 : a*b*c;
}

Оптимизация кода

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

public static int getProductForPythagoreanTriplerOfPerim(int n)
{
int a=0, b=0, c=0;
for (int i=1; i<n; i++) {
for (int j=i+1; j<=n; j++) {
//These two loops run to take a pair of numbers. j=(i+1) to avoid repetitions in the future.
int squareCand = i*i + j*j;
int squareRoot = (int)Math.sqrt(squareCand);
if (squareRoot*squareRoot == squareCand) {
if (squareRoot + i + j == n) {
a = i;
b = j;
c = squareRoot;
}
}
}
}
return (c==0) ? -1 : a*b*c;
}

Тогда понятно, что условия могут быть переписаны:

           if (squareRoot*squareRoot == squareCand &&
squareRoot == n - i - j) {
a = i;
b = j;
c = squareRoot;
}

Затем вы можете использовать это для того, чтобы не вычислить любое корня:

            int squareRootCand = n - i - j;
int squareCand = i*i + j*j;
if (squareRootCand*squareRootCand == squareCand) {
a = i;
b = j;
c = squareRootCand;
}

Также это еще понятней, что мы хотим i + j <= n. Потому что i < jмы также имеем 2 * i < n.
Таким образом, границы цикла могут быть переписаны:

    for (int i=1; 2*i < n; i++) {
for (int j=i+1; i+j<=n; j++) {

Я думаю, что более точный анализ математических свойств приведет к меньше пространства поиска. На самом деле, потому что i соответствует наименьшему стороны, мы можем написать: 3 * i < nи i + 2j < n.

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

Ограничивая число суб-выражений вычисляемых несколько раз, можно было бы написать (но я не считаю это очень красивым):

    int a=0, b=0, c=0;
for (int i=1; 3*i < n; i++) {
int i2 = i*i;
int rem = n-i;
for (int j=i+1; 2*j<=rem; j++) {
int squareRootCand = rem - j;
int squareCand = i2 + j*j;
if (squareRootCand*squareRootCand == squareCand) {
a = i;
b = j;
c = squareRootCand;
}
}
}

Затем, используя математические свойства: squareRootCand*squareRootCand = (rem - j)^2 = rem^2 -2*rem*j + j^2 и несколько упрощений:

    for (int i=1; 3*i < n; i++) {
int i2 = i*i;
int rem = n-i;
int rem2 = rem*rem;
for (int j=i+1; 2*j<=rem; j++) {
if (rem2 - i2 == 2 * rem * j) {
a = i;
b = j;
c = rem - j;
}
}
}

Становится немного сумасшедшие, мы видим, что мы на самом деле хотим j == (rem2 - i2) / (2*rem) а отдел работает нормально:

    for (int i=1; 3*i < n; i++) {
int i2 = i*i;
int rem = n-i;
int rem2 = rem*rem;
int tmp1 = rem2 - i2;
int tmp2 = 2 * rem;
if (tmp1 % tmp2 == 0)
{
int tmp3 = tmp1 / tmp2;
for (int j=i+1; 2*j<=rem; j++) {
if (tmp3 == j) {
a = i;
b = j;
c = rem - j;
}
}
}
}

и тогда нам не очень нужны j петли: код теперь один цикл:

public static int getProductForPythagoreanTriplerOfPerim(int n) 
{
// a + b + c = n
// 0 < a < b < c < n
// a^2 + b^2 = c^2
int a=0, b=0, c=0;
for (int i=1; 3*i < n; i++) {
int rem = n-i;
int tmp1 = rem*rem - i*i;
int tmp2 = 2 * rem;
if (tmp1 % tmp2 == 0)
{
int j = tmp1 / tmp2;
if (i+1 <= j && 2*j <= rem) { // not needed ?
a = i;
b = j;
c = rem - j;
}
}
}
return (c==0) ? -1 : a*b*c;
}

Или, что делает математику более явные и добавление проверки для нечетных значений n:

public static int getProductForPythagoreanTriplerOfPerim(int n)
{
// a + b + c = n => c = n - (a + b)
// a² + b² = c² becomes:
// a² + b² = (n - (a + b))² = n² + a² + b² + 2ab - 2n(a+b)
// 2 b (n - a) = n (n - 2a)
// we must have n = 2m
// b = n (n-2a) / (2n -2a) = 2m(2m-2a) / (4m - 2a)
// = 2m(m-a) / (2m -a )
// = n(m-a) / (n-a)
int a=0, b=0, c=0;
if (n % 2 == 0) {
int m = n/2;
for (int i=1; 3*i < n; i++) {
int top = n*(m-i);
int down = n-i;
if (top % down == 0)
{
a = i;
b = top/down;
c = down - b;
}
}
}
return (c==0) ? -1 : a*b*c;
}

Идем дальше

Это может не иметь отношение к этой проблеме (а это может быть если вы будете продолжать на проект Эйлера): другой алгоритм можно найти с помощью формул для генерации Pythagoran троек.

4
ответ дан 13 февраля 2018 в 06:02 Источник Поделиться