2017年02月21日

TypeScriptでProject Euler #6 「二乗和の差」

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

問題

最初の10個の自然数について, その二乗の和は,

12 + 22 + ... + 102 = 385

最初の10個の自然数について, その和の二乗は,

(1 + 2 + ... + 10)2 = 3025

これらの数の差は 3025 - 385 = 2640 となる.

同様にして, 最初の100個の自然数について二乗の和と和の二乗の差を求めよ.

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

TypeScriptのコード

3つの方法で書いてみました。

オーソドックスなTypeScript のコード

import * as Utils from './utils';
import Stopwatch = Utils.Stopwatch;

class Solver {
    exec(num: number): number {
        let a = 0;
        let b = 0;
        for (let i = 1; i <= num; i++) {
            a += i;
            b += (i * i);
        }
        return a * a - b;
    }
}

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

Application.run();

reduceを使ったコード

      exec(num: number): number {
          let a = Utils.makeSeq(1, num).reduce((x, y) => x + y);
          let b = Utils.makeSeq(1, num).reduce((x, y) => x + y * y);
          return a * a - b;
      }

makeSeq関数(TypeScriptでProject Euler #5「最小の倍数」で作成)の第2引数は、countではなく、最後の値を指定します。

変数bの値を求める際は、配列の最初が 0 であることを利用しています。

公式を使ったコード

      exec(num: number): number {
          let a = (num * (num + 1)) / 2;
          let b = (num * (num + 1) * (2 * num + 1)) / 6;
          return a * a - b;
      }

12 + 22 + 32 + 42... + n2 の公式は、ネットで検索すると解説しているページがたくさんヒットします。

なるほどなーと感心します。

ただ、公式使っても、最初の100個となるとたいして速度の差がでないです。


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



 

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

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