2.3. Búsqueda exhaustiva#

2.3.1. Adivinar un número entre 1 y 100#

Nos piden adivinar un número entero \(N\) entre el \(1\) y el \(100,\) ambos inclusive. Un algoritmo de búsqueda exhaustiva consistiría en probar suerte con todos los números entre el \(1\) y el \(100,\) hasta que llegemos al número \(N\) que hay que adivinar. Para no olvidar niguna posibilidad, lo mejor es ser sistemático y elegirlos en orden; primero el \(1\) después el \(2\) y así sucesivamente. En este algoritmo empecemos, en este caso, por el valor \(n_0 = 1.\)

Vamos a hacer un programa. Primero asignamos un valor arbitrario a la variable \(N\) y despúes vamos probando, sitemáticamente, con todos los número hasta que acertemos.

Así generamos el número que hay que adivinar y que se guarda en la variable N.

import random
N = random.randint(1,100)

Ahora definimos la función que va haciendo las comprobaciones hasta que se llega al número que guada la máquina. En ese momento hemos acertado el número que habíaque adivinar. Ya podemos parar.

def busqueda_exhaustiva(N):

    for i in range(1,101):
        if i == N:
            print('Este es el número que había que adivinar:', N)
            print('Has acertado, este el número que has eligido:',i)
            break

busqueda_exhaustiva(N)

Este es el número que había que adivinar: 45
Has acertado, este el número que has eligido: 45

Observación: la pregunta de la que disponemos en la búsqueda exhaustiva es si nuestra apuesta es igual al número \(N\) que debemos adivinar. En este caso usamos el operador de comparación ==, porque estamos trabajando con enteros.

2.3.2. Máximo o mínimo de una secuencia#

Estos ejemplos son similares a los que vimos en la sección, Estrategias de programación, de la unidad anterior.

Vamos a determinar el dígito mayor de una secuencia de dígitos.

mayor = int(digitos[0])

for digito in digitos:
    if int(digito) > mayor:
        mayor = int(digito)
        
print('El mayor dígito es ' + str(mayor))

Aquí la estrategía es la siguiente:

  • se inicia la variable mayor con el valor del primer dígito

  • se recorren sucesivamente los todos los dígitos de la secuencia

  • se cambia el valor de mayor cada vez que aparece uno mayor

Así de forma exhaustiva encontramos el mayor.

De forma similar se podría determinar el dígito menor.

En este ejemplo determinamos la letra “menor” de las que contiene una cadena

secuencia_de_letras = input('Escribe una cadena que solo tenga letras minúsculas sin tilde: ')

menor = secuencia_de_letras[0]

for letra in secuencia_de_letras:
    if letra < menor:
        menor = letra
        
print('El letra "menor" es ' + menor)

Obsérvese como se inicia la variable menor con el valor de la primera letra de la secuencia

De forma similar se podría determinar la letra “mayor”.

2.3.3. Máximo de una función en un conjunto de puntos#

Veamos primero un caso particular.

Tenemos la función \(f(x) = -(x-2)(x-5)\) y queremo determinar el máximo de \(f\) en los números \(1, 2, 3, 4, 5, 6\)

Primer defino la función \(f:\)

def f(x):
    return -(x-2)*(x-5)

Ahora voy a utilizar un procedimiento similar al del anterior epígrafe, pero buscando el máximo de los valores de \(f(x)\) cuando \(x\in\{1,2,3,4,5,6\}.\) Obsrevese que los valores de \(x\) están ordenados.

I = range(1,7)

for x1 in I:
    primero = x1
    break

maximo = f(primero)

x = primero
for x2 in I:
    if f(x2) > maximo:
        maximo = f(x2)
        x = x2

print('Maximo = ', maximo)
print('Primero = ', primero)
print('Primer valor de x dónde se alcanza el máximo: ', x)

Maximo =  2
Primero =  1
Primer valor de x dónde se alcanza el máximo:  3

Obsérvese que:

for x in I:
    print(f(x))

-4
0
2
2
0
-4

