2017年04月18日

TypeScriptでProject Euler #21 「友愛数」

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

昨年の12月からTypeScriptでProjectEulerを解く記事を書き続けてきましたが、 当初の目標の10問をクリアし、その倍の問題を解いたので、そろそろ、このProjectEulerの挑戦も終わりにしたいと思います。 ということで、これが最後の問題です。

問題

d(n) を n の真の約数の和と定義する. (真の約数とは n 以外の約数のことである. ) もし, d(a) = b かつ d(b) = a (a ≠ b のとき) を満たすとき, a と b は友愛数(親和数)であるという.

例えば, 220 の約数は 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 なので d(220) = 284 である. また, 284 の約数は 1, 2, 4, 71, 142 なので d(284) = 220 である.

それでは10000未満の友愛数の和を求めよ.

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


約数を求めるDivisorsクラスを定義する

約数を求めるメソッドは、Divisorsクラスを作成し、その静的メソッドとして作成。 この手のメソッド書くときに迷うのが、TypeScriptの場合は、クラスではなく、単独の関数でも良いのかなということ。

名前空間に適切な名前を付ければ、そのほうが良いのかもしれないなーとは思いつつ、 C#erの僕は、クラスにすることを選択。

export class Divisors {
    // 約数を求める (自分自身は含めない)
    public static get(num: number): number[] {
        let ary = [];
        let m = Math.floor(num / 2);
        for (let n = 1; n <= m; n++) {
            if (num % n === 0) {
                ary.push(n);
            }
        }
        return ary;
    }
}


友愛数を求める

このメソッドができれば、友愛数を求めるのはそれほど難しくありませんね。

import * as Utils from './utils';
import { Divisors } from './math/divisors';


class Solver {
    exec(num: number): number {
        return this.amicableNumbers(num).map(x => x[0] + x[1]).reduce((x, y) => x + y,0);
    }

    // n 未満の友愛数のペアを列挙する
    private amicableNumbers(n: number): [number,number][] {
        var amicables = [];
        for (let a = 1; a < n; a++) {
            let temp = Divisors.get(a);
            let d = temp.reduce((x, y) => x + y,0);
            if (a >= d)
                continue;
            let y = Divisors.get(d).reduce((x, y) => x + y,0);
            if (a == y)
                amicables.push([a, d]);
        }
        return amicables;
    }
}


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

Application.run();
[number,number]

というのは、数値の要素を2つ持つオブジェクトという意味。 TypeScriptだと、これをタプルと言うらしいです。 まあ、実態は配列だけどね。

amicableNumbers メソッドでは、このタプルの配列を返しています。

なお、reduceの第2引数に 0 を与えていますが、これがないと例外が発生します。 JavaScriptのreduceは、第2引数が無いと、要素の数が 0 の時に例外が発生するんですね。 この第2引数は、reduceをする際の初期値を与えます。

最初は、第2引数与えななったので、例外が発生して、あれっなんで? ってちょっと悩んでしまいました。 よくよく考えると、「要素数ゼロの時は、何返したらいいかわからないよね、だから例外出すよ!」 ということで、至極当たり前の仕様ですね。

実行時間は、400ミリ秒でした。約数求めるところが効率悪いですから、まあ想定の範囲内です。


高速化する

Divisors.getメソッドをちょっと改良してみました。

export class Divisors {
    // 約数を求める (自分自身は含めない)
    public static get(num: number): number[] {
        let ary = [];
        if (num == 1)
            return ary;
        ary.push(1);
        let m = Math.floor(Math.sqrt(num));
        if (m * m === num) {
            ary.push(m);
            m--;
        }
        for (let i = 2; i <= m; i++) {
            if (num % i === 0) {
                ary.push(i);
                ary.push(Math.floor(num / i));
            }
        }
        return ary;
    }

}

かなりごちゃごちゃしたコードになりましたが、計算量が格段に減ってます。 これで、39ミリ秒まで速くすることができました。10倍の高速化です。

素因数分解から求めるという方法もあるのかもしれませんが、これで十分でしょう。


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



 

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

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