<< Memorizando Respuestas>>

Lecciones anteriores:

Cuadrado lleno de múltiplos de 17 (El programa original y algunas variaciones)

El problema original:

En la lección anterior analizamos el siguiente problema:

Se tiene un tablero de 4x4 en el que se anota un dígito en cada casilla. En cada fila y en cada columna se forma un número de cuatro dígitos. Un tablero de este tipo es legal si los ocho números que se forman así son múltiplos de 17. ¿Cuántos tableros legales distintos hay?

Probamos diferentes formas de hacer un programa que lo resuelva, para poder comparar algunos métodos, pero todos los programas tardaban más de 5 horas en una Pentium ~100 Mhz. En esta lección vamos a ver algunas ideas para que el programa vaya más rápido.

A la Memoria

Miremos el primer programa de la lección pasada y empecemos analizando la función CompletarNumero(N1, N2, N3) que dadas las primeras tres cifras de un número busca cuál es la cuarta para que sea un múltiplo de 17. Por ejemplo

CompletarNumero(1,7,0) da 0 porque 1700 es múltiplo de 17.
CompletarNumero(0,3,5) da 7 porque 0357 es múltiplo de 17.
CompletarNumero(0,0,2) da -1 para indicar un error ya que no hay ningún múltiplo de 17 entre 0020 y 0029.

La observación astuta que permite seguir adelante es la siguiente:

¿Cuántas posibilidades distintas hay para elegir los valores de los parámetros (N1, N2, N3)?

No es muy difícil de calcular, lo difícil es que a uno se le ocurra la pregunta.

(Supongo que todos habrán llegado en unos segundos a que la respuesta es 1000.)

Entonces lo que se puede hacer es armarse una "matriz" de 10x10x10 (se parece más a una cajita) con todas las respuestas de esta función, así que reemplazamos completamente todas las llamadas a esta función por fijarse cuál es el valor correspondiente en la tabla. De esta manera en vez de estar haciendo multiplicaciones y divisiones para ver el resultado, casi todo lo que tiene que hacer la computadora es copiar un número de un lugar a otro, por lo que esto es muchísimo más rápido. El único problema es que hay que perder un poco de tiempo al principio inicializando la tabla con los valores correctos, pero estos cálculos se hacen una sola vez por lo que de todas maneras se ahorra tiempo.

Más Memoria

Contentos con estos resultados tratamos de repetir el truco con la función Cifra(Numero , Posicion ) que se usa para separar los números en cifras. Así que la pregunta mágica es

¿Cuántas posibilidades distintas hay para elegir los valores de los parámetros (Numero, Posicion)?

El problema es que 40000 es demasiado grande, o sea demasiado grande para guardarlo en memoria. Como vamos a guardar el resultado en un Integer que ocupa dos bytes entonces la matriz necesaria para guardar todos estos resultados ocupa 80000>65536=2¹⁶. Esto es un segmento de memoria y en general a los programas para DOS les cuesta bastante trabajar con estructuras que ocupen más de un segmento.

Hay varias soluciones, pero me parece que la más interesante es tratar de aprovechar que en realidad no quiero las cifras de cualquier número, sino que sólo las de los múltiplos de 17. Así que pensemos en una función CifraS17(NumeroS17 As Long, Posicion As Long) que primero multiplica a NumeroS17 por 17 y después le calcula la cifra correspondiente.

De esta manera tenemos solo 4x588 posibilidades que guardamos en una memoria de 4x588x2=4704 bytes <65536. Además así nos ahorramos estar multiplicando o dividiendo por 17 muy seguido.

¡¡¡¡¡El contador!!!!!

En la lección anterior quedo planteada la pregunta sobre qué variable NO se podía pasar a Integer. Y la respuesta es el contador. Las demás variables tienen intervalos fijos de 0 a 9, de 0 a 9999, ..., pero el contador va subiendo despacio pero seguro y el único límite es (a lo bruto) la cantidad total de tableros =10¹⁶. En general hay que analizar los programas uno por uno, pero en muchos hay un contador que se puede desbandar.

