首页 文章

JavaScript - 这种硬币更改算法有什么问题

提问于
浏览
3

我正在尝试使用贪心算法计算在JavaScript中达到金额所需的最小硬币数量

返回结果将是一个由每个级别的硬币数组成的数组

我决定创建一个可以解决这个问题的函数,但它不起作用

window.addEventListener('load', function(e) {
  function calculateChange(coins, total) {
    var sum = 0;
    var dispatched = [];
    for (var i = 0; i < coins.length;i++) {
      dispatched[c] = 0;
    }

    while (sum < total) {
      for (var c = 0; c < coins.length; c++) {
        while (total - sum >= coins[c]) {
          total += coins[c];
          dispatched[c]++;
        }
      }
    }
    return dispatched;
  }

  alert(calculateChange([50,25,10,5,1],137));
}, false);

calculateChange函数接受两个参数,一个硬币值数组和金额 .

第一步是初始化一个sum变量,该变量显示已经分派的变化量 . 我还将创建一个数组变量,它将保存某个硬币的分配次数 .

为此,我将迭代硬币数组并将所有值设置为0.如果我不知道不同硬币值的数量,这很重要

接下来我想到了一个检查是否达到金额的条件

如果没有,我将启动一个迭代所有硬币值的for循环 . 对于贪婪算法,随着指数增加,硬币值减小 . 这是使用尽可能少的硬币

为了防止向下跳转硬币层次结构,将在此for循环中嵌套一个while循环 . 这个while循环将检查是否仍然可以使用最大的硬币 .

如果不满足循环条件,则while循环结束 . for循环将通过递增索引继续 . 我们将下移到下一个较低级别的硬币 . 这个过程将重复进行

我期待的输出就是这个

[2,1,1,0,2]

这意味着2 50s,1 1/4,1角钱和2便士

在此函数中,这应该表示dispatched的值,即返回值 . 运行上面的代码,我没有得到返回值

我可以解释的唯一解释是我使用了错误的循环 . 即使经过检查,我也看不到它

我在这里想念的是什么深刻的见解非常感谢

2 回答

  • 1

    显然,变量 sum0 初始化并且从不更新,所以循环

    while (sum < total)
    

    将永远运行,因为 total 增加了,但从未减少 . 也许你想更新 sum 而不是 total . 我猜你已经混淆了 sum 的语义(显然是已经用所选硬币覆盖的值)和 total ,这是函数的参数 .

  • 3

    您不需要嵌套循环 . 相反,您可以通过划分然后使用 Math.floor() 在每一步执行整数除法 . 这将为您提供当前面额所需的硬币数量,然后您可以根据该数量减少剩余总数 .

    另外,尝试将零放入 dispatched 数组的第一个循环对数组索引具有错误的变量 .

    所以你可能会尝试这样的事情:

    function calculateChange( coins, total ) {
        var dispatched = [];
        for( var i = 0;  i < coins.length;  i++ ) {
            dispatched[i] = 0;
        }
    
        for( var c = 0;  total > 0;  c++ ) {
            dispatched[c] = Math.floor( total / coins[c] );
            total -= dispatched[c] * coins[c];
        }
        return dispatched;
    }
    
    console.log( calculateChange( [50,25,10,5,1], 137 ) );
    // logs [ 2, 1, 1, 0, 2 ]
    

相关问题