javascript制作变更算法 [英] javascript making change algorithm

问题描述

我正在使用javascript解决此问题进行更改：

问题：

给出一定数量的钱（一系列硬币面额），使用可用的
面额的硬币计算出
种方法来赚钱。

示例：

对于数量= 4（4¢）和面额= [1,2,3]（1¢，
2¢和3¢），您的程序将输出4-用这些面额制作
4¢的方法数量：

1¢，1¢ ，1¢，1¢

1¢，1¢，2¢

1¢，3¢

2¢，2¢

我找到了解决方案：

  var makeChange = function（total）{
 var count = 0; 
个var硬币= [1、2、5、10、20、50、100、200]； 
 
 var changer = function（index，value）{
 
 var currentCoin = coin [index]; 
 
 if（index === 0）{
 if（value％currentCoin ==== 0）{
 count ++; 
} 
回报； 
} 
 
 while（value> = 0）{
 changer（index-1，value）; 
值-= currentCoin; 
} 
} 
转换器（coins.length-1，总计）； 
返回计数； 
}; 
 
 makeChange（200）; 
  

问题：

1. 有人可以向我解释发生了什么吗？我尝试遵循代码，但在递归之间迷路了。

我了解他正在使用最终的硬币价值，而他从给定的总数中减去。 （但是为什么？）我有点迷茫。

2. 当while循环中的值> = 0时，它会保持循环增加索引，我不明白为什么。

有人可以从这种算法中理解吗？

对不起，刚刚开始学习动态编程。

谢谢，

解决方案

让我们跟踪 makeChange（4）会发生什么：

函数 changer 被定义然后第一次调用。

  value = 4，索引= 7，硬币[7] = 200 
  

由于变量， index 不为0，我们进入 while 循环。

A使用 index 6

<$ p进行第二次 changer 的调用$ p> 同时，第一个调用继续执行 while
循环，但是由于从 value中减去了200，因此
value现在小于0，因此 w hile循环终止
，而第一个调用不再执行任何操作。

（请记住，变量值是不同的
，并且对于每个调用都是私有的，因此 while循环仅
会影响其自身函数中的值调用。）


好了，现在此模式继续所有具有 index 指向大于值的硬币，直到 index 为1。

 值= 4，索引= 1，硬币[1] = 2 
  

这次是在 while 循环中发生的更多事情：

 我们得到函数调用'changer（0,4）'，
和第二个函数调用'changer（0,2）'，
从'value'中减去2，即4，
，然后在从'value'中减去2，即第3个函数调用'changer（0,0）'，
。
 
这3个呼叫分别代表：
 
 1 +1和1 + 1 
 2 +1 +1 1 b 
 2 + 2 
 
每次执行'value-= currentCoin'行时，
代表s包含该代币的
解决方案的另一组选择。 
 
 4％硬币[0] = 0，表示4可被1整除表示1 + 1 +1 + 1 
 
 4-2跟随2％1表示2 + 1 + 1 
 
和4-2-2代表2 + 2 
  

个总数： 3

I'm solving this problem "Making change" in javascript:

Question:

Given an amount of money, an array of coin denominations, compute the number of ways to make the amount of money with coins of the available denominations.

Example:

For amount=4 (4¢) and denominations=[1,2,3] (1¢, 2¢ and 3¢), your program would output 4—the number of ways to make 4¢ with those denominations:

1¢, 1¢, 1¢, 1¢

1¢, 1¢, 2¢

1¢, 3¢

2¢, 2¢

I found a solution:

var makeChange = function(total){
  var count = 0;
  var coins = [1, 2, 5, 10, 20, 50, 100, 200];

  var changer = function(index, value){

    var currentCoin = coins[index];

    if( index === 0){
      if( value % currentCoin === 0){
        count++;
      }
      return;
    }

    while( value >= 0 ){
      changer(index-1, value);
      value -= currentCoin;
    }
  }
  changer(coins.length-1, total);
  return count;
};

makeChange(200);

Problem(s):

1. Can someone explain to me what is going on? I tried following the code but i get lost in between the recursion.

I understand that he is taking the final coin value and he is substracting from the given total. (But why?) I'm kinda lost.

2. When value >= 0 in the while loop, It keeps looping around increasing the index, i couldn't understand why.

Can someone make sense out of this algorithm?

Sorry, just started learning Dynamic Programming.

Thank you,

解决方案

Let's track what happens with makeChange(4):

The function changer gets defined then called for the first time.

value = 4, index = 7, coins[7] = 200

Since the variable, index is not 0, we move on to the while loop.

A second call to changer is made with index 6

Meanwhile, the first call continues the 'while'
loop but since 200 has been subtracted from 'value',
'value' is now less than 0 so the 'while' loop terminates
and this first call does nothing more.

(Keep in mind that the variable 'value' is distinct 
and private to each call, so the 'while' loop only 
affects the 'value' in its own function call.)

Ok, now this pattern continues with all the function calls that have index pointing to a coin larger than value until index is 1.

value = 4, index = 1, coins[1] = 2 

This time more happens in the while loop:

We get the function call, 'changer(0,4)', 
AND a second function call, 'changer(0,2)', 
after we subtract 2 from 'value', which was 4,
AND a third function call, 'changer(0,0)', 
after we subtract 2 from 'value', which was 2.

These 3 calls respectively represent:

   1 + 1 + 1 + 1
   2 + 1 + 1
   2 + 2

Each time the line 'value -= currentCoin' is executed,
it represents the start of another set of choices for 
solutions that include that coin.

4 % coins[0] = 0, meaning 4 is divisible by 1 represents 1 + 1 + 1 + 1

4 - 2 folllowed by 2 % 1 represents 2 + 1 + 1

and 4 - 2 - 2 represents 2 + 2

Total count: 3

这篇关于javascript制作变更算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！