Advertencia: no has iniciado sesión. Tu dirección IP se hará pública si haces cualquier edición. Si
inicias sesión o
creas una cuenta, tus ediciones se atribuirán a tu nombre de usuario, además de otros beneficios.
Puedes deshacer la edición.
Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
Revisión actual |
Tu texto |
Línea 65: |
Línea 65: |
|
| |
|
| b2) El hecho de que se agregue un 5% de palabras nuevas, ¿Es relevante? ¿Cambiaría su respuesta (y cómo) su cada año se agregase un 50% de palabras nuevas? ¿Y si fuese un 100%, es decir se duplicara el vocabulario cada año? | | b2) El hecho de que se agregue un 5% de palabras nuevas, ¿Es relevante? ¿Cambiaría su respuesta (y cómo) su cada año se agregase un 50% de palabras nuevas? ¿Y si fuese un 100%, es decir se duplicara el vocabulario cada año? |
|
| |
| == Ejercicio 3: Dividir y conquistar ==
| |
|
| |
| Dado un árbol binario de números enteros, se desea calcular la máxima suma de los nodos pertenecientes a un camino entre dos nodos cualesquiera del árbol. Un camino entre dos nodos <math>n_1</math> y <math>n_2</math> está formado por todos los nodos que hay que atravesar en el árbol para llegar desde <math>n_1</math> hasta <math>n_2</math>, incluyéndolos a ambos. Un camino entre un nodo y sí mismo está formado únicamente por ese nodo. El algoritmo debe recorrer <b>como máximo una vez</b> cada nodo del árbol, que no necesariamente es completo. Se considerará incorrecto a un algoritmo que no cumpla con esta condición.
| |
|
| |
| [[File:Grafo_de_ejemplo_Ej3_Recu_2p_1C_2015_AyED2.jpg|600px]]
| |
| <!-- Acá había un ejemplo de máxima suma, pero es una imagen, así que no la transcribí -->
| |
|
| |
| Se pide dar un algoritmo MáximaSumaCamino(a: ab(int)) -> int que resuelva el problema utilizando la técnica de Dividir y Conquistar, calculando y justificando claramente su complejidad. El algoritmo debe tener una complejidad temporal de peor caso igual o mejor que <math>O(n)</math> siendo <math>n</math> la cantidad de nodos del árbol.
| |
|
| |
| [[Categoría: Parciales]]
| |
| [[Categoría: Segundos Parciales]]
| |