a + b + c = 1000となるピタゴラスの三重項を求めます

Question

ピタゴラスの三重項は、3つの自然数のセット、a <b <c、それのために、² +b² = c²

たとえば、3² + 4² = 9 + 16 = 25 = 5².

a + b + c = 1000 となるピタゴラスの三重項が 1 つだけ存在します。製品 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;
}

説明：

• b = a;
  a、b (a <= b)、c がピタゴラスの 3 つ組の場合、
  次に、b、a (b >= a)、および c - これも解なので、1 つのケースのみを検索できます。
• c = 1000 - a - b;これは問題の条件の 1 つです (考えられるすべての 'c' をスキャンする必要はありません:計算するだけです）

Answer 2

私^は、あなたがそれはあなたの最善の策は、整数の正方形のためa*aを使用することで、Cでないと思う何をしません怖います。

Answer 3

これは Euclid の公式を使用した解決策です (リンク).

いくつか計算してみましょう:一般に、すべてのソリューションは次の形式になります。

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 の 6 つの値をチェックし、実装の詳細に応じて y の最大 1 つの値をチェックする必要があります。ボタンを放す前にこれは終了します。

Answer 4

としては、上述した、^ビット単位の排他的論理和ではなく、電力である。

また、第3のループを削除し、代わりに使用することができます 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

この問題に非常に汚いが、迅速な解決策があります。二つの式

を考えます

* + B * B = C * C

A + B + C = 1000。

あなたは次の関係

を推測することができます

A =（1000 * 1000-2000 * B）/（2000-2b）

または2つの単純な数学変換した後、あなたが得る：

A = 1000 *（500-B）/（1,000 - B）

自然数でなければならないからです。したがって、あなたができます：

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は比較的小さな整数が正確な表現を持っているとして、この場合には、[OK]をする必要がありますが、（あなたに正確な結果を与えることはほとんどありませんこれは、浮動小数点演算を使用している。しかし、一般的なため、そのに依存しませんケース）...整数演算の数字を二乗に使用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

Answer 8

はC ^演算子を計算ビット単位の排他的論理和ではなく、電源。使用x*x代わります。

Answer 9

他の人としては、あなたが^演算子を理解する必要が言及しています。 また、あなたのアルゴリズムでは、パラメータを使用して異なる順序で、a、b及びcを複数の同等の答えを生成します。

Answer 10

多くの人々はあなたがpowの使用に切り替える一度あなたのコードは罰金を動作することを指摘してきたようにしながら。それはCSに適用される数学の理論のビットを学ぶことで、あなたの興味があるならば、私は（ピタゴラスのトリプルを生成するための「ユークリッドの公式」を使用して、よりエフィエントバージョンを実装しようとして推薦する<のhref = "http://en.wikipedia.org /ウィキ/ Pythagorean_triple＃Generating_a_triple」のrel = "nofollowをnoreferrer">リンクの）ます。

Answer 11

私はこの質問はかなり古いです知っている、と誰もが必要とされていないループのため3で解決策を掲載しています。私はこれは**equating the formulas**; **a+b+c=1000 and a^2 + b^2 = c^2**

により、O（n）の中で解決しました

だから、さらに我々が得る解決;

a+b = 1000-c

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

私たちは、さらに解決した場合の私たちを推論のそれをします。

  

A =（（50000-（1,000 * 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

はユークリッド方法は（M + N）= P / 2ここで、m> nおよび側面であるM ^ 2 + N ^ 2斜辺であり、足が2MNおよびm ^ 2-nは^ mで周囲を与えます2.thus（M + N）= 500は、迅速に、M = 20、N = 5が得られます。側面はすべてpythorean原始的な質問を解決するために200、375および425を使用するユークリッドされます。

Answer 13

二つの式が（a+b+c = 1000 && aˆ2 + bˆ2 = cˆ2）は、3つの変数であるように、

、我々はただ一つの変数のすべての可能な値をループすることにより線形時間でそれを解決することができ、その後、我々は、一定時間内に他の2つの変数を解決することができます。

最初の式から、我々はb=1000-a-cを取得し、我々はこれで2回目の式にBを交換した場合、我々はc^2 = aˆ2 + (1000-a-c)ˆ2に簡素化c=(aˆ2 + 500000 - 1000a)/(1000-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;
 }

説明： 我々は二つのループを使用する必要はありませんので、我々はNと定数を指すものとします。 我々はので、それを行うことができます c=n-a-b 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
}

上記の答えは十分に良いですが、情報の重要な一枚の + 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)

オレグの答えからのさらなる最適化。 一つの側面は、他の2つの合計よりも大きくすることはできません。 + bが500よりも小さくすることはできませんので、