Java рекурсия максимальный элемент массива

Нахождение максимального значения в массиве с помощью рекурсии

Для одного из вопросов, которые мне было предложено решить, я нашел максимальное значение массива с помощью цикла for, поэтому я попытался найти его с помощью рекурсии, и вот что я придумал:

public static int findMax(int[] a, int head, int last) < int max = 0; if (head == last) < return a[head]; >else if (a[head] < a[last]) < return findMax(a, head + 1, last); >else < return a[head]; >> 

Так что он работает нормально и получает максимальное значение, но мой вопрос: нормально ли, чтобы для базового случая возвращалось [head], а для случая, когда значение в заголовке равно> значению наконец?

16 ответов

С таким же успехом вы можете сделать это только с одним счетчиком, просто индексом значения, которое вы хотите сравнить на этот раз:

public static int findMax(int[] a, int index) < if (index >0) < return Math.max(a[index], findMax(a, index-1)) >else < return a[0]; >> 

Это намного лучше показывает, что происходит, и использует макет «рекурсии» по умолчанию, например, с общим базовым шагом. Первоначальный звонок делается findMax(a, a.length-1) ,

Это на самом деле намного проще, чем это. Базовый случай — это если вы достигли конца массива (часть «else» троичного управляющего блока ниже). В противном случае вы возвращаете максимум текущего и рекурсивного вызова.

public static int findMax(int[] a) < return findMax(a, 0); >private static int findMax(int[] a, int i)

В каждом элементе вы возвращаете больший из текущего элемента и все элементы с большим индексом. Integer.MIN_VALUE будут возвращены только на пустых массивах. Это работает за линейное время.

Я бы решил это, разделив массив пополам при каждом рекурсивном вызове.

 findMax(int[] data, int a, int b) 

где a и b — индексы массива.

 findMax(int[] data, int 0, data.length -1); 

Это уменьшает максимальную глубину рекурсии с N до log2(N).
Но поиск все еще остается O(N).

