Ці магу я зрабіць гэтую функцыю больш эфектыўнай (Project Euler Number 9)?

Я толькі што скончыў праект Эйлера праблемы 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;
}

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

9
@MarkoTopolnik, я адрэдагаваў мой код, дзякуй. Тым не менш, здаецца, што з-за чаго-то ў трыганаметрыі ці некаторых матэматычных прынцыпах, я адчуваю, што павінен быць спосаб, каб атрымаць гэтую працу, выкарыстоўваючы толькі адзін цыкл.
дададзена аўтар Steve P., крыніца
@Fabinout, не ўпэўнены, што вы маеце на ўвазе. Па пабудове, а + B + C павінен быць роўны 1000 (Num-а-б) , дзе Num 1000.
дададзена аўтар Steve P., крыніца
@Fabinout, не праблема, вы таксама.
дададзена аўтар Steve P., крыніца
Толькі з -loop патрэбны. Вы можаце знайсці а і B , вырашаючы квадратнае раўнанне.
дададзена аўтар Egor Skriptunoff, крыніца
Калі вы хочаце імгненнага паскарэння, выкарыстоўвайце х * х замест Паў (х, 2) . Акрамя таго, гледзячы на ​​квадратны корань пераборам відавочна нешта палепшыць.
дададзена аўтар Marko Topolnik, крыніца
<�Код> + 42 32 = 9 + 16 = 25 = 52 - Я не разумею, гэта - Вы, верагодна, азначае 2 ^ 3 + 4 ^ 2 = 9 + 16 = 25 = 5 ^ 2
дададзена аўтар Maroun, крыніца
дададзена аўтар starblue, крыніца
3 ^ 2 + 4 ^ 2 = 9 + 16 = 25 = 5 ^ 2
дададзена аўтар Gabriel Negut, крыніца
Ваша другая пятля Я думаю, што гэта памылка, як бы Ь = 2 і яшчэ менш, чым у пачатковай кропцы? Я думаю, што ён памірае ад а 's другі ітэрацыі. Праверце мой адказ.
дададзена аўтар マルちゃん だよ, крыніца
@SteveP. Так, і дзякуй за сайт праекта Эйлера. Здаецца дзіўным. Добрага дня!
дададзена аўтар Fabinout, крыніца
@SteveP. На самай справе, я думаў, што ты прыняў гэтую праблему, і на самай справе шукаў a² + b² = 1000, але гэта было па-дурному. Выбачайце за дурны каментар;)
дададзена аўтар Fabinout, крыніца
Ці можаце вы пацвердзіць гэта + Ь + з = 1000?
дададзена аўтар Fabinout, крыніца

8 адказы

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)

то you try every b until you find one that makes a natural number out of a.

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: b can't be higher than 499, because c>b and (b+c) would то be higher than 1000.

