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
%