Programa y vencerás: Scratch, números primos y divisores

Hace ya casi tres años desde mi último post en este blog. En él recordaba las 250 entradas publicadas desde 2010 y resumía lo más visitado desde entonces. Y cerraba una etapa.

Hoy vuelvo por aquí, no sé si con la intención de retomar el blog (mientras lo escribo lo medito por primera vez…) o simplemente para publicar un recurso con el que estaba trabajando esta tarde y que he considerado oportuno compartir. ¿Dónde?, he pensado. Pues en Esfera TIC. Este blog era el lugar adecuado. Así de sencillo. El espacio está, y la voluntad también, así que ahí va.

Ya desde el año pasado trabajamos en algunos cursos de la ESO con Scratch, un lenguaje de programación visual diseñado especialmente para escolares. Los conceptos de programación son los mismos que en otros lenguajes “de verdad” (salvando las distancias, claro está), solo que en Scratch se presentan de forma muy visual para el alumno, eliminando toda sintaxis caprichosa, que siempre es fuente de errores innecesarios para un alumno al que lo único que debe preocuparle es comprender los fundamentos de la programación. A través de piezas de puzzle encajadas de la forma adecuada, se consigue que la aplicación funcione según se ha diseñado (mientras escribo esta incompleta definición de Scratch, veo ya la necesidad de dedicarle un artículo a este lenguaje…).

Pero cómo avisaba, solo pasaba por aquí para compartir una pequeña aplicación programada con Scratch y que puede resultar útil, tanto para asignaturas de informática como de matemáticas. El programa es capaz de determinar si un número es primo o no, calculando todos sus divisores. Lo hace por fuerza bruta, probando todos los posibles divisores. Para números muy grandes, la resolución puede llevar un tiempo.

Cada vez que he terminado programando algún concepto, técnica o método matemático (sobre todo esos cálculos básicos que todos hemos estudiado en algún momento), tengo más claro que la mejor forma de comprender el funcionamiento de algo es diseñando su algoritmo, programándolo y probándolo.

App Scratch | «¿Es ‘n’ un número primo? Cálculo de divisores de un número»

«Apellido1 Apellido2, Nombre»: procesando cadenas de texto con la hoja de cálculo

Los programas de hoja de cálculo, como LibreOffice, Numbers o Excel, cuentan con funciones que van más allá del cálculo numérico con operaciones básicas y otras fórmulas más complejas. Podemos simular funciones de bases de datos, definir funciones lógicas, realizar conversiones entre unidades de medida o procesar fechas. De este último tipo, incluso podemos encontrar aplicaciones de lo más extrañas, como conocer el día en el que cae el Domingo de Pascua. Todas ellas vienen «de serie». El usuario, por su cuenta, puede definir sus propias funciones. Y este es el tema que ocupa esta entrada.

Personalmente, no hay curso en el que no me encuentre con el problema de analizar una lista de nombres (de alumnos, lógicamente). Los listados que exportan algunas bases de datos nunca tienen el formato adecuado para los programas que necesitan importarlos. Uno se plantea siempre si merece la pena modificarlos manualmente. Pensándolo un par de veces, está claro: mejor procesar los datos con algún programa. El tiempo invertido compensará; y quizá podamos reutilizar el «programita» en años posteriores.

En cualquier caso nos enfrentamos al problema de procesar cadenas de texto. Podríamos programar unas pocas líneas de código en cualquier lenguaje de script y ejecutarlo; pero es una opción demasiado técnica. También podemos optar por utilizar un programa de hoja de cálculo, que incorporan funciones para el tratamiento de texto. Con paciencia y en varios pasos, podemos lograr la conversión que necesitamos.
El problema que se presenta año tras año es el mismo: llega un listado de nombres de personas con este formato.

Apellido1 Apellido2, Nombre

