简单更改程序中的奇怪计数行为
Strange counting behavior in simple change making program
所以我制定了这个相当直接的最佳变更程序,在大多数情况下都运行良好。但是出于某种奇怪的原因,它的行为前后矛盾,有时不会添加所需的最后一分钱,但有时会。
我尝试了不同的输出,代码总是正确的,除了有时最后一分钱;使用美国货币时。我确定原因很明显,但我就是看不到。
public static int[] optimal_change(double[] currency, double amount) {
int[] count = new int[currency.length];
for (int i = 0; i < currency.length; i++) {
if (amount >= currency[i]) {
amount -= currency[i];
count[i]++;
i--;
}
if (amount == 0.0000) {
break;
}
}
return count;
}
public static void main(String[] args) {
double[] american_currency = {100,50,20,10,5,1,0.25,0.10,0.05,0.01};
//Japanese currency: https://www.boj.or.jp/en/note_tfjgs/note/valid/index.htm/
double[] japanese_currency = {10000,5000,2000,1000,500,100,50,10,5,1};
int[] american_change = optimal_change(american_currency, 78.36);
int[] japanese_change = optimal_change(japanese_currency, 793048);
System.out.println("Optimal change for: .38");
for (int i = 0; i < american_currency.length; i++) {
if (i <= 5) {
System.out.println(Integer.toString(american_change[i]) + " $" + Double.toString(american_currency[i]));
} else {
System.out.println(Integer.toString(american_change[i]) + " " + Double.toString(american_currency[i]) + "¢");
}
}
System.out.println("--------------------------");
System.out.println("Optimal change for: ¥793040");
for (int i = 0; i < japanese_currency.length; i++) {
System.out.println(Integer.toString(japanese_change[i]) + " ¥" + Double.toString(japanese_currency[i]));
}
}
正确结果:
输入:78.37
输出:
最佳零钱:78.37 美元
0 100.0 美元
1 50.0 美元
1 20.0 美元
0 10.0 美元
1 $5.0
3 1.0 美元
1 0.25¢
1 0.1¢
0 0.05¢
2 0.01¢
不正确的结果:
输入:78.38
输出:
最佳零钱:78.38 美元
0 100.0 美元
1 50.0 美元
1 20.0 美元
0 10.0 美元
1 $5.0
3 1.0 美元
1 0.25¢
1 0.1¢
0 0.05¢
2 0.01¢
输出应该是:
最佳零钱:78.38 美元
0 100.0 美元
1 50.0 美元
1 20.0 美元
0 10.0 美元
1 $5.0
3 1.0 美元
1 0.25¢
1 0.1¢
0 0.05¢
3 0.01¢
正如其他人在评论中指出的那样,问题是由 Java double 值的“近似值”引起的。
在 BigDecimal 中更改它。
请参阅此 question 了解更多信息。
切换到 BigDecimal 似乎解决了这个问题。不知道为什么双打问题持续了这么久。但值得庆幸的是它有效。
import java.math.BigDecimal;
public class Greedy_Money_BigInteger {
public static int[] optimal_change(BigDecimal[] currency, BigDecimal amount) {
int[] count = new int[currency.length];
for (int i = 0; i < currency.length; i++) {
//if (amount >= currency[i]) {
if (amount.compareTo(currency[i]) >= 0) {
amount = amount.subtract(currency[i]);
count[i]++;
i--;
}
if (amount.compareTo(BigDecimal.valueOf(0)) <= 0) {
break;
}
}
return count;
}
public static void main(String[] args) {
BigDecimal[] american_currency = {BigDecimal.valueOf(100),BigDecimal.valueOf(50),BigDecimal.valueOf(20),BigDecimal.valueOf(10),BigDecimal.valueOf(5),BigDecimal.valueOf(1),BigDecimal.valueOf(0.25),BigDecimal.valueOf(0.10),BigDecimal.valueOf(0.05),BigDecimal.valueOf(0.01)};
//Japanese currency: https://www.boj.or.jp/en/note_tfjgs/note/valid/index.htm/
BigDecimal[] japanese_currency = {BigDecimal.valueOf(10000),BigDecimal.valueOf(5000),BigDecimal.valueOf(2000),BigDecimal.valueOf(1000),BigDecimal.valueOf(500),BigDecimal.valueOf(100),BigDecimal.valueOf(50),BigDecimal.valueOf(10),BigDecimal.valueOf(5),BigDecimal.valueOf(1)};
BigDecimal american_change_value = BigDecimal.valueOf(78.31);
BigDecimal japanese_change_value = BigDecimal.valueOf(793043);
int[] american_change = optimal_change(american_currency, american_change_value);
int[] japanese_change = optimal_change(japanese_currency, japanese_change_value);
System.out.println("Optimal change for: $" + american_change_value.toString());
for (int i = 0; i < american_currency.length; i++) {
if (american_change[i] > 0) {
if (i <= 5) {
System.out.println(Integer.toString(american_change[i]) + " $" + american_currency[i].toString());
} else {
System.out.println(Integer.toString(american_change[i]) + " " + american_currency[i].toString() + "¢");
}
}
}
System.out.println("--------------------------");
System.out.println("Optimal change for: ¥" + japanese_change_value.toString());
for (int i = 0; i < japanese_currency.length; i++) {
if (japanese_change[i] > 0) {
System.out.println(Integer.toString(japanese_change[i]) + " ¥" + japanese_currency[i].toString());
}
}
}
}
所以我制定了这个相当直接的最佳变更程序,在大多数情况下都运行良好。但是出于某种奇怪的原因,它的行为前后矛盾,有时不会添加所需的最后一分钱,但有时会。
我尝试了不同的输出,代码总是正确的,除了有时最后一分钱;使用美国货币时。我确定原因很明显,但我就是看不到。
public static int[] optimal_change(double[] currency, double amount) {
int[] count = new int[currency.length];
for (int i = 0; i < currency.length; i++) {
if (amount >= currency[i]) {
amount -= currency[i];
count[i]++;
i--;
}
if (amount == 0.0000) {
break;
}
}
return count;
}
public static void main(String[] args) {
double[] american_currency = {100,50,20,10,5,1,0.25,0.10,0.05,0.01};
//Japanese currency: https://www.boj.or.jp/en/note_tfjgs/note/valid/index.htm/
double[] japanese_currency = {10000,5000,2000,1000,500,100,50,10,5,1};
int[] american_change = optimal_change(american_currency, 78.36);
int[] japanese_change = optimal_change(japanese_currency, 793048);
System.out.println("Optimal change for: .38");
for (int i = 0; i < american_currency.length; i++) {
if (i <= 5) {
System.out.println(Integer.toString(american_change[i]) + " $" + Double.toString(american_currency[i]));
} else {
System.out.println(Integer.toString(american_change[i]) + " " + Double.toString(american_currency[i]) + "¢");
}
}
System.out.println("--------------------------");
System.out.println("Optimal change for: ¥793040");
for (int i = 0; i < japanese_currency.length; i++) {
System.out.println(Integer.toString(japanese_change[i]) + " ¥" + Double.toString(japanese_currency[i]));
}
}
正确结果:
输入:78.37
输出:
最佳零钱:78.37 美元
0 100.0 美元
1 50.0 美元
1 20.0 美元
0 10.0 美元
1 $5.0
3 1.0 美元
1 0.25¢
1 0.1¢
0 0.05¢
2 0.01¢
不正确的结果:
输入:78.38
输出:
最佳零钱:78.38 美元
0 100.0 美元
1 50.0 美元
1 20.0 美元
0 10.0 美元
1 $5.0
3 1.0 美元
1 0.25¢
1 0.1¢
0 0.05¢
2 0.01¢
输出应该是:
最佳零钱:78.38 美元
0 100.0 美元
1 50.0 美元
1 20.0 美元
0 10.0 美元
1 $5.0
3 1.0 美元
1 0.25¢
1 0.1¢
0 0.05¢
3 0.01¢
正如其他人在评论中指出的那样,问题是由 Java double 值的“近似值”引起的。
在 BigDecimal 中更改它。
请参阅此 question 了解更多信息。
切换到 BigDecimal 似乎解决了这个问题。不知道为什么双打问题持续了这么久。但值得庆幸的是它有效。
import java.math.BigDecimal;
public class Greedy_Money_BigInteger {
public static int[] optimal_change(BigDecimal[] currency, BigDecimal amount) {
int[] count = new int[currency.length];
for (int i = 0; i < currency.length; i++) {
//if (amount >= currency[i]) {
if (amount.compareTo(currency[i]) >= 0) {
amount = amount.subtract(currency[i]);
count[i]++;
i--;
}
if (amount.compareTo(BigDecimal.valueOf(0)) <= 0) {
break;
}
}
return count;
}
public static void main(String[] args) {
BigDecimal[] american_currency = {BigDecimal.valueOf(100),BigDecimal.valueOf(50),BigDecimal.valueOf(20),BigDecimal.valueOf(10),BigDecimal.valueOf(5),BigDecimal.valueOf(1),BigDecimal.valueOf(0.25),BigDecimal.valueOf(0.10),BigDecimal.valueOf(0.05),BigDecimal.valueOf(0.01)};
//Japanese currency: https://www.boj.or.jp/en/note_tfjgs/note/valid/index.htm/
BigDecimal[] japanese_currency = {BigDecimal.valueOf(10000),BigDecimal.valueOf(5000),BigDecimal.valueOf(2000),BigDecimal.valueOf(1000),BigDecimal.valueOf(500),BigDecimal.valueOf(100),BigDecimal.valueOf(50),BigDecimal.valueOf(10),BigDecimal.valueOf(5),BigDecimal.valueOf(1)};
BigDecimal american_change_value = BigDecimal.valueOf(78.31);
BigDecimal japanese_change_value = BigDecimal.valueOf(793043);
int[] american_change = optimal_change(american_currency, american_change_value);
int[] japanese_change = optimal_change(japanese_currency, japanese_change_value);
System.out.println("Optimal change for: $" + american_change_value.toString());
for (int i = 0; i < american_currency.length; i++) {
if (american_change[i] > 0) {
if (i <= 5) {
System.out.println(Integer.toString(american_change[i]) + " $" + american_currency[i].toString());
} else {
System.out.println(Integer.toString(american_change[i]) + " " + american_currency[i].toString() + "¢");
}
}
}
System.out.println("--------------------------");
System.out.println("Optimal change for: ¥" + japanese_change_value.toString());
for (int i = 0; i < japanese_currency.length; i++) {
if (japanese_change[i] > 0) {
System.out.println(Integer.toString(japanese_change[i]) + " ¥" + japanese_currency[i].toString());
}
}
}
}