Saltar a contenido

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.