أوجد ثلاثية فيثاغورس التي فيها a + b + c = 1000

Question

ثلاثة أضعاف فيثاغورات هي مجموعة من ثلاثة أرقام طبيعية ، A <B <C ، والتي ، أ² + ب² = ج²

على سبيل المثال، 3² + 4² = 9 + 16 = 25 = 5².

يوجد بالضبط ثلاثية فيثاغورس واحدة حيث a + b + c = 1000.ابحث عن المنتج ABC.

مصدر: http://projecteuler.net/index.php?section=problems&id=9

لقد حاولت ولكن لم أعرف أين حدث الخطأ في الكود الخاص بي.هذا هو الكود الخاص بي في C:

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


void main()
{
    int a=0, b=0, c=0;
    int i;
    for (a = 0; a<=1000; a++)
    {
        for (b = 0; b<=1000; b++)
        {
            for (c = 0; c<=1000; c++)
            {
                if ((a^(2) + b^(2) == c^(2)) && ((a+b+c) ==1000)))
                    printf("a=%d, b=%d, c=%d",a,b,c);
            }
        }
    }
getch();    
}

Answer 1

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

int main()
{
    const int sum = 1000;
    int a;
    for (a = 1; a <= sum/3; a++)
    {
        int b;
        for (b = a + 1; b <= sum/2; b++)
        {
            int c = sum - a - b;
            if ( a*a + b*b == c*c )
               printf("a=%d, b=%d, c=%d\n",a,b,c);
        }
    }
    return 0;
}

توضيح:

• ب = أ؛
  إذا كانت a وb (a <= b) وc هي ثلاثية فيثاغورس،
  ثم b وa (b >= a) وc - الحل أيضًا، بحيث يمكننا البحث في حالة واحدة فقط
• ج = 1000 - أ - ب؛إنه أحد شروط المشكلة (لسنا بحاجة إلى فحص كل "c" الممكنة:فقط احسبها)

Answer 2

أنا خائف ^ لا تفعل ما تعتقد أنه في C. أفضل رهان هو الاستخدام a*a لساحات عدد صحيح.

Answer 3

إليك حل باستخدام صيغة Euclid's (حلقة الوصل).

دعونا نفعل بعض الرياضيات: بشكل عام ، سيكون لكل حل النموذج

a=k(x²-y²)
b=2kxy
c=k(x²+y²)

عندما يكون K و X و Y من أعداد صحيحة إيجابية ، Y <X و GCD (X ، Y) = 1 (سنتجاهل هذا الشرط ، مما سيؤدي إلى حلول إضافية. يمكن تجاهلها بعد ذلك)

الآن ، a+b+c = kx²-ky²+2kxy+kx²+ky² = 2kx²+2kxy = 2kx (x+y) = 1000

قسمة على 2: KX (x+y) = 500

الآن قمنا بتعيين s = x+y: kxs = 500

الآن نحن نبحث عن حلول KXS = 500 ، حيث K و X و S هي أعداد صحيحة و x < s < 2x. نظرًا لأن جميعهم يقسمون 500 ، يمكنهم فقط أخذ القيم 1 ، 2 ، 4 ، 5 ، 10 ، 20 ، 25 ، 50 ، 100 ، 125 ، 250 ، 500. بعض الرمز الكاذب للقيام بذلك من أجل n التعسفي ( تم باليد بسهولة لـ N = 1000)

If n is odd
  return "no solution"
else
  L = List of divisors of n/2
for x in L
  for s in L
    if x< s <2*x and n/2 is divisible by x*s
      y=s-x
      k=((n/2)/x)/s      
      add (k*(x*x-y*y),2*k*x*y,k*(x*x+y*y)) to list of solutions
sort the triples in the list of solutions
delete solutions appearing twice
return list of solutions

لا يزال بإمكانك تحسين هذا:

• لن يكون X أكبر من جذر N/2
• يمكن أن تبدأ الحلقة لـ S عند x وتوقف بعد تمرير 2x (إذا تم طلب القائمة)

بالنسبة إلى n = 1000 ، يتعين على البرنامج التحقق من ست قيم لـ x واعتمادًا على تفاصيل التنفيذ حتى قيمة واحدة لـ y. سيؤدي هذا إلى إنهاء الزر قبل تحريره.

Answer 4

كما ذكر أعلاه ، ^ هو bitwise xor ، وليس القوة.

يمكنك أيضًا إزالة الحلقة الثالثة ، وبدلاً من ذلك الاستخدامc = 1000-a-b; وتحسين هذا قليلا.

كود مزيف

for a in 1..1000
    for b in a+1..1000
        c=1000-a-b
        print a, b, c if a*a+b*b=c*c

Answer 5

