Autor Tema: Cambio de base modificado: ¿cómo funciona?.

0 Usuarios y 1 Visitante están viendo este tema.

22 Diciembre, 2015, 05:26 am
Leído 3693 veces

Tachikomaia

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 208
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
La idea es transformar un número decimal a otra forma de numeración. No es simplemente otra base (como 2 o "pasar a binario" por ejemplo), si la base fuese 2 así serían las transformación en mi sistema:
Número decimal____________Transformación
1________________________1
2________________________2
3________________________11
4________________________12
5________________________21
6________________________22
7________________________111
8________________________112
9________________________121
10_______________________122
etc.
Si en vez de ser 1 y 2 fuese 0 y 1, entonces habría casos con 0s delante. Con el método más conocido de transformación no sucede así, por eso esta es otro tipo de transformación.

Bueno, me han dado y explicado un código que por lo visto lo resuelve; les paso el original (python 3 dice) y luego un pseudo:
Código: [Seleccionar]
import math
N=int(input("Introduzca numero:"))
B=int(input("Introduzca base numerica:"))
C=0
while N>=B**C:
    N = N - B**C
    C+=1
lista=[]
print(N,C)
while N>0:
    lista.insert(0,N%B)
    N=N//B
lista=[0]*(C-len(lista)) + lista
print(lista)
N es el número decimal a traducir.
B es la base a la que traducir (nro de símbolos).
C es un contador que inicia en 0
Repetir mientras que el número sea mayor o igual a la cantidad de números generables con C cifras, lo cual se calcula haciendo B^C y en este caso es 1.
____A N, o sea al número a traducir, lle restamos B^C.
____C aumenta 1.
Fin de la repetición.
Creamos una lista vacía.
Mostramos N y C en pantalla (esto creo que es innecesario, no sé si print hace algo extra).
Comentario: Ahora inicia el método normal de transformación.
Repetir mientras el número que nos quedó sea mayor que 0
____Al inicio de la lista, colocamos el resto que nos da N/B.
____N pasa a ser el resultado de N/B, convertido a entero.
Fin del mientras.
En la lista, por delante, colocamos X cantidad de 0s, donde X es C-el largo de la lista.

También lo he traducido a mi lenguaje favorito, pero, aunque entiendo el código (supongo...) no entiendo por qué funciona, cómo es posible que funcione, cual es la lógica, el mecanismo, el método, matemática subyacente, lo que sea. Quisiera que me lo expliquen.

Primero se averigua cuántas cifras tendrá el número. Eso se hace con el 1er while, no entiendo por qué se cuenta el caso de 0 cifras pero lo básico ya está. Si por ejemplo quiero traducir el 7 a base 2 tengo que 2^0 es 1 y por tanto menor que 7, así que podemos deducir que la traducción tendrá más de 0 dígitos (es obvio pero estoy haciendo lo que me dijeron, cuando lo entienda mejor veré si se puede mejorar). 2^1 es 2 y le sumamos el 1 que teníamos, lo cual nos da 3, que sigue siendo menor que 7 por lo que ahora deducimos que la trad tendrá más de 1 cifra. 2^2 es 4 y sumado al 3 nos da 7, así que seguimos, "mientras 7 >= la cantidad de números posibles con C cifras"; deducimos que la trad tendrá más de 2 cifras. 2^3 es 8 que sumado con 7 nos da 15, así que ahora sí paramos, deducimos que la traducción tendrá 3 cifras.
La fórmula B^C puede comprobarse más o menos así:

Números que pueden formarse con 2 símbolos y 0 dígitos:
? Supuestamente es 1, no sé mucho de esto.
1, o sea 2^0

Números que pueden formarse con 2 símbolos y 1 dígito:
1, 2
2, o sea 2^1

Números que pueden formarse con 2 símbolos y 2 dígitos:
11, 12, 21, 22
4, o sea 2^2

O sea... si uno hace una lista lo puede ver mejor, fíjense por ejemplo la que mostré al inicio, si el número a traducir es 7 sabemos que tendrá 3 cifras porque es igual o menor que 2^0 + 2^1 + 2^2. Yo no tengo mucha idea, casi que me parece magia, pero en fin, es lo que puedo explicar o decir por ahora.

La segunda parte o segundo while, hace una traducción común y corriente. Simplemente no entiendo por qué al inicio no funciona y luego sí. Ojo, en realidad acá traduce la diferencia entre:
2^0 + 2^1 + 2^2 o hasta donde corresponda
y N.
En el caso de que N sea 7 la diferencia es 0, así que el while no se hace. Si se hace entonces los restos (ver método común (*)), se agregan a la lista.
(*): https://www.youtube.com/watch?v=xC6snIf0feg

Al final, agrega X 0s delante donde X es C-el largo de la lista. Eso tampoco entiendo bien por qué funciona.

En fin, gracias.

