在硬币找零类型的问题中将递归函数重构为迭代函数

Question

在 coin-change 类型的问题中，我试图将递归函数重构为迭代函数。给定一组 coin_types，函数 coinr 递归地找到支付给定金额 sum 的最小硬币数。

# Any coin_type could be used more than once or it may not be used at all

sub coinr ($sum, @coin_types) { # As this is for learning basic programming 
    my $result = $sum;          # No memoization (dynamic programming) is used
    if $sum == @coin_types.any { return 1 }
    else { for @coin_types.grep(* <= $sum) -> $coin_type {
        my $current = 1 + coinr($sum - $coin_type, @coin_types);
        $result = $current if $current < $result; } }
    $result;
}

say &coinr(@*ARGS[0], split(' ', @*ARGS[1])); 

# calling with
# 8 "1 4 5" gives 2 (4+4)
# 14 "1 3 5" gives 4 (1+3+5+5), etc.

这个函数原来是用Python写的，我把它转成Raku了。这是我对迭代版本的看法，它非常不完整：

# Iterative

sub coini ($sum, @coin_types) {
    my $result = 1;
    for @coin_types -> $coin_type {
    for 1 ... $sum -> $i {
        if $sum-$coin_type == @coin_types.any { $result += 1 } #?
        else { # ???
        }
     }
   }
}

有人可以帮我解决这个问题吗？

Answer 1

有许多不同的方法可以迭代地实现它（正如我们喜欢说的，有不止一种方法可以做到！）这是一种方法：

sub coini($sum is copy, @coin-types) {
    gather while $sum > 0 { take $sum -= @coin-types.grep(* ≤ $sum).max } .elems
}

这会将（现在可变的）$sum 减去尽可能大的硬币，并在列表中跟踪当前的 $sum。然后，因为我们只想要硬币的数量，所以它 returns 该列表的长度。

在硬币找零类型的问题中将递归函数重构为迭代函数

Refactoring a recursive function into iterative in a coin-change type of problem

recursion

iteration

raku

coin-change