a + b + c = 1000인 피타고라스 삼중항 찾기

a + b + c = 1000인 피타고라스 삼중항 찾기

피타고라스 삼중항은 3개의 자연수의 집합으로, a < b < c 에 대하여, 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();    
}

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

설명:

• b a;
  a,=약 a, b (a = b)가 피타고라스 삼중항,
  a( =a) 및 c -음 b, a (b = a)및 c -할 수 .
• c = 1000 - a - b; 문제의 조건 중 하나입니다. (가능한 모든 'c'를 스캔할 필요는 없습니다: 계산만 하면 됩니다.)

^당신이 생각하는 것처럼 C에서 하지 않습니다.당신의 최선의 선택은 다음을 사용하는 것입니다.a*a정수 제곱의 경우.

유클리드의 공식(link)을 이용한 해결 방법은 다음과 같습니다.

수학을 좀 해봅시다: 일반적으로, 모든 풀이는 형태를 가질 것입니다.

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²=2kx²+2kxy =2kx(x+y) = 1000

2로 나누기: kx(x+y) = 500

이제 s=x+y: kxs = 500으로 설정합니다.

k, k, x, 는 k, x, s는 인 kxs500 의의 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의 경우 6개의 값을 확인해야 하며 구현의 세부 정보에 따라 y의 경우 1개의 값까지 확인해야 합니다.버튼을 해제하기 전에 종료됩니다.

위에서 언급한 바와 같이 ^는 검정력이 아닌 비트 와이즈 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

이 문제에 대해 꽤 더럽지만 빠른 해결책이 있습니다.두 개의 방정식이 주어졌을 때

a*a + b*b = c*c

a+b+c = 1000.

다음 관계를 추론할 수 있습니다.

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

두 번의 간단한 수학적 변환을 거치면 다음과 같은 결과를 얻을 수 있습니다.

a = 1000*(500-b) / (1000-b)

가 자연수여야 하기 때문에따라서 다음을 수행할 수 있습니다.

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

200과 375의 결과를 얻었습니다.

행운을 빌어요

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

테스트해 본 적은 없지만 올바른 방향으로 갈 수 있을 겁니다.

: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정수 산술에서 숫자를 제곱합니다(또한 강력한 부동 소수점 장치가 있는 현대 CPU에서는 부동 소수점에서 처리량이 훨씬 더 높을 수 있지만 정수에서 부동 소수점으로 변환하는 것은 CPU 사이클 수에 있어 비용이 매우 높으므로 정수를 다룰 때는 정수 산술을 고수하십시오).

알고리즘을 최적화하는 데 도움이 되는 의사코드:

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

C에서 ^ 연산자는 거듭제곱이 아닌 비트 와이즈 xor를 계산합니다. 사용합니다.x*x대신.

저는 이 질문이 꽤 오래된 것으로 알고 있으며, 모두가 루프용 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"를 찾습니다.

일단 "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;
}

다른 사람들이 언급한 것처럼 ^ 연산자를 이해해야 합니다.또한 알고리즘은 모수 a, b, c를 다른 순서로 사용하여 여러 개의 동등한 답변을 생성합니다.

이 당신이 했습니다를 사용하는 으로 전환하면 가 잘 작동할 했습니다.pow. CS에 적용되는 수학 이론을 조금이라도 배우고 싶다면 피타고라스 삼중항(링크) 생성을 위해 '유클리드 공식'을 활용해 좀 더 효율적인 버전을 구현해보는 것을 추천합니다.

유클리드 방법은 둘레를 m(m+n)= p/2로 하고, 여기서 m> n이고, 변은 m^2+n^2이고, 다리는 2mn이고 m^2-n^2입니다. thus m(m+n)=500은 m=20이고 n=5입니다.측면은 200, 375, 425 입니다.유클리드를 이용해 파이토리아의 원시적인 질문을 모두 풀어보세요.

두 개의 방정식이 있으므로 (a+b+c = 1000&&aˆ2 + bˆ2 = cˆ2) 세 개의 변수로 한 변수의 가능한 모든 값을 반복하여 선형 시간으로 해결하고 나머지 두 개의 변수를 일정한 시간으로 해결할 수 있습니다.

첫 번째 공식으로부터 우리는b=1000-a-c, 그리고 2차 공식에서 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;
        }
    }

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보다 작을 수 없습니다.

여기서 가장 좋은 방법은 다음과 같습니다.

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

설명:N과 A 상수를 참조하여 두 개의 루프를 사용할 필요가 없습니다.우리가 할 수 있는 것은.c=n-a-b 고 =(a^2-(a-n)^2)/(2(a-n))방정식 체계를 풀어서 다음 공식을 얻었습니다.

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

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 ;)의 중요한 정보가 하나 빠져 있습니다.

문의하시는 분들께 더 자세한 내용이 안내될 예정입니다.

파이썬으로

def findPythagorean1000():
    for c in range(1001):
        for b in range(1,c):
            for a in range(1,b):
                if (a+b+c==1000):
                    if(pow(a,2)+pow(b,2)) ==pow(c,2):
                        print(a,b,c)
                        print(a*b*c)
                        return

findPythagorean1000()

언급URL : https://stackoverflow.com/questions/2817848/find-pythagorean-triplet-for-which-a-b-c-1000