Проблема с изменением монеты Java с использованием рекурсии не работает

Я искал код и логику для этого и в основном скопировал код с https://www.youtube.com/watch?v=k4y5Pr0YVhg и https://www.techiedelight.com/coin-change-problem-find-total-number-ways-get-denomination-coins/

Но моя программа неверна, потому что определенно есть более двух способов набрать 2 фунта.

public class TwoPounds
{
    private static int[] coins = {1, 2, 5, 10, 20, 50, 100, 200};
    private static int amount;
    private static int count;

    public TwoPounds()
    {
        amount = 2;
        count = 0;
    }

    public static void main(String[] args)
    {
        TwoPounds run = new TwoPounds();
        count = run.combos(amount);
        run.printOut();
    }

    public int combos(int amountIn)
    {       
        if (amountIn == 0)
        {
            return 1;
        }

        if (amountIn < 0)
        {
            return 0;
        }

        int combosCount = 0;

        for(int i = 0; i < coins.length; i++)
        {
            System.out.println("amountIn now is " + amountIn);
            combosCount += combos(amountIn - coins[i]);
        }
        return combosCount;
    }

    public void printOut()
    {
        System.out.println("\n\n\n");
        System.out.println("There are " + count + " ways can 2 pounds be made, "
            + "using any number of coins");
        System.out.println("\n\n\n");
    }
 }

Вывод:

There are 2 ways can 2 pounds be made, using any number of coins


java arrays recursion algorithm coin-change
person Stacey Lee    schedule 06.10.2019    source источник
comment
Общий комментарий: вместо того, чтобы заимствовать код, заимствовайте концепции, а затем используйте их для написания собственного кода. Даже если вы не получите ответ, вы сможете написать лучший вопрос.   -  person Hovercraft Full Of Eels    schedule 07.10.2019

Ответы (2)


arrow_upward
0
arrow_downward

Ваши coins выражены в центах (или пенсах, поскольку я предполагаю, что вы используете британские фунты), поэтому, поскольку вы выполняете amountIn - coins[i] с ними, это означает, что ваша сумма также равна центам/пенсам.

Итак, измените сумму на:

amount = 200;

Стоит уделить немного времени тому, чтобы подумать об именовании переменных и о том, как это могло бы помочь выявить или даже полностью избежать этой проблемы. Термины «сумма» и «суммаВ» неоднозначны.

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

например, если переменные были названы 'amountInPounds', то ошибка становится более очевидной при записи amountInPounds - coins[i]

Теперь, прежде чем выполнять обновление до amount = 200;, имейте в виду, что:

1) Будет БОЛЬШОЕ количество результатов (200 пенсов, 198 пенсов + 2 пенса), для повторения которых потребуется некоторое время по одному пенсу за раз, плюс

2) Ваш код в настоящее время написан для прохождения КАЖДОЙ дискретной упорядоченной комбинации - например, он будет считать:

  • 198 "1 цент" + 1 "2 цента"
  • 197 «1 цент» + 1 «2 цента» + 1 «1 цент»
  • 196 «1 цент» + 1 «2 цента» + 2 «1 цент»
  • 195 «1 цент» + 1 «2 цента» + 3 «1 цент» и т. д.

Опять же, НАМНОГО слишком много времени выполнения. Что вы хотите, так это не запускать for(int i = 0; i < coins.length; i++) с нуля каждый раз, а вместо этого добавлять дополнительный параметр к combos - что-то вроде:

public int combos (int amountIn, int startCoin)
{       

    // blah ... existing code ... blah

    for(int i = startCoin; i < coins.length; i++)
    {
        System.out.println("amountIn now is " + amountIn);
        combosCount += combos(amountIn - coins[i], i);
    }

Наконец, как я уже говорил ранее, 200 приведут к БОЛЬШИМ числам, которые вам будет практически невозможно подтвердить правильность, поэтому вместо этого начните с небольших сумм, которые вы можете проверить.

person racraman    schedule 07.10.2019

arrow_upward
-1
arrow_downward

Этот алгоритм позволяет использовать несколько монет одного номинала, поэтому есть 2 способа заработать 2 фунта:

  1. {1, 1}
  2. {2}
person Артур Газизов    schedule 06.10.2019