Visual Basic Foro
General => General => Mensaje iniciado por: YAcosta en Junio 24, 2015, 11:05:06 pm
-
Esto mensaje lo expuso un amigo y lo republico aqui a ver quien la hace, dice:
Les voy a proponer un desafío algoritmico no tan dificil, pero quizás tengan que pensar un poco.
Tenemos un número, por ejemplo 49 y además dos símbolos: A y B.
A significa "multiplica por uno" y B significa "multiplica por dos".
Si escribo una cadena de símbolos A y B, por el orden en que se escriban "el peso" va a ir aumentando como en los números binarios, es decir el primero va a valer 2^0 el segundo 2^1 el tercero 2^2 y así sucesivamente.
Para escribir el 49 debemos escribir:
A B A A B
Según los pesos, los números serían:
A B A A B
1 2 4 8 16 (sólo pesos)
Pero como B es el símbolo que siempre multiplica por 2, tenemos:
A B A A B
1 4 4 8 32
Donde 1+4+4+8+32 = 49 que es correcto.
El reto es crear un algoritmo que sirva para cualquier numero, encontrar su representación en símbolos A y B.
-
nadie?
-
HOLA!!!
No le veo la dificultad, ya que con un bin2dec y todas A el problema estaria resuelto.
GRACIAS POR LEER!!!
-
HOLA!!!
No le veo la dificultad, ya que con un bin2dec y todas A el problema estaria resuelto.
GRACIAS POR LEER!!!
Respuesta Incorrecta papa
-
HOLA!!!
No le veo la dificultad, ya que con un bin2dec y todas A el problema estaria resuelto.
GRACIAS POR LEER!!!
No, el problema no dice que codifiques en binario y luego reemplaces unos por A y ceros por B.
Esta es una codificación totalmente diferente a la codificación binaria (por ello es un desafío algorítmico)
Para ilustrártelo mejor, verifica el ejemplo que te proporcionaron:
El número 49 está codificado como ABAAB (longitud 5)
El número 49 en binario es: 110001 (longitud 6)
-
interesante para pensar un rato después me pongo haber si me sale,
para que se entienda dejo esta tabla hasta el numero 15
A 1
B 2
AA 3
BA 4
AB 5
BB 6
AAA 7
BAA 8
ABA 9
BBA 10
AAB 11
BAB 12
ABB 13
BBB 14
AAAA 15
-
Con el numero que queres, haces esto en un bucle:
Si el numero es par, restarle 2. Si es impar, restarle 1. (esto indica la LETRA de este digito, A si es impar, B si es par).
Al resultado, dividirlo por 2.
Y volver hasta arriba, hasta que el resultado de la division resulte 1 o 0 (si es 1 la primer letra es A, y si es 0 indica que es B).
Tener en cuenta que los digitos que devuelve el bucle son LIFO (el que primero entra, es el ultimo en salir)
-
Como seria eso coco?? me perdi :-\
-
Private Function ChangeBaseBizarra(ByVal lNumero As Long) As String
Do
'// es impar?
If lNumero And 1 Then
'// si, es impar, agregar una A
ChangeBaseBizarra = ChangeBaseBizarra & "A"
'// decrementar en 1 al numero (volver a un numero par y de paso bajar el orden)
lNumero = lNumero - 1
Else
'// no, es par, agregar una B
ChangeBaseBizarra = ChangeBaseBizarra & "B"
'// decrementar 2 unidades (bajar el orden)
lNumero = lNumero - 2
End If
lNumero = lNumero / 2
Loop While Not (lNumero <= 0)
End Function
Resulta que esta idea me salió pensando que el primer "digito" sale de saber si es par o impar nada mas... Asi que simplemente viendo si el numero es impar o par, restando 1 o 2 (depende si es par o impar) y dividiendo por 2, puedo repetir el proceso, ya que "le bajo el orden" (seria el exponente de 2^n, donde n es el exponente). y resulta que funciona asi!
-
Buena Coco entonces Argentina = 1 chile = 0 :D
-
Buena Coco entonces Argentina = 1 chile = 0 :D
Y el lunes Chile también quedara en CERO!!! ...espero :-)
-
Coco estaba tibio con la respuesta, pero parte de la respuesta es explicar de una manera concreta como solucionarlo y como estaba muy cerca, les regalo la solución:
La clave para resolver este problema es "recursión", veamos porque:
Vamos a generar una tabla de números para observar el patrón de generación:
1 A
2 B
3 AA
4 BA
5 AB
6 BB
7 AAA
8 BAA
9 ABA
10 BBA
11 AAB
12 BAB
13 ABB
14 BBB
15 AAAA
16 BAAA
17 ABAA
18 BBAA
19 AABA
.
.
.
Ok, lo primero que notamos es que hay un patrón y está clarísimo.
Lo primero más obvio es notar que cuando un número es par, empieza en B, y cuando es impar empieza en A.
Lo que quizás tome un poco más de tiempo descubrir es que un patrón viejo se repite agregándole una A o una B segun sea par o impar, observemos el patrón generado por ejemplo por el número 4 = BA, ahora miremos el patrón del número 9 = ABA y ahora el del número 19 = AABA.
Si queremos resolver el patrón para el 19 (AABA), primero ponemos una "A" (porque es impar) y luego ponemos a continuación el patrón del 9 (ABA), para resolver el patrón del 9 (ABA) ponemos una "A" (porque es impar) y ponemos a continuación el patrón del 4 (BA). Para resolver el patrón del 4 (BA) ponemos una "B" (porque es par) y luego ponemos el patrón del 1 (A). Y ya sabemos resolver el patrón del 1 a ojos cerrados.
Es decir, para el patrón de cualquier número, primero debemos resolver patrones de números anteriores, y luego concatenarlos hasta llegar al caso base. Para este algoritmo el caso base (a ojos cerrados) es cuando es 1 = A y 2 = B.
Por lo tanto necesitamos una función que se llame a sí misma (recursiva) para que calcule los valores pasados, hasta que sea tan obvio de calcular que tire la respuesta inmediata (caso base).
Pero como saber que numero le corresponde calcular previamente para resolver por ejemplo 19?
Aqui otra vez pensamos si hay alguna relación:
En el ejemplo anterior:
Para calcular el 19, necesitamos el 9. (19=AABA y 9=ABA)
Para calcular el 9, necesitamos el 4. (9=ABA y 4=BA)
Y por ejemplo para calcular el 17 necesitamos el 8. (17=ABAA y 8=BAA)
Entonces la relación es (n-1)/2
Nótese que esto funciona para los números impares... y para los pares? veamos la tabla y observamos que:
Para calcular el 8, necesitamos el 3. (8=BAA y 3=AA)
Para calcular el 10, necesitamos el 4. (10=BBA y 4=BA)
Para calcular el 16, necesitamos el 7. (16=BAAA y 7=AAA)
Entonces la relación es (n-2)/2
Ok entonces ya tenemos un algoritmo, pero como hacemos la función recursiva? De la siguiente manera:
A tener en cuenta:
* El caso base: cuando n =1 o n =2 vale A y B respectivamente
* Si n es impar, calcula primero el valor de (n-1)/2 y luego concaténalo con "A".
* Si n es par, calcula primero el valor de (n-2)/2 y luego concaténalo con "B".
El pseudocódigo:
Funcion calcula(entero n)
inicio_funcion
si (n = 1) retorna "A"
si (n = 2) retorna "B"
si (n>=3)
si (n es impar)
retorna "A" concatenado con calcula((n-1)/2)
si (n es par)
retorna "B" concatenado con calcula((n-2)/2)
fin_funcion
-
Hola "amaldonado". Sin ningun tipo de bronca ni ofensas, mi explicación resulta mas valida que la que expones vos "usando patrones". Lo digo en base a que dijiste que la mia era "una explicacion tibia", cuando en realidad la matematica respalda la misma.
Te adjunto un .pdf que me tomé la molestia de hacer tan solo explicando que matematica resulta estar atras de todo esto.
Explicacion.pdf (https://www.dropbox.com/s/o9mc02tf5texqgf/Explicacion.pdf?dl=0)
Recomiendo que lo lean los interesados.
Saludos
-
Hola "coco"
Un poco tarde tu explicación no crees?, claro después de haberlo explicado yo eficientemente.
Bueno, suerte en el próximo desafío :)
Por cierto, te contradices un poquito cuando dices "mi respuesta es más válida" para luego decir "la matemática es la misma", como evalúas algo más valido que otro?
-
Hola, no quise subir un pdf antes porque me parecia que la idea era simplemente buscar un algoritmo (leer post original por las dudas que no quede claro lo que pedia el desafio!), a pesar que la matematica ya la tenia hecha (Yvan lo sabe, lo discuti con el por whatsapp).
Vos no lo explicaste eficientemente desgraciadamente. Simplemente propusiste una explicacion trivial.
La proxima que desafies a alguien con un problema matematico tené en cuenta que una explicacion trivial con"patrones" no tiene el mismo sustento que las ecuaciones genericas (como las que usé yo). (excepto claro está, que tus patrones cumplan con las leyes de induccion matematica, y puedas demostrarlo).
Saludos!
-
Si leí tu PDF, un poco exagerado porque no era el caso, no se pedía una demostración matemática (que por cierto de inducción no tiene nada, simplemente usaste un poco de lógica y ya está).
Para ser inducción matemática necesitas construir el caso base, y luego generalizar para un n +1. Presentar una hipótesis inductiva y luego demostrarla, pero eso no lo haces en el PDF.
Lo siento amigo "coco" pero esto te lo digo sin animo de ofensa ni ningún tipo de bronca.
¡Que tengas un buen día! :)
P.d. No era un problema matemático, era un desafío algorítmico, un poco de comprensión lectora no estaría mal eh?
-
Me referia a que lo tuyo deberia poder ser demostrado por induccion. Debdio a que usa patrones (y generalizar)
En cambio, si uno expresa los resultados usando formulas generales, NO hay que recaer en eso.
Saludos
-
Mmm no, no era necesario. Bastaba con resolver el desafío ALGORÍTMICO.
Nos vemos en el próximo.
-
Coco excelente bofetada, esa explicación Matemática fue un K.O..! Muy linda y limpia la función...! Saludos