Переписать getLargest в рекурсивный метод в Java - PullRequest
Новая
       40

Переписать getLargest в рекурсивный метод в Java

1 голос
/ 17 октября 2011

Я выполняю это задание, и мне трудно рекурсивно писать этот метод. У меня есть такой способ, который эффективен, но не рекурсивен: 

public static <T extends Comparable< ? super T>> T getLargest(T [] a, int low, 
              int high)
{
    if(low>high)
            throw new IllegalArgumentException();
    return Collections.max(Arrays.asList(Arrays.copyOfRange(a, low, high)));

Итак, оттуда я пошел к этому, который расширяет его, но также не является рекурсивным: 

T[] arrCopy = (T[]) new Object[high-low];
    for(int i=low;i<high;i++){
        if(a[i].compareTo(a[i-1])>0)
            arrCopy[i]=a[i];
        else
            arrCopy[i]=a[i+1];
    }
    return arrCopy[0];

И я работал над этим часами и не могу представить способ сделать его рекурсивным и заставить его работать. Любая помощь и идеи с благодарностью!

Ответы [ 4 ]

0 голосов
/ 18 октября 2011

Хорошо, пока это не вышло из-под контроля, вот простое итеративное и эквивалентное ему рекурсивное решение - реализованное с помощью int, хотя, поэтому вам придется немного его изменить;) 

public static int getLargest(int[] vals) {
    int max = vals[0];
    for (int i = 1; i < vals.length; i++) {
        max = Math.max(max, vals[i]);
    }
    return max;
}

public static int getLargestRec(int[] vals) {
    return getLargestRec(vals, 0, vals.length);
}

private static int getLargestRec(int[] vals, int low, int high) {
    if (low + 1 == high) {
        return vals[low];
    }
    int middle = low + (high - low) / 2;
    int left = getLargestRec(vals, low, middle);
    int right = getLargestRec(vals, middle, high);
    return Math.max(left, right);
}

public static void main(String[] args) {
    int[] vals = {5, 23, 32, -5, 4, 6};
    System.out.println(getLargestRec(vals));
    System.out.println(getLargest(vals));
}

Обратите внимание, что, как обычно для рекурсивных задач, нижняя граница является включающей, а верхняя - исключительной. Также мы могли бы реализовать это и по-другому, но обычный подход «разделяй и властвуй» довольно полезен и прекрасно подходит для распараллеливания с помощью структуры fork, так что это нормально. (И да для пустого массива обе версии потерпят неудачу)

0 голосов
/ 17 октября 2011

Во-первых, подпись вашего метода неверна.Вам не нужно «низкий».Вы должны взять массив / список в качестве входных данных и вернуть самый большой элемент.Однако вы можете обнаружить, что вам нужен дополнительный метод, требующий дополнительных аргументов.

Когда вы подходите к рекурсии, и вы застряли, часто лучше сначала определить базовый (-ые) случай (-ы), а затем разобраться с рекурсивным случаем (s) следующий.

Ваш базовый случай - самый простой случай, в котором вы знаете ответ.В этой задаче вы сразу знаете, какой самый крупный элемент, если размер вашего списка равен 1 - вы просто возвращаете единственный элемент.Возможно, вы захотите подумать о случае, когда ваш список также пуст.

Тогда ваш рекурсивный случай - это когда ваш список имеет размер больше 1. В вашем рекурсивном случае вы хотите попробовать и «разбитькусать », а затем отправить остальное на рекурсивный вызов.В этом случае вы можете посмотреть на первый элемент в списке и сравнить его с результатом, который вы получите от рекурсивного вызова в остальной части списка.

0 голосов
/ 17 октября 2011

Это был бы правильный ответ: 

T tmp = a[low];
    for(int i=0;i<=high;i++){
        if(a[i].compareTo(tmp)>0){
            tmp = a[i];
            getLargest(a,i,high);               
        }
    }
    return tmp;
0 голосов
/ 17 октября 2011

Хорошо, вот шаблон для преобразования цикла for в метод с хвостовой рекурсией: 

//iterative version
public Object getIteratively(Object[] a) {
   Object retVal = null;
   for (int i = 0; i < a.length; a++ ) {
      //do something
   }
   return retVal;
}

//recursive version
public Object getRecursively(Object[] a) {
    doGetRecursively(a, 0, null);
}

private Object doGetRecursively(Object[] a, int i, Object retVal) {
   if ( i == a.length ) {
      return retVal;
   }
   //do something
   return doGetRecursively(a, i+1, retVal);
}

Почему вы захотите сделать это на нефункциональном языке, я не знаю.

В этом случае //do something будет одинаковым в обоих случаях, например ::100100 

if ( a[i].compareTo(retVal) > 0 ) {
   retVal = a[i];
}
...