int findMax(int[] data, int a, int b) < if (b - a else < int mid = (a+b) /2; // this can overflow for values near Integer.Max: can be solved by a + (b-a) / 2; int leftMax = findMax(a, mid); int rightMax = findMax(mid +1, b); return Math.max(leftMax, rightMax); >> 

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

//use divide and conquer. public int findMaxDivideConquer(int[] arr) < return findMaxDivideConquerHelper(arr, 0, arr.length-1); >private int findMaxDivideConquerHelper(int[] arr, int start, int end) < //base case if(end - start // use recursion. return the max of the current and recursive call public int findMaxRec(int[] arr) < return findMaxRec(arr, 0); >private int findMaxRec(int[] arr, int i) < if (i == arr.length) < return Integer.MIN_VALUE; >return Math.max(arr[i], findMaxRec(arr, i+1)); > 

Источник

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

Найти максимальный элемент массива и его индекс
A1, A2, . и A10 — массивы. Найти Самый большой элемент этого массива и его число . Если в.

Найти максимальный элемент массива табличных значений функции cos(x)
Всем привет.. Не знаю правильно ли я создал тему, но надеюсь что вы поможете .. С java встретился.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

static int max(int [] a ,int index) { int max = 0; if(indexa.length) { max = a[index]; for(int i=0;ia.length;i++) { if(maxa[i]) { max = max(a,i); } } return max; } else { System.out.print("Выход за пределы массива. Код возврата : "); return -1; } }

int [] a = {1,2,3,34,4,6,47}; System.out.println(max(a,0));

Источник

Write C and Java programs to find the largest element in an array using recursion.

Here, we develop C and Java code to find the maximum element in an array using recursion. We develop a method revursiveMax that takes an array arr storing n integers, where n >= 1 and returns the maximum element in arr .

Following are the Java and C codes respectively to find the maximum element of an array using recursion.

Java program to find the maximum element of an array using recursion.

class RecursiveMax { public static void main(String[] args) { int[] arr = {10, 5, 7, 9, 15, 6, 11, 8, 12, 2, 3}; int max = recursiveMax(arr, arr.length); System.out.println("Maximum element: " + max); } static int recursiveMax(int[] arr, int length) { if (length == 1) return arr[0]; return max(recursiveMax(arr, length - 1), arr[length - 1]); } private static int max(int n1, int n2) { return n1 > n2 ? n1 : n2; } } OUTPUT ====== D:\JavaPrograms>javac RecursiveMax.java D:\JavaPrograms>java RecursiveMax Maximum element: 15

C program to find the maximum element of an array using recursion.

#include int recursiveMax(int[], int); int max(int, int); int main() { int arr[] = {10, 5, 7, 9, 15, 6, 11, 8, 12, 2,}; int max = recursiveMax(arr, 10); printf("Maximum element: %d\n", max); } int recursiveMax(int* arr, int length) { if (length == 1) return arr[0]; return max(recursiveMax(arr, length - 1), arr[length - 1]); } int max(int n1, int n2) { return n1 > n2 ? n1 : n2; } OUTPUT ====== Maximum element: 15

Hope you have enjoyed reading C and java programs to find maximum number in an array by recursion. However, recursive solution in this case has no advantage over iterative one because there is more overhead associated with making recursive calls due to the fact that all recursive calls are saved at call stack.

Please do write us if you have any suggestion/comment or come across any error on this page. Thanks for reading!

Источник

Рекурсия: максимальный элемент в односвязном списке

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

1 2 3 4 5 6 7 8 9 10 11 12

public static int recmax(Node tail) { int max = 0; if(tail == null) { return max; } else { if(tail.value > max) { max = tail.value; } return max + recmax(tail.next); } }

Найти в заданном односвязном списке максимальный элемент
задано односвязный список в котором содержатся целые числа. найти в нем максимальный элемент .

Найти в односвязном списке минимальный и максимальный элементы и поменять их местами с помощью указателей
Нужно найти в односвязном списке минимальный и максимальный элемент и поменять их местами с помощью.

Удалить нулевой элемент в односвязном списке
найти и удалить первый нулевой элемент в списке Program Spisok; uses crt; type .

В односвязном списке добавить элемент в начало списка
В односвязном списке добавить элемент в начало списка.

public int maxElement() { return maxElementHelper(head, head).value; } // private метод, который собственно и выполняет основную работу private Node maxElementHelper(Node start, Node max) { return (start == null) ? max : maxElementHelper(start.next, (start.value > max.value) ? start : max); }

Eстественно, метод maxElement должен принимать(как стартовую позицию) и возвращать итератор, но в качестве примера думаю сойдёт и так.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

public class Node { public int data; public Node next; public Node(int data){ this(data, null); } public Node(int data, Node next){ this.data = data; this.next = next; } @Override public String toString(){ String str = String.valueOf(data); if(this.next != null){ str += " " + next.toString(); } return str; } public static int max(Node head){ if(head == null){ return Integer.MIN_VALUE; } int max = head.data; if(head.next != null){ int nextValue = max(head.next); if(nextValue > max) { max = nextValue ; } } return max; } public static void main(String[] args) { Node head = new Node(2, new Node(8, new Node(5, new Node(6)))); System.out.println(head); System.out.println("max: " + max(head)); } }

Наиболее часто встречающийся элемент в односвязном кольцевом списке
Здравствуйте! Как должна выглядеть функция поиска рейса, на котором больше всего пассажиров? .

В односвязном списке вставить элемент после заданного элемента списка
В односвязном списке вставить элемент после n-го элемента списка.

Как в односвязном списке поменять местами один элемент и следующий за ним?
Напр., что есть: 0 1 2 3 4 5 6 7 должно быть: 0 1 2 3 4 6 5 7

Вставить новый элемент после самого большого элемента в односвязном списке
Задача в том чтоб сделать функцию которая вставляет новый node после самого большого в списке .

Источник

Написать рекурсивную функцию для вычисления индекса максимального элемента массива из n элементов

Завтра рубежный контроль. Аттестация помогите кто чем сможет. буду благодарен
Java в среде NetBeans
5. Написать рекурсивную функцию для вычисления индекса максимального элемента массива из n элементов.

Написать рекурсивную функцию для вычисления индекса максимального элемента массива из n элементов
Не могу понять, как же написать рекурсию для нахождения максимального элемента массива и его индекс.

Написать рекурсивную функцию для вычисления индекса максимального элемента массива из n элементов
Написать рекурсивную функцию для вычисления индекса максимального элемента массива из n элементов.

Написать рекурсивную функцию для вычисления максимального элемента массива из n элементов
Добрый день, помогите пожалуйста, нужно написать рекурсивную функцию для вычисления максимального.

Написать рекурсивную функцию для вычисления максимального элемента массива из n элементов.
Написать рекурсивную функцию для вычисления максимального элемента массива из n элементов.

Сообщение было отмечено StiO как решение

Решение

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

public class Test { // функция находит индекс наибольшего елемента в массиве arr, начиная с индекса start private int maxIndex(int[] arr, int start) { if (isMaxElement(arr, arr[start])) return start; return maxIndex(arr, start + 1); } // функция проверяет является ли число element наибольшим в массиве arr private boolean isMaxElement(int[] arr, int element) { for (int i = 0; i  arr.length; i++) { if (arr[i] > element) return false; } return true; } // то шо вам надо public int maxIndex(int[] arr) { return maxIndex(arr, 0); } }

Сообщение от StiO

Источник