22 Diciembre, 2015, 10:35 am
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,123
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

 En primer lugar con el código que has puesto la transformación sería más bien:

\( 1\longrightarrow{}0 \)
\( 2\longrightarrow{}1 \)
\( 3\longrightarrow{}00 \)
\( 4\longrightarrow{}01 \)
\( 5\longrightarrow{}10 \)
\( 6\longrightarrow{}11 \)
\( 7\longrightarrow{}000 \)
\( 8\longrightarrow{}001 \)
\( 9\longrightarrow{}010 \)

 Ahora fíjate que hay: \( b^1 \) expresiones de \( 1 \) cifra; a continuación \( b^2 \) expresiones de \( 2 \) cifras; a continuación \( b^3 \) expresiones de \( 3 \) cifras y así sucesivamente...

 Por tanto los números comprendidos

\( b^0+b^1+b^2+\ldots+b^{c-1} \) y \( b^0+b^1+b^2+\ldots+b^{c-1}+b^c-1 \)

 estarán representados por \( c \) cifras. Esto justifica el bucle while inicial del código.

 Ahora fíjate que el primer número que está representado por \( c \) cifras es \( b^0+b^1+\ldots+b^{c-1} \); eso es justo lo que le hemos restado a \( N \) en el primer bucle while. Por tanto lo que tenemos representado en \( N \) ahora es que puesto ocupa nuestro nuestro número entre los números de \( c \) cifras.

 Si ocupa el puesto cero; directamente se representará por \( c \) ceros.
 Si ocupa el puesto uno; pues se representará por \( 1 \) uno a la derecha y el resto ceros.

 Entonces basta notar que nuestra representación pude obtenerse simplemente pasando ese puesto a base \( b \) (¡ahora de la forma usual!) y completando con ceros a la izquierda hasta \( c \) cifras.

 Por ejemplo si aplicamos el proceso a \( N=9 \) y \( b=2 \). Tenemos que:

 \( 9-2^0-2^1-2^2=2 \)  (*)

 (pero \( 9-2^0-2^1-2^2-2^3<0 \)). Por tanto \( c=3 \) yhora simplemte pasamos a binario el número \( 2 \) obtenido en (*), \( 2=10_{2)} \). Completamos con ceros a la izquierda hasta tener tres cifras y obtenemos \( 010 \).

Saludos.

22 Diciembre, 2015, 10:17 pm
Respuesta #2

Tachikomaia

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 208
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Entendí un poco más.

Quizá es cuestión de que haga muchos ejercicios manualmente.

Por otro lado ¿habrá alguna forma más sencilla de hacer la transformación?

23 Diciembre, 2015, 10:12 am
Respuesta #3

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,123
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

Por otro lado ¿habrá alguna forma más sencilla de hacer la transformación?

¿Más sencilla en qué sentido? El algoritmo es bastante simple; de hecho una vez calculado el número de dígitos es un cambio de base usual. ¿Para qué lo necesitas?.

Saludos.

23 Diciembre, 2015, 08:11 pm
Respuesta #4

Tachikomaia

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 208
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Citar
¿Más sencilla en qué sentido?
De entender, que sea más fácil entender por qué funciona.

Citar
¿Para qué lo necesitas?
Está en otro tema, quiero que una variable vaya cambiando según la serie de Fibonacci y que otra variable muestre cómo sería dicho número si se transformara a letras usando mi sistema. Pero no quiero que lo hagas, sé que debo usar otra base y supongo que no hay mucho más problema, por ahora simplemente quiero entender este caso que sería más sencillo y aún así me cuesta mucho.

24 Diciembre, 2015, 03:38 pm
Respuesta #5

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,123
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

Citar
¿Más sencilla en qué sentido?
De entender, que sea más fácil entender por qué funciona.

Es que no éste no es difícil.  ;)

Creo que debes de intentar entender cada paso hasta quedar convencido, en lugar de mirarlo "todo de golpe". Comienza comprendiendo por completo como se calcula el número \( c \) de cifras.

Saludos.

25 Diciembre, 2015, 07:26 am
Respuesta #6

Tachikomaia

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 208
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Muy buen consejo, digamos que lo intentaba entender por whiles, o sea en 2 partes + las otras, pero los whiles a su vez tienen partes.

El cálculo de cifras o C.
Es el mínimo número entero que sumándose de esta forma: B^0 + ... + B^C resulta ser mayor que N.
Si B es 2 y N es 9 entonces C es 3, porque:
2^0 = 1
1 + 2^1 = 3
3 + 2^2 = 7
7 + 2^3 = 15
C3 es el mínimo valor con el que N resulta menor.

