UNIDAD V
SOLUCIÓN POR BÚSQUEDA EXHAUSTIVA
JUSTIFICACIÓN
Esta
unidad trataremos de la búsqueda exhaustiva es una estrategia que se utiliza
para resolver problemas en las cuales no es posible hacer una
representación a partir de su enunciado. En este tipo de problemas generalmente
se identifican características de la solución, y en base a estas
características se procede en proceso de búsqueda sistemática de una respuesta.
A la
primera alternativa se le denomina "Tanteo sistemáyico por acotación del
error", o simplemente "acotación del error" por estar implícito
en el tanteo al generar soluciones tentativas.
OBJETIVOS
A través
de la unidad se pretende que los alumnos sean capaces de:
- Aplicar las estrategias de búsqueda exhaustiva en la resolución de problemas.
- Reconocer los tipos de problemas que admiten el uso de esta estrategia.
- Comprender la utilidad de la estrategia que nos ocupa.
LECCIÓN 1:PROBLEMAS DE TANTEO
SISTEMÁTICO POR ACOTACIÓN DEL ERROR
-Estrategia de tanteo sistemático por acotación del error
El tanteo
sistemático por acotación del error consiste en definir el rango de todas las
soluciones tentativas del problema, evaluamos los extremos del rango para
verificar que la respuesta está en él, y luego vamos explorando soluciones
tentativas en el rango hasta encontrar una que no tenga desviación respecto a
los requerimientos expresados en el enunciado del problema.
-Estrategia binaria para el tanteo sistamático
El método
seguido para encontrar cual de las soluciones tentativas es la respuesta
correcta se llama estrategia binaria. Para poder aplicar esta estrategia
hacemos lo siguiente:
Ordenamos
el conjunto de soluciones tentativas de acuerdo a un criterio.
Luego
aplicamos el criterio de validación a los valores extremos para verificar si es
uno de ellos la respuesta, o que la respuesta es una de las solucione
intermedias.
Continuamos
identificando el punto intermedio que divide el rango en dos porciones y le
aplicamos la validación a dicho punto.
Repetimos
el paso anterior camenzando por identificar el nuevo punto intermedio que
divide el nuevo rango en dos porciones y repetimos la validación en ese
punto
Repetimos
esto hasta encontrar la respuesta al problema.
Este
método es myu efectivo para descartar soluciones tentativas incorectas.
Practica 1:
En una máquina de venta de
golosinas 12 niños compraron caramelos y chocolates. Todos los niños compraron
solamente una golosina. Los caramelos valen 2 Um y los chocolates 4 Um.
¿Cuántos caramelos y cuantos chocolates compraron los niños si gastaron entre
todos 40 Um?
1)
¿Cuál es el primer paso para resolver el problema?
Leer el
problema.
2)
¿Qué tipos de datos se dan en el problema?
Caramelos
Chocolates
3)
¿Qué se pide?
¿Cuántos caramelos y cuantos chocolates compraron
los niños si gastaron entre todos 40 Um?
4)
¿Cuáles podrían ser las posibles soluciones? Haz una tabla con los
valores
5) ¿Qué relación nos puede servir para determinar
si una posible respuesta es correcta? ¿Qué pares de posibles soluciones debemos
evaluar para encontrar la respuesta con el menor esfuerzo?
Multiplicar
el valor monetario y sumamos
6)
¿Cuál es la repuesta?
Caramelos: 4
Chocolates:
8
7)
¿Qué estrategia aplicamos en está practica?
Tanteo
sistemático por acotación del error.
LECCIÓN 2:PROBLEMAS DE CONSTRUCCIÓN
DE SOLUCIONES
-Estrategia de búsqueda exhaustiva por construcción de soluciones
La
búsqueda exhaustiva por construcción de soluciones es una estrategia qur tiene
como objetico la construcción de respuestas al problema mediante el desarrollo
de procedimientos específicos que dependen de cada situación. La ejecución de
esta estrategia generalmente permite establecer no solo una respuesta, sino que
permite visualizar la globalidad de soluciones que se ajustan al problema.
Practica 1:
Coloque
los digitos del 1 al 9 en los cuadros de la figura de abajo, de forma tal que
cada fila, cada columna y cada diagonal sumen 15.
1) ¿Cuáles son tadas las ternas
posibles?
159
168
195
258
267
294
357
384
2) ¿Cuáles grupos de 3 ternas sirven
para construir la solución?
159 168
267 294
384 357
3) ¿Cómo quedan las figuras?
|
8
|
3
|
4
|
|
1
|
5
|
9
|
|
6
|
7
|
2
|
|
8
|
1
|
6
|
|
3
|
5
|
7
|
|
4
|
9
|
2
|
-¿Dónde buscar la información?
En este
tipo de problemas donde se aplica la búsqueda de solución lo primero que se
hace es la búsqueda de la información que vamos a usar. En primer lugar se
busca la información en el enunciado del problema. En las prácticas anteriores
la forma de la figura, los números que vamos a usar y la condición que se le
impone están todos en el enunciado.
Practica 2:
Identifica
los valores de números enteros que corresponden a las letras O, S y U para que
la operación indicada sea correcta. Cada letra solo puede tomar un único valor.
OSO +
USO
----------
SUU
El
enunciado solo nos plantea que reemplacemos las letras por números para que la
operación sea correcta. El resto de la información tiene que salir de la
respuesta.
En primer
término observamos que tenemos S+S=U y O+O=U. ¿Es posible que dos números
diferentes den el mismo número? Hagamos la tabla que sigue para ayudarnos.
|
Primer número
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
|
Segundo número
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
|
Suma de los dos números
|
0
|
2
|
4
|
6
|
8
|
10
|
12
|
14
|
16
|
18
|
Vemos que
el 1+1 da 2, pero el 6+6 da 12. Coloco el 2 y llevo 1. De esta forma S y O
pueden ser los pares (0 y 5), (1 y 6), (2 y 7), (3 y 8) y (4 y 9). Noten que en
los pares el primer número está entre 0 y 4 y el segundo entre 5 y 9. Las sumas
de los números del 5 y 9 consigo mismo llevan 1 a la columna de la izquierda.
Esto nos obliga a que el número a colocar en la primera columna de la derecha
debe ser el número menor del par. Si colocamos el mayor llevaríamos un 1
adicional para la suma de la segunda columna, con la cual las sumas de las dos
columnas no tendrían el mismo resultado.
Entonces,
O es un número entre 0 y 4. Con esa información podemos encontrar los valores
correspondientes a la U. El valor cero hay que descartarlo porque cero más cero
en la primera columna deberá dar caero también y vemos en la suma del enunciado
que la suma de la primera columna es un número diferente al de los términos de
la suma.
|
O
|
|
1
|
2
|
3
|
4
|
|
U
|
|
2
|
4
|
6
|
8
|
Luego que
tenemos los posibles valores de O y U, podemos determinar los valores
correspondientes para la S.
|
O
|
|
1
|
2
|
3
|
4
|
|
U
|
|
2
|
4
|
6
|
8
|
|
S
|
6
|
7
|
8
|
9
|
|
Finalmente
podemos calcular el resultado de sumar O con U y el 1 que llevemos de la
segunda columna a la tercera columna.
|
O
|
|
|
2
|
|
|
|
U
|
|
|
4
|
|
|
|
S
|
|
7
|
|
|
|
|
O+U+1
|
|
7
|
|
|
A partir
de esta última tabla podemos eliminar los valores de 3 y 4 para la O porque la
suma tiene un valor superior a 9 y eso obligaría a tener un cuarto dígito que
no es el caso a partir del enunciado. También debemos hacer notar que debe
cumplirse que O+U+1 dede ser igual a S. Eso solo se da para el valor de 2 para
O. Por lo tanto podemos descartar los valores 1,3 y 4 de la O en la tabla.
Reemplazando
los valores en la operación para verificar la respuesta nos da:
272 +
472
----------
744
Esta es una
operación matemática correcta. Por lo tanto es la respuesta al ejercicio.
En esta
práctica obtuvimos una respuesta única, sin embargo existen cosas en los cuales
puede hacer más de unas solución. Algunas ayudas en este tipo de ploblemas:
- Cuando se suma dos números iguales en la primera columna de la derecha el resultado de la suma es un número par, como se muestra en la tabla que hicimos en la practica 1.
- Cuando se suman dos números iguales en otras columnas diferentes a la primera de la derescha el resultado de la sumaes un número par si la suma de la columna a la derecha en menor de 10, y es un número impar si la suma de la columna a la derecha es igual o mayor a 10.
- Si es una columna los dos sumandos son iguales entre sí y también son iguales al resultado, hay dos posibilidades: si no se lleva de la columna anterior, es 0+0=0; y si se lleva 1 de la columna anterior, es 1+9+9=9 y llevo 1 para la columna de la izquierda.
- Si el resultado de la suma tiene una cifra más que el número de columnas, el número de la izquierda es un 1.
No hay comentarios:
Publicar un comentario