2017年01月15日

TypeScriptでProject Euler #3 「最大の素因数」

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

第3問目は素因数分解の問題です。

13195 の素因数は 5, 7, 13, 29 である.

600851475143 の素因数のうち最大のものを求めよ.

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


ポラード・ロー素因数分解法

せっかくなので、少し前にC#で書いた「ポラード・ロー素因数分解法」をTypeScriptに移植しようと思います。

事前に、最大公約数をもとめるGcd関数と、素数判定の関数 IsPrime を定義します。この2つのメソッドは、Utilsクラスに入れ、前回と同様、mathフォルダに保存します。ファイル名は、mathUtils.tsです。

export class Utils {
    static gcd(a: number, b: number): number {
        if (a < b)
            return this.gcd(b, a);  // 引数を入替えて自分を呼び出す
        if (b === 0)
            return a;
        let d = 0;
        do {
            d = a % b;
            a = b;
            b = d;
        } while (d !== 0);
        return a;
    }

    static isPrime(num: number): boolean {
        let boundary = Math.floor(Math.sqrt(num));
        if (num === 1)
            return false;
        if (num === 2)
            return true;
        for (let i = 2; i <= boundary; ++i) {
            if (num % i === 0)
                return false;
        }
        return true;
    }
}

これを使い、「ポラード・ロー素因数分解法」を使った素因数分解クラスを定義します。C#のコードをTypeScriptに移植しただけなので、それほど苦労なく書けました。

import { Utils } from './mathUtils';

export class PrimeFactor {
    public *enumerate(n: number): IterableIterator<number> {
        while (n > 1) {
            let factor = this.getFactor(n);
            yield factor;
            n = n / factor;
        }
    }

    private getFactor(n: number, seed: number = 1): number {
        if (n % 2 === 0)
            return 2;
        if (Utils.isPrime(n))
            return n;
        let x = 2;
        let y = 2;
        let d = 1;
        let count = 0;
        while (d === 1) {
            count++;
            x = this.f(x, n, seed);
            y = this.f(this.f(y, n, seed), n, seed);
            d = Utils.gcd(Math.abs(x - y), n);
        }
        if (d === n)
            // 見つからなかった、乱数発生のシードを変えて再挑戦。
            return this.getFactor(n, seed + 1);
        // 素数でない可能性もあるので、再度呼び出す
        return this.getFactor(d);
    }

    private seeds: number[] = [3, 5, 7, 11, 13, 17];
    private f(x: number, n: number, seed: number): number {
        return (this.seeds[seed % 6] * x + seed) % n;
    }
}

このクラスを PrimeFactor.ts としてmathフォルダに保存します。

getFactorメソッドの引数には、省略時の値を指定しました。これはC#と同じですね。

TypeScript書いていて、いつも間違えるのは、比較演算子 === を == と書いてしまうこと。慣れるしかないですね。


最大の素因数を求める

さて、素因数分解はできましたので、これで問題を解くことができます。最大の素因数を求めればいいんですね。

ところで、「ポラード・ロー素因数分解法」って因数を小さい順に列挙してくれるのかな? たぶん小さい順位列挙してくれると思います。ということで最後の素因数が最大の素因数ということになります。LINQ使えれば、Lastメソッドで一発なんですがね。

しかたない、for文で回すことにしましょう。もっと賢いやり方があるような気もしますが...

import * as Utils from './utils';
import Stopwatch = Utils.Stopwatch;
import { PrimeFactor } from './math/PrimeFactor';

class Solver {
    exec(num: number): number {
        let pf = new PrimeFactor();
        let last;
        for (let n of pf.enumerate(num)) {
            last = n;
        }
        return last;
    }
}

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

Application.run();

これで、完成です。 正しく動いているようです。

ところで、C#に慣れていると、ついつい大文字で始まるファイル名にしたくなりますが。 TypeScriptの場合、ファイル名は小文字で始めるのが慣習なのかな?
 


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

  

Posted by gushwell at 22:00Comments(0)TrackBack(0)

2017年01月12日