Lo que no entiendo sobre eso es por qué se cuenta el 0, de hecho acabo de hacer este código que por lo visto funciona igual pero sin contar el 0.
Código: [Seleccionar]
N = 1;
B = 2;
C = 1;
Nums = Math.pow(B, C);
// parte 2:
if (Nums >= N) {
    gotoAndPlay (4);
}
// parte 3:
C = C+1;
Nums = Math.pow(B, C) + Nums;
gotoAndPlay (2);
// parte 4:
N = N-(Nums-Math.pow(B, C));
stop ();
A los programadores no les gusta el goto, pero en la práctica es igual.
¿Entonces es necesario contar el 0? Por lo visto no, aunque cambia la condición: En este caso la suma puede ser igual a N.

------------------------------------------------------------------------

Sin embargo, con ese código N termina siendo 1 más. Por supuesto se puede reducir 1, pero ¿qué es ese N que queda?

Habías dicho:
Citar
Ahora fíjate que el primer número que está representado por c cifras es b0+b1+…+bc−1; eso es justo lo que le hemos restado a N en el primer bucle while. Por tanto lo que tenemos representado en N ahora es que puesto ocupa nuestro nuestro número entre los números de c cifras.

 Si ocupa el puesto cero; directamente se representará por c ceros.
 Si ocupa el puesto uno; pues se representará por 1 uno a la derecha y el resto ceros.
Pero... ¿cómo puedo visualizarlo mejor? Por ejemplo con N 10 C sería 3 y e N resultante sería 3 también. El resultado sabemos que sería 001. 3 cifras, como dice C. Pero ¿y N3 qué tiene que ver? N/2=1, m... ¿qué condiciones tiene ese N? ¿por qué traducir ese N de la forma convencional da el resultado buscado, y traducir el N inicial no? ¿por qué en un caso al forma convencional funciona y en otro no?

26 Diciembre, 2015, 10:44 pm
Respuesta #7

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,123
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

El cálculo de cifras o C.
Es el mínimo número entero que sumándose de esta forma: B^0 + ... + B^C resulta ser mayor que N.
Si B es 2 y N es 9 entonces C es 3, porque:
2^0 = 1
1 + 2^1 = 3
3 + 2^2 = 7
7 + 2^3 = 15
C3 es el mínimo valor con el que N resulta menor.

Lo que no entiendo sobre eso es por qué se cuenta el 0, de hecho acabo de hacer este código que por lo visto funciona igual pero sin contar el 0.
Código: [Seleccionar]
N = 1;
B = 2;
C = 1;
Nums = Math.pow(B, C);
// parte 2:
if (Nums >= N) {
    gotoAndPlay (4);
}
// parte 3:
C = C+1;
Nums = Math.pow(B, C) + Nums;
gotoAndPlay (2);
// parte 4:
N = N-(Nums-Math.pow(B, C));
stop ();
A los programadores no les gusta el goto, pero en la práctica es igual.
¿Entonces es necesario contar el 0? Por lo visto no, aunque cambia la condición: En este caso la suma puede ser igual a N.

Pero en tu propia pregunta das la respuesta; si empiezas en \( C=1 \), pues efectivamente basta cambiar la condición para permanecer en el bucle while de un mayor o igual a un mayor estricto (en tu versión con el goto usas la condición de salida; es decir la traducción directa sería que hubieras puesto la condición\(  N<Nums \) y al empezar en \( C=1 \) pasas a \( N<=Nums \).

Entonces no es que sea mejor una forma de programarlo que otra; son opciones que funcionan. Y si revisas mi explicación inicial de porque se hace así y tomas unos ejemplos es inmediato ver porque funciona de las dos maneras.

Citar
Sin embargo, con ese código N termina siendo 1 más. Por supuesto se puede reducir 1, pero ¿qué es ese N que queda?

Habías dicho:
Citar
Ahora fíjate que el primer número que está representado por c cifras es b0+b1+…+bc−1; eso es justo lo que le hemos restado a N en el primer bucle while. Por tanto lo que tenemos representado en N ahora es que puesto ocupa nuestro nuestro número entre los números de c cifras.

 Si ocupa el puesto cero; directamente se representará por c ceros.
 Si ocupa el puesto uno; pues se representará por 1 uno a la derecha y el resto ceros.
Pero... ¿cómo puedo visualizarlo mejor? Por ejemplo con N 10 C sería 3 y e N resultante sería 3 también. El resultado sabemos que sería 001. 3 cifras, como dice C. Pero ¿y N3 qué tiene que ver? N/2=1, m... ¿qué condiciones tiene ese N? ¿por qué traducir ese N de la forma convencional da el resultado buscado, y traducir el N inicial no? ¿por qué en un caso al forma convencional funciona y en otro no?
[/quote]

Pero no acabo de entender la dudas; de nuevo la simple revisión de ejemplos debería de aclararte porqué funciona. Lo anólamo del sistema de representación que usamos es que permitimos que la cifra de la izquierda sea cero. Pero solventado ese hecho es el  sistema de representación "normal" de números en una base.

Saludos.