計算機科学のブログ

Building Abstractions with Functions - Functions and the Processes They Generate - Orders of Growth - tree

Structure and Interpretation of Computer Programs: JavaScript Edition(Harold Abelson(著)、Gerald Jay Sussman(著)、Julie Sussman(著)、The MIT Press)のChapter 1(Building Abstractions with Functions)、1.2(Functions and the Processes They Generate)、1.2.3(Orders of Growth)、Exercise 1.14の解答を求めてみる。

実際に木を描いてみると以下のような感じに。

count_change(11)

cc(11, 5)

+ cc(11, 4)
  + cc(11, 3)
    + cc(11, 2)
      + cc(11, 1)
        + cc(11, 0)
            0
          cc(10, 1)
          + cc(10, 0)
              0
            cc(9, 1)
            + cc(9, 0)
                0
              cc(8, 1)
              + cc(8, 0)
                  0
                cc(7, 1)
                + cc(7, 0)
                    0
                  cc(6, 1)
                  + cc(6, 0)
                      0
                    cc(5, 1)
                    + cc(5, 0)
                        0
                      cc(4, 1)
                      + cc(4, 0)
                          0
                        cc(3, 1)
                        + cc(3, 0)
                            0
                          cc(2, 1)
                          + cc(2, 0)
                              0
                            cc(1, 1)
                            + cc(1, 0)
                                0
                              cc(0, 1)
                                1
        cc(6, 2)
        + cc(6, 1)
          + cc(6, 0)
              0
            cc(5, 1)
            + cc(5, 0)
                0
              cc(4, 1)
              + cc(4, 0)
                  0
                cc(3, 1)
                + cc(3, 0)
                    0
                  cc(2, 1)
                  + cc(2, 0)
                      0
                    cc(1, 1)
                    + cc(1, 0)
                        0
                      cc(0, 1)
                        1
          cc(1, 2)
          + cc(1, 1)
            + cc(1, 0)
                0
              cc(0, 1)
                1
            cc(-4, 2)
              0
      cc(1, 3)
      + cc(1, 2)
        + cc(1, 1)
          + cc(1, 0)
              0
            cc(0, 1)
              1
          cc(-4, 2)
            0
        cc(-9, 3)
          0
    cc(-14, 4)
      0
  cc(-39, 5)
    0

JavaScriptで似たような木を描くコード。

コード

function cc_log(amount, kinds_of_coins, indent) {
    console.log(`${'  '.repeat(indent)}cc(${amount}, ${kinds_of_coins})`)
    if (amount === 0) {
        console.log(`${'  '.repeat(indent)}  1`);
    } else if (amount < 0 || kinds_of_coins === 0) {
        console.log(`${'  '.repeat(indent)}  0`);
    } else {
        cc_log(amount, kinds_of_coins - 1, indent + 1);
        cc_log(amount - first_denomination(kinds_of_coins), kinds_of_coins, indent + 1)
    }
}
function first_denomination(kinds_of_coins) {
    return kinds_of_coins === 1 ?
        1 :
        kinds_of_coins === 2 ?
            5 :
            kinds_of_coins === 3 ?
                10 :
                kinds_of_coins === 4 ?
                    25 :
                    kinds_of_coins === 5 ?
                        50 :
                        0;
}

cc_log(11, 5, 0);

入出力結果(Terminal, Zsh)

% node answer1.14.js
cc(11, 5)
  cc(11, 4)
    cc(11, 3)
      cc(11, 2)
        cc(11, 1)
          cc(11, 0)
            0
          cc(10, 1)
            cc(10, 0)
              0
            cc(9, 1)
              cc(9, 0)
                0
              cc(8, 1)
                cc(8, 0)
                  0
                cc(7, 1)
                  cc(7, 0)
                    0
                  cc(6, 1)
                    cc(6, 0)
                      0
                    cc(5, 1)
                      cc(5, 0)
                        0
                      cc(4, 1)
                        cc(4, 0)
                          0
                        cc(3, 1)
                          cc(3, 0)
                            0
                          cc(2, 1)
                            cc(2, 0)
                              0
                            cc(1, 1)
                              cc(1, 0)
                                0
                              cc(0, 1)
                                1
        cc(6, 2)
          cc(6, 1)
            cc(6, 0)
              0
            cc(5, 1)
              cc(5, 0)
                0
              cc(4, 1)
                cc(4, 0)
                  0
                cc(3, 1)
                  cc(3, 0)
                    0
                  cc(2, 1)
                    cc(2, 0)
                      0
                    cc(1, 1)
                      cc(1, 0)
                        0
                      cc(0, 1)
                        1
          cc(1, 2)
            cc(1, 1)
              cc(1, 0)
                0
              cc(0, 1)
                1
            cc(-4, 2)
              0
      cc(1, 3)
        cc(1, 2)
          cc(1, 1)
            cc(1, 0)
              0
            cc(0, 1)
              1
          cc(-4, 2)
            0
        cc(-9, 3)
          0
    cc(-14, 4)
      0
  cc(-39, 5)
    0
%