22
дададзена
Так, гэта менавіта тое, што я шукаў. Дзякуй! Дзякуючы ўсім астатнім таксама.
дададзена аўтар Steve P., крыніца
Ваша функцыя не вяртае правільны адказ 60, калі вы выклікаеце яго з NUM = 12 = 3 + 4 + 5
дададзена аўтар James Waldby - jwpat7, крыніца
справа; і замяніць 499 з NUM/2. Напрыклад, 499 не будзе працаваць у некаторых выпадках з NUM> 1000
дададзена аўтар James Waldby - jwpat7, крыніца
@ Jwpat7 я атрымаў яго: калі вы карыстаецеся = 3 B = 4 з = 5, вы карыстаецеся Num = 12, а не Num = 1000. У вас ёсць тое: а = (лік * Num 2 -число/* 4)/( Num-4); -> а = (12 * 6 -12 * 4)/(12-4) = 3
дададзена аўтар Fabinout, крыніца
@ Jwpat7 вы маеце рацыю, я гляджу на яго.
дададзена аўтар Fabinout, крыніца
а б і з станоўчымі цэлымі лікамі, гэта тое ж самае, з = sqroot (a² + b²)
дададзена аўтар Fabinout, крыніца
@SteveP. Дзякуй за шчодрасць;)
дададзена аўтар Fabinout, крыніца
Выдатны адказ!
дададзена аўтар NirmalGeo, крыніца
гэта не працуе ўмова павінна быць ^ 2 + Ь ^ 2 == ск 2 :-);
дададзена аўтар Sachin Godara, крыніца

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

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

(Я не лічу, што гэта аддае занадта шмат, таму што частка з мэтай ПЭ з'яўляецца, каб заахвоціць людзей, каб даведацца пра тое, як гэта.)

5
дададзена

рашэнне C

Увага: рашэнне мяркуе, што Нод (а, Ь) = 1. Яна працуе тут, але не заўсёды можа працаваць. Я палатаю рашэнне ў нейкі час.

#include 
#include 

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;
}

Рашэнне выкарыстоўвае Еўкліда формулы для трыплет, які абвяшчае, што любы прымітыўны трайная мае выгляд а = г ^ 2 - х ^ 2, B = 2RS, з = г ^ 2 + в е ^ 2.

Certain restrictions like sqrt(n/2) <= r <= sqrt(n) can be added based on the fact that s is positive and r > s.

Увага: вам можа спатрэбіцца доўга доўга, калі прадукт з'яўляецца вялікім

1
дададзена

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

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

мы можам вырашыць гэтыя ўраўненні і знайсці Ь і з для далі, якія ўжо задавальняюць гэтыя раўнанні і няма неабходнасці правяраць, калі а ^ 2 + Ь ^ 2 = з ^ 2, як вы робіце цяпер. Усё, што вам трэба праверыць, калі б і цэлыя. І гэта робіцца ў адным цыкле

for (int a = 1; a < num/3; a++)
1
дададзена
Я бачу, маё неразуменне. Дзякуючы.
дададзена аўтар Steve P., крыніца
Не павінна быць <�лік/(3 + SQRT (3))?
дададзена аўтар Steve P., крыніца
Дзякуй, што робіць шмат сэнсу, але я не разумею, чаму Num/3 дастаткова. Не маглі б вы ўдакладніць?
дададзена аўтар Steve P., крыніца
Не, я меў рацыю, і мы можам праверыць толькі тыя выпадкі, калі <�лік/(2 + SQRT (2)), так як мы можам выказаць здагадку, што гэта найменшая бок трыкутніка.
дададзена аўтар Alexei Kaigorodov, крыніца
@Steve я быў няправільна, на самай справе п/2, так як а, бы, у форме прастакутнага трыкутніка.
дададзена аўтар Alexei Kaigorodov, крыніца
Максімальныя а, гэта разумна, каб праверыць, калі прастакутны трыкутнік isoscales, то Num = а + а + SQRT (2) * а.
дададзена аўтар Alexei Kaigorodov, крыніца

Запускаецца ў 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
1
дададзена

You say a < b < c, then b must always be bigger than a, so your starting point in the second loop could be b = a + 1; that would lead certainly to fewer iterations.

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;
}
0
дададзена
Чаму Num/3, то Num/2? Як вы вызначыць гэтыя межы?
дададзена аўтар Steve P., крыніца
Гэта дакладна тады і толькі тады ваша зацвярджэнне дакладна. Вы не растлумачыце, чаму.
дададзена аўтар Steve P., крыніца
Таму што, калі а> Num/3, то а + B + C> Num.
дададзена аўтар Fabinout, крыніца

У першым дадзенага раўнання, то ёсць тры зменныя а, Ь, з . Калі вы хочаце, каб знайсці выхад адпаведных значэнняў для гэтага раўнання, вы павінны запусціць 3 памер завесы. На шчасце, ёсць яшчэ адно раўнанне A + B + C = N , дзе N вядомы нумар.

Выкарыстоўваючы гэта, вы можаце зменшыць ўніз памер да двух, таму што калі вы ведаеце, два з трох, вы можаце вылічыць астатнія. Напрыклад, калі вы ведаеце, а і B , з роўны N - A - B .

Што рабіць, калі вы можаце зменшыць яшчэ адно вымярэнне завесы? Гэта магчыма, калі вы важдацца з двума зададзенымі раўнаннямі. Атрымаць ручку і паперу. Пасля таго, як вы атрымаеце дадатковае ураўненне з двума зменнымі і адной канстантай (N), вы будзеце мець магчымасць атрымаць вынік у O (п) . Вырашыць два ўраўненні A + B + C = N; а ^ 2 + B ^ 2 = з ^ 2 прымаць п і а , каб быць сталым і вырашыць для B і <�код > з :

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
0
дададзена

Вызначана не самае аптымальнае рашэнне, але мой першы інстынкт павінен быў выкарыстаць мадыфікаваны 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
0
дададзена