Exact Change 测试用例不足 #299

ylsxch commented 7 years ago

QUARTER（0.25）和DIME（0.10）不是倍数关系，加上以下测试用例比较严谨。

checkCashRegister(19.20, 20.00, [["PENNY", 0], ["NICKEL", 0], ["DIME", 0.30], ["QUARTER", 0.75], ["ONE", 0], ["FIVE", 0], ["TEN", 0], ["TWENTY", 0], ["ONE HUNDRED", 0]])应该返回 [["QUARTER", 0.50], ["DIME", 0.30]].

原题链接：https://www.freecodecamp.cn/challenges/exact-change

S1ngS1ng commented 7 years ago

@ylsxch 谢谢你的建议。我过两天看一下这个

ylsxch commented 7 years ago

上面的用例中QUARTER（25美分）和DIME（10美分） 25和10的最小公倍数是50，也就是说QUARTER最少要尝试2种可能性。如果要凑80美分，如果只尝试了3个QUARTER（75美分）就得出"Insufficient Funds"的结论是不对的。 2个QUARTER（50美分）加3个DIME（10美分）才是正确组合。

AnClark commented 7 years ago

还有。。我也不敢相信原题中会有3.10个10美分，2.05个5美分。会不会是把一个美分硬币掰成了很多份？

S1ngS1ng commented 7 years ago

@AnClark 题目不是这个意思。。。3.10 表示 dime 总价值为 $3.10，意思就是有 31 个 dime。2.05 就是 Nickel 总价值为 $2.05

S1ngS1ng commented 7 years ago

@ylsxch 前两天在写这道题的攻略，已经发现了类似问题。其实不管是英文版还是中文版，这道题测试用例其实是一样的。如果要考虑类似情况，就需要通过回溯法去做，或者动态规划。这样难度就太大了。不过我觉得，这样的检测可以作为额外条件，留给大家思考。你认为呢？ @wudifeixue

AnClark commented 7 years ago

怪不得我说怎么这么奇怪。。。多谢啦~（建议把题目写清楚，这里很容易有歧义）

S1ngS1ng commented 7 years ago

@AnClark #368 谢谢你的建议。我尽快把这个加上

ylsxch commented 7 years ago

@S1ngS1ng 很久没关注这事了，居然又回复。如果只是针对这题（美元）去解题的话，其实也不用线性规划那么麻烦。贴个之前自己做题时的解法仅供参考： function checkCashRegister(price, cash, cid) { var change; // Here is your change, ma'am.

change = (cash-price).toFixed(2);

if(change === cid.reduce(function(a, b){return a + b[1];}, 0).toFixed(2)) return "Closed";

// reduce the prices form dollar to cents. var cid_100 = cid.map(function(item){return [item[0], reduceToCents(item[1])];});

// (The Least common multiple of QUARTER and DIME) / QUARTER = Loop Number(2) var arrMoney = [["PENNY", 1, 1], ["NICKEL", 5, 1], ["DIME", 10, 1], ["QUARTER", 25, 2], ["ONE", 100, 1], ["FIVE", 500, 1], ["TEN", 1000, 1], ["TWENTY", 2000, 1], ["ONE HUNDRED", 10000, 1]];

function getCashArr(p, i) { if (i < 0) return "Insufficient Funds";

var p_last = p >= cid_100[i][1] ? (p - cid_100[i][1]) : (p % arrMoney[i][1]);

var arrRtn = [];

if (p_last === 0) {
  arrRtn.unshift([cid_100[i][0], reduceToDollar(p)]);
} else {
  for(var intLoop = 0;intLoop < arrMoney[i][2];intLoop++) {
    p_last = p_last + intLoop * arrMoney[i][1];
    arrRtn = getCashArr(p_last, i-1);

    if ((arrRtn instanceof Array) && p !== p_last ) {
      arrRtn.unshift([cid_100[i][0], reduceToDollar(p - p_last)]);
      break;
    }
  }
}

return arrRtn;

}

function reduceToCents(p) { return Math.round(p*100); }

function reduceToDollar(p) { return p/100; }

change = getCashArr(reduceToCents(change), arrMoney.length - 1);

return change; }

S1ngS1ng commented 7 years ago

@ylsxch 很好的解法。 :+1: 这道题确实可以不用 DP，但用的话也是没问题的。个人觉得用 DP 应该会比 backtrack 好想一些。你的代码，如果我没理解错的话，就是 backtrack 嘛。主要是，在 FCC 平台学习的，新手偏多，这样的解法大家会比较难写出来

ylsxch commented 7 years ago

@S1ngS1ng 嗯嗯

Zalezale commented 6 years ago

检测结果对吗？

Zalezale commented 6 years ago

否则, 返回应找回的零钱列表,且由大到小存在二维数组中.这句话的意思应该现有零钱大于需要找回的零钱数且现有零钱组合不出应找回的钱

Zalezale commented 6 years ago

貌似是我理解错了。。。。。。

FreeCodeCampChina / freecodecamp.cn

Exact Change 测试用例不足 #299 #280