Отклонение мин. Опции для суммирования числа с использованием 1, 5 и 7 через рекурсию - JAVA - PullRequest
Новая
       73

Отклонение мин. Опции для суммирования числа с использованием 1, 5 и 7 через рекурсию - JAVA

0 голосов
/ 05 февраля 2019

Я хочу создать рекурсивную функцию, которая возвращает минимальные параметры для создания определенного числа, используя числа 1, 5 и 7 (фиксированные предварительно определенные числа).Важно, чтобы это делалось только путем рекурсии без циклов вообще.

Например:

если n = 10, то это дается схеме 5 +5, это 2 числа, так что это минимум, и это то, что мы получим (в отличие от 7 + 1 + 1 + 1 или 5 + 1 + 1 + 1 + 1 + 1, что составляет 4 или 6 вариантов, которые длиннее).

Если n = 6, то мы получаем результат 2 (потому что он дается как сумма 1 + 5).

Если n = 5 (или 7 или 1), томы получаем результат 1 (потому что он дается только числом). 

class TEST { 

static int countMin( int S[], int m, int n ,int min) 
    { 
        if (n == 0) 
            return 1;      
        if (n < 0) 
            return 0; 
        if (m <=0 && n >= 1) 
            return 0; 
        return Math.min(min,countMin( S, m - 1, n ,min-1) + countMin( S, m, n-S[m-1],min-1 )); 
    } 

public  static int f(int n)  {
      int arr[] = {1, 5, 7};  
      return countMin(arr, arr.length, n,n);
} 

    public static void main(String[] args) 
    { 
        int n = 10;
        System.out.println("The number "+n+ " - " + f(n) + " minimum options to create");
        int n2 = 7;
        System.out.println("The number "+n2+ " - " + f(n2) + " minimum options to create"); 
        int n3 = 6;
        System.out.println("The number "+n3+ " - " + f(n3) + " minimum options to create");

    } 

}

Я получаю для n = 10 и n = 5 для правильного результата, но не для n = 6, который должен вернуть 2.

* Я использовал эту ссылку: https://www.geeksforgeeks.org/coin-change-dp-7/

1 Ответ

0 голосов
/ 06 февраля 2019

Представьте себе дерево, в котором каждый узел имеет значение и имеет 3 дочерних элементов, значение которых уменьшено соответственно на 7, 5 и 1

Таким образом, у узла с общим числом 15 будут дочерние элементы со значениями 8, 10, 14

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

Например, для 10: 

                10
            /    |    \
        3        5       9
      / | \    / | \   / | \
    -4 -2 2   -2 0 4   2 4 1

Мы находим ноль на глубине 2 

private static int calculate(int total, int depth) {
    if (total == 0)
        return depth;
    else {
        int i = total - 7  >= 0 ? calculate(total - 7, depth+1) : Integer.MAX_VALUE;
        int j = total - 5  >= 0 ? calculate(total - 5, depth+1) : Integer.MAX_VALUE;
        int k = total - 1  >= 0 ? calculate(total - 1, depth+1) : Integer.MAX_VALUE;
        return Collections.min(Arrays.asList(i, j, k));
    }
}

This 

int n = 10;
System.out.println("The number "+n+ " - " + calculate(n, 0) + " minimum options to create");
n = 7;
System.out.println("The number "+n+ " - " + calculate(n, 0) + " minimum options to create");
n = 6;
System.out.println("The number "+n+ " - " + calculate(n, 0) + " minimum options to create");
n = 18;
System.out.println("The number "+n+ " - " + calculate(n, 0) + " minimum options to create");

Выводит это 

The number 10 - 2 minimum options to create
The number 7 - 1 minimum options to create
The number 6 - 2 minimum options to create
The number 18 - 4 minimum options to create

РЕДАКТИРОВАТЬ: То же самое в стиле фанк лямбда: 

private static int calculate(int total, int depth) {
    return total == 0 ? 
        depth : 
        Stream.of(7, 5, 1)
              .map(i -> total - i  >= 0 ? calculate(total - i, depth+1) : Integer.MAX_VALUE)
              .min(Integer::compare)
              .get();
}
...