Ejercicios · AyG PUJ · Recursion¶
Cada enlace abre un ejercicio que se trabaja directo en el navegador. La mecánica es la de siempre: prediga antes de ejecutar, recorra el algoritmo paso a paso y busque el patrón en la traza. La diferencia está en el destino: aquí el patrón no es una fórmula de conteo sino una pareja de invariantes —I₀ para las cotas del índice, I₁ para el acumulador— y una vez los encuentre el ejercicio lo lleva, paso por paso, a la demostración completa: inicialización, estabilidad y terminación.
Invariantes de ciclo¶
sumar¶
El primer ciclo de la clase: sumar un arreglo. Mire la traza por estados: todo cambia de chequeo en chequeo, menos dos propiedades que se conservan desde (0, 0) hasta el final.
Cuando las encuentre —I₀ e I₁—, el ejercicio abre la demostración del Teorema 1 y usted la arma respondiendo una pregunta por movimiento, hasta el Teorema 2.
factorial¶
El mismo recorrido, con menos ayuda y una condición distinta: aquí el while
usa i <= N, así que las cotas de I₀ cambian. Proponga los dos invariantes
entre candidatos con trampa instructiva y complete la demostración.
Al final hay un experimento: llamar fact(-1) y ver qué promete —y qué
no— la especificación cuando la entrada no cumple la precondición.
Divide y vencerás¶
mezclar¶
Dos tramos ordenados del mismo arreglo entran, y la mezcla escribe el tramo completo, ordenado, sobre ese arreglo. Ejecute escritura por escritura y proponga la pareja de invariantes del primer while: las cotas de i, j y k, y lo que lista[ini..k) cumple en cada chequeo. Con ellos se arma la demostración completa —Teorema 1 por inicialización y estabilidad, esta vez por casos, y la terminación hasta el Teorema 2— del ciclo que hace funcionar todo el ordenamiento por mezcla.
Pruebe los tres arreglos: uno deja «sobras» cuando la copia izquierda se
agota y otro tiene empates que el <= resuelve.
ordenar¶
El ordenamiento por mezcla dibujado completo: baje partiendo la lista nivel por nivel hasta el caso base y súbala mezclando con el ejercicio anterior.
La tabla acumula el trabajo de cada nivel y ahí aparece el patrón que explica el n·lg n: todos los pisos del árbol mueven exactamente n elementos, y pisos hay lg n.
Árbol de llamadas¶
movil¶
UVa 839, Not so Mobile. Cargue la muestra del enunciado, un móvil al azar o
uno propio, y siga la función movil() lectura por lectura: el móvil se
dibuja a medida que se lee y la pila de llamadas muestra lo que espera cada
marco. En cada lectura decida si es caso base o recursivo, y en cada retorno
escriba el peso y si el submóvil está en equilibrio.
Fíjese en las líneas con borde punteado: aparecen cuando un submóvil ya devolvió que no está en equilibrio, y se leen igual. Si la función dejara de leer, la siguiente lectura tomaría una línea que no le corresponde.
grey¶
UVa 11173, Grey Codes. Elija \(n\) y \(k\) y baje por las mitades del rango \([ini, fin)\): en cada nivel marque en qué mitad cae \(k\), escriba el bit, el rango nuevo y la posición, que se refleja cuando cae en la mitad derecha. La pila crece al bajar y, al subir, cada marco muestra lo que devuelve.
La expansión de \(T(m) = T(m/2) + c\) aparece nivel por nivel, y la lista completa de \(2^n\) códigos solo al final, para comprobar la respuesta.
contar parejas fuera de orden¶
UVa 10810, Ultra-QuickSort, dividir y vencerás con una combinación que no es solo pegar las dos mitades. Contar las parejas una por una cuesta \(\Theta(n^2)\); partiendo por la mitad, las de cada lado son el mismo problema más chico y las que cruzan se cuentan mientras se mezcla.
Se predice el número de parejas sobre un arreglo chico y después corre el código
de la sesión, mezclar y contar, con las posiciones i y j marcadas en el
arreglo y el aporte de cada elemento que sale de la derecha. Cuatro arreglos:
el del enunciado, uno ya ordenado, uno al revés del todo y uno de ocho valores.
- Enunciado y envío: https://vjudge.net/problem/UVA-10810