Fichas de dominó

Las fichas del dominó se pueden enumerar de forma ordenada, como se muestra en la figura de abajo:

domino_imagen

Pues nuestros desafíos de algoritmia van a ser:

  1. Número de una ficha: Vamos a escribir una expresión que dadas dos variables, llamadas menor y mayor, conteniendo los valores menor y mayor de una ficha de dominó respectivamente, calcule el número asociado, según la figura anterior. Por ejemplo, dada una ficha con los números 1 y 5, la expresión debe calcular el número 11 (ten en en cuenta que consideramos el primer elemento 0).
  2. Ficha de un número: También vamos a escribir las expresiones inversas a ésta, es decir, las que obtienen el valor menor y el valor mayor de una ficha a partir de su número de ficha n. Por ejemplo, dado el número 7, la expresión debe calcular los números de la ficha correspondiente, que son el 1 y el 1. Por si no ha quedado claro, el número de ficha es la posición que ocupa, comenzando a contar por la ficha 0-0, cuyo número de ficha es cero.

¡Vamos a resolverlo!

Solución

Como se puede llegar a pensar, el valor menor de una ficha determina la fila, mientras que la diferencia entre ambos indica la columna. Así pues, habrá que comenzar determinando el número que corresponde a la primera ficha de cada fila. Esto aparece así:

valor menor primer valor de
la fila
0 0
1 7
2 13 7+6
3 18 7+6+5
4 22 7+6+5+4
5 25 7+6+5+4+3
6 27 7+6+5+4+3+2

Hay que darse cuenta que el número asociado a la primera ficha de cada fila equivale a la suma de una sucesión aritmética. Y aplicando la fórmula, podemos hallar el primer valor de la fila m:

((7 -m +1 +7)*m)/2 = m*(15-m)/2 = (15*m – m²)/2

Y sólo nos queda por determinar el desplazamiento dentro de la fila, que será función de los dos valores de la ficha. La relación que guardan los dos valores de la ficha con el desplazamiento dentro de la fila es el siguiente:

desplazamiento = mayor – menor.

Por lo tanto, la expresión pedida será la suma de las dos:

(15*menor – menor²)/2 + mayor – menor = (13*menor – menor²)/2 + mayor

Lo que en Java se puede escribir:

int ficha = (13*menor – menor*menor)/2 + mayor;

Y ahora calculemos la ficha de un número.

Dado un número de ficha n, hemos de calcular el valor mayor y menor. En primer lugar, calculemos el menor; debemos encontrar el mayor m que verifique esto:

(15*m – m²)/2<= n

Esto implica encontrar la solución de la siguiente ecuación:

m² – 15*m -2*n = 0

Debemos quedarnos con la parte entera y no negativa de dicha solución. Al ser una ecuación de segundo grado, tiene dos soluciones, que son:

(15 + √(15² – 8*n))/2 y (15 – √(15² – 8*n))/2

Por un lado sabemos que n<27, con lo que:

15² – 8*n>0

Por lo que ambas son soluciones reales. Pero, por otra parte, la primera solución es mayor que 7, que no es un valor aceptable (como máximo, pueden valer 6). Por lo tanto, el valor buscado será la parte entera de la segunda solución, que en Java se puede escribir así:

int menor = (int)((15 – Math.sqrt(15*15 – 8*ficha))/2);

Una vez calculado el valor menor, el mayor es más sencillo, puesto que simplemente tenemos que hacer esto:

int mayor = ficha – (13*menor – menor*menor)/2;

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s