货币兑换考试
我被要求创建一个方法，以便：
- 如果没有可能的更改，则返回更改对象或null
- “机器”有无限的账单: 2，5和10。
- 更改对象必须返回尽可能最少的票据数量。
这是codingame.com中提出的一个问题，并希望对此进行进一步的调查：
package moc;
class Change {
long coin2 = 0, bill5 = 0, bill10 = 0;
}
public class Test {
static Change c = new Change();
public static void main(String[] args) {
Change m = optimalChange(19L);
if (m == null) {
System.out.println("no change possible ...");
return;
}
System.out.println("Coin 2E: " + m.coin2);
System.out.println("bill 5E: " + m.bill5);
System.out.println("bill 10E: " + m.bill10);
long result = m.coin2 * 2 + m.bill5 * 5 + m.bill10 * 10;
System.out.println("Change given: " + result);
}
static Change optimalChange(long s) {
if (s < 2) {
return s == 0 ? c : null;
} else {
int decrementor = 0;
if (s < 5) {
c.coin2++;
decrementor = 2;
} else if (s < 10) {
if (s % 2 != 0) {
c.bill5++;
decrementor = 5;
} else {
c.coin2++;
decrementor = 2;
}
} else {
c.bill10++;
decrementor = 10;
}
return optimalChange(s - decrementor);
}
}
}回答 3
Code Review用户
发布于 2020-11-15 21:59:13
看起来根本不需要递归或循环。如果变化是奇数，它必须包括一个5-法案(特殊情况是1和3的变化，这是不可能作出的)。其余的将由10张钞票(其中将有change / 10 )和2-账单(将有(change % 10) / 2 )提供。顺便说一句，这正是您的代码所做的，但是在很长的一段时间内。
也就是说，第二个版本使递归调用成为一个尾递归。这很好。但是，Java不支持尾调用消除。这不太好。我强烈建议手动删除它。
Code Review用户
发布于 2020-11-16 08:21:47
其他人可以给出算法方面的建议，我会把你的原样留给你，然后给你一些文体上的建议。
Test是一个负责显示事物的类，Change是一个负责处理与变化相关的逻辑的类。所以optimalChange应该进入Change。
int decrementor = 0
您可以避免初始化它，然后IDE会告诉您是否有任何分支在使用之前忘记设置它的值。(你从来不想让它变成零-无限循环！)
if (s < 2) {
return s == 0 ? c : null;
} else {当您有了早期返回时，您可以通过删除else块来避免增加嵌套级别，这可以使代码更容易阅读。
} else if (s < 10) {
if (s % 2 != 0) {
c.bill5++;
decrementor = 5;
} else {您可以避免嵌套，方法是在顶层检查这两个条件，然后检查第二个条件。
static Change c = new Change();我首先把它搬到了Change，因为optimalChange已经搬到那里了，这取决于它。那么，Change拥有一个static Change成员是没有意义的，因为当调用不止一次或其他线程使用时，optimalChange将不再有效。您希望每次调用Change时都要一个optimalChange实例，optimalChange保持static是有意义的，那么在递归之间保持状态的位置是什么呢？答:我为递归部分做了一个单独的函数。
package moc;
public class Test {
static class Change {
long coin2 = 0;
long bill5 = 0;
long bill10 = 0;
public static Change optimalChange(long s) {
return optimalChangeRecursive(s, new Change());
}
private static Change optimalChangeRecursive(long s, Change c) {
int decrement;
if (s == 0} {
return c;
} else if (s < 2) {
return null;
} else if (s < 5) {
c.coin2++;
decrement = 2;
} else if (s < 10 && s % 2 != 0) {
c.bill5++;
decrement = 5;
} else if (s < 10) {
c.coin2++;
decrement = 2;
} else {
c.bill10++;
decrement = 10;
}
return optimalChangeRecursive(s - decrement, c);
}
}
public static void main(String[] args) {
Change m = Change.optimalChange(19L);
if (m == null) {
System.out.println("no change possible ...");
return;
}
System.out.println("Coin 2E: " + m.coin2);
System.out.println("bill 5E: " + m.bill5);
System.out.println("bill 10E: " + m.bill10);
long result = m.coin2 * 2 + m.bill5 * 5 + m.bill10 * 10;
System.out.println("Change given: " + result);
}
}Code Review用户
发布于 2020-11-15 22:13:58
正如vnp所说，对于这个问题的特定约束，有一种不用递归的更简单的方法。
然而，对于不同的参数/面额，情况可能并非如此。
我建议编写更健壮的代码，而不需要额外的if循环检查奇偶校验，因为这些循环专门针对这个问题。
你的算法有一个小缺陷。您假设每次挑选最大的钞票就能找到最少的钞票。正如您在s=8示例中所看到的那样，情况并不总是如此。在每个递归节点，您必须尝试所有可能的选项(我认为。在这一步中，您可能可以进行优化。如果其中一个选项是另一个选项的倍数，您也许可以剪短)，以防最大的选项不起作用。
如果你知道的话，你也可以做动态编程。
https://codereview.stackexchange.com/questions/252160
复制相似问题
腾讯云开发者