TypeScriptでProject Euler #2 「偶数のフィボナッチ数」

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

TypeScriptでProject Eulerに挑戦する第2問目です。
第1回目から随分と間が空いてしまいましたが、気にせずマイペースで進めます。 

問題

フィボナッチ数列の項は前の2つの項の和である. 最初の2項を 1, 2 とすれば, 最初の10項は以下の通りである.

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

数列の項の値が400万以下の, 偶数値の項の総和を求めよ.

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

フィボナッチ数列を求める関数を定義

まずは、以下のようなクラスを定義して、fibonacci.ts として保存。mathフォルダを作成し、そこに保存します。

export class Fibonacci {
    static enumerate(first: number, second: number, callback: (n: number) => boolean): void {
        if (callback(first) === false)
            return;
        if (callback(second) === false)
            return;
        while (true) {
            let fibo = first + second;
            first = second;
            second = fibo;
            if (callback(fibo) === false)
                return;
        }
    }
}

配列に入れて返すことも考えたけど、今回はパス。 yield 構文が使えるみたいだけど、まだよくわかっていないので、コールバック関数を使うことにします。

コールバック関数の引数として、求めたフィボナッチ数が渡ります。 コールバック関数では、戻り値として true を返せば列挙を継続し、falseを返せば列挙を終了します。

こうすれば、フィボナッチ数列を求めるロジックと、問題特有の条件部の記述をきれいに分けることができます。

完成させる

Fibonacci.tsは、mathフォルダにあるので、そこを指すようにしてimpoortします。

つぎのようにすると、exportされたFibonacciクラスがその名前のまま利用できます。

import { Fibonacci } from './math/Fibonacci';

Fibonacciクラスを使って、solveメソッドを以下のように書きます。 コールバック関数の中で、偶数のフィボナッチ数だけを加算するようにしています。

import * as Utils from './utils';
import Stopwatch = Utils.Stopwatch;
import { Fibonacci } from './math/Fibonacci';

class Solver {
    public exec(maxnum: number): number {
        let sum = 0;
        Fibonacci.enumerate(1, 2, (n) => {
            if (n >= maxnum)
                return false;
            if (n % 2 === 0)
                sum += n;
            return true;
        });
        return sum;
    }
}

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

Application.run();

ファイルを小分けにすると、いちいち、import 書かないといけないのが面倒ですね。 なにか良い方法がないのかなー。

とりあえず、実行して動くことが確認できました。
 

やっぱり yield使いたい

でもやっぱり yield使いたいです。ということで、yield使って書き直してみました。 さっきと、メソッド名変えてます。

export class Fibonacci {
    static * generate(first: number, second: number): IterableIterator<number> { 
        yield first; 
        yield second;
        while (true) {
            let fibo = first + second;
            first = second;
            second = fibo;
            yield fibo;
        }
    }
}

まだ良くわかってないけど、メソッド名の前に * を付けないといけないみたいです。戻り値を IterableIterator<number> にしてるんだから、それだけでいいんじゃね、という気がするけど、まあそういう文法なので従うしかないです。TypeScriptでは、この * の付いているメソッド/関数を Generatorと呼ぶらしいです。

Fibonacci.generateを呼び出す側の ProjectEuler.ts は以下のようになります。
 

import * as Utils from './utils';
const Stopwatch = Utils.Stopwatch;
import { Fibonacci } from './math/Fibonacci';

class Solver {
    public exec(maxnum: number): number {
        let sum = 0;
        for (let n of Fibonacci.generate(1, 2)) {
            if (n >= maxnum)
                break;
            if (n % 2 === 0)
                sum += n;
        }
        return sum;
    }
}

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

Application.run();


for 文が使えるので、随分と読みやすくなったと思います。 やっぱり、今どきの言語は、yield使えないとね。

でも、for..in と for..of で動きが違うってどうなの? 間違いやすいですね。 英語圏の人は、inとofのニュアンスから違いを類推できるのかな?

 

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

  
Posted by gushwell at 22:10Comments(0)TrackBack(0)