배열에서 가장 작은 요소를 찾는 재귀 알고리즘

Question

배열에서 가장 작은 수를 찾는 재귀 알고리즘에 대한 의사 코드가 있습니다.

다음은 알고리즘입니다. 나는이 의사 코드에 대해 이해하지 못하는

Min(A[0..n - 1]) 
If n = 1 return A[0] 
else 
{ 
    temp <-- Min(A[0..n - 2]) 
    if temp <= A[n - 1] 
    return temp 
    else return A[n - 1] 
} 

한 부분은 라인 "- 최소 (A [0..N - 2]) 온도 <"입니다. 특히 "n - 1"대신 재귀 호출에서 "n - 2"인 이유는 무엇입니까?

내 다른 질문은 코드에서 해당 줄을 구현하는 방법입니다. 자바를 사용하고 있습니다.

미리 도움을 청하십시오.

Answer 1

배열의 인덱스가 0부터 n-1까지이므로 하나의 요소가 더 작은 하위 배열에서 재귀해야하므로 n-2가됩니다.

Answer 2

내 다른 질문은 어떻게 그 코드에서 코드를 구현할 것입니다.

배열을 사용하는 경우.

// create an array with one less element. 
A a2 = new A[a.length-1]; 
// copy the elements 
System.arrayCopy(a,0,a2,0,a2.length); 

당신이 당신의 첫번째 질문에 대한 목록

List<A> a2 = a.subList(0, a.length-1); 

Answer 3

를 사용하는 경우 :

이 문제를 해결하기 위해, 재귀 알고리즘을 사용하고 있기 때문에, 먼저 해결해야 더 작은 크기와 같은 문제. 이 의사 코드에서 길이가 n 인 배열의 최소값을 찾으려면 먼저 n-1 크기의 동일한 배열의 최소값을 찾은 다음 최소값을 n 번째 요소와 비교합니다. 배열의 인덱스는 0에서 n-1 (길이가 n이됩니다)이므로 재귀 호출의 경우 인덱스 0에서 n-2 (n-1 요소)까지 배열을 호출해야합니다. 당신의 두번째 질문에 대한

:

public class Minimum { 
    public Minimum(int[] A) { 
    findMin(A, 0, A.length-1); 
} 

public int findMin(int [] A, int start, int end){ 
    if (start== end-1) 
     return A[0]; 
    else{ 
     int temp=findMin(A, start, end-1); 
     if (temp<=A[end]) 
      return temp; 
     else 
      return A[end]; 
    } 
} 

}