30

ピタゴラスのトリプレットは、a < b < c の 3 つの自然数のセットであり、a 2 + b 2 = c 2

たとえば、3 2 + 4 2 = 9 + 16 = 25 = 5 2です。

a + b + c = 1000 であるピタゴラスの 3 連符が 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();    
}
4

16 に答える 16

32 
#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がピタゴラストリプレットである
    場合、b、a（b> = a）およびc-これも解であるため、1つのケースのみを検索できます。
  • c = 1000 --a --b; これは問題の条件の1つです（可能なすべての「c」をスキャンする必要はありません。計算するだけです）
于 2010-05-12T12:32:09.160 に答える
31

残念^ながら、あなたが C で行うと思っていることはしません。あなたの最善の策はa*a、整数平方に使用することです。

于 2010-05-12T10:26:20.920 に答える
18

これが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つの値までチェックする必要があります。これは、ボタンを離す前に終了します。

于 2010-05-14T14:49:06.193 に答える
15

前述のように、^ は累乗ではなくビット単位の xor です。

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
于 2010-05-12T10:28:21.417 に答える
13

この問題には、非常に汚いが迅速な解決策があります。与えられた 2 つの方程式

a*a + b*b = c*c

a+b+c = 1000。

次の関係を導き出すことができます

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

または、単純な数学変換を 2 回行うと、次のようになります。

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

a は自然数でなければならないからです。したがって、次のことができます。

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

結果は 200 と 375 でした。

幸運を

于 2010-08-08T21:33:52.327 に答える
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;
}

これをテストしていませんが、正しい軌道に乗るはずです。

于 2010-05-12T10:29:15.360 に答える
6

から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整数演算で数値を 2 乗するために使用します (また、強力な浮動小数点ユニットを備えた最新の 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
于 2010-05-12T10:40:09.800 に答える
5

C では、^ 演算子は累乗ではなく、ビットごとの xor を計算します。x*x代わりに使用してください。

于 2010-05-12T10:25:22.093 に答える
2

多くの人が、使用に切り替えるとコードが正常に機能することを指摘していますpow。CSに適用される数学理論を少し学ぶことに興味がある場合は、ピタゴラスのトリプルを生成するための「ユークリッドの公式」を使用して、より効率的なバージョンを実装することをお勧めします（リンク）。

于 2010-05-14T05:51:37.567 に答える
2

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

于 2010-05-12T10:29:45.110 に答える
1

ユークリッド法では、周囲が m(m+n)= p/2 になるように指定されます。ここで、m> n で辺は m^2+n^2 は斜辺で、脚は 2mn で m^2-n^2 です。 m(m+n)=500 はすぐに m= 20 と n=5 になります。側面は 200、375、および 425 です。Euclid を使用して、すべての pythorea 原始問題を解決します。

于 2014-04-13T18:35:14.240 に答える
1

3 つの変数を持つ2 つの方程式 ( a+b+c = 1000&& aˆ2 + bˆ2 = cˆ2) があるため、1 つの変数のすべての可能な値をループするだけで線形時間で解くことができ、その後、他の 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;
        }
    }
于 2017-06-01T12:02:58.253 に答える