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

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ループでできるか?
より効率的な方法はあるか?
思考過程とコードの解説を詳しく解説しなさい。

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

m.ts10806

2022/09/19 22:31

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

退会済みユーザー

2022/09/19 22:41

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

m.ts10806

2022/09/19 23:30

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

episteme

2022/09/20 02:18

> 3重forループでできるか? ２重for-loop でよかろう。

fana

2022/09/20 04:46

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

xebme

2022/09/20 09:08

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

tmp

2022/09/20 09:19 編集

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

退会済みユーザー

2022/09/20 09:25

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

行動規範の内容に同意します

回答3件

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

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

投稿2022/09/19 21:57

y_waiwai

総合スコア88163

退会済みユーザー

2022/09/19 21:58

ストーカーやめて

行動規範の内容に同意します

ベストアンサー

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

C++
1#include <iostream>
2#include <chrono>
3
4// 条件を満たせば true
5bool is_ok(int a, int b, int c) {
6  if ( a < b && b < c ) {
7    if ( a + b + c == 1000 ) {
8      if ( a*a + b*b == c*c ) {
9        return true;
10      }
11    }
12  }
13  return false;
14}
15  
16int main() {
17  auto start = std::chrono::high_resolution_clock::now();
18  for ( int c = 0; c < 1000; ++c ) {
19    for ( int a = 0; a < c; ++a ) {
20      int b = 1000 - c - a; // a+b+c = 1000 だから
21      if ( is_ok(a,b,c) ) {
22        std::cout << " a = " << a
23                  << " b = " << b
24                  << " c = " << c
25                  << " : abc = " << a*b*c << std::endl;
26        auto stop = std::chrono::high_resolution_clock::now();
27        std::cout << std::chrono::duration_cast<std::chrono::microseconds>(stop - start).count() << " [us]\n";
28      }
29    }
30  }
31}