Q05 枚数で考えるパスカルの三角形

JavaScriptのソース

//パスカルの三角形の次の段を返す
function DeriveNextDan(pPrevArr) {
    var WillReturn = new Array();

    var UB = pPrevArr.length - 1;
    for (var I = 0; I <= UB + 1; I++) {
        var Ind1 = I - 1;
        var Ind2 = I;

        var NextVal = 0;
        if (0 <= Ind1 && Ind1 <= UB) {
            NextVal += pPrevArr[Ind1];
        }
        if (0 <= Ind2 && Ind2 <= UB) {
            NextVal += pPrevArr[Ind2];
        }

        WillReturn[I] = NextVal;
    }
    return WillReturn;
}

//必要な硬貨の枚数を返す
function DeriveMaisuu(pYen) {
    var WillReturn = 0;

    var wkArr = new Array(10000, 5000, 2000, 1000, 500, 100, 50, 10, 5, 1);
    for (var I = 0; I <= wkArr.length - 1; I++) {
        if (pYen >= wkArr[I]) {
            var Rest = pYen % wkArr[I];
            WillReturn += (pYen - Rest) / wkArr[I];
            pYen = Rest;
        }
    }
    return WillReturn;
}

//配列を引数として、必要な枚数の合計を表示
function DeriveMaisuuSum(pPascalArr) {
    var MaisuuSum = 0;

    for (var I = 0; I <= pPascalArr.length - 1; I++) {
        MaisuuSum += DeriveMaisuu(pPascalArr[I]);
    }
    document.write("n=", pPascalArr.length - 1, "での枚数合計=", MaisuuSum, "<br>");
}

var PascalArr = new Array();
PascalArr[0] = 1;
DeriveMaisuuSum(PascalArr);
for (var I = 1; I <= 45; I++) {
    PascalArr = DeriveNextDan(PascalArr);
    DeriveMaisuuSum(PascalArr);
}

実行結果

省略
n=43での枚数合計=879609668
n=44での枚数合計=1759218933
n=45での枚数合計=3518437540

解説

ナイーブに解いてます。