2017年03月29日

TypeScriptでProject Euler #16 「べき乗の数字和」

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

問題

215 = 32768 であり, 各位の数字の和は 3 + 2 + 7 + 6 + 8 = 26 となる.

同様にして, 21000 の各位の数字の和を求めよ.

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


簡易BigIntクラスを書く

C#ならば、BigIntegerを使って簡単に実装できますが、BigInteger がないTypeScriptだとそういわけにもいきません。
しかたないので、2倍するTwiceメソッドだけを実装した桁数無制限のBigIntクラスを作成しました。

このProjectEulerの連載をこのまま続けていくと、加減乗除できる BigIntクラスが必要になりそうですが、まあ、そこまで続ける予定はないので、この方針でいきます。

// twiceだけを行うBigIntクラス

const Fig: number = 1000000000000000;
const Format: string = "00000000000000";
const SliceNum: number = -15;

export class BigInt {

    private list: number[] = [];

    constructor(n: number) {
        this.list.push(n);
    }

    private create(src: number[]): BigInt {
        var obj = new BigInt(0);
        obj.list = src;
        return obj;
    }

    public twice() {
        var ans: number[] = [];
        var carry: number = 0;
        for (var n of this.list) {
            var a: number = n + n + carry;
            carry = Math.floor(a / Fig);
            ans.push(a % Fig);
        }
        if (carry > 0)
            ans.push(carry);
        return this.create(ans);
    }

    public toString() {
        var s: string = "";
        for (var i = this.list.length - 1; i >= 0; i--) {
            var n = this.list[i];
            s += (Format + n).slice(SliceNum);
        }
        return s.replace(/^0+/g, '');
    }
}

割り算の商を求めるのに、最初は、

var q = parseInt(a / Fig);

と書いたのですが、型が違うとエラーになってしまいました。

なので、

var q = a / Fig;
var qstr = (q < 1) ? "0" : q.toString();
carry = parseInt(qstr);

と書いたのですが、あまりにも泥臭いコードなので没。 調べたら、Mathクラスのfloor が使えることがわかりました。

ところで、TypeScriptには、for...in と、for...of という構文があるんですよね。 ほんとうにまぎらわしいです...

それと、toStringメソッドが思いのほか面倒くさかったです。C#のような String.Formatがほしいです。 ところで、const がクラスの中に書けないんですね。なんで?って感じです。

const Figの値は、大きければ大きいほど効率が良くなりますが、TypeScriptの場合は、これが最高値だと思います。


プログラムを完成させる

BigIntクラスができたので、あとはこれを使って、問題を解くコードを書くだけです。

import * as Utils from './utils';
import { BigInt } from './math/bigInt';

class Solver {
    exec(num: number): number {
        var int = new BigInt(2);
        for (var i = 1; i < num; i++) {
            int = int.twice();
        }
        var s = int.toString();
        return s.split("").map(x => parseInt(x)).reduce((x, y) => x + y);
    }
}

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();

今回のBingIntクラスも、math フォルダーに格納しています。


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



 

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

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