2017年03月01日

TypeScriptでProject Euler #9 「特別なピタゴラス数」

   このエントリーをはてなブックマークに追加 Clip to Evernote

問題

ピタゴラス数(ピタゴラスの定理を満たす自然数)とは a < b < c で以下の式を満たす数の組である.

a2 + b2 = c2

例えば, 32 + 42 = 9 + 16 = 25 = 52 である.

a + b + c = 1000 となるピタゴラスの三つ組が一つだけ存在する.
これらの積 abc を計算しなさい.

   Project Euler日本語翻訳サイト から引用

考えかた

a + b + c = 1000となる a,b,c を見つけ、 それがピタゴラスの定理を満たしているかを調べればいいだけですね。

ということで、力技ですが、aとbがわかればCはわかるので、aとbについては、総当たりで調べています。

しいて工夫した点を挙げるとすれば、 if (c < b) という判断を入れているところでしょうか。 これで、速度がかなり速くなりました。

TypeScriptのコード

import * as Utils from './utils';

class Solver {
    exec(sum: number): number {
        for (let a = 1; a < sum; a++) {
            for (let b = a + 1; b < sum - a; b++) {
                let c = sum - a - b;
                if (c < b)
                    break;
                if (a * a + b * b === c * c) {
                    return a * b * c;
                }
            }
        }
        return 0;
    }
}

class Application {
    static run(): void {
        let sw = Utils.Stopwatch.startNew();
        try {
            let p = new Solver();
            let n = p.exec(1000);
            console.log(n);
        } finally {
            sw.stop();
            console.log(sw.toString());
        }
    }
}

Application.run();

今回の問題に関しては、TypeScriptの言語的には特筆すべき点はないかなー。

僕のマシンだと 21ミリ秒で求めることができましたから、これで十分と判断します。

これまでやって気がついたのですが、どうもnode.jsの問題なのか、VSCodeのデバッグの問題なのか、僕のマシンだとどんなコードでも、20ミリ秒を下回ることがないみたいです。


※Stopwatchクラスについては、「TypeScriptでProject Euler #0」 を見てください。



 

この記事へのトラックバックURL

http://trackback.blogsys.jp/livedoor/gushwell/52486188