Apellidos y nombre en la misma columna de una hoja de cálculo. Y uno sencillamente necesita los apellidos en una columna y el nombre en otra. Probablemente exista alguna función (muy escondida supongo) que esté diseñada precisamente para este propósito. Sin embargo, una solución más entretenida puede ser combinar funciones de texto ya definidas en la hoja de cálculo. De hecho, puede ser un modo interesante de introducir el concepto de función a los alumnos. Puede ser incluso ser un primer paso en el mundo de la programación.

Volvamos al problema. Para separar apellidos de nombre bastaría con combinar adecuadamente las funciones de texto IZQUIERDA, ENCONTRAR, DERECHA y LARGO. Suponiendo que el nombre completo está almacenado en la celda A1, en la celda contigua (B1) definimos la siguiente fórmula, que nos devolverá los apellidos de la persona:

=IZQUIERDA(A1;ENCONTRAR(",";A1)-1)

En otra celda (C1) definimos esta fórmula, que nos devolverá el nombre de la persona:

=DERECHA(A1;LARGO(A1)-ENCONTRAR(",";A1)-1)

ScriptEs cierto que si necesitamos aplicar esta conversión varias veces en el mismo documento de hoja de cálculo, la definición de las funciones puede resultar un poco tedioso. En este caso, el usuario podría definir su propia función programando una «macro»; un conjunto de instrucciones que hacen exactamente lo mismo que la combinación de funciones anterior. En el programa de hoja de cálculo se accede a esta opción a través del menú: «Herramientas – Macros – Organizar macros». Quizá dedique futuras entradas a este tema. De momento, si alguno ha definido alguna vez (o ha copiado y pegado) alguna macro, un posible fragmento de código sería el siguiente:

REM * Funciones LosApellidos & ElNombre *
Function LosApellidos(NombreCompleto As String)
Dim Apellidos As String
Dim Pos As Integer
Pos = InStr(NombreCompleto,",")-1
Apellidos = Left(NombreCompleto, Pos)
LosApellidos = Apellidos
End Function
Function ElNombre(NombreCompleto As String)
Dim Nombre As String
Dim Pos As Integer
Dim LNC As Integer
lNC = Len(NombreCompleto)
lAP = Len(LosApellidos(NombreCompleto))
Pos = lNC-lAP-2
Nombre = Right(NombreCompleto, Pos)
ElNombre = Nombre
End Function

Con esta definición, suponiendo que el nombre completo de la persona está almacenado en A1, bastaría con utilizar las funciones de este modo en cualquier celda.

Para obtener los apellidos:

=LosApellidos(A1)

Y para obtener el nombre:

=ElNombre(A1)

Podéis encontrar algunos detalles sobre estas funciones en la wiki de reciente creación que comenté hace unos días.

Wiki | Funciones de texto con hoja de cálculo

Huracanes, conejos y piñas: matemáticas en la naturaleza y cómo calcular la sucesión de Fibonacci

Las matemáticas están presentes en la naturaleza, mucho más de lo que podemos imaginar. Formas, proporciones y crecimientos; infinidad de elementos naturales siguen un orden matemático, un patrón. Uno de los casos de estudio más curiosos es la aparición de la sucesión de Fibonacci en muchos elementos naturales.

Por ejemplo, el pasado 28 de octubre a las 6:45 PM EDST, el decimoctavo ciclón tropical de la temporada 2012 adquiría la forma de la espiral de Fibonacci. Era el huracán Sandy.

También es curioso comprobar que si observamos las hileras espirales de escamas en una piña, se pueden contar 8 espirales enrollándose hacia la izquierda y 13 espirales que lo hacen en sentido contrario. O también 13 hacia la izquierda y 21 hacia la derecha. También se pueden dar otras parejas de números, pero en cualquier caso se tratan de números consecutivos en la famosa sucesión de Fibonacci: 1, 1, 2, 3, 5, 8, 13, 21, …

La longitud de tus falanges también sigue la sucesión de Fibonacci:

¿Qué es la sucesión de Fibonacci?

En matemáticas, una sucesión es una lista ordenada de objetos, cada uno de ellos denominado término, elemento o miembro de la sucesión. Podríamos encontrar (e inventar) sucesiones, finitas e infinitas, pero de todas ellas, probablemente una de las que más curiosidad despierta es la sucesión de Fibonacci. De hecho, el interés por esta famosa serie de números no sólo tiene que ver con sus aplicaciones directas en el mundo de las ciencias de la computación y las matemáticas, sino por estar presente, como comentaba, en muchos elementos de la naturaleza.

La sucesión de Fibonacci corresponde a la sucesión infinita de números naturales en la que cada elemento es la suma de los dos anteriores:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17111, 28657, 46638, …

En ocasiones y de forma errónea, se hace referencia a esta secuencia de números como «serie de Fibonacci», sin embargo, una serie matemática es un concepto que tiene que ver con la suma de los términos de una sucesión infinita.

Aunque la sucesión ya había sido descubierta por matemáticos indios, fue Leonardo de Pisa (1170-1250), matemático italiano del siglo XIII conocido como Fibonacci, quien describió la sucesión como solución a un problema de cría de conejos.

El problema decía:

Cierto hombre tenía una pareja de conejos juntos en un lugar cerrado y uno desea saber cuántos son creados a partir de este par en un año cuando es su naturaleza parir otro par en un simple mes, y en el segundo mes los nacidos parir también.

En un lenguaje más actual:

  • Al comienzo del primer mes nace una pareja de conejos y a final de mes se cruzan.
  • Al final del segundo mes, la pareja A da a luz a la pareja B y se vuelve a cruzar la pareja A.
  • Al final de tercer mes, la pareja A da a luz a la pareja C y se cruzan las parejas A y B.
  • Al final del cuarto mes, las parejas A y B dan a luz a las parejas D y E y se cruzan las parejas A, B y C.
  • Al final del quinto mes, las parejas A, B y C dan a luz a las parejas F, G y H y se cruzan las parejas A, B, C, D y E.
  • Y así sucesivamente…

Es decir, las parejas se irían reproduciendo con el siguiente esquema:

  • Fin del mes 0: 0 parejas
  • Comienzo del primer mes: 1 pareja AA
  • Después de 1 mes: 1 pareja AA
  • Después de 2 meses: 2 parejas AA BB
  • Después de 3 meses: 3 parejas AA CC BB
  • Después de 4 meses: 5 parejas AA DD CC BB EE
  • Después de 5 meses: 8 parejas AA FF DD CC HH BB GG EE
  • Después de 6 meses: 13 parejas AA II FF DD LL CC KK HH BB JJ GG EE MM

En cada paso se indica en negrita la pareja de conejos que nace, a la derecha de la pareja adulta (después de un mes) que se han cruzado. Siguiendo la sucesión, es sencillo calcular el número de conejos después de «n» meses.

Podemos observar en la sucesión como el número de parejas de conejos en cada paso es la suma del número de parejas en los dos meses anteriores. Por ejemplo, después de 6 meses tenemos 13 parejas, que es la suma de 5 y 8 (el número de parejas en los meses 4 y 5).

Cálculo del elemento «n» en la sucesión de Fibonacci: F(n)

Para conocer el valor del elemento en cualquier posición de la sucesión, hay varios algoritmos o métodos, que además podemos implementar prácticamente con cualquier lenguaje de programación actual. Si utilizamos la propia definición de la sucesión de Fibonacci, podríamos programar la siguiente función:

La función sería válida para valores de «n» mayores o iguales que 2. Para n=0 la función vale 0, y para n=1 la función vale 1. Observamos que la función se define utilizando la propia definición de la función. Es una definición recursiva de la función y con los lenguajes de programación más extendidos (Java, C++, etc.), desde hace mucho tiempo podemos expresar este tipo de funciones.

Versión recursiva de la función Fibonacci

Para implementar la función Fibonacci con una definición recursiva, simplemente tomamos la función y la expresamos con instrucciones del lenguaje de programación que hemos elegido, en este caso Java. Podemos ver la definición recursiva en la línea 48.

