両替の計算の例

[Hattorix0]

P.22 の両替の計算のCでの実装です。

const int coins[] = {50, 25, 10, 5, 1};
const int coins_count = sizeof(coins) / sizeof(int);

int sicp_count_change(int amount, int deno = 0)
{
if (amount == 0)
return 1;
if (amount < 0
|| !(deno < coins_count))
return 0;
return sicp_count_change(amount, deno + 1)
+ sicp_count_change(amount - coins[deno], deno);
}


これを、読書会時に話題になったように、再起部分をループ展開してみました。

int count_change(int amount, int deno = 0)
{
int cases = 0;
while (0 < amount) {
for (int i = deno + 1; i < coins_count; ++i) {
if (coins[i] <= amount) {
cases += count_change(amount, i);
break;
}
}
amount -= coins[deno];
}
if (0 == amount)
++cases;
return cases;
}

この方が遙かに早く処理してくれます。