Метод работает следующим образом:
Первые заявления являются условием остановки для текущего рекурсии (без них для всех случаев, то вы в конечном итоге с бесконечным циклом, который в конечном счете закончится в StackOverflow)
Последняя строка - это расчеты. Каждый из утверждений уменьшает проблему на более мелкие куски с помощью:
count(S, m - 1, n) уменьшает количество монет (m-1), которая исключает последнюю монету в следующем рекурсивном вызове кcount(S, m, n-S[m-1]) использует последнюю монету в массиве и уменьшает сумму, которая необходимо достичь на величину этой монеты
Рассмотрим небольшой пример:
S[] = {1,2) // We have a 1 and 2 cent coin
m = S.length // Consider all possibilities (= 2)
n = 3 // How many ways can we make 3c
// Obviously with: 1x1c + 1x2c
// and: 3x1c
Рекурсия как дерево; Левая ветвь = count(S, m - 1, n), правая ветвь = count(S, m, n-S[m-1]):
m=2;n=3
/ \
m=1;n=3 m=2;n=1
/ \ / \
m=0;n=3 m=1;n=2 m=1;n=1 m=2;n=-1
/ \ / \
m=0;n=2 m=1;n=1 m=0;n=1 m=1;n=0
/ \
m=0;n=1 m=1;n=0
Это рекурсии можно рассматривать как Pre-order Traversal этого дерева.
Если вы затем рассмотрите условия метода, в котором найдено решение, или нет. Поэтому на листовых узлах, где n = 0.
Каждый который приходит примерно так:
Первое решение
- т = 1; п = 3 - Исключить последнюю монету (2c)
- т = 1; п = 2 - Использование эту монету (1c) и уменьшить на 1
- m = 1; n = 1 - Используйте эту монету (1c) и уменьшите на 1
- m = 1; n = 0 - Используйте эту монету (1c) и уменьшите на 1
- n = 0 - as olution (3x1c)
Второе решение
- т = 2; п = 1 - Используйте эту монету (2c) и уменьшить на 2
- т = 1; п = 1 - Исключить последний монета (2c)
- т = 1; п = 0 - Используйте эту монету (1c) и уменьшить на 1
- п = 0 - раствор (1x2c + 1x2c)
В каждом узле значение является return - 0 (без решения) или 1 (решение) - для добавления общего количества найденных решений. Как только рекурсия заканчивается, возвращается это окончательное значение и количество решений.
Некоторые дополнительные примечания:
- Этот фрагмент кода будет рассматривать только первые
m монеты в массиве S так, чтобы рассмотреть все возможные пути первоначальный вызов метода должен иметь m == S.length
- Предполагается, что каждая монета может быть использована несколько раз
Код модификации с заявлениями для печати, чтобы увидеть рекурсии:
public static void main(String[] args){
int[] coins = new int[]{1,2};
System.out.println("Final Count = " + count(coins, coins.length, 3, ""));
}
public static int calls = 0;
public static int count(int S[], int m, int n , String from){
calls++;
System.out.print("Call#" + calls + ": " + from + "; m = " + m + "; n = " + n);
// If n is 0 then there is 1 solution (do not include any coin)
if (n == 0)
{
System.out.println(" - Solution Found");
return 1;
}
// If n is less than 0 then no solution exists
if (n < 0)
{
System.out.println(" - No Solution Found n < 0");
return 0;
}
// If there are no coins and n is greater than 0, then no solution exist
if (m <=0 && n >= 1)
{
System.out.println(" - No Solution Found (other Case)");
return 0;
}
System.out.println();
// count is sum of solutions (i) including S[m-1] (ii) excluding S[m-1]
return count(S, m - 1, n , from + "E") + count(S, m, n-S[m-1], from + "I");
}
Как это называется? Что такое S? – Behe
@Behe Похоже, что массив монет суммирует –
@ Java Devil точно, он выглядит как массив целых чисел – user3185735