두 개의 정렬 된 배열

Question

나는 다음과 같은 문제에 근무하고 this question in stackoverflow에 응답으로 제공되는 재귀 솔루션을 다음 후 모든 결과 배열을 점점 방법을 이해하지 않았다 요소를 교대에서 가능한 모든 정렬 된 배열을 생성 문제는 다음과 같습니다. 두 개의 정렬 된 배열 A와 B가있는 경우 첫 번째 요소가 A에서 가져온 다음 B에서 가져온 다음 A부터 배열 순서대로 배열이 고갈 될 때까지 모든 가능한 배열을 생성합니다. A = {10, 15, 25} B가

얻어진 배열은 {1, 5, 20, 30}이다 = : [생성 된 배열 B.

예에서 요소로 끝나야 10 ~ 20], [10 20 25 30], [10 30], [15 20], [15 20 25 30], [15 30], [25 30] 제안 된 해결책 :

public static void main(String[] args) { 

    int[] A = {10, 15, 25}; 
    int[] B = {1, 5, 20, 30}; 

    Stack<Integer> st = new Stack<>(); 

    for (int i = 0; i < A.length; i++) { 
     st.push(A[i]); 
     generateArrays(A, B, i, 0, st, false); 
     st.clear(); 
    } 
} 

static void generateArrays(int ar1[], int ar2[], int index_of_a, int index_of_b, Stack<Integer> st, boolean first) { 
    if (index_of_a >= ar1.length || index_of_b >= ar2.length) { 
     st.pop(); 
     return; 
    } 

    // take from second if available 
    if (!first) { 
     for (int j = index_of_b; j < ar2.length; j++) { 
      if (ar1[index_of_a] < ar2[j]) { 
       st.push(ar2[j]); 
       System.out.println(st); 
       generateArrays(ar1, ar2, index_of_a + 1, j, st, true); 
      } 
     } 
    } 

    // take from first if available 
    else if (first) { 
     for (int i = index_of_a; i < ar1.length; i++) { 
      if (ar1[i] > ar2[index_of_b]) { 
       st.push(ar1[i]); 
       generateArrays(ar1, ar2, i, index_of_b + 1, st, false); 
      } 
     } 
    } 

    st.pop(); 
} 

주어진 입력 예제로 직접 알고리즘을 실행 한 후에는 [10 30], [15 30]을 얻지 못했습니다. 배열. B의 및 인덱스 인덱스 내로 진행되지 I 또는 J의 루프마다 감소되는

그래서,이뿐만 아니라, 코드를 디버깅하여 이해하려고 발견 첫 번째 값은 a = 0의 인덱스와 b = 1의 인덱스를 얻을 때까지 값을 변경합니다. 왜 그런 일이 발생합니까? algortihm 처형의 흐름에서 나는 무엇을 놓치고 있습니까? 알고리즘은 출력에서 ​​[10 30], [15 30]을 어떻게 얻습니까?

Answer 1

generateArrays()를 호출 할 때마다 스택이 팝되므로 (스택은 객체이므로 모든 메소드 호출에서 동일 함) 원래 상태로 돌아가므로 각 후 for 루프의 반복은 스택이 이전과 동일했다.

e.e. 수행 :

st.push(ar1[i]); 
    generateArrays(ar1, ar2, i, index_of_b + 1, st, false); 

스택에 영향을주지 않습니다.

맨 처음 통화 : generateArrays(A, B, i, 0, st, false);

3 방법이 루프에서 호출 생성

for (int i = index_of_a; i < ar1.length; i++) { 
     if (ar1[i] > ar2[index_of_b]) { 
      st.push(ar1[i]); 
      generateArrays(ar1, ar2, i, index_of_b + 1, st, false); 
     } 
    } 

스택 함유 값 [10]을

, [15] 및 [25].

[10,30]

스택이 [10]는 종래 루프로 진행하여 2 개 통화 생성 스택 함유 값 [10

for (int j = index_of_b; j < ar2.length; j++) { 
     if (ar1[index_of_a] < ar2[j]) { 
      st.push(ar2[j]); 
      System.out.println(st); 
      generateArrays(ar1, ar2, index_of_a + 1, j, st, true); 
     } 
    } 

을 20], [10, 30]을 볼 수있는 것처럼 그들을 인쇄합니다.

[15, 30]

스택이 [15]는 종래 루프로 진행하여 2 개 통화 생성 스택 함유 값 [15

for (int j = index_of_b; j < ar2.length; j++) { 
     if (ar1[index_of_a] < ar2[j]) { 
      st.push(ar2[j]); 
      System.out.println(st); 
      generateArrays(ar1, ar2, index_of_a + 1, j, st, true); 
     } 
    } 

을 20], [15, 30] 그리고 그들을 인쇄합니다.

generateArrays가 즉시 나타납니다 중 하나 (기본 케이스) :

편집 : generateArrays 항상 한 번 더 팝업으로 끝나는 이유를 더 설명하기

if (index_of_a >= ar1.length || index_of_b >= ar2.length) { 
    st.pop(); 
    return; 
} 

또는 끝에 팝업 :

st.pop(); 

모두 push + generateArrays은 스택을 변경하지 않고 +1 푸시와 +1 팝 (위의 인수 당)이됩니다.