El programa:

Para que se parezca lo más posible al anterior, dejamos las funciones viejas para hacer los cálculos iniciales y guardamos los resultados en la matriz que tiene el mismo nombre que la función pero agregándole al principio "Mat".

Declare Sub IniciarMatrices ()
Declare Function CompletarNumero% (N1 As Integer, N2 As Integer, N3 As Integer) 'As Integer
Declare Function CifraS17% (NumeroS17 As Integer, Posicion AS Integer) 'As Integer
Const C9999D17 = 9999 \ 17 '=588
Dim Shared MatCifraS17(0 To C9999D17, 1 To 4) As Integer
Dim Shared MatCompletarNumero(0 To 9, 0 To 9, 0 To 9) As Integer

Dim L1 As Integer
Dim L2 As Integer
Dim L3 As Integer

Dim C1 As Integer
Dim C2 As Integer
Dim C3 As Integer
Dim C4 As Integer

Dim Columna As Integer

Dim Contador As Long

Dim Inicio As Single
Dim Tiempo As Single
Dim Pasos As Single

Inicio = Timer
IniciarMatrices
Print
Print "Tiempo", "Tiempo", "Tableros", "Valor"
Print "Trans.(s)", "Estimado(H)", "Encontrados", "L1"
For L1 = 0 To C9999D17
        Tiempo = Timer - Inicio
        Pasos = L1 + 0.1 ' "+.1" porque sino empieza de Cero
        Print Tiempo, Tiempo / Pasos * (C9999D17 + 1) / 3600, Contador, L1 * 17
        For L2 = 0 To C9999D17
                For L3 = 0 To C9999D17
                        C1 = MatCompletarNumero(MatCifraS17(L1, 1), MatCifraS17(L2, 1), MatCifraS17(L3, 1))
                        C2 = MatCompletarNumero(MatCifraS17(L1, 2), MatCifraS17(L2, 2), MatCifraS17(L3, 2))
                        C3 = MatCompletarNumero(MatCifraS17(L1, 3), MatCifraS17(L2, 3), MatCifraS17(L3, 3))
                        C4 = MatCompletarNumero(MatCifraS17(L1, 4), MatCifraS17(L2, 4), MatCifraS17(L3, 4))
                        If C1 >= 0 And C2 >= 0 And C3 >= 0 And C4 >= 0 Then
                            If C4 = MatCompletarNumero(C1, C2, C3) Then
                                Contador = Contador + 1
                            End If
                        End If
                Next
        Next
Next
Print Contador, Timer - Inicio

Function CifraS17%(NumeroS17 As Integer, Posicion As Integer)  ' AS Integer
    Dim Columna As Integer
    Dim Queda As Integer
    Queda = NumeroS17 * 17
    
    For Columna = 4 To Posicion + 1 Step -1
        Queda = Queda \ 10
    Next Columna
    CifraS17 = Queda Mod 10
    'en C: Return CifraS17
End Function

Function CompletarNumero%(N1 As Integer, N2 As Integer, N3 As Integer)  'AS Integer
    Dim Valor As Integer
    Dim Sobra As Integer
    Dim Falta As Integer
    Valor = N1 * 1000 + N2 * 100 + N3 * 10
    Sobra = Valor Mod 17
    If Sobra <> 0 Then
        Falta = 17 - Sobra
        If Falta >= 10 Then
            Falta = -1 'ERROR
        End If
    Else
        Falta = 0
    End If
    CompletarNumero = Falta
    'Return Falta
End Function

Sub IniciarMatrices()
    Dim X1 As Integer
    Dim X2 As Integer
    Dim X3 As Integer
    Dim X4 As Integer
    Dim NumeroS17 As Integer
    Dim Posicion As Integer

    For X1 = 0 To 9
        For X2 = 0 To 9
            For X3 = 0 To 9
                MatCompletarNumero(X1, X2, X3) = CompletarNumero(X1, X2, X3)
            Next X3
        Next X2
    Next X1

    For NumeroS17 = 0 To C9999D17
        For Posicion = 1 To 4
            MatCifraS17(NumeroS17, Posicion) = CifraS17(NumeroS17, Posicion)
        Next Posicion
    Next NumeroS17
