Open zwhu opened 7 years ago
现在有100块钱人民币,将 100 块钱换成零钱(最小币值 1 元),一共有多少方式?
总的不同方式的数目等于:
ok, 根据上面的说法来实现吧:
'use strict' // 实现 lisp 中的 list // car 是 list 中的第一个值 // cdr 是 list 中的剩下的值的集合 const list = (...args) => args ,car = (list) => list[0] ,cdr = (list) => list.slice(1) // 换零钱的方式 // 如果换 0 元钱,就算是有一种换钱方式 // 如果换的钱小于 0, 那么就算有零种换钱方式 // 如果币值的长度为 0, 那么也算是有零种换钱方式 function count_change(amount, coin_values) { switch (true) { case (amount === 0): return 1 case (amount < 0 || no_more(coin_values)): return 0 default: return ( count_change(amount, except_first_denomination(coin_values)) + count_change( amount - first_denomination(coin_values), coin_values ) ) } } function no_more(coin_values) { return coin_values.length === 0 } function first_denomination(coin_values) { return car(coin_values) } function except_first_denomination(coin_values) { return cdr(coin_values) }
测试一下:
const cn_coins = list(100, 50, 20, 10, 5, 2, 1) count_change(100, cn_coins) // ---> 4563
现在有100块钱人民币,将 100 块钱换成零钱(最小币值 1 元),一共有多少方式?
总的不同方式的数目等于:
ok, 根据上面的说法来实现吧:
测试一下: