La mayor diferencia: los invariantes del recorrido
UVa 11078, Open Credit System, pide el mayor valor de
A[i] − A[k] con i < k. El enunciado está en
https://vjudge.net/problem/UVA-11078.
La solución lo resuelve con un solo recorrido y dos acumuladores. Aquí se
busca lo que ese recorrido sostiene en cada chequeo del while, se escribe
como fórmula y se demuestra en tres pasos: inicialización, estabilidad y
terminación.
1. La especificación y la predicción
Entrada: un arreglo A[0..N) de enteros con
N ≥ 2. Salida: máx {A[i] − A[k] : 0 ≤ i < k < N}.
Arreglo:
Los tres últimos son los casos del enunciado.
¿Qué devuelve mayorDiferencia(A)?
2. Ejecute y mire
Paso 0 de 0
Las casillas azules son A[0..j), las que el ciclo ya
leyó. Cada vez que la ejecución pasa por la línea 5, el while evalúa
su condición y la terna (j, maximo, mejor) queda en la tabla.
3. La traza por estados
Chequeo
j
maximo
mejor
¿Qué se repite?
Una fila en rojo es el chequeo donde falla la fórmula
que eligió en la tarjeta 4. La columna de la derecha se llena cuando
acierte los tres invariantes.
4. Los invariantes
Busque lo que se cumple en todas las filas,
incluida la primera y la última, escrito en términos de N, j y A. Para
abreviar, Dj = {A[i] − A[k] : 0 ≤ i < k < j} es el
conjunto de las diferencias cuyas dos posiciones ya se leyeron.
¿Entre qué valores se mueve j en los chequeos? (I₀)
¿Qué guarda maximo? (I₁)
¿Y mejor? (I₂)
5. La demostración
Encuentre primero los
tres invariantes en la tarjeta 4. El teorema a demostrar:
Teorema 1. Los invariantes I₀, I₁ e I₂ se cumplen.
Inicialización: tras las líneas 1 a 4, ¿qué vale (j, maximo, mejor)?
Para I₀: 1 ≤ 1 ≤ N, que vale porque la
precondición pide N ≥ 2. ✓ Para I₁: {A[t] : 0 ≤ t < 1} = {A[0]},
cuyo máximo es A[0] = maximo. ✓ Para I₂: no hay i, k con
0 ≤ i < k < 1, así que D₁ = ∅ y
máx (∅ ∪ {A[0] − A[1]}) = A[0] − A[1] = mejor. ✓
Estabilidad. Se toma una vuelta con j = t,
1 ≤ t < N, y se asumen I₀, I₁ e I₂ en t. ¿Qué parejas tiene
Dt+1 que Dt no tenía?
Dt+1 = Dt ∪
{A[i] − A[t] : 0 ≤ i < t}.
¿Cuál es la mayor de esas diferencias nuevas?
máx {A[i] − A[t] : 0 ≤ i < t} =
(máx {A[i] : 0 ≤ i < t}) − A[t] = maximo − A[t], por I₁ en t.
La línea 6 usa maximo antes de que la línea 9
lo actualice. ¿Por qué ese orden?
I₂ en t + 1. Las líneas 6 y 7 dejan
mejor' = máx (mejor, maximo − A[t]). Por I₂ en t y el paso anterior,
mejor' = máx (máx (Dt ∪ {A[0] − A[1]}),
máx {A[i] − A[t] : 0 ≤ i < t}) = máx (Dt+1 ∪ {A[0] − A[1]}). ✓
I₁ en t + 1. Las líneas 8 y 9 dejan
maximo' = máx (maximo, A[t]) = máx (máx {A[i] : 0 ≤ i < t}, A[t]) =
máx {A[i] : 0 ≤ i < t + 1}, usando I₁ en t. ✓
I₀ en t + 1. La línea 10 deja j = t + 1, y de 1 ≤ t < N sale
2 ≤ t + 1 ≤ N, luego 1 ≤ t + 1 ≤ N. ✓
La estabilidad de I₂ usó I₁; la de I₁ no usó I₂. Por eso se enuncian
juntos.
Terminación: ¿con qué valor de j termina el ciclo?
El ciclo termina porque j crece de 1 en 1 e I₀ lo
acota por N. Al salir, la condición j < N es falsa, o sea j ≥ N; con
j ≤ N de I₀ queda j = N. Sustituyendo en I₂:
mejor = máx (DN ∪ {A[0] − A[1]}). Como N ≥ 2, la pareja
(0, 1) está en DN, así que mejor = máx DN =
máx {A[i] − A[k] : 0 ≤ i < k < N}, que es la poscondición. ∎
Teorema 2. La invocación mayorDiferencia(A) sobre
cualquier arreglo con N ≥ 2 devuelve máx {A[i] − A[k] : 0 ≤ i < k < N}.
Demostración: por el Teorema 1 los invariantes se cumplen; la
terminación deja j = N, y sustituir ese valor en I₂ da la poscondición. ∎
El recorrido hace N − 1 vueltas de costo constante: O(N), contra las
N(N − 1)/2 parejas que revisa la solución con dos ciclos.
6. Para llevarse
Sin solución aquí. Cambie el código para que
arranque con j = 2, maximo = máx (A[0], A[1]) y mejor = A[0] − A[1].
¿Qué dicen ahora I₀ e I₂? ¿Sigue haciendo falta el término
{A[0] − A[1]}? Después agregue dos variables que guarden la pareja
(i, k) de la mejor diferencia y escriba su invariante.