SoloCodigo

Hola, que tal.

Llevo un par de dias intentando implementar el algoritmo de huffman ( solo por aprender un poco más ), y a pesar de haber leido varios textos todavía tengo algunas dudas que no consigo resolver, a ver si alguien puede echarme una mano.

De momento tengo hecho:

- Tabla con valor-frequencia.
- Lista enlazada con los valores de la tabla ordenada de menor a mayor.

Es decir, teniendo la frase: "hola papa":

hola papa
Table [ 0 ]      Char:           Freq: 1
Table [ 1 ]      Char: o         Freq: 1
Table [ 2 ]      Char: h         Freq: 1
Table [ 3 ]      Char: l         Freq: 1
Table [ 4 ]      Char: p         Freq: 2
Table [ 5 ]      Char: a         Freq: 3
Total r 6
List: Char:     Freq: 1
List: Char: o   Freq: 1
List: Char: h   Freq: 1
List: Char: l   Freq: 1
List: Char: p   Freq: 2
List: Char: a   Freq: 3
Segun lo leido, el arbol huffman se forma así:

Teniendo eso: [espacio](1) - o(1) - h(1) - l(1) - p(2) - a(3)

- Se toman los dos valores con menos frequencia, por ejemplo: ( [espacio] y o ) y se forma un arbol:

   (          2         )
        /               \
" "[1 peso]          o[1 peso]

Y seguimos, ahora nos quedan: h(1) - l(1) - 2 - p(2) - a(3)
Así que cogemos "h" y "l".

Mi duda es que, a mi parecer, h y l deberían quedar asi:


               (          4        )
                   /            \
(          2         )        (         2     )             
        /          \                /       \
" "[1]           o[1]       h(1)       l(1)

Y nos queda:   p(2) - a(3) - 4


Cogemos p( 2 ) y a(3):

                                 (          9       )
                                    /                  \

               (          4        )                 (       5        )
                   /            \                        /          \
(          2         )        (         2     )         p(2)      a(3)     
        /          \                /       \
" "[1]           o[1]       h(1)       l(1)

Y nos queda: 4:

                              (               14             )
                            /                             \

                                  (          9       )            (         4       )
                                    /                  \

               (          4        )                 (       5        )
                   /            \                        /          \
(          2         )        (         2     )         p(2)      a(3)     
        /          \                /       \
" "[1]           o[1]       h(1)       l(1)

Así que de esta forma quedaría el arbol, pero creo que no es correcto.
A ver si me podéis decir donde me voy del plano y me pierdo.

Gracias de antemano

Hola,

Ahora mismo no recuerdo mucho el juego del siete y medio, solo se que las figuras valen 0.5 y las demás 1.
Puedes empezar por idear el algoritmo, algo como:


Se puede mejorar bastante más, de hecho la forma de ver si es repetida no es la optima, pero bueno, para que vayas haciendo creo que sirve.

NOTA: La variable que guarda la suma actual de tus cartas debe ser un float.

Una vez acabada la jugada, es decir, cuando el usuario no quiere más cartas, pasamos al otro usuario, y cuando este también termina, procedemos a ver quien se ha quedado mas cerca del 7.5.

Una forma de descartar ya de entrada es ver si alguno de los dos se ha pasado de dicho valor. Esto es si el resultado de la suma de sus cartas es superior a 7.5, si es así ya no hace falta mirar mas.
Si ambos son inferiores, comparas a ver quien tiene el valor mas alto ( a > b ) ? a : b y ya tienes al ganador.

Espero haberte ayudado.

Saludos

El tema del complemento es unicamente para los controladores o procesadores. Como solo funcionan con 0's y 1's se busco la forma de representar el  signo -

Por otro lado, si una pc usa un complemento u otro no es algo que realmente deberia preocuparte como programador. (aunque es bueno saber como funcionan las cosas).

Saludos

Entonces el ordenador no entiende  -11011 , no? Si no que cuando le damos un: -9, el ordenador pasa a C2 el valor absoluto del numero que le hemos dado, en este caso 9, para saber como representar internamente el -9. Es así?  

Se que doy bastante la bara, disculpad.  

ProfesorX, gracias por tu tiempo.

Por lo que tengo entendido, tanto el complemento a 1 y a 2, ambos solo se usan para buscar y representar números negativos.
Y lo de rellenar con 0's o 1's, me guie por esto que encontre:

" En realidad, un número en complemento a dos se expresa con una cantidad arbitraria de unos a la izquierda, de la misma manera que un número binario positivo se expresa con una cantidad arbitraria de ceros."

Fuente: http://es.wikipedia.org/wiki/Complemento_a_dos

Quizá simplemente lo he interpretado mal.


Sobre esto que diceS:

Ahora, segundo error que tienes, recuerda cuando se utiliza el complemento a 1 y 2, el primer digito indica que el numero es un numero NEGATIVO, no un numero positivo, suponiendo que el numero esta en complemento a 2, 10111 es negativo, ya que su primer digito es uno.

Uhm, si por ejemplo yo presentara el numero 10111 a alguien, y no le dijera si esta en complemento 1 o 2, uno tiende a pensar que es un numero binario sin mas, el 23.
Ahora, si yo lo presento como: 00010111, o como 11110111, entonces sabrá por el 1 o 0 del principio si se trata de un número negativo, o un numero positivo. Es correcto?

Algo que pensaba que tenia claro, pero viendo esto

Recapitulando, solo se calcula el complemento a 2, si el primer digito es uno

se me tambalea un poco. El complemento a 2  se usa para encontrar el negativo de un numero positivo en binario, no?
Entonces, si quiero encontrar el numero en binario que representa el -9, tengo que hacer el complemento a 2 del 9, que es lo que hice en el anterior post. Esto es así, o me lo he inventado?

Respecto a lo de C, todo empezó por eso, porque vi un ejercicio donde hablaban sobre esto, y me di cuenta de que yo no tenía ni idea respecto al tema, así que me puse a investigar.
Creo que puse el enlace al principio pero viniendo a resumir, diciendo que no se puede representar en complemento a dos el numero negativo más grande en su valor absoluto. Como CHAR_MIN = -128, no se podría representar el +128.  Y a partir de ahí fui leyendo a poco, pero no se, me cuesta un poco xD

Gracias chicos  

Hola:

1- Podrías etiquetar el código? Arriba tienes una pestañita. Más que nada es más leible, y da menos "pereza" visual.
2- Puedes explicar mejor el problema, o como debes hacerlo, o para que necesitas los arrays? Ya que al menos por mi parte no lo he visto demasiado claro.

Gracias

La función getc() no devuelve un entero en vez un char ?  

Si, devuelve un entero, que es el codigo en ascii que representa dicha letra o numero.  

Aclarado entonces   , fallo mio por no pensar en castellano  

|| -> OR :

&& -> AND


Saludos  

Si solo quieres saber si es fin de linea ves cogiendo caracteres hasta que encuentres un salto de linea: 'n'. Eso querrá decir que la linea se ha acabado.

Saludos

Si estás en linux puedes re-programar la terminal: http://www.mkssoftware.com/docs/man5/st ... mios.5.asp  
Tendrías que hacerlo en modo no canónico.

Bueno,  más que nada fue para darme a entender.  

Podrías poner un poco de código. No esperarás que adivinemos que te esta fallando, verdad?