Странное поведение подсчета в простой программе внесения изменений

Итак, я сделал эту довольно простую программу оптимальных изменений, которая в большинстве случаев отлично работает. Но по какой-то странной причине он действует непоследовательно и иногда не добавляет последнюю необходимую копейку, но в других случаях это будет.

Я пробовал разные выходы, и код всегда выходит правильно, за исключением иногда последней копейки; при использовании американской валюты. Я уверен, что причина очевидна, но я ее просто не вижу.

   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: $78.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 currency greedy
person ziberteck    schedule 17.04.2019    source источник
comment
Не используйте дубли, когда требуется точный ответ. См. Главу Избегайте float и double, если в Эффективной Java требуются точные ответы. (пункт 48 здесь: the-eye .eu / public / Books / IT% 20Various /)   -  person    schedule 17.04.2019
comment
Я сильно подозреваю, что это потому, что вы используете double для обозначения валюты. Это имеет серьезные проблемы, потому что валюта, естественно, является десятичной, и не все десятичные значения могут быть точно представлены в двоичной системе с плавающей запятой. Например, значение 0,1 невозможно представить точно. Варианты: 1) используйте целые числа, представляющие количество центов (и т. Д.), А не долларов. 2) используйте BigDecimal, который является десятичным типом с плавающей запятой.   -  person Jon Skeet    schedule 17.04.2019

Ответы (2)


arrow_upward
0
arrow_downward

Переход на 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());
            }
        }


    }
}
person ziberteck    schedule 18.04.2019

arrow_upward
-1
arrow_downward

Как отмечали другие люди в комментариях, проблема вызвана «аппроксимацией» Java значений двойника.

Измените его в BigDecimal.

Обратитесь к этому вопросу для получения дополнительной информации.

person Capo80    schedule 17.04.2019