El inconveniente de este tipo de definición recursiva es el número de sumas que se efectúan: concretamente f(n-1)-1 sumas. Es decir, en varios pasos del proceso se repiten cálculos (aunque con estrategias de programación dinámica se pondría solución a este problema).

Versión iterativa de la función Fibonacci

Otro enfoque para abordar el problema es implementar una versión iterativa del problema, con la que solamente es necesario realizar «n» sumas y no «f(n-1)-1» sumas, como en el caso recursivo.  Es decir, en la versión iterativa se va obteniendo en orden y paso a paso cada uno de los elementos de la sucesión en función de los 2 anteriores. Lógicamente, para poder empezar, es necesario definir los valores de los dos primeros elementos de la sucesión: 0 y 1. A continuación se suma 0+1=1 y se obtiene la sucesión 0,1,1. Se vuelven a sumar los dos últimos elementos 1+1=2 y se obtiene la sucesión 0,1,1,2. Se procede de la misma forma con el 1 y el 2, 1+2=3 y se añade a la sucesión: 0,1,1,2,3. Estos pasos son exactamente los que están programados en el código Java que se muestra a continuación. Se puede observar el cálculo de la suma de los dos elementos anteriores en la línea 38.

Fibonacci y diseño

También la sucesión de Fibonacci llega al diseño de interiores. Podéis echarle un vistazo a este curioso armario con una distribución de cajones siguiendo la famosa sucesión. Lo compartía el blog de matemáticas Gaussianos.

Y un último intento de explicar la sucesión de Fibonacci:

Wikipedia | Sucesión de Fibonacci
Wolfram|Alpha | Primeros números de la sucesión
Programa Java (rextester) | Versión iterativa | Versión recursiva
Fotografía | Fibonacci Cabinet de Utopia Architecture & Design (vía Gaussianos)

Piedra, papel, tijera, lagarto, Spock. Una cuestión de combinatoria

The Big Bang Theory es una de las mejores series que he visto en mucho tiempo. En ella se hacen continuamente referencias al mundo de las matemáticas, la física y ciencia en general. En mi opinión el guión está lleno de genialidad. Mi serie favorita, sin más.

La serie cuenta con su propia página en Wikipedia que presenta a los personajes, cada uno de ellos con alguna rareza:

La serie comienza con la llegada de Penny, aspirante a actriz, al apartamento vecino que comparten Sheldon y Leonard, dos físicos, que trabajan en el Instituto Tecnológico de California (Caltech). Ambos son intelectuales brillantes en su trabajo, amigos a su vez de Howard y Raj, que son presentados como unos completos geeks, muy alejados de las inquietudes y problemas de la gente común. Howard Wolowitz es un ingeniero pseudo-galán de origen judío, paradigma de una película psicodélica de los sesenta. Rajesh Koothrappali es astrofísico de nacionalidad india. En el curso de la serie se muestra la dificultad de los protagonistas masculinos para relacionarse con personas fuera de su entorno, principalmente de sexo femenino, dando lugar a situaciones cómicas.

La serie contiene una gran cantidad de situaciones muy cómicas y referencias a principios y teorías físicas auténticas, aunque son simplificados al máximo para poder ser entendidos rápidamente por la audiencia que no posea estudios en física, matemáticas o ingeniería.

De todos los personajes, probablemente el más popular es Sheldon Cooper. El blog emezeta publicaba «20 razones por las que gusta Sheldon Cooper»: sus normas y cláusulas, el uso que hace del Klingon, su infancia, sus referencias a la tecnología o sus teorías en general. Una de sus rarezas más divertidas es su versión del popular juego «Piedra, papel o tijera». Según él, «está demostrado que los jugadores que se conocen empatan entre un 75 y un 80% de las veces por el número limitado de resultados». Es por esta razón que tiene su propia versión del juego, que incluye a un lagarto y el saludo de Spock en Star Trek. En varios capítulos de la serie aparecen los personajes jugando a «Piedra, papel, tijera, lagarto, Spock». En esta escena explica las reglas del juego:

