Ejercicio obligatorio 1

Fecha de entrega: Viernes 11 de abril

Introducción

Como ya sabemos mientras nuestra cultura opera las matemáticas con números decimales las computadoras operan con números binarios. Ahora bien también sabemos que la conversión entre números binarios y decimales es compleja y gastadora de recursos. Entonces una solución es utilizar las computadoras binarias para representar dígitos decimales y efectuar las operaciones sobre estos dígitos por software. Genéricamente representar valores decimales en computadoras se conoce como BCD, binary-coded decimal (decimales codificados como binarios).

En un sistema de tipo BCD podríamos representar al número 130 como sus dígitos 1, 3 y 0, dejando que la computadora codifique cada uno de estos dígitos en su forma binaria. Ahora bien, si quisiéramos operar al 130 para, por ejemplo, sumarle el número 9511, dado que codificamos sus dígitos decimales por separado no podemos utilizar el harware, que opera en binario, para operar la opeación. Deberíamos resolver \(130 + 9511\) dígito a dígito, es decir, sumar \(0 + 1 = 1\), luego \(3 + 1 = 4\), luego \(1 + 5 = 6\) y finalmente \(0 + 9 = 9\), obteniendo \(9641\) que se representará a su vez como sus dígitos decimales de forma individual.

¿Por qué operamos en nuestra cuenta empezando desde las unidades, los dígitos menos significativos, hacia los dígitos más significativos? Porque dado que representamos dígitos decimales si el resultado de la cuenta sobre un dígito hubiera dado igual o superior a 10 deberíamos habernos llevado un dígito al siguiente dígito a la izquierda. Por ejemplo \(130 + 295 = 425\), en ese caso cuando operamos \(3 + 9 = 12\), debemos quedarnos con la unidad 2, como resultado de la cuenta de ese dígito y acarrear la decena a la cuenta siguiente, que será \(1 + 2 + 1 = 4\), donde el último 1 es la decena que acarreamos de la cuenta anterior.

En todo caso si no sabés de qué estamos hablando, repasá los apuntes de la primaria.

Yendo a los contenidos de Algoritmos y Programación, podríamos representar a los números en formato BCD como un arreglo con sus dígitos. Cada dígito será un número entre 0 y 9, por lo que un byte nos sobrará. También por cuestiones de comodidad convendrá representar a los números desde sus dígitos menos significativos hacia los más significativos. De esta forma podríamos representar a los números 130 y 9511 de esta forma:

char a[] = {0, 3, 1};
char b[] = {1, 1, 5, 9};

¿Sirve para algo haberlos representado al revés?, sí, los números del mismo peso de a y b están en la misma posición, i.e. por ejemplo la decena de ambos está en [1]. Incluso podríamos observar que siendo nuestro sistema de representación pesado un polinomio en potencias de la base, cada uno de los dígitos está en la posición \(i\) que se corresponde con su multiplicador de \(10^i\). Dicho de otra manera, el número \(a\) puede reconstruirse como \(a = \sum_{i=0}^{2} 10^i a_i\), esta cuenta dará 130.

Cabe destacar que en la sumatoria anterior la cantidad de iteraciones está relacionada con que a tiene longitud 3. Por fuera de eso, si necesitáramos pedirle a a más dígitos por encima de sus 3 dígitos porque, por ejemplo, quisiéramos sumárselo a b que tiene 4 dígitos, un número en nuestro sistema de representación tiene infinitos dígitos superiores que valen 0.

Notar que nuestra representación BCD en principio sólo admite números positivos.

Trabajo

Impresión

Implementar una función void imprimir_bcd(const char bcd[], size_t digitos); que dado bcd un número en formato BCD de digitos dígitos lo imprima por stdout. El número debe imprimirse utilizando _ como separador de miles, por ejemplo, la función llamada con el vector {7, 6, 5, 4, 3, 2, 1} y 7 como cantidad de dígitos imprimirá la cadena "1_234_567" (notar que no hay '\n' al final de la misma).

Conversión

Implementar una función unsigned long bcd_a_binario(const char bcd[], size_t digitos); que dado un BCD con determinada cantidad de dígitos lo convierta a binario y devuelva esa representación.

Si el BCD fuera tan grande que no entrara en un unsigned long no será problema de esta función, así que no hay que preocuparse por posibles desbordamientos.

Por ejemplo, si esta función recibe {1, 1, 5, 9} como bcd y 4 como digitos debe devolver 9511.

Implementar una función size_t binario_a_bcd(unsigned long binario, char bcd[]); que reciba un número binario y lo almacene en representación BCD en el arreglo bcd. La función debe devolver la cantidad de dígitos que utilizó en el arreglo.

Por ejemplo, si la función recibe 9511 como binario debe devolver 4 y adem ás bcd será cargado en {1, 1, 5, 9}.

Operaciones

Implementar una función size_t sumar_bcd(const char a[], size_t na, const char b[], size_t nb, char r[]); que compute r = a + b. Siendo na y nb la cantidad de dígitos de a y b respectivamente. La función debe devolver la cantidad de dígitos de r.

Implementar una función size_t multiplicar_por_un_digito(const char a[], size_t na, char b, char r[]); que opere \(r = a \times b\). Notar que b es un número de sólo un dígito.

Nota

Recordemos el algoritmo de la multiplicación, supongamos \(9511 \times 3\), deberemos operar la multiplicación del 3 con cada uno de los dígitos de nuestro número para luego sumar los resultados parciales:

9511 x 3 =>

 9511 x
    3
 ====
    3 +
   3  +
 15   +
27    +
=====
28533

Notar que las multiplicaciones parciales son entre dos números de un dígito por lo que su resultado tiene uno o dos.

Aplicación

Implementar una aplicación que le pida indefinidamente números al usuario de a dos por vez (pueden ser en líneas separadas) hasta que se dispare la señal de final de archivo.

El programa tiene que calcular e imprimir la suma de los dos números y la multiplicación entre el primer número y la unidad del segundo número.

Por ejemplo, esta podría ser la salida del programa:

$ ./ej1
>>> 123
>>> 123
123 + 123 = 246
123 * 3 = 369
>>> 9876
>>> 8765
9_876 + 8_765 = 18_641
9_876 * 5 = 49_380
>>> 987654321
>>> 9
987_654_321 + 9 = 987_654_330
987_654_321 * 9 = 8_888_888_889
>>>
$

(Para mayor claridad se agregó ">>> " previo a la entrada del usuario.)

Entrega

Deberá entregarse el código fuente del programa desarrollado.

Ambos programas deben compilar correctamente con los flags:

-Wall -Werror -std=c99 -pedantic

La entrega se realiza a través del sistema de entregas.

El ejercicio es de entrega individual.