CyM98

<< Cuadrado lleno de
múltiplos de 17>>

Dificultad: Computación Computación Matemática

Se necesitan solamente conocimientos elementales de matemática. Algunos de los temas de computacion se pueden repasar leyendo las lecciones anteriores.

Lecciones anteriores:

Midiendo tiempos Computación (con más información sobre como medir el tiempo que tarda el programa)

Bases de numeración Computación Matemática (con más información sobre como separar un número en cifras)

 
Google
Web www.oma.org.ar

Resumen:

Vamos a analizar un problema y comparar varias formas de resolverlo. En esta lección mostramos la solución más sencilla que es justamente la más lenta.

El problema original:

En la Segunda Ronda del Torneo del año 2000 tomamos un problema en tercer nivel que decía:

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?

Resulto bastante difícil, así que la idea es discutir un poco algunas maneras de hacer que valla más rápido y la solución termine en un tiempo razonable.

Primera Propuesta:

Vamos a empezar con la versión más simple del programa y analizar algunas variaciones. El programa prueba con todas los posibles números en las primeras tres filas y trata de completar cada columna para que sea un múltiplo de 17. Si lo logra se fija si la última fila también es múltiplo de 17 y en este caso aumenta el contador

El programa separa los números en cifras utilizando una función. Llama a otra función para que busque cuál debería ser la ultima cifra de cada columna a medida que lo necesita. Para todas las cuentas usamos división(\) entera y módulo (Mod) que andan más rápido. El programa en QB es:

Dim L1 As Long
Dim L2 As Long
Dim L3 As Long

Dim C1 As Long
Dim C2 As Long
Dim C3 As Long
Dim C4 As Long

Dim Columna As Long

Dim Contador As Long

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

Inicio = Timer
Print
Print "Tiempo", "Tiempo", "Tableros", "Valor"
Print "Trans.(s)", "Estimado(H)", "Encontrados", "L1"
'L1, L2, L3 son las tres primeras filas
For L1 = 0 To 9999
  If L1 Mod 17 = 0 Then
    For L2 = 0 To 9999
      If L2 Mod 17 = 0 Then
        Tiempo = Timer - Inicio
        Pasos = L1 * 10000 + L2 + 0.1 ' "+.1" porque sino empieza de Cero
        Print Tiempo, Tiempo / Pasos * 10000 ^ 2 / 60 ^ 2, Contador, L1

        For L3 = 0 To 9999
          If L3 Mod 17 = 0 Then
            'En C1, C2, C3, C4 se guarda la ultima cifra de cada columna
            C1 = CompletarNumero(Cifra(L1, 1), Cifra(L2, 1), Cifra(L3, 1))
            C2 = CompletarNumero(Cifra(L1, 2), Cifra(L2, 2), Cifra(L3, 2))
            C3 = CompletarNumero(Cifra(L1, 3), Cifra(L2, 3), Cifra(L3, 3))
            C4 = CompletarNumero(Cifra(L1, 4), Cifra(L2, 4), Cifra(L3, 4))
            If C1 >= 0 And C2 >= 0 And C3 >= 0 And C4 >= 0 Then
              If C4 = CompletarNumero(C1, C2, C3) Then
                Contador = Contador + 1
              End If
            End If
          End If
        Next
      End If
    Next
  End If
Next
Print Contador

Function Cifra&(Numero As Long, Posicion As Long)  ' As Long
  Dim Columna As Long
  Dim Queda As Long
  Queda = Numero
  
  For Columna = 4 To Posicion + 1 Step -1'Cuenta para atras
    Queda = Queda \ 10
  Next Columna
  Cifra = Queda Mod 10
  'en C: Return Cifra
End Function

Function CifraString&(Numero As Long, Posicion As Long)  ' As Long
  CifraString = Val(Mid$(Str$(10000 + Numero), Posicion + 2, 1))
  'en C: Return Cifra
End Function

Function CompletarNumero&(N1 As Long, N2 As Long, N3 As Long)  'As Long
  Dim Valor As Long
  Dim Sobra As Long
  Dim Falta As Long
  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

Function CompletarNumeroBuscando&(N1 As Long,N2 As Long,N3 As Long)'As Long
  Dim Valor As Long
  Dim Ultimo As Long
  Valor = N1 * 1000 + N2 * 100 + N3 * 10
  For Ultimo = 0 To 9
    If (Valor + Ultimo) Mod 17 = 0 Then
      Exit For
    End If
  Next
  If Ultimo >= 10 Then Ultimo = -1
  CompletarNumeroBuscando = Ultimo
  'Return Ultimo
End Function

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

 

  

El programa tiene dos funciones, cada una con dos versiones. Además terminan en & para indicar que el resultado es un Long (En el VB se puede indicar de una manera más clara que es poniendo "As Long" al final.)

La primera es Cifra(Numero As Long, Posicion As Long) que se usa para separar los números en cifras. Cuenta las posiciones de izquierda a derecha, suponiendo que el número tiene cuatro "cifras" y si es necesario completa con ceros. Hay otra función que aparece como CifraString que hace exactamente lo mismo, pero utilizando cadenas de texto.

