2017年01月15日
TypeScriptでProject Euler #3 「最大の素因数」
第3問目は素因数分解の問題です。
13195 の素因数は 5, 7, 13, 29 である.
600851475143 の素因数のうち最大のものを求めよ.
ポラード・ロー素因数分解法
せっかくなので、少し前にC#で書いた「ポラード・ロー素因数分解法」をTypeScriptに移植しようと思います。
事前に、最大公約数をもとめるGcd関数と、素数判定の関数 IsPrime を定義します。この２つのメソッドは、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」 を見てください。
2017年01月12日
TypeScriptでProject Euler #2 「偶数のフィボナッチ数」
TypeScriptでProject Eulerに挑戦する第２問目です。
第1回目から随分と間が空いてしまいましたが、気にせずマイペースで進めます。
問題
フィボナッチ数列の項は前の2つの項の和である. 最初の2項を 1, 2 とすれば, 最初の10項は以下の通りである.
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
数列の項の値が400万以下の, 偶数値の項の総和を求めよ.
フィボナッチ数列を求める関数を定義
まずは、以下のようなクラスを定義して、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」 を見てください。
