arrays - numero - Encuentre el valor máximo en una matriz por recursión
numero mayor recursividad (5)
Está utilizando el algoritmo Divide and Conquer para encontrar el elemento máximo de la matriz. Primero estás dividiendo la matriz en elementos individuales (dividir), luego estás comparando los elementos (conquistar). Está dividiendo la matriz usando llamar a findMaxHelper recursivamente.
La idea general de Dividir y conquistar se muestra en la figura:
Ejemplo:
Aquí max es igual a su función findMaxHelper con dos argumentos, es decir, left y right .
Verifique este ejemplo para una comprensión más profunda del concepto.
// Find a maximum element in the array.
findMax(A)
findMaxHelper(A, 0, A.length)
findMaxHelper(A, left, right)
if (left == right - 1)
return A[left]
else
max1 = findMaxHelper(A, left, (right + left) / 2)
max2 = findMaxHelper(A, (right + left) / 2, right)
if (max1 > max2)
return max1
else
return max2
Me está costando entender lo que está sucediendo en este pseudo-código.
¿Alguien puede ayudar a explicar lo que está sucediendo en cada línea? Necesito entender este código antes de poder responder las preguntas.
Sé que la función findMax llama a la función auxiliar findMaxHelper, luego findMaxHelper usa la recursión. Aparte de eso, realmente no lo entiendo.
findMaxHelper divide la matriz en la mitad cada vez, y encuentra el máximo a la izquierda, a la derecha:
por ejemplo, tiene la matriz A = [1, 3, 5, 8] , llame a findMax(A) -> findMaxHelper(A, 0, A.length) :
max1 | max2
1 3 | 5 8
max1|max2 | max1|max2
1 |3 | 5 |8
Jaguar ha puesto el concepto bastante bien y Paul ha proporcionado una explicación correcta y detallada. Para agregar a esto, me gustaría compartir un simple código C que le da una idea de cómo se ejecuta el código. Aquí está el código con la misma entrada que usó Jaguar:
#include<stdio.h>
int findMaxHelper(int A[], int left, int right){
int max1,max2;
int static tabcount;
int loop;
for(loop = 0 ; loop <tabcount;loop++) printf("/t");
tabcount++;
printf(" Entering: findMaxHelper(A, left = %d ,right = %d)/n/n",left,right);
if (left == right - 1){
for(loop = 0 ; loop <tabcount;loop++) printf("/t");
printf("/b/b/b/b/b/b/bLeaving: findMaxHelper(A, left = %d ,right = %d)| returning %d/n/n",left,right , A[left]);
tabcount--;
return A[left];
}
else
{
max1 = findMaxHelper(A, left, (right + left) / 2);
max2 = findMaxHelper(A, (right + left) / 2, right);
if (max1 > max2){
for(loop = 0 ; loop <tabcount;loop++) printf("/t");
printf("/b/b/b/b/b/b/bLeaving: findMaxHelper(A, left = %d ,right = %d) | returning max1=%d/n/n",left,right,max1);
tabcount--;
return max1;
}
else {
for(loop = 0 ; loop <tabcount;loop++) printf("/t");
printf("/b/b/b/b/b/b/bLeaving: findMaxHelper(A, left = %d ,right = %d)| returning max2=%d/n/n",left,right,max2);
tabcount--;
return max2;
}
}
}
int main (){
int A[] = { 34,3,47,91,32,0 };
int Ans =findMaxHelper(A,0,7);
printf( "And The Answer Is = %d /n",Ans);
}
U puede copiar y pegar el código en la máquina ur linux ... ¡Quizás ponga sleep (5) después de cada printf y vea cómo funciona realmente la recursión! ... Espero que esto ayude ... También compartiré la salida de mi sistema aquí:
Entering: findMaxHelper(A, left = 0 ,right = 7)
Entering: findMaxHelper(A, left = 0 ,right = 3)
Entering: findMaxHelper(A, left = 0 ,right = 1)
Leaving: findMaxHelper(A, left = 0 ,right = 1)| returning 34
Entering: findMaxHelper(A, left = 1 ,right = 3)
Entering: findMaxHelper(A, left = 1 ,right = 2)
Leaving: findMaxHelper(A, left = 1 ,right = 2)| returning 3
Entering: findMaxHelper(A, left = 2 ,right = 3)
Leaving: findMaxHelper(A, left = 2 ,right = 3)| returning 47
Leaving: findMaxHelper(A, left = 1 ,right = 3)| returning max2=47
Leaving: findMaxHelper(A, left = 0 ,right = 3)| returning max2=47
Entering: findMaxHelper(A, left = 3 ,right = 7)
Entering: findMaxHelper(A, left = 3 ,right = 5)
Entering: findMaxHelper(A, left = 3 ,right = 4)
Leaving: findMaxHelper(A, left = 3 ,right = 4)| returning 91
Entering: findMaxHelper(A, left = 4 ,right = 5)
Leaving: findMaxHelper(A, left = 4 ,right = 5)| returning 32
Leaving: findMaxHelper(A, left = 3 ,right = 5) | returning max1=91
Entering: findMaxHelper(A, left = 5 ,right = 7)
Entering: findMaxHelper(A, left = 5 ,right = 6)
Leaving: findMaxHelper(A, left = 5 ,right = 6)| returning 0
Entering: findMaxHelper(A, left = 6 ,right = 7)
Leaving: findMaxHelper(A, left = 6 ,right = 7)| returning 0
Leaving: findMaxHelper(A, left = 5 ,right = 7)| returning max2=0
Leaving: findMaxHelper(A, left = 3 ,right = 7) | returning max1=91
Leaving: findMaxHelper(A, left = 0 ,right = 7)| returning max2=91
And The Answer Is = 91
Básicamente, la recurrencia no recomienda buscar max in array, ya que no es necesario. Los algoritmos de división y conquista (recursivo) son más costosos en tiempo. Pero a pesar de que si quieres usarlo, puedes usar mi algoritmo de abajo. Básicamente, trae el elemento más grande de la matriz en la primera posición y tiene un tiempo de ejecución casi lineal. (¡Este algoritmo es solo una ilusión recursiva!):
int getRecursiveMax(int arr[], int size){
if(size==1){
return arr[0];
}else{
if(arr[0]< arr[size-1]){
arr[0]=arr[size-1];
}
return(getRecursiveMax(arr,size-1));
}
}
#include<stdio.h>
#include<stdlib.h>
int high,*a,i=0,n,h;
int max(int *);
int main()
{
printf("Size of array: ");
scanf("%d",&n);
a=(int *)malloc(n*sizeof(int)); //dynamic allocation
for(i=0;i<n;i++)
{
scanf("%d",(a+i));
}
i=0;
high=*a;
h=max(a);
printf("The highest element is %d/n",h);
}
int max(int *a)
{
if(i<n)
{
if(*(a+i)>high)
{high=*(a+i);}
i++;
max(a); //recursive call
}
return high;
}