Могу ли я сделать эту функцию более эффективной (Project Euler Number 9)?

Question

Я только что закончил проблема проекта Эйлера 9 (предупреждение спойлеры):

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which, 
a^2 + b^2 = c^2 

For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2. 

There exists exactly one Pythagorean triplet for which a + b + c = 1000. 
Find the product abc. 

Вот мое решение:

public static int specPyth(int num) 
{ 
    for (int a = 1; a < num; a++) 
     for (int b = 2; b < a; b++) 
      { 
       if (a*a +b*b == (num-a-b)*(num-a-b)) 
        return a*b*(num-a-b); //ans = 31875000 
      } 

    return -1; 
} 

Я не могу помочь, но думаю, что есть решение, которое включает в себя только одну петлю , У кого-нибудь есть идеи? Я предпочел бы ответы, используя только один цикл, но все, что более эффективно, чем то, что у меня сейчас, было бы неплохо.

Answer 1

if a + b +c = 1000 

затем

a + b + sqroot(a² + b²) = 1000 

-> (a² + b²) = (1000 - a - b)² 

-> a² + b² = 1000000 - 2000*(a+b) + a² + 2*a*b + b² 

-> 0 = 1000000 - 2000*(a+b) + 2*a*b 

-> ... (easy basic maths) 

-> a = (500000 - 1000*b)/(1000 - b) 

Тогда вы пытаетесь все б, пока не найдете тот, который делает натуральное число из а.

public static int specPyth(int num) 
    { 
     double a; 
     for (int b = 1; b < num/2; b++) 
     { 
      a=(num*num/2 - num*b)/(num - b); 

      if (a%1 == 0) 
       return (int) (a*b*(num-a-b)); 
     } 

     return -1; 
    } 

EDIT: б не может быть выше, чем 499, так как с> Ь и (Ь + с) затем будет выше, чем 1000.

Answer 2

Вы говорите a < b < c, то b всегда должно быть больше a, поэтому отправной точкой во втором цикле может быть b = a + 1; что привело бы к меньшему количеству итераций.

int specPyth(int num) 
{ 
    for (int a = 1; a < num/3; a++) 
     for (int b = a + 1; b < num/2; b++) 
     { 
      int c = num - a - b; 
      if (a * a + b * b == c * c) 
       return a * b * c; //ans = 31875000 
     } 

    return -1; 
} 

Answer 3

Во-первых, поскольку это наименьшее, вам не нужно подсчитать его до NUM, пит/3 достаточно, и даже Num/(2 + SQRT (2)). Во-вторых, имея и ограничения

a+b+c=num 
a^2+b^2=c^2 

мы можем решить эти уравнения и найти б и для дали, которые уже удовлетворяют эти уравнения и нет необходимости проверять, если а^2 + B^2 = с^2, как и сейчас. Все, что вам нужно, это проверить, являются ли b и c целыми. И это делается в одной петле

for (int a = 1; a < num/3; a++) 

Answer 4

Я настоятельно рекомендую прочитать http://en.wikipedia.org/wiki/Pythagorean_triple#Generating_a_triple и писать функцию, которая будет генерировать Пифагора троек один на один.

Не слишком много спойлеров, но есть ряд других проблем с PE, которые эта функция пригодится.

(я не считаю, что это отдает слишком много, потому что часть с целью ПЭ является, чтобы побудить людей, чтобы узнать о том, как это.)

Answer 5

Определенно не самое оптимальное решение, но мой первый инстинкт было использование модифицированного 3SUM. В Python,

def problem_9(max_value = 1000): 
    i = 0 
    range_of_values = [n for n in range(1, max_value + 1)] 
    while i < max_value - 3: 
     j = i + 1 
     k = max_value - 1 
     while j < k: 
      a = range_of_values[i] 
      b = range_of_values[j] 
      c = range_of_values[k] 
      if ((a + b + c) == 1000) and (a*a + b*b == c*c): 
       return a*b*c 
      elif (a + b + c) < 1000: 
       j += 1 
      else: 
       k -= 1 
     i += 1 
    return -1 

Answer 6

Запускается в 62 милли секунд

import time 
    s = time.time() 
    tag,n=True,1000 
    for a in xrange (1,n/2): 
     if tag==False: 
      break 
     for b in xrange (1,n/2): 
      if a*a + b*b - (n-a-b)*(n-a-b) ==0: 
       print a,b,n-a-b 
       print a*b*(n-a-b) 
       tag=False 
    print time.time() - s 

Answer 7

В первом данного уравнения, у вас есть три переменные a, b, c. Если вы хотите найти соответствующие значения для этого уравнения, вам нужно запустить 3 цикла измерения. К счастью, существует еще одно уравнение: a+b+c=N, где N - известное число.

Используя это, вы можете уменьшить размер до двух, потому что, если вы знаете два из трех, вы можете рассчитать остальное. Например, если вы знаете a и b, c равно N - a - b.

Что делать, если вы можете уменьшить еще одно измерение цикла? Это возможно, если вы играете с двумя заданными уравнениями. Возьмите ручку и бумагу. Как только вы получите дополнительное уравнение с двумя переменными и одной константой (N), вы сможете получить результат в O(n). Решить эти два уравнения a+b+c=n; a^2+b^2=c^2 принимая n и a быть постоянным и решить для b и c:

public static void main(String[] args) { 
    Scanner in = new Scanner(System.in); 
    int t = in.nextInt(); 
    for(int a0 = 0; a0 < t; a0++){ 
     int n = in.nextInt(); 
     int max=-1; 
     int multi=0; 
     int b=1,c=1; 
     for(int i=1;i<=n;i++) 
      { 
      if(2*(i-n)!=0) 
      b=(2*i*n-(n*n))/(2*(i-n)); 
      c=n-b-i; 
      if((i*i+b*b==c*c)&& i+b+c==n && b>0 && c>=0 && i+b>c && c+i>b && b+c>i) 
       { 
       multi=i*b*c; 
       if(max<multi) 
        max=multi; 

      } 
     } 
     if(max==-1) 
     System.out.println(-1); 
     else 
      System.out.println(max); 

    } 
} 

Answer 8

C раствор

Предупреждение: решение предполагает, что НОД (а, Ь) = 1. Она работает здесь, но может не всегда работать. Я исправлю решение через некоторое время.

#include <stdio.h> 
#include <math.h> 

int main(void) 
{ 
    int n = 1000;   // a + b + c = n 
    n /= 2; 

    for(int r = (int) sqrt(n/2); r <= (int) sqrt(n); r++) 
    { 
    if(n % r == 0) 
    { 
     int s = (n/r) - r; 
     printf("%d %d %d\n", r*r - s*s, 2*r*s, r*r + s*s); 
     printf("Product is %d\n", (2*r*s) * (r*r - s*s) * (r*r + s*s)); 
    } 
    } 

    return 0; 
} 

Решение использует Euclid's formula для триплетов, который гласит, что любой примитивный тройная имеет вид а = г^2 - х^2, B = 2RS, с = г^2 + з^2.

Некоторые ограничения, такие как sqrt (n/2) < = r < = sqrt (n) могут быть добавлены на основании того, что s положительно и r> s.

Предупреждение: вам может понадобиться долго долго, если продукт является большой