هناك حل متسخ للغاية ولكنه سريع لهذه المشكلة. بالنظر إلى المعادلتين

A*A + B*B = C*C

A+B+C = 1000.

يمكنك استنتاج العلاقة التالية

a = (1000*1000-2000*b)/(2000-2b)

أو بعد تحوّلين للرياضيات البسيطة ، تحصل على:

A = 1000*(500 -B) / (1000 - ب)

منذ أن يكون رقم طبيعي. وبالتالي يمكنك:

for b in range(1, 500):
    if 1000*(500-b) % (1000-b) == 0:
        print b, 1000*(500-b) / (1000-b) 

حصلت على النتيجة 200 و 375.

حظا طيبا وفقك الله

Answer 6

#include <stdio.h>

int main() // main always returns int!
{
 int a, b, c;
 for (a = 0; a<=1000; a++)
 {
  for (b = a + 1; b<=1000; b++) // no point starting from 0, otherwise you'll just try the same solution more than once. The condition says a < b < c.
  {
   for (c = b + 1; c<=1000; c++) // same, this ensures a < b < c.
   {
    if (((a*a + b*b == c*c) && ((a+b+c) ==1000))) // ^ is the bitwise xor operator, use multiplication for squaring
     printf("a=%d, b=%d, c=%d",a,b,c);
   }
  }
 }
 return 0;
}

لم تختبر هذا ، ولكن يجب أن يضعك على المسار الصحيح.

Answer 7

من عند man pow:

POW(3)                                       Linux Programmer's Manual                                      POW(3)

NAME
       pow, powf, powl - power functions

SYNOPSIS
       #include <math.h>

       double pow(double x, double y);
       float powf(float x, float y);
       long double powl(long double x, long double y);

       Link with -lm.

   Feature Test Macro Requirements for glibc (see feature_test_macros(7)):

       powf(), powl(): _BSD_SOURCE || _SVID_SOURCE || _XOPEN_SOURCE >= 600 || _ISOC99_SOURCE; or cc -std=c99

DESCRIPTION
       The pow() function returns the value of x raised to the power of y.

RETURN VALUE
       On success, these functions return the value of x to the power of y.

       If  x  is  a  finite  value less than 0, and y is a finite non-integer, a domain error occurs, and a NaN is
       returned.

       If the result overflows, a range error occurs, and the functions return HUGE_VAL, HUGE_VALF, or  HUGE_VALL,

كما ترى، pow يستخدم حساب النقطة العائمة ، والذي من غير المرجح أن يمنحك النتيجة الدقيقة (على الرغم من أنه في هذه الحالة يجب أن تكون على ما يرام ، لأن الأعداد الصحيحة الصغيرة نسبيًا لها تمثيل دقيق ؛ لكن لا تعتمد على ذلك للحالات العامة) ... استخدام n*n لترفيه الأرقام في حساب عدد صحيح (أيضًا ، في وحدة المعالجة المركزية الحديثة ذات وحدات النقطة العائمة القوية ، يمكن أن تكون الإنتاجية أعلى في نقطة عائمة ، ولكن التحويل من عدد صحيح إلى نقطة عائمة له تكلفة عالية جدًا في دورات وحدة المعالجة المركزية ، لذلك إذا كنت "إذا كنت". إعادة التعامل مع الأعداد الصحيحة ، حاول التمسك بالحساب الصحيح).

بعض الرمز الكاذب لمساعدتك على تحسين خوارزميةك قليلاً:

for a from 1 to 998:
    for b from 1 to 999-a:
        c = 1000 - a - b
        if a*a + b*b == c*c:
             print a, b, c

Answer 8

في C ، يحسب المشغل ^ bitwise xor ، وليس القوة. يستخدم x*x في حين أن.

Answer 9

كما ذكر الآخرون ، تحتاج إلى فهم المشغل ^. كما ستنتج الخوارزمية إجابات مكافئة متعددة مع المعلمات A و B و C في أوامر مختلفة.

Answer 10

على الرغم من أن العديد من الأشخاص أشاروا إلى أن الكود الخاص بك سيعمل بشكل جيد بمجرد التبديل إلى استخدامه pow. إذا كنت مهتمًا بتعلم القليل من نظرية الرياضيات كما تنطبق على CS ، فإنني أوصي بمحاولة تنفيذ نسخة أكثر فعالية باستخدام "صيغة Euclid" لتوليد ثلاثية فيثاغوريان (حلقة الوصل).

Answer 11

أعلم أن هذا السؤال قديم جدًا ، وقد قام الجميع بنشر حلول مع 3 لحلقات ، وهو أمر غير مطلوب. حصلت على هذا في O (n) ، بواسطة **equating the formulas**; **a+b+c=1000 and a^2 + b^2 = c^2**

