Ejercicios · Refuerzo PUJ 24 de octubre¶
Ocho actividades para trabajar en el navegador. Las dos primeras recorren paso
a paso los problemas de la
sesión del 24 de octubre,
y tamano pregunta por el costo de las soluciones. Las cuatro
últimas son del invariante de ciclo, que es la hora de lógica de la
sesión del 14 de noviembre, escrito como fórmula y
demostrado en tres pasos; movil acompaña a UVa 839, que quedó como problema
propuesto.
mejor-tramo¶
UVa 507: decidir en cada posición si el tramo sigue o se reinicia, con el desempate por el tramo más largo y después por el que empieza antes.
acumulados¶
UVa 108: con la tabla de acumulados de una matriz, obtener la suma de cualquier rectángulo con cuatro lecturas.
movil¶
UVa 839: seguir la función recursiva lectura por lectura, con el móvil dibujado a la izquierda y la pila de llamadas a la derecha. En cada barra se elige el caso, y en cada retorno se escribe el peso y si está en equilibrio.
tamano¶
Ocho soluciones de juez, entre ellas las de 507, 108, 839, 100, 10189 y 620: decir de qué variable depende el tamaño, cuántas veces corre cada ciclo o llamada, el total en \(O\) y si alcanza contra los límites del enunciado.
sumar¶
La suma de un arreglo: predecir qué devuelve, mirar la traza de estados y encontrar los invariantes \(I_0\) e \(I_1\), que se demuestran con inicialización, estabilidad y terminación.
mayores¶
El mayor y el segundo mayor en un recorrido: ninguno de los dos invariantes se demuestra por separado, y un arreglo con todos los valores iguales decide cómo escribir el del segundo.
credito¶
UVa 11078: los invariantes de maximo y de mejor en el ciclo de la
solución. Al elegir un candidato errado, la traza marca en rojo el chequeo
donde falla, y el invariante de mejor muestra por qué el valor inicial
cuenta.
tramo¶
UVa 507 sin el desempate: el invariante de suma y el de mejor, con el
tramo vacío como el 0. El de mejor no se deja demostrar sin el de suma.