[至急] Project Euler: #9 Special Pythagorean triplet コード、入力、出力、できれば解説もお願いします。アルゴリズムとデータ構造

Question

https://projecteuler.net/problem=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.

結論からお伝えすると、答えを教えてください。C,C++,javaのどれかで。
コードと入力と出力とできれば解説もお願いします。
プログラミング未経験でも簡単に理解できるように説明してほしい。
今回は、2通りの異なる方法で解きなさい。
ただし、どうしても片方の解法しか分からない場合はその解法を投稿してもよい。

[1] 数学的に解く
解を埋め込んだコードでよい。
式変形や導出の過程を詳しく解説しなさい。

[2] アルゴリズムで解く
全探索だとどれくらいの時間で計算できるか?
3重forループでできるか?
より効率的な方法はあるか?
思考過程とコードの解説を詳しく解説しなさい。

私の考え
難しい問題です。

Comments

[m.ts10806]

丸投げを良しとしないteratailでもらうのは無理なので、teratail以外でどうぞ。

[退会済みユーザー]

同じ丸投げでも「どんな風に考えたか」とかを書くだけでも相当違いますよ

[m.ts10806]

では、そのように対応してください。

[episteme]

> 3重forループでできるか?

２重for-loop でよかろう。

[fana]

ピタゴラス数を列挙するコードを書く．列挙中に a+b+c が 1000 の約数になるやつが見つかったらそこで終了．

…みたいな？

[xebme]

(200,375,425)は規約にすると(8,15,17)

[tmp]

至急は、カンニングのお手伝いになる場合があるから、特に丸投げは気を付けないと。

[退会済みユーザー]

@episteme b = 1000 - c - aに気づかなかった
@tmp これは試験問題じゃないので、大丈夫

Answer 1

残念ながら、ここではコードの作成依頼は受け付けていません

まずはあなたなりにコードを書いてみましょう。その上でわからないことを聞いていただければお答えできるかと思います。

Comments

[退会済みユーザー]

ストーカーやめて

Answer 2

僕んちのPCで750μ秒、時間切れにはならなそうです。

#include <iostream>
#include <chrono>

// 条件を満たせば true
bool is_ok(int a, int b, int c) {
  if ( a < b && b < c ) {
    if ( a + b + c == 1000 ) {
      if ( a*a + b*b == c*c ) {
        return true;
      }
    }
  }
  return false;
}
  
int main() {
  auto start = std::chrono::high_resolution_clock::now();
  for ( int c = 0; c < 1000; ++c ) {
    for ( int a = 0; a < c; ++a ) {
      int b = 1000 - c - a; // a+b+c = 1000 だから
      if ( is_ok(a,b,c) ) {
        std::cout << " a = " << a
                  << " b = " << b
                  << " c = " << c
                  << " : abc = " << a*b*c << std::endl;
        auto stop = std::chrono::high_resolution_clock::now();
        std::cout << std::chrono::duration_cast<std::chrono::microseconds>(stop - start).count() << " [us]\n";
      }
    }
  }
}

Comments

[xebme]

if ( a + b + c == 1000 ) {
これは必要ですか？

[退会済みユーザー]

b = 1000 - c - aに気づかなかった

[episteme]

> if ( a + b + c == 1000 ) {
> これは必要ですか？

もちろん不要です。
どんな呼ばれ方してもいいように、満たすべき条件は全部書いておきました。

Answer 3

TIME LIMIT EXCEEDED

になると想定される。

Comments

[episteme]

なぜに?

[退会済みユーザー]

b = 1000 - c - aに気づかなかった