لذلك ، حلنا أكثر ؛

a+b = 1000-c

(a+b)^2 = (1000-c)^2

إذا حلنا أكثر نستنتج ل.

a = ((50000- (1000*b))/(1000-b)). نحن حلقة ل "B" ، ونجد "أ".

بمجرد أن يكون لدينا "A" و "B" ، نحصل على "C".

public long pythagorasTriplet(){
    long a = 0, b=0 , c=0;

    for(long divisor=1; divisor<1000; divisor++){
        if( ((500000-(1000*divisor))%(1000-divisor)) ==0){
            a = (500000 - (1000*divisor))/(1000-divisor);
            b = divisor;
            c = (long)Math.sqrt(a*a + b*b);
            System.out.println("a is " + a + " b is: " + b + " c is : " + c);
            break;
        }
    }
    return a*b*c;
}

Answer 12

تعطي طريقة Euclid للمحيط ليكون m (m+n) = p/2 حيث m> n والجانبين هي m^2+n^2 هي hypotenuse والساقين 2mn و m^2-n^2.thus m (m+n) = 500 يعطي بسرعة m = 20 و n = 5. الجوانب هي 200 و 375 و 425. استخدم إقليدس لحل جميع الأسئلة البدائية في بيتوريان.

Answer 13

لأن هناك معادلتان (a+b+c = 1000 && aˆ2 + bˆ2 = cˆ2) مع ثلاثة متغيرات ، يمكننا حلها في الوقت الخطي عن طريق مجرد حلق من خلال جميع القيم الممكنة لمتغير واحد ، ثم يمكننا حل المتغيرات الأخرى في وقت ثابت.

من الصيغة الأولى ، نحصل عليها b=1000-a-c, ، وإذا استبدلنا B في الصيغة الثانية بهذا ، نحصل على ذلك c^2 = aˆ2 + (1000-a-c)ˆ2, الذي يبسط إلى c=(aˆ2 + 500000 - 1000a)/(1000-a).

ثم نحلق من خلال جميع القيم الممكنة لـ A ، حل C و B مع الصيغ المذكورة أعلاه ، وإذا كانت الشروط راضية ، فقد وجدنا الثلاثي لدينا.

    int n = 1000;

    for (int a = 1; a < n; a++) {
        int c = (a*a + 500000 - 1000*a) / (1000 - a);
        int b = (1000 - a - c);

        if (b > a && c > b && (a * a + b * b) == c * c) {
            return a * b * c;
        }
    }

Answer 14

أعتقد أن أفضل نهج هنا هو:

int n = 1000;
unsigned long long b =0;
unsigned long long c =0;
for(int a =1;a<n/3;a++){
    b=((a*a)- (a-n)*(a-n)) /(2*(a-n));
    c=n-a-b;

    if(a*a+b*b==c*c)
        cout<<a<<' '<<b<<' '<<c<<endl;
 }

Explanation: يجب أن نشير إلى N وثابتة حتى لا نضطر إلى استخدام حلقتين. يمكننا أن نفعل ذلك بسببc=n-a-b و ب =(a^2-(a-n)^2)/(2(a-n))حصلت على هذه الصيغ عن طريق حل نظام المعادلات:

a+b+c=n, a^2+b^2=c^2

Answer 15

func maxProd(sum:Int)->Int{
    var prod = 0
    //    var b = 0
    var c = 0
    let bMin:Int = (sum/4)+1 //b can not be less than sum/4+1 as (a+b) must be greater than c as there will be no triangle if this condition is false and any pythagorus numbers can be represented by a triangle.
    for b in bMin..<sum/2 {
        for a in ((sum/2) - b + 1)..<sum/3{ //as (a+b)>c for a valid triangle
            c = sum - a - b
            let csquare = Int(pow(Double(a), 2) + pow(Double(b), 2))
            if(c*c == csquare){
                let newProd = a*b*c
                if(newProd > prod){
                    prod = newProd
                    print(a,b,c)
                }
            }
        }
    }
    //
    return prod
}

الإجابات أعلاه جيدة بما يكفي ولكنها مفقودة واحدة من المعلومات المهمة A + B> C. ;)

سيتم توفير مزيد من التفاصيل لأولئك الذين يسألون.

Answer 16

for a in range(1,334):
    for b in range(500, a, -1):
        if a + b < 500:
            break
        c = 1000 - a - b
        if a**2 + b**2 == c**2:
            print(a,b,c)

مزيد من التحسين من إجابة أوليغ. لا يمكن أن يكون جانب واحد أكبر من مجموع الاثنين الآخرين. لذلك لا يمكن أن يكون A + B أقل من 500.