La lista de las 10 reglas del juego es la siguiente:

1. Scissors cuts Paper
2. Paper covers Rock
3. Rock crushes Lizard
4. Lizard poisons Spock
5. Spock smashes Scissors
6. Scissors decapitates Lizard
7. Lizard eats Paper
8. Paper disproves Spock
9. Spock vaporizes Rock
10. Rock crushes Scissors

En español:

“Las tijeras cortan el papel, el papel cubre a la piedra, la piedra aplasta al lagarto, el lagarto envenena a Spock, Spock destroza las tijeras, las tijeras decapitan al lagarto, el lagarto se come el papel, el papel refuta a Spock, Spock vaporiza la piedra, y, como es habitual… la piedra aplasta las tijeras.”

Las reglas en un grafo dirigido

Incluso escuchando con atención, no resulta sencillo memorizar todas las posibles combinaciones de posibles resultados. Es por ello que podemos encontrar publicados en Internet infinidad de gráficos explicando detalladamente las reglas. Se suele utilizar lo que se conoce en matemáticas como grafo: una serie de puntos (vértices o nodos) unidos por líneas (aristas). Para representar las reglas del juego son necesarios 5 puntos y 10 líneas. Los puntos son las 5 posibles opciones del juego: piedra, papel, tijera, lagarto o Spock. Las líneas representan las distintas combinaciones entre las opciones de juego. En particular, las aristas (líneas) de este grafo son del tipo «dirigidas», representadas con una flecha, para indicar que no es lo mismo que el jugador 1 saque «piedra» y el jugador 2 saque «tijera», que al contrario.

Cuestión de combinatoria

Observamos 10 combinaciones posibles. Este es un dato que podemos ver a simple vista, contando el número de flechas, que no son demasiadas. Pero, ¿cuántas combinaciones posibles habría si quisiéramos incluir un elemento más en el juego? ¿y si fueran un total de 10 elementos? ¿Existe alguna forma de calcular las posibles combinaciones sabiendo el número de elementos que hay que combinar por parejas? Existe un método, y una parte de las matemáticas se encarga precisamente de este tipo de cálculos: la combinatoria.

Para este juego en particular, puesto que solo queremos conocer el número de parejas distintas que se pueden formar, habría que aplicar la fórmula de las combinaciones, donde «n» es el número de elementos para combinar (5 elementos),  y «k» el subgrupo que se forma (parejas: 2 elementos).

Recientemente explicaba la función factorial (!) en este mismo blog. Sustituyendo n por 5 y k por 2, y realizando los cálculos, obtenemos el resultado de 10 combinaciones para 5 elementos agrupados por parejas. Si fueran 10 elementos tendríamos 45 combinaciones y si fueran 20, 190 combinaciones. WolframAlpha también es capaz de realizar el cálculo de forma inmediata utilizando los términos de búsqueda «combinations 10 2».

La combinatoria es una parte de las matemáticas que es fundamental conocer para el cálculo de probabilidades, principalmente para hallar con exactitud el número de casos favorables de un suceso o todos los casos posibles de un determinado experimento.

Piedra, papel, tijera, lagarto, Spock. Versión en Java para jugar

Para los que no tengan ni tiempo ni ganas de memorizar las reglas del juego, pueden jugar directamente con la implementación (siempre mejorable) que he hecho del juego con el lenguaje de programación Java. Básicamente se han programado las reglas utilizando una matriz que almacena el resultado de cada posible jugada, que se genera de forma aleatoria.

(clic sobre la imagen para jugar)

El juego también cuenta con su propio artículo en Wikipedia, y también existe todo tipo de merchandising alrededor de esta genial ocurrencia.

Vídeo TBBT | Rock, Paper, Scissors, Lizard, Spock (subtítulos en español)
Código Java | Rock, Paper, Scissors, Lizard, Spock

