我正在使用命令式样式将数字转换数组的代码写入新数据主义但我想使用javascript库将其转换为函数样式,如ramdajs
代码背景假设美元价值总共有5个硬币,25美元,20美元,...... 1美元。我们将不得不兑换美元硬币。用最少的硬币
const data = [25, 20, 10, 5, 1];
const fn = n => data.map((v) => {
const numberOfCoin = Number.parseInt(n / v, 10);
const result = [v, numberOfCoin];
n %= v;
return numberOfCoin ? result : [];
}).filter(i => i.length > 0);
这段代码的结果应该是
fn(48) => [[25, 1], [20, 1], [1, 3]]
fn(100) => [[25, 4]]
我认为你已经有了一个非常好的开始,但是为了使它更具功能性我还会改变一些事情:
return
)n %= v
)你不一定需要Ramda:
const coins = value =>
[25, 20, 10, 5, 1].reduce(([acc, val], cur) =>
val < cur ? [acc, val] : [[...acc, [cur, Math.floor(val / cur)]], val % cur],
[[], value]
)[0];
console.log(coins(48));
console.log(coins(100));
如果你发现自己使用map
然后filter
,你很可能需要reduce
。在上面的函数coins
中,迭代器返回一个数组,其中包含一对硬币和硬币数量以及每一步的减少值。
请注意,在每个步骤中,我使用解构分配来捕获对的数组和各个参数中的减少的值。
现在,当然也可以使用Ramda:
const {compose, filter, last, mapAccum, flip} = R;
const mapIterator = (a, b) => [a % b, [b, Math.floor(a / b)]];
const withCoins = ([coins, number]) => number > 0;
const coins = compose(filter(withCoins), last, flip(mapAccum(mapIterator))([25, 20, 10, 5, 1]));
console.log(coins(48));
console.log(coins(100));
<script src="https://cdnjs.cloudflare.com/ajax/libs/ramda/0.26.1/ramda.min.js"></script>
编辑:正如斯科特正确地指出的那样,我上面的任何解决方案都会给你最小的改变。
事实证明,这比我预期的要多得多,我决定采用一种我确信可以改进的解决方案:
我定义了5套硬币:
我计算每组产生多少变化,并保持产生最少的变化。
例如,要更改30
:
const {compose, pipe, sum, map, last, head, mapAccum, curry, flip, applyTo, sortBy, reject, not} = R;
const numCoins = compose(sum, map(last));
const changeFn = curry((coins, num) => mapAccum((cur, coin) => [cur % coin, [coin, Math.floor(cur / coin)]], num, coins)[1]);
const change1 = changeFn([1]);
const change2 = changeFn([5, 1]);
const change3 = changeFn([10, 5, 1]);
const change4 = changeFn([20, 10, 5, 1]);
const change5 = changeFn([25, 20, 10, 5, 1]);
const change = pipe(
applyTo,
flip(map)([
change1,
change2,
change3,
change4,
change5]),
sortBy(numCoins),
head,
reject(compose(not, last)));
console.log(change(30));
console.log(change(40));
console.log(change(48));
<script src="https://cdnjs.cloudflare.com/ajax/libs/ramda/0.26.1/ramda.min.js"></script>
来自user633183的答案的这种变体将找到最小数量的硬币,它不使用选择每个较大面额的最大数量的常用技术,其可能的代价是总体上选择更多硬币。
请注意,这可能涉及比原始答案或来自customcommander的初始答案大得多的计算。
change
这里返回一个硬币值列表,所以对于58
来说它会返回[25, 25, 5, 1, 1, 1]
。 makeChange
将其转换为[ [25, 2], [5, 1], [1, 3] ]
格式。如果你将minLength
函数从<=
更改为<
,那么这将生成[ [25, 1], [20, 1], [10, 1], [1, 3] ]
。这是相同数量的硬币,但使用不同的面额。
如果退货的顺序对您无关紧要,您也可以删除sort
行。
这里混合风格有点不幸。如果我们尝试的话,我们可以用makeChange
替换那个change
的Ramda管道版本。但我认为在拉姆达;这是最容易想到的。用Ramda管道替换change
并不容易,因为以这种方式进行递归更难。
感谢customcommander在这个答案的早期版本中指出了一个缺陷。
const minLength = (as, bs) =>
as.length <= bs.length ? as : bs
const change = ([ c, ...rest ], amount = 0) =>
amount === 0
? []
: c === 1
? Array(amount).fill(1)
: c <= amount
? minLength (
[ c, ...change ([c, ...rest], amount - c)],
change (rest, amount)
)
: change (rest, amount)
const makeChange = pipe(
change,
countBy(identity),
toPairs,
map(map(Number)),
sort(descend(head)) // if desired
)
const coins =
[ 25, 20, 10, 5, 1 ]
console.log (makeChange (coins, 40))
//=> [ [ 20, 2 ] ]
console.log (makeChange (coins, 45))
//=> [ [ 25, 1 ], [ 20, 1 ] ]
console.log (change (coins, 48))
//=> [ [ 25, 1 ], [ 20, 1 ], [ 1, 3 ] ]
console.log (makeChange (coins, 100))
//=> [ [ 25, 4 ] ]
<script src = "https://cdnjs.cloudflare.com/ajax/libs/ramda/0.26.1/ramda.js"></script>
<script> const { pipe, countBy, identity, toPairs, map, sort, descend, head } = R </script>
人们通常会到达map
,filter
和reduce
,但结果往往是圆孔中的方形钉。
map
没有意义,因为它产生了一比一的结果;如果我有4种类型的硬币,我总会收到4种类型的改变,这当然不是我们想要的。使用filter
会强制您进行更多处理以达到预期效果。reduce
可以消除由map
+ filter
引起的中间值,但同样,我们可能会在分析每个硬币之前达到预期的结果。在返回fn(100)
的[ [25, 4] ]
的例子中,甚至没有必要查看硬币20
,10
,5
或1
,因为结果已经达到;进一步减少将是浪费。对我来说,函数式编程是关于方便的。如果我没有能够满足我需要的功能,那么我就完成它,因为我的程序清楚地传达了它的意图是很重要的。有时这意味着使用更适合我正在处理的数据的构造 -
const change = (coins = [], amount = 0) =>
loop // begin a loop, initializing:
( ( acc = [] // an empty accumulator, acc
, r = amount // the remaining amount to make change for, r
, [ c, ...rest ] = coins // the first coin, c, and the rest of coins
) =>
r === 0 // if the remainder is zero
? acc // return the accumulator
: c <= r // if the coin is small enough
? recur // recur with
( [ ...acc, [ c, div (r, c) ] ] // updated acc
, mod (r, c) // updated remainder
, rest // rest of coins
)
// otherwise (inductive) coin is too large
: recur // recur with
( acc // unmodified acc
, r // unmodified remainder
, rest // rest of coins
)
)
与map
,filter
和reduce
不同,我们的解决方案在确定结果后不会继续迭代输入。使用它看起来像这样 -
const coins =
[ 25, 20, 10, 5, 1 ]
console.log (change (coins, 48))
// [ [ 25, 1 ], [ 20, 1 ], [ 1, 3 ] ]
console.log (change (coins, 100))
// [ [ 25, 4 ] ]
在下面的浏览器中验证结果 -
const div = (x, y) =>
Math .round (x / y)
const mod = (x, y) =>
x % y
const recur = (...values) =>
({ recur, values })
const loop = f =>
{ let acc = f ()
while (acc && acc.recur === recur)
acc = f (...acc.values)
return acc
}
const change = (coins = [], amount = 0) =>
loop
( ( acc = []
, r = amount
, [ c, ...rest ] = coins
) =>
r === 0
? acc
: c <= r
? recur
( [ ...acc, [ c, div (r, c) ] ]
, mod (r, c)
, rest
)
: recur
( acc
, r
, rest
)
)
const coins =
[ 25, 20, 10, 5, 1 ]
console.log (change (coins, 48))
// [ [ 25, 1 ], [ 20, 1 ], [ 1, 3 ] ]
console.log (change (coins, 100))
// [ [ 25, 4 ] ]
Ramda用户可以使用R.until
,但可读性因其纯粹的功能驱动界面而受损。 loop
和recur
的灵活性非常有利,imo -
const change = (coins = [], amount = 0) =>
R.until
( ([ acc, r, coins ]) => r === 0
, ([ acc, r, [ c, ...rest ] ]) =>
c <= r
? [ [ ...acc
, [ c, Math.floor (R.divide (r, c)) ]
]
, R.modulo (r, c)
, rest
]
: [ acc
, r
, rest
]
, [ [], amount, coins ]
)
[ 0 ]
另一种方法是将其写为递归函数 -
const div = (x, y) =>
Math .round (x / y)
const mod = (x, y) =>
x % y
const change = ([ c, ...rest ], amount = 0) =>
amount === 0
? []
: c <= amount
? [ [ c, div (amount, c) ]
, ...change (rest, mod (amount, c))
]
: change (rest, amount)
const coins =
[ 25, 20, 10, 5, 1 ]
console.log (change (coins, 48))
// [ [ 25, 1 ], [ 20, 1 ], [ 1, 3 ] ]
console.log (change (coins, 100))
// [ [ 25, 4 ] ]