Es decir, \(f(3) =f(4) =2:\) para los valores de \(x\) especificados, \(f(x)\) alcanza el máximo en los puntos \(2\) y \(3.\)

Vamos a crear una función para este programa. Lo haremos en dos pasos:

  • creamos una función que elige el primero de los números de I; la llamaremos primero(I)

  • creamos la funión que selecciona el mayor valor de \(f(x)\) para lo números de I: la llamaremos maximo_funcion_iterable_1(I,f)

Por último encapsularemos todo en una sola función.

def primero(I):
    for p in I:
        return p

primero(I)

1

def maximo_funcion_iterable_1(I,f):
    maximo = f(primero(I))
    for x in I:
        if f(x) > maximo:
            maximo = f(x)
    return maximo

maximo_funcion_iterable_1(I,f)

2

Ahora encapsulamos todo en una sola función:

def maximo_funcion_iterable(I,f):
    def primero(I):
        for p in I:
            return p
    maximo = f(primero(I))
    for x in I:
        if f(x) > maximo:
            maximo = f(x)
    return maximo

Ejemplo

Máximo valor de \(x(8-x)\) en \(\{0,1, \ldots, 10\}\).

def f(x):
    return x*(8-x)

maximo_funcion_iterable(range(11),f)

16

2.3.3.1. Máximo de una función en una malla de paso \(h\) en el intervalo \((a,b)\).#

La gráfica de \(f(x)=-(x-2)(x-5),\) de antes, es una parábola que pasa por los puntos \((3,2)\) y \((4,2),\) ya uqe \(f(3)=f(4)=2.\) Pero, hay valores de la \(x\) entre \(3\) y \(4\) que son mayores que \(2.\)

¿Cómo podemos obtener esos valores? Un métoco consiste en considerar un mayor número de punto entre \(1\) y \(6.\)

Los números \(1, 2, 3, 4, 5, 6\) se pueden ver como una malla de puntos entre \(1\) y \(6\) con un paso igual a \(1:\) la distancia que hay entre dos puntos consecutivos cualesquiera es \(1,\) o también, cada uno se obtiene a partir del anterior sumando \(1.\) Esto es una malla en el intervalo \((1, 6)\) de paso \(1.\)

Los punto de esta malla se obtienen de la siguiente forma:

a, b, h = 1, 6, 1

N = int((b - a)/h)

for i in range(N+1):
    puntos = a + i*h
    print(puntos)

1
2
3
4
5
6

En la malla anterior hay \(6\) puntos y \(5\) subintervalos. Los subintervalos son:

\[(1,2), (2,3), (3,4), (4,5), (5,6)\]

Disminuyendo el paso tenemos una malla más tupida; con un paso de \(0.5\) tenemos \(11\) puntos y \(10\) subintervalos

a, b, h = 1, 6, 0.5

N = int((b - a)/h)

for p in range(N + 1):
    puntos = a + p*h
    print(puntos)

1.0
1.5
2.0
2.5
3.0
3.5
4.0
4.5
5.0
5.5
6.0

Ahora creamos una malla con un paso \(0.1;\) tenemos \(51\) puntos y \(50\) subintervalos

a, b, h = 1, 6, .1

N = int((b - a)/h)

for i in range(N + 1):
    puntos = a + i*h
    print(puntos)

1.0
1.1
1.2
1.3
1.4
1.5
1.6
1.7000000000000002
1.8
1.9
2.0
2.1
2.2
2.3
2.4000000000000004
2.5
2.6
2.7
2.8
2.9000000000000004
3.0
3.1
3.2
3.3000000000000003
3.4000000000000004
3.5
3.6
3.7
3.8000000000000003
3.9000000000000004
4.0
4.1
4.2
4.300000000000001
4.4
4.5
4.6
4.7
4.800000000000001
4.9
5.0
5.1000000000000005
5.2
5.3
5.4
5.5
5.6000000000000005
5.7
5.800000000000001
5.9
6.0

Obsérvese que uando I = range(N+1) el número de puntos de la malla es \(\textbf{N+1}\) y que el número de subintervalos es \(N\)

Ahora podemos usar maximo_funcion_iterable_(I,g) dónde:

  • I son los valores de los índices de los puntos de la malla

  • g será el valor de la función \(f\) en el punto \(a + ih,\) es decir \(g(i) = f(a + ih)\)

Entonces, si defino:

## datos de entrada: (i) función y (ii) extremos del intervalo y paso
def f(x):
    return -(x-2)*(x-5)

a, b, h = 1, 6, 1

# númeo de intervalos en lso que se divide le intervalo (a,b) con un paso h
N = int((b - a)/h)

# iterable con el número de puntos de la malla
I = range(N+1)

# función que se maximiza: valores f(x) en los puntos de la malla
def g(i):
    return f(a + i*h)

Se puede obtener el máximo de \(f\) en la malla del intervalo \((1,6)\) de paso \(0.1\) de la siguiente forma.

maximo_funcion_iterable(I,g)

2

Podemos mejorar el resultado si refinamos la malla

## datos de entrada: (i) función y (ii) extremos del intervalo y paso
def f(x):
    return -(x-2)*(x-5)

a, b, h = 1, 6, .5

# númeo de intervalos en lso que se divide le intervalo (a,b) con un paso h
N = int((b - a)/h)

# iterable con el número de puntos de la malla
I = range(N+1)

# función que se maximiza: valores f(x) en los puntos de la malla
def g(i):
    return f(a + i*h)

maximo_funcion_iterable(I,g)

2.25

Pero en esta ocasión no mejora el resultado si aumentamos el número de puntos de la malla disminuyendo el paso. Veamos

## datos de entrada: (i) función y (ii) extremos del intervalo y paso
def f(x):
    return -(x-2)*(x-5)

a, b, h = 1, 6, .1

# númeo de intervalos en lso que se divide le intervalo (a,b) con un paso h
N = int((b - a)/h)

# iterable con el número de puntos de la malla
I = range(N+1)

# función que se maximiza: valores f(x) en los puntos de la malla
def g(i):
    return f(a + i*h)

maximo_funcion_iterable(I,g)

2.25

Sabemos que el máximo de \(f(x)=-(2-x)(5-x)\) se alcanza en el punto medio del intervalo \((2,5),\) \((2+5)/2=3.5\) Pero este punto pertenece a la malla de paso \(0.5\)

f((2+5)/2)

2.25

Ejemplo

def f(x):
    return x**3 - 5*x**2 - 4*x + 1

h, a, b = 0.001, -4, 5

N = int((b-a)/h)

def puntos(i,a,h):
    return a + i*h

def g(i):
    return f(puntos(i,a,h))

I = range(N + 1)
maximo_funcion_iterable(I,g)

1.7453491190000001

2.3.4. Ejercicios#

  1. Escribir una función que determine si un entero no negativo es un cuadrado perfecto. La función deveulve la raíz del entero no negativo, cuando se trata de un cuadrado perfecto y devuelve No cuando no lo es.

  2. Comprobar que la disminución del paso mejora la determinación del máximo de \(f(x) = -(x-2.01)(x-4.05).\) Tomar valores de \(h\) como \(1, 0.5, 0.1, 0.01, \dots.\) ¿Cuándo deja de mejorar la determinación? ¿Cómo se puede interpretar esto?

  3. Definir la función maximo_funcion(a, b, h, f) que devuelve el máximo de \(f\) en el intervalo \((a, b)\) con una malla de paso \(h.\)

  4. Utilizar el esquema seguido para calcular el máximo de una función sobre un iterable para definir la función mayor_frecuencia(texto). Esta función devuelve el máximo de la frecuencia de los caracteres del un texto. En este caso se puede utilizar la cadena de la variable texto como iterable en la función maximo_funcion_iterable(I,f); la función f tendría por argumento un caracter de texto y devolvería la frecuencia de ese caracter.

2.3.5. Cuestionarios de Moodle#

Enumeración exhaustiva 1

Enumeración exhaustiva 2