Рекурсивный подход к поиску всех способов изменить купюру в 5 евро?

Question

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

Мой подход был основан на следующем:

500 можно разделить на 200, 200 и 100. 200 можноделится на 100 и 100. 100 можно разделить на 50 и 50.

После того, как я написал свой код, я понял, что 100 также можно разделить на 5 20. Это ошибка, о которой я знаю, но я не знаю, как исправить ее, используя мой подход.

Мой подход был рекурсивным, как можно видеть ниже, он просто проверяет первую цифру и делит ее соответственно.

Вот что я попробовал:

public class Q1 {

    public static int counter;

    public static void main(String[] args) {

        divide(500);
        System.out.println(counter);

    }

    private static void divide(int x) {


        System.out.println("Dividing " + x);


        if(x == 1) {
            return;
        }

        counter++;

        int length = String.valueOf(x).length();

        int fd = Integer.parseInt(Integer.toString(x).substring(0, 1));
        String zeros;

        if(fd != 1) {
            zeros = Integer.toString(x).substring(1, length);
        }else {
            zeros = Integer.toString(x).substring(1, length-1);
        }


        if(fd == 5) {
            divide(Integer.parseInt(2 + "" + zeros));
            divide(Integer.parseInt(2 + "" + zeros));
            divide(Integer.parseInt(1 + "" + zeros));
        }else if(fd == 2) {
            divide(Integer.parseInt(1 + "" + zeros));
            divide(Integer.parseInt(1 + "" + zeros));
        }else if(fd == 1) {
            divide(Integer.parseInt(5 + "" + zeros));
            divide(Integer.parseInt(5 + "" + zeros));
        }


    }

}

Например, при использовании вышеуказанной программы пропускает

10 = 2 + 2 + 2 + 2 + 2

Мне известны уже существующие рабочие решения , подобные этому , но я хотел бы сохранить свой подход, если это возможно.

Использование программы для поиска комбинаций для результатов 500 центов 388 способов,где правильный ответ 6295435. Что-то подсказывает мне, что я забыл что-то еще, кроме приведенного выше примера.

Answer 1

Вот несколько советов о том, почему вы получаете неправильное число:

Правильный способ определения всех возможностей

---

Попробуйте разделить 5 вместо 500 для простоты. Обратите внимание, что существует 4 варианта: 5 =

1. 5
2. 2 + 2 + 1
3. 2 + 1 + 1 + 1
4. 1 + 1 + 1 + 1 + 1

Теперь попробуйте разделить 10 вместо 500. Обратите внимание, что это можно разделить на 11 различных способов: 10 =

1. 10
2. 5 + 5
3. 5 + 2 + 2 + 1
4. 5 + 2 + 1 + 1 + 1
5. 5 + 1 + 1 + 1+ 1 + 1
6. 2 + 2 + 2 + 2 + 2
7. 2 + 2 + 2 + 2 + 1 + 1
8. 2 + 2 + 2 + 1 +1 + 1 + 1
9. 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1
10. 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
11. 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

Это решение следует следующей схеме: число x, которое вы хотите разделить, уже являетсяответ. Уменьшите количество младших чисел на 1, разделив одно из этих чисел на максимально возможное число следующих чисел. Всегда игнорируйте их. Если осталось только одно число (и единицы), разделите x на максимально возможное число следующих наименьших чисел и продолжайте.

Например, x = 10. Затем: 10 - наименьшее число -> разделите егона 5 + 5 -> 5 - это наименьшее число -> разделить его на 2 + 2 + 1 -> 2 - наименьшее число, так как единицы игнорируются -> разделить его на 1 + 1 -> у нас есть еще 2, разделитьэто до 1 + 1 (это равно решению 5 + 1 + 1 + 1 + 1, так что теперь у нас есть 5 как только одно число, кроме единиц. Следующее наименьшее число равно 2) -> разделить x = 10 на 2 +2 + 2 + 2 + 2 -> 2 - наименьшее число;разделите его на 1 + 1 -> у нас есть еще 2 ...

Это можно сделать рекурсивным подходом.

Что не так в вашем коде

---

То, что вы делаете с примером деления 10, выглядит следующим образом:

1. 10 делится на 5 + 5
2. , первые 5 делятся на 2 + 2 + 1
3. одна из этих двойок делится на 1 + 1
4. , остальные две делятся на 1 + 1
5. Теперь вторые 5 из деления на 5 + 5 делятсяна 2 + 2 + 1
6. Одна из этих двойок делится на 1 + 1
7. Две другие делятся на 1 + 1

Предоставление всегооценка 7 возможностей. Пытаясь сопоставить эти 7 возможностей с 11 приведенными выше, вы считаете 10 =

• 10 один раз
• 5 + 5 один раз
• 5 + 2 + 2 + 1 дважды
• 5 + 2 + 1 + 1 + 1 дважды
• 5 + 1 + 1 + 1 + 1 + 1 дважды

и пропущены остальные 6 опций.

---

Таким образом, предположение, что этот вопрос может быть решен с помощью такого подхода, как этот:

10 = 5 + 5 -> оцените первые 5, затем оцените вторые 5

неверно, потому что в обоих случаях это приводит к распределению 10 = 5 + оценка 5, считая только те варианты, в которых хотя бы один 5 содержится в окончательном распределении 10 (считая его многократно, без распределения пятерок). не оцениваются).

---

Другая ошибка заключается в том, что в коде сказано, что нет возможного распределения 1, если оно действительно существует (1 = 1). Кроме того, неясен вопрос о том,

• может ли х равняться всем возможным целым числам? -> 4 не делится на 2 + 2 в вашем коде
• - это 1 + 1 + 2, отличное от 1 + 2 + 1 и 2 + 1 + 1?

(У меня пока нет репутации спрашивать об этом в комментарии).

---

Оставить рекурсивный подход можно только с некоторыми существенными изменениями. Возможный способ сделать это указан выше.