← Volver a los ejercicios

Resolver un problema con bisección, paso a paso

Un problema de juez en línea que nadie vio en clase, atacado con el método completo: entender qué se pide, nombrar la función objetivo, demostrar que es monótona, acotar el rango, decidir si la solución existe, fijar la tolerancia y recién ahí escribir código. Cada tarjeta se abre cuando la anterior queda resuelta.

1. El problema

UVa 10341 — Solve It.

Enunciado:
https://vjudge.net/problem/UVA-10341
Enviar la solución:
https://vjudge.net/problem/UVA-10341

Resuelva la ecuación

p·e⁻ˣ + q·sen(x) + r·cos(x) + s·tan(x) + t·x² + u = 0

donde 0 ≤ x ≤ 1.

Entrada. Varios casos de prueba hasta EOF. Cada caso trae seis enteros en una línea: p q r s t u, con 0 ≤ p, r ≤ 20 y −20 ≤ q, s, t ≤ 0.

Salida. Por cada caso, el valor de x con 4 decimales, o la cadena No solution cuando corresponda.

Fíjese en las restricciones de los coeficientes antes de seguir: parecen un detalle de formato y son el corazón del problema.

2. Entender la entrada

Cada línea trae seis enteros. ¿Qué son?

3. La función objetivo

¿Cuál es la función sobre la que se va a buscar, y qué valor se busca?

4. ¿Es monótona? La parte que no se asume

La bisección solo funciona si f es monótona en el rango. Nadie lo dice en el enunciado: hay que demostrarlo, y la prueba se arma término a término. Para cada uno, derive y decida qué hace en [0, 1] con la restricción que le impone el enunciado.

Los seis términos tienen derivada ≤ 0 en [0, 1], así que f′(x) ≤ 0: la función decrece en todo el rango. Ahí está la licencia para aplicar bisección. Y note de dónde salió: de las restricciones sobre los coeficientes, esas que parecían formato. Si el enunciado permitiera t > 0, el término t·x² subiría, la monotonía se caería y este problema pediría otra técnica.

5. El rango y la pregunta que casi nadie hace

El rango viene regalado: [0, 1]. Pero el enunciado admite responder No solution, así que hay algo más que comprobar. ¿Cómo se decide si la solución existe?

6. Los casos del enunciado

Entrada:
[a, b]mitadf(mitad)Decisión

El segundo caso es el que enseña: f(0) y f(1) son los dos positivos, la curva nunca cruza el cero dentro del rango y la respuesta no es un número.

7. La tolerancia

El juez pide 4 decimales. ¿Qué ε conviene?

8. El código: complete el esqueleto

El esqueleto ya trae la forma que salió de las tarjetas anteriores. Lo que falta es justo lo que cada tarjeta decidió: complételo usted.

import math

def f(p, q, r, s, t, u, x):
    # El lado izquierdo de la ecuacion, evaluado en x
    # Transcriba la formula del enunciado
    resultado = 0
    return resultado

def resolver(p, q, r, s, t, u, eps):
    # Tarjeta 5: la solucion existe solo si el cero queda encerrado.
    # Escriba la condicion que descarta los casos sin solucion.
    if ...:
        resultado = None
    else:
        # Tarjeta 5: el rango lo fija el enunciado
        a = ...
        b = ...
        # Tarjeta 7: el ciclo corre mientras el intervalo sea mas ancho que eps
        while ...:
            mitad = (a + b) / 2
            # Tarjeta 4: f decrece. Decida que extremo se mueve en cada caso
            if ...:
                a = mitad
            else:
                b = mitad
        # El valor que se devuelve es el centro del intervalo final
        resultado = ...
    return resultado

Ninguno de los huecos es de sintaxis: cada uno es una decisión que ya tomó en las tarjetas anteriores. El del if interno es el que separa a quien entendió la monotonía de quien copió la plantilla de la clase.

9. El error que cuesta el problema

De estos tres descuidos, ¿cuál produce un programa que compila, corre, no se cuelga y responde mal?

10. Enviarlo al juez

El problema no está resuelto hasta que el juez lo acepta.

https://vjudge.net/problem/UVA-10341

Antes de enviar

  • Corra los tres casos del enunciado y compare carácter por carácter: 0.7071, No solution, 0.7554.
  • Lea hasta EOF. El enunciado admite hasta 2100 líneas y no dice cuántas vienen.
  • Imprima con cuatro decimales exactos, incluidos los ceros de relleno: "%.4f", no el print por defecto.

Si el veredicto no es Accepted

  • Wrong Answer con los ejemplos bien: casi siempre es la comparación invertida de la tarjeta 9, o el caso No solution sin comprobar.
  • Time Limit Exceeded: ε demasiado fino, o un ciclo que no reduce el intervalo.
  • Presentation Error: sobra o falta un salto de línea.

Para seguir

El mismo recorrido —entrada, función objetivo, monotonía demostrada, rango, existencia, tolerancia, código— sirve para los tres problemas de la sesión:

  • UVa 11909 — Soya Milk.
    Enunciado: https://vjudge.net/problem/UVA-11909
    Enviar: https://vjudge.net/problem/UVA-11909
  • UVa 11646 — Athletics Track.
    Enunciado: https://vjudge.net/problem/UVA-11646
    Enviar: https://vjudge.net/problem/UVA-11646
  • UVa 714 — Copying Books.
    Enunciado: https://vjudge.net/problem/UVA-714
    Enviar: https://vjudge.net/problem/UVA-714