A ver la cosa es la siguiente: salgo hoy de la reclamacion del examen de Metodologia y Tecnologia de la Programacion 2 y suspendo por el siguiente problema donde tengo un 0 de 10:
AlgoritmoMaxElemTabla (tabla T, indice P, indice U){
Si P=U return P
else {
M=P+U/2 //indice medio
izq = AlgoritmoMaxElemTabla (tabla T, indice P, indice M)
der = AlgoritmoMaxElemTabla (tabla T, indice M+1, indice U)
Si T[izq]>T[der] return izq, else return der
}
Vamos que de forma recursiva y partiendo la tabla por la mitad el algoritmo encuentra el elemento mas grande de la tabla
Escribir la recursion para el caso general (N=nº elementos=2^k) y resolver la recurrencia
----------------------------------------------------------------------------
Mi planteamiento de resolucion:
Al ir partiendo la tabla en 2 cuando N=2^k podria plantearme el problema como un arbol binario, donde qal principio tengo todos los elementos en un bloque, luego en 2, luego en 4, etc hasta que los tengo en N bloques. Una vez aqui voy a comparar cada uno de los nodos con su hermano, de modo que al final logicamente voy a tener N/2 comparaciones en el ultimo nivel del arbol. Tomando esto como base, se que las comparaciones que voy a tener que hacer son las de este ultimo nivel (N/2) mas las de un nivel menos (que este nivel va a tener N/2 elementos, es decir, N/4 comparaciones), mas las de un nivel menos, mas las de uno menos... asi hasta llegar al nivel inmediatamente inferior a la raíz. Con esto he tenido la recursividad de la forma N/2 + T(N/2). He resuelto esta correctamente segun lo aprendido en clase y he obtenido el resultado correcto, N-1 comparaciones.
El planteamiento del corrector:
Al principio vas a hacer 1 sola comparacion para cuando tienes el numero maximo de cada una de las 2 mitades. Antes de esto habras sacado estos dos máximos con 2 comparaciones (comparar entre si los dos maximos de cada una de las dos subtablas... y asi sucesivamente). El desarrollo de su recurrencia da el mismo resultado que la mia, N-1 comparaciones
Es decir, EXACTAMENTE LO MISMO QUE LO QUE YO PROPONGO PERO PLANTEADO AL REVES
Y nada, un 0
Si estoy diciendo una tonteria que alguien me explique por que por favor porque el corrector se niega a darme una explicacion de porqué mi planteamiento es tan disparatado. Si realmente lo es yo no lucho mas pero si es normal me pongo a lo Erin Brockovich
![[uzi]](/images/smilies/nuevos2/uzi.gif "uzi")
Ayer hice un dibujo para explicarselo a un amigo, aqui va