La otra función es CompletarNumero(N1 As Long, N2 As Long, N3 As Long) 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 función CompletarNumeroBuscando hace lo mismo, pero más a mano, probando con todos los números posibles.

Comparando los tiempos:

Además el programa va mostrando cuanto tiempo lleva ejecutándose y una estimación de cuánto va a tardar. A veces es bueno hacer estas estimaciones para no quedarse esperando que el programa termine o pulir durante media hora un programa que tarda 10 minutos.

También la idea es que al practicar hagan varias versiones de las funciones para ver que tipo de cosas andan más rápido y acostumbrarse a usarlas. Al ejecutarlo utilizando las diversas funciones obtenemos los siguientes tiempos en una Pentium de ~100Mhz:

Condiciones

Tiempo con
L1=0(Segundos)
Tiempo Total
Estimado (Horas)

Usando CifraString y CompletarNumeroBuscando

132

21,5

Usando CifraString

116

18,9

Usando CompletarNumeroBuscando

68

11,1

Sin Cambios

52

8,5

Cambiando "todas" las variables y funciones a Integer

35

5,8

En realidad al principio (durante los primeros 2 o 3 minutos) el tiempo estimado que muestra el programa es mucho mayor (unas 17 veces :) ). Este pequeño misterio queda como ejercicio.

Como se puede ver en la tabla la función para separar en cifras que usa cadenas es mucho más lenta y le agrega unas 10 horas más al programa, ¡¡de manera que tarda casi el doble!!. El efecto de usar CompletarNumeroBuscando no es tan terrible, pero son unas 2 horas más de ejecución.

Una mejora importante se logra cambiando todos los "Long" por "Integer" (y los "& por "%"), bueno, todos menos 1 que hay que dejar como Long. Un error muy normal es confiarse de que ningún valor va a ser muy grande y usar Integer para ahorrar memoria y que el programa ande más rápido. Es importante darse cuenta a ojo cual es la única variable que no se puede achicar (otro ejercicio). (Ver Tabla de traducción de tipos de variables)

Otra ayuda importante para que le programa vaya más rápido es el uso de la división entera en todos los casos en que es posible. Sería interesante cambiarlas por divisiones normales y ver cuanto (más) tarda.

Más o menos carteles:

También es importante regular correctamente la cantidad de carteles. Si aparecen más de unos 10 carteles por segundo el tiempo que le toma a la computadora hacer que la información en la pantalla suba empieza a molestar y a hacer realmente más lento el programa. Si entre cartel y cartel pasan más de unos 10 segundos uno se empieza a aburrir y preguntarse si se colgó. Yo prefiero unos 2 o 3 por segundo, pero es cuestión de gusto.

Una forma de tener actualizado continuamente la pantalla sin que se consuma tanto tiempo es mediante la instrucción Locate (QB) o gotoxy (Pascal/C) que permite escribir siempre en un punto fijo de la pantalla.

En la siguiente tabla se compara el tiempo que tarda el programa poniendo carteles adentro de diferentes ciclos. Por ejemplo si se pone un cartel en pantalla adentro de todo, de manera que se actualiza cada vez que la tercera fila cambia, el tiempo aumenta considerablemente de unas 10 horas a 6 días.

Condiciones

Tiempo con
L1=0(Segundos)
Tiempo Total
Estimado (Horas)

Cartel cuando cambia L1 (o sin Carteles)

51

8,3

Sin Cambios(Cartel cuando cambia L2)

51

8,5

Cartel cuando cambia L3

871

142,2

Cartel cuando cambia L3, pero con "Locate 1, 1"

122

19,9

En las lecciones siguientes vamos a hacerle a este programa algunos pequeños cambios para que vaya más rápido.


Ejercicios:

  1. ¿Por qué durante los primeros dos o tres minutos el tiempo estimado es unas 17 veces el que realmente va a tardar?
  2. ¿Cuál de todas las variables no se puede convertir en un Integer? ¿Por qué? ¿Por qué el resto si? Cambiar el programa y ver que funciona (dejarlo correr al menos unos 10 minutos).
  3. La verdad es medio inútil que el programa pruebe con todos los números si después se va a quedar sólo con los múltiplos de 17. Modificarlo convenientemente

Lecciones siguientes:

Memorizando las respuestas Computación Computación Matemática

Otras formas de llenar el tablero Computación Computación Matemática

 


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.

¿Cuál es tu calificación general de esta clase?

No entendí nada   Mala   Regular   Buena   Muy buena

El contenido de esta clase te resultó:

Nuevo   Conocido en parte   Conocido

El contenido de esta clase te pareció:

Difícil   Regular   Fácil

Los problemas de esta clase te parecieron:

Difíciles   Regulares   Fáciles

Comentarios, preguntas, sugerencias:

Agregar más información o una nueva lección sobre:

Funciones y subrutinas (Sub, Function, Procedure, ...)

Nombre y apellido (opcional):

E-mail (opcional):

    


OmaNet   Curso CyM98 OmaNet - Educación Interactiva
   
www.oma.org.ar/omanet | omanet@oma.org.ar
mensajes: webmaster@oma.org.ar
buy duty free alcohol online duty free cigs where to buy cigars cosmetics duty free prices fragrances duty free where to buy duty free tobacco