Trocitos de código (II). Recursividad y la función factorial

Leí en el blog Fotomat sobre fotografía y matemáticas una fantástica frase para explicar la recursividad. También la fotografía que publica refleja perfectamente el concepto.

«Si un genio te ofrece tres deseos dile que te bastan dos: El 1º lo que quieras y el 2º otros dos deseos. Eso es recursividad

Una definición de recursividad (también llamada recursión o recurrencia) sería

«La recursividad es la forma en la cual se especifica un proceso basado en su propia definición.»

Como se puede observar en la imagen, en el cuadro que sostiene la chica, aparece de nuevo la imagen completa original. Y así sucesivamente, idealmente hasta el infinito. Sin embargo, cuando se utiliza la recursividad en matemáticas, es necesario definir lo que se denomina «caso base», una condición que permite evitar el carácter infinito de la recursividad.

Podemos encontrar muchos ejemplos de recursión en las funciones matemáticas. Uno de los ejemplos clásicos de funciones que pueden definirse de forma recursiva son la función factorial de un número: n!

¿Qué es el factorial de un número?

De nuevo, una definición:

Para todo entero positivo n, el factorial de n o n factorial se define como el producto de todos los números enteros positivos desde 1 (es decir, los números naturales) hasta n.

La letra pi mayúscula que aparece en la fórmula se llama productorio, y es un operador matemático (como el sumatorio) que representa una multiplicación de una serie de números (finita o infinita).

Es decir, para calcular por ejemplo el factorial de 6, y se expresa como 6!, habría que realizar el producto de los número naturales desde 1 (k=1) hasta 6 (que es el valor de n).

Se dice que este método para calcular la función factorial es de tipo iterativo. Se realiza un recorrido (iteración) por los distintos números, multiplicando en cada paso cada número de la serie por el siguiente (que es el anterior más 1).

Se trata de una función que aparece con mucha frecuencia en los cálculos de combinatoria (combinaciones, variaciones y permutaciones), fundamental para el cálculo de probabilidades. De hecho, en cualquier calculadora científica, podemos encontrar una tecla que realiza precisamente esta función sobre un número.

Pero también existe una definición recursiva de la función factorial.

Podemos observar que en la definición de la función factorial (la expresión a la derecha del símbolo «=»), aparece de nuevo la función factorial. Esta situación corresponde con la definición de recursividad que comentábamos al principio: «la forma en la cual se especifica un proceso basado en su propia definición.»

Ahora sabemos que la calculadoras disponen de la función factorial. Pero, ¿cómo se puede programar este cálculo con un ordenador? Los lenguajes de programación también permiten definir funciones de forma recursiva, y un ejemplo de implementación de la función factorial en Java sería la siguiente (clic sobre la imagen para probar el código).

El desarrollo de la función factorial de forma recursiva según el código anterior sería:

factorial(6) = 6·factorial(5)
factorial(5) = 5·factorial(4)
factorial(4) = 4·factorial(3)
factorial(3) = 3·factorial(2)
factorial(2) = 2·factorial(1)
factorial(1) = 1·factorial(0)
factorial(0) = 1

Y procediendo y resolviendo en orden inverso:

factorial(0) = 1
factorial(1) = 1·factorial(0) = 1
factorial(2) = 2·factorial(1) = 2·1 = 2
factorial(3) = 3·factorial(2) = 3·2 = 6
factorial(4) = 4·factorial(3) = 4·6 = 24
factorial(5) = 5·factorial(4) = 5·24 = 120
factorial(6) = 6·factorial(5) = 6·120 = 720

Este último paso se denomina caso base. En algún momento, la recursión debe terminar. Si ni impusiéramos una última condición, la recursión seguiría indefinidamente.

Código Java | Función factorial
En Tiching | Recursividad y la función factorial
Foto Recursividad | Fotomat
Foto Calculadora | por Simon Q en Flickr