Yosue Dijo:
La Matemática en acción:
Primero que todo un saludo a Nuestro querido Profesor Nestor del Prado (y que de paso le deseo lo mejor en la nueva escalada médica) que me llamó interesándose el por qué no había participado en este acertijo donde me conminó a resolver el inciso 4, hallar un algoritmo para determinar los números malvados, y me sacó de la cama que estoy convaleciente de una quemadura y fui y compré un ticket de internet para poder brindarle mi pequeño aporte.
Primero explicaré el algoritmo para realizarlo manualmente y luego un pequeño código en VB para Excel para automatizarlo, “utilizando teorías matemáticas elementales sin utilizar las funciones de conversión a binario o funciones de texto”.
Algoritmo manual.
Nota1: Este algoritmo utiliza una de las formas de llevar un número de base 10 a binario, base 2, además, utilizo la función log2(x) “logaritmo en base 2 de x” para determinar el exponente de la potencia de 2 que es menor que x. De esta función solamente tomo la parte entera.
Por ejemplo para el número x=58 tenemos entero(log2(x)) = 5, esto significa que 2^5=32 es la mayor potencia de 2 que es menor que 58.
Ahora sí el algoritmo paso a paso.
Paso1: Sea x = n, n es el número que verificaremos si es malvado.
Paso2: Si x =0 ó x=1 entonces devolver x, sino los pasos del 3 al 6
Paso3: Sea L2= 2^(entero(log2(x) )) , ver nota de potencia.
Paso4: Sea c= entero(x/L2) , c es la división entera entre x y la mayor potencia de 2 que es menor que x. (Pueden percatarse que c siempre da uno o cero)
Paso5: Sea r=resto(x/L2), r es el resto de la división entera entre x y L2.
Nota2: Voy a utilizar un operador lógico (“XOR” o “OR” exclusivo) que se utiliza en lógica matemática y que no es muy aplicada, pero ya que estamos hablando de números binarios es muy útil utilizarla (se utiliza mucho a la hora de programar ), de todas maneras se puede sustituir por un signo de “+” y el resultado se obtiene, lo que si utiliza el signo de más al final tendría que comparar si el resultado es par o no, si utilizamos XOR el resultado es 0 si es Malvado ó 1 si no lo es.
(a XOR b = 0 si a= b, a XOR b=1 si a<>b ), (a y b pueden ser 0 ó 1)
Paso6: Malvado= c XOR (Repetir pasos a partir del paso 1 con n=r)
Ejemplo.
Para n=3
Paso1: x=3
Paso2: sigo para el paso 3 porque x no es cero ni uno.
Paso3: L2=2^(entero(log2(3)) ) = 2
Paso4: c=entero(3/2)=1
Paso5: r=resto(3/2)=1
Vean que Malvado= x XOR (y esta parte se repite pero devuelve un valor), por tanto este paso queda en espera de este resultado.
1ra Vuelta: Paso6: 1 XOR …. (Este 1 hay que guardarlo para el retorno) Repetir pasos a partir del 1 con n= r, o sea, n=1
Paso1 de la Segunda vuelta(sv) x=1
Paso2sv: como x =1 entonces devolver 1 y salto los pasos del 3 al 6 de la sv.
Retorno al paso 6 de la primera vuelta:
Paso6 primera vuelta: Malvado= 1 XOR 1, (Este último 1 es el que se retornó)
Luego Malvado= 1 XOR 1=0
Por tanto como es cero el 3 es malvado.
Nota: Lo pueden probar para los demás valores, por un problema de espacio no los voy a poner. )Cuando el resultado es cero el número es malvado, cuando es Uno el Número es odioso)
Como pueden ver es un procedimiento que se repite, en informática esto se llama procedimiento recursivo y ahora le explico el procedimiento en VB para Excel.
Rem Primero crearla función Log2(x) porque en VB la función Log(x) es el logaritmo natural de x.
Public Function Log2(x) As Double
Log2 = Log(x) / Log(2)
End Function
Rem Ahora la función Malvado. Esta función es recursiva, se llama a sí misma y nos devuelve al final 0 si es malvado ó 1 si no lo es.
Public Function Malvado(x) As Integer
If x = 1 Or x = 0 Then
Malvado = x
Else
Malvado = Int(x / (2 ^ (Int(Log2(x))))) Xor Malvado(x Mod (2 ^ (Int(Log2(x)))))
End If
End Function
Fin del código.
En VB a Mod b, es el resto de la división entera. Int() es la función entero()
Ahora toman una hoja de cálculo en la columna A ponen consecutivamente hacia abajo los números desde el 0 hasta el 2000 (comiencen en la celda A1); y en la celda B1 escriban lo siguiente:
=Malvado(A1)
Luego arrastren la celda hacia abajo hasta llegar a la celda B2001 y copiaran la formula dada con su correspondiente desplazamiento.
Al final todas las celdas con valores 0, serán Malvados.
Vean que en el código se utilizaron funciones y expresiones matemáticas comunes.
Esta expresión Malvado = Int(x / (2 ^ (Int(Log2(x))))) Xor Malvado(x Mod (2 ^ (Int(Log2(x)))))
Sustituye los pasos del 3 al 6.
Que le aproveche!. Anímense a programar, es un mundo fascinante. Disculpen si no se ve bien el código y la tabla, lo pueden ver en mi página “yosue.cubava.cu”, recuerden poner “https://”, lo pongo así para que Cubadebate lo publique parece que no permite enlaces directos a otros sitios cubanos.
Aquí les dejo los primeros 31 valores:
|
n |
Malvado=0, Odioso=1 |
|
0 |
0 |
|
1 |
1 |
|
2 |
1 |
|
3 |
0 |
|
4 |
1 |
|
5 |
0 |
|
6 |
0 |
|
7 |
1 |
|
8 |
1 |
|
9 |
0 |
|
10 |
0 |
|
11 |
1 |
|
12 |
0 |
|
13 |
1 |
|
14 |
1 |
|
15 |
0 |
|
16 |
1 |
|
17 |
0 |
|
18 |
0 |
|
19 |
1 |
|
20 |
0 |
|
21 |
1 |
|
22 |
1 |
|
23 |
0 |
|
24 |
0 |
|
25 |
1 |
|
26 |
1 |
|
27 |
0 |
|
28 |
1 |
|
29 |
0 |
|
30 |
0 |
Aquí les dejo el excel https://yosue1970.cubava.cu/files/2019/09/Malvados.xlsm
Deja un comentario