2017年04月17日

TypeScriptでProject Euler #20 「各位の数字の和 2」

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

問題

n × (n - 1) × ... × 3 × 2 × 1 を n! と表す.

例えば, 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800 となる. この数の各桁の合計は 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27 である.

では, 100! の各位の数字の和を求めよ.

注: Problem 16 も各位の数字の和に関する問題です。解いていない方は解いてみてください。

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


BigUIntクラスを定義する

とうとう BigInt クラスを作る時が来たようです。 今回の問題では、BigInt * int が計算できれば良いのですが、 思い切って、BigInt * BigInt ができるクラスとしました。

なお、負の数は扱えないので、クラス名を BigUInt にしています。 加算と乗算だけの実装です。 減算、除算は実装していません。

const Fig: number = 10000000;
const Format: string = "000000";
const SliceNum: number = -7;

export class BigUInt {
    private list: number[] = [];
    constructor(n: number) {
        let i = 0;
        while (n > 0) {
            this.list[i] = n % Fig;
            n = Math.floor(n / Fig);
            i++;
        }
    }
    private create(src: number[]): BigUInt {
        var obj = new BigUInt(0);
        obj.list = src;
        return obj;
    }
    public clone(): BigUInt {
        var obj = new BigUInt(0);
        for (var i = 0; i < this.list.length; i++)
            obj.list[i] = this.list[i];
        return obj;
    }
    public add(num: BigUInt): BigUInt {
        let sum: number[] = [];
        let carry = 0;
        if (this.list.length > num.list.length) {
            var a = this.list;
            var b = num.list;
        } else {
            var a = num.list;
            var b = this.list;
        }
        for (var i = 0; i < a.length; i++) {
            if (i < b.length)
                var n = a[i] + b[i] + carry;
            else
                var n = a[i] + carry;
            sum[i] = n % Fig;
            carry = Math.floor(n / Fig);
        }
        if (carry > 0)
            sum[i] = carry;
        return this.create(sum);
    }
    public multiple(num: BigUInt): BigUInt {
        let ans = new BigUInt(0);
        let wrk: number[] = [];
        let a = this.list;
        let b = num.list;
        for (let ax = 0; ax < a.length; ax++) {
            for (let i = 0; i < ax; i++)
                wrk[i] = 0;
            let carry = 0;
            for (var bx = 0; bx < b.length; bx++) {
                var n = a[ax] * b[bx] + carry;
                wrk[bx + ax] = n % Fig;
                carry = Math.floor(n / Fig);
            }
            wrk[bx+ax] = carry;
            let w = this.create(wrk);
            ans = ans.add(w);
        }
        return 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, '');
    }
}


BigUIntクラスを使って問題を解く

BigUInt クラスができれば、100! を求めるのは、ロジック的には、int での計算と変わらないですね。 このBigUIntを使って、以下のようなコードを書きました。 答えはあっているので、この BigUIntは、いちおう正しく動いているようです。

import * as Utils from './utils';
import { BigUInt } from './math/bigUInt';


class Solver {
    exec(maxnum: number): number {
        var a = new BigUInt(1);
        for (var i = 2; i <= maxnum; i++) {
            a = a.multiple(new BigUInt(i));
        }
        return a.toString().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(100);
            console.log(n);
        } finally {
            sw.stop();
            console.log(sw.toString());
        } 
    }
}

Application.run();

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



 

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

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