рекурсивный алгоритм поиска наименьшего элемента в массиве

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]
}

Одна часть, которую я не понимаю в этом псевдокоде, - это строка "temp <- Min (A [0..n - 2])". В частности, почему в рекурсивном вызове указано «n - 2», а не «n - 1»? </p>

Мой другой вопрос - как мне реализовать эту строку в коде. Я использую Java.

Заранее спасибо за любую помощь.

Answer 1

Поскольку ваш массив проиндексирован от 0 до n-1 включительно.Вам нужно найти массив, который на один элемент меньше, следовательно, n-2.

Answer 2

для вашего 1-го вопроса:

, так как вы используете рекурсивный алгоритм, чтобы решить проблему, сначала нужно решить ту же проблему с меньшим размером.В этом псевдокоде для нахождения минимума массива с длиной n сначала определяется минимум этого же массива с размером n-1, а затем минимум сравнивается с n-м элементом.Ваш массив индексируется от 0 до n-1 (что делает его длину = n), поэтому для рекурсивного вызова вы должны вызывать массив от индекса 0 до n-2 (n-1 элементов).на ваш 2-й вопрос: вот как бы я реализовал код на Java:

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];
    }
}

}

Answer 3

Мой другой вопрос - как мне реализовать эту строку в коде.

Если вы используете массив.

// 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);