이 재귀 함수 이해하기

Question

이 재귀 함수를 변경/개선하고 있습니다. 내 의도는 전역 클래스 변수 nrOfFails를 추가하여 검색이 실패한 모든 반복을 저장하는 것입니다.

{ 
    ArrayList<Integer> solutions = new ArrayList<>(); 
    int[] money1= {2,2,2,5,10,10,20} 
    int targe1 = 24 
    System.out.print(solutions(money1,target1,solutions)) 
} 

/** 
    * Returns the number of ways of creating specified target value as a sum of money starting with c 
    * @param money the set of coins 
    * @param c Index of the array 
    * @param target the amount to give back 
    * @return number of ways 
    */ 
    private static int solutions(int[] money, int c, int target, ArrayList<Integer> s) 
    { 
    assert money!=null : "array should be initialized"; 
    assert c>=0&&c<=money.length; 
    nrOfFails = 0; 

    if(target==0) 
    { 
     showSolution(s); 
     return 1; 
    } 
    if(target<0) 
     return 0; 
    if(c>=money.length) 
     return 0; 
    else 
    { 
     s.add(money[c]); 
     int with = solutions(money, c + 1, target - money[c], s); 
     s.remove(s.size()-1); 
     int without = solutions(money, c + 1, target,s); 
     return with + without; 
    } 
    } 

    private static void showSolution(ArrayList<Integer> s) 
    { 
    System.out.print(s); 
    } 

내가 실패의 반복을 '계산'의 원시적 방법을 함께했다, 그러나 나는이 문제를 해결하기 위해 재귀를 사용하고자 다음과 같이

은 내가 함수를 호출합니다.

원시 솔루션과 같습니다. 어떤 반복에서든 돈의 내용이 목표 수량의 배수를 포함하지 않는 값인지를 확인하려고 시도했지만 그 다음에 헛수고로 검색했습니다. for와 counter를 사용하여 공통 배수가 있었는지 여부를 확인하고, 없으면 아무 것도 검색하지 않았습니다.

Answer 1

"조사가 실패한 반복"을 생각해 봅시다.

이러한 경우 중 하나는 재귀 호출에 target (즉, solutions(money, c + 1, target - money[c], s) 재귀 호출의 경우 target - money[c] < 0을 의미)을 전달할 때입니다.

또 다른 경우는 목표 합계에 도달하기 전에 배열 요소가 부족한 경우입니다 (예 : c >= money.length).

따라서이 두 가지 경우에 nrOfFails 카운터를 증가시켜야합니다. 나는 코드 단축하기 위해, 하나의 상태로 그들을 통합 :

static int nrOfFails = 0; 
private static int solutions(int[] money, int c, int target, ArrayList<Integer> s) 
{ 
    assert money != null : "array should be initialized"; 
    assert c >= 0 && c <= money.length; 

    if (target == 0) { 
     showSolution(s); 
     return 1; 
    } else if (target < 0 || c >= money.length) { 
     nrOfFails++; 
     return 0; 
    } else { 
     s.add(money[c]); 
     int with = solutions(money, c + 1, target - money[c], s); 
     s.remove(s.size() - 1); 
     int without = solutions(money, c + 1, target, s); 
     return with + without; 
    } 
} 

당신은 이전에 solutions의 최초의 호출에 0에 정적 변수를 재설정해야합니다.

재귀 메서드를 처음 호출 할 때 c 인수를 잊어 버렸습니다. 나는 그것을 여기에 추가했다.

[2, 2, 10, 10] 
[2, 2, 20] 
[2, 2, 10, 10] 
[2, 2, 20] 
[2, 2, 10, 10] 
[2, 2, 20] 
6 
number of fails = 110 

:

nrOfFails = 0; 
ArrayList<Integer> solutions = new ArrayList<>(); 
int[] money1= {2,2,2,5,10,10,20}; 
int target = 24; 
System.out.println(solutions(money1,0,target,solutions)); 
System.out.println ("number of fails = " + nrOfFails); 

이것은 다음과 같은 출력을 생성한다 : 또한 리셋 인쇄 nrOfFails 첨가