Нахождение максимального целого числа в массиве с указанием начального и конечного индексов в Java, ** рекурсивно ** - PullRequest
Новая
       9

Нахождение максимального целого числа в массиве с указанием начального и конечного индексов в Java, ** рекурсивно **

1 голос
/ 19 апреля 2020

Для чего-то, над чем я работаю, мне нужно иметь целочисленный массив и получить два индекса от пользователя. Один из них является отправной точкой в ​​массиве, а другой - конечной точкой. С этими двумя точками я должен найти максимальное значение в массиве, рекурсивно. Код, который у меня сейчас есть, работает, но я чувствую, что есть вещи, которые могли бы сделать его более свободным, и, возможно, даже я мог бы сделать что-то другое, чтобы избавиться от некоторого бесполезного кода. Я опубликую свой код ниже. 

import java.util.Scanner;

public class RecursiveProblem {

    public static void main(String args[]) {
        int start, end, size, max;
        Scanner scan = new Scanner(System.in);

        System.out.println("How many numbers would you like to enter in total?");
        size = scan.nextInt();
        int[] myArray = new int[size];

        System.out.println("Please enter the specified starting index.");
        start = scan.nextInt() - 1;

        System.out.println("Please enter the specified ending index.");
        end = scan.nextInt() - 1;

        System.out.println("Please enter " + size + " integers seperated by a space, or press "
                + "enter after each number: ");
        for(int i = 0; i < myArray.length; i++) {
            myArray[i] = scan.nextInt();
        }
        scan.close();

        max = myArray[start];

        max = findMax(myArray, start, end, max);

        System.out.println("The max of your array between the indices of " + (start + 1) +
                "-" + (end + 1) + " is..." + max);

    }

    public static int findMax(int[] myArray, int start, int end, int max) {
        if(start < end) {
            if(myArray[start + 1] > max) {
                start++;
                max = myArray[start];
                return findMax(myArray, start, end, max);
            }
            else {
                start++;
                return findMax(myArray, start, end, max);
            }
        }
        return max;
    }
}

Одна вещь, в которой я в основном смущен, но не единственный вопрос, который у меня возникает, - всякий раз, когда я решаю поместить команду start ++ в вызов функции для findMax (myArray, start ++, end, max) <- (вроде так), это закончится бесконечной рекурсией. Я не понимаю, почему это вызывает бесконечную рекурсию, но то, как я это сделал, - нет. Заранее благодарю за помощь в очистке кода и за помощь в моем вопросе! </p>

Ответы [ 3 ]

2 голосов
/ 20 апреля 2020

Вы на правильном пути, но ваше решение может быть упрощено.

Ключевое наблюдение заключается в том, что максимальный элемент массива:

  1. Первый элемент, или

  2. Максимум остатка массива после первого элемента 

    // requires start <= end (not checked, left as exercise for reader)  
public static int findMax(int[] myArray, int start, int end) {  
    if (start < end) {  
        int maxOfRest = findMax(myArray, start+1, end);  
        return myArray[start] > maxOfRest ? myArray[start] : maxOfRest;  
    }  
    else { // start == end  
        return myArray[start];  
    }  
}

Обратите внимание, что мое решение не требует переноса 'max до сих пор 'в каждую рекурсивную активацию findMax - думаю, это делает его чище.

Сноска: оператор ?: правильно называется условным оператором . Иногда его называют «троичным оператором», но все это означает «оператор с тремя операндами», в отличие от различных бинарных операторов (два операнда) и унарных операторов (один операнд), поэтому он не особенно информативен.

2 голосов
/ 20 апреля 2020

Все, что вам нужно передать, это array и значение 0

  • Начните с инициализации m до конечного минимального значения.
  • , затем продолжайте звонить max до i == the array length - 1
  • , затем просто сравните значения m, когда они возвращаются из стека вызовов, со значением в массиве, на которое указывает i
int [] a = {1,3,20,2,55,32,4,9,44,10,29};
int m = max(a,0);
System.out.println(m);


public int max(int[] a, int i) {
   int m = Integer.MIN_VALUE;
   if (i < a.length-1) {
       m = max(a,i+1);
   }
   return m > a[i] ? m : a[i];
}

Отпечатки 

55
2 голосов
/ 19 апреля 2020

Ваш код в целом в порядке, но если вы хотите что-то сжатое, вы можете использовать код ниже: 

//Before calling this particular method, you'll have to set the max to 
//Integer.MINIMUM_VALUE so it's guaranteed to be changed later OR call it
//with start + 1 instead of start
public static int findMax(int[] myArray, int start, int end, int max) {
  return (start < end) ? 
    findMax(myArray, 
            start + 1, 
            end, 
            (myArray[start] > max) ? myArray[start] : max))
    : max;
}

Причина, по которой вы повторяетесь бесконечно, заключается в том, как работает оператор постинкрементного вычисления.

Когда вы говорите start++, оно выдает sh значение начала в стек, а затем увеличивает его на фоне . Так что это нормально как отдельное утверждение, но когда вы пишете его как findMax(myArray, start++, end, max), это на самом деле то же самое, что и вызов findMax(myArray, start, end, max), потому что начало аргумента действительно не меняется.

...