End Sub

(Nota: De vuelta quizás L1, L2, L3 y C1, C2, C3, C4 deberían ser dos vectores(array) )

Comparando los tiempos:

Al igual que en la lección pasada comparamos los tiempos de ejecución en una Pentium de ~100Mhz del programa tal cual aparece con el que se obtiene borrando todos los "Mat". Al borrarlos se dejan de utilizar las matrices y se calcula todo nuevamente cada vez.

Al fin logramos un programa que corriera en un tiempo razonable (sin una Pentium III de 700MHz:). Además como se ve si no utilizamos el truco de las matrices el tiempo vuelve a ser del orden de los que aparecieron en la lección anterior como era de esperar. (En realidad es un poquito menor porque antes probaba con todos los números del 0 al 9999 y se fijaba si eran múltiplos de 17.)

Algunos comentarios:

Hay una serie de hechos que simplificó mucho la transformación de funciones en tablas:

• Hay pocos valores posibles, tan pocos que la tabla entra en memoria.
• Se puede predecir (más o menos) cuales son los que realmente se van a usar (en este caso "todos").
• El calculo de un determinado valor no depende de los otros valores.
• Se nos ocurrió la pregunta mágica.
• El programa tardaba demasiado (y nos dimos cuenta).

Las dos últimas son fáciles de solucionar entrenando. La idea es que casi automáticamente uno estime a ojo el tiempo que va a tardar el programa (y si es necesario lo mida un poco mejor). Si el programa tarda demasiado siempre se puede intentar pensar si no hay una forma mejor de resolverlo, y si falla pensar se puede intentar usar este método.

Cuando los valores están más enredados y dependen unos de otros se complica sólo un poquito. Esto se analiza en la lección Recursividad con Tablas (aunque conviene que antes lean Recursividad e Iteraciones).

Y por ultimo si no hay lugar para guardar toda esa información se puede intentar ir guardando parte y tratando de descartar la que no es necesaria (como el cache de paginas web), pero esto ya es más complicado. En particular ¿cómo saber (o por lo memos elegir astutamente) que descartar y que guardar?

En la próxima lección vamos a ver como acelerar el programa llenando el tablero en otros órdenes.

Ejercicios:

1. Cambiar la inicialización de las matrices para hacerla toda junta, sin que llame a las funciones viejas.
   
2. Modificar el programa para que en vez de llenar el tablero de múltiplos de 17 lo llene con múltiplos de 11(Facil). Lo mismo pero con múltiplos de 9 (Mucho más difícil.).
   
3. Me parece que al cambiar el 17 por 11 o 9 sale a mano. Inténtenlo, pero por favor manden los resultados, comentarios u objeciones. Compararlo con lo que dice la computadora.
   

Lecciones siguientes:

Otras formas de llenar el tablero.

Lecciones relacionadas:

Recursividad con Tabla. (Qué hacer cuando los valores dependen de los otros valores.)

La idea es que hagan los ejercicios y piensen que otras cosas interesantes se pueden hacer relacionadas con estos temas. Cuéntennos lo que consiguieron y pregunten lo que no les salió. Envíen sus preguntas, dudas, sugerencias, experiencias y propuestas. Nuestra dirección es cym98@oma.org.ar .

También nos gustaría saber tu opinión sobre esta clase. Les pedimos que se tomen unos instantes y contesten estas preguntas. Con tu ayuda podremos hacer un curso cada vez mejor.

OmaNet   Curso CyM98	OmaNet - Educación Interactiva    www.oma.org.ar/omanet | omanet@oma.org.ar
mensajes: webmaster@oma.org.ar