Asignatura: Fundamentos de Informática | ![]() |
![]() |
Especialidad: Electrónica - UPV/EHU | ||
Curso académico: 2013-2014 | ||
Profesor: Ismael Etxeberria Agiriano |
Utilizaremos el algoritmo de toda la vida para sumar, es decir, empezaremos por el dígito menos significativo de cada uno de los sumandos (el que está más a la derecha al final de la cadena) e iremos sumándolos teniendo en cuenta el acarreo o llevada. Cuando hayamos terminado con todos los dígitos de uno de los sumandos pero no con los del otro podremos suponer que el resto de los dígitos a la izquierda son ceros, siguiendo la norma de que "los ceros a la izquierda no valen nada".
No sabemos cuál será la longitud del resultado, pero supondremos que será la
del mayor de los sumandos.
En caso de que tras sumar nos quede una llevada por computar, si es posible
desplazaremos todo el resultado a la derecha para incluir la última llevada;
si ya hemos utilizado toda la cadena (según el valor de
TOPE
)
devolveremos un 1 indicando que ha habido
sobrepasamiento, devolviendo un 0 en caso contrario.
Podemos dividir el programa principal y la función propuesta
para que ambos se pongan de acuerdo en el tamaño TOPE
de las
cadenas, así como en el prototipo.
Como ya hemos visto anteriormente, en el lenguaje C esto se realiza
mediante ficheros de cabeceras, de extensión *.h
(del inglés, headers).
Normalmente la inclusión de un fichero de cabeceras no debe suponer un aumento
en el tamaño del programa resultante, es decir, no se debe especificar en
ellos código.
Para eso están las bibliotecas, donde se guardaría la función
propuesta, SumaStrs
.
Para esta función y con previsión de la codificación de otras funciones el fichero de cabeceras de aritmética con cadenas podría ser:
/* AritStrs.h * Módulo de aritmética de enteros con cadenas. */ #define TOPE 25 int SumaStrs (char *res, const char *num1, const char *num2);
Hemos antepuesto const
a la declaración de parámetro de los dos
sumandos para indicar que no se va a modificar la cadena.
De hecho esta declaración va a proteger la implementación de la función
de modificaciones involuntarias.
A modo ilustrativo hemos intercambiado declaraciones tipo puntero como char *res
con declaraciones tipo vector como char res[]
sin ningún problema.
Estos dos modos son intercambiables para el paso de parámetros pero no en la declaración de una
variable local.
Adicionalmente, hemos utilizado dos funciones locales
(que sólo tienen importancia dentro de este módulo):
Digito
y DesplazaDcha
.
Para evitar choques con funciones que se llamen igual en otros módulos
las declaramos como static
, lo que hace que no se
puedan ver y/o utilizar fuera del módulo.
Estas funciones se describen a continuación.
Una posible implementación de la función SumaStrs
se proporciona a
continuación:
/* AritStrs.c * Módulo de aritmética de enteros con cadenas. */ #include <string.h> #include "AritStrs.h" /* Prototipos de funciones locales. * Como no queremos exportarlas anteponemos la palabra static a su * definición. Así sólo son visibles dentro de este programa y se pueden * tener funciones con el mismo nombre en otros módulos */ static int Digito (const char *num, int pos); static void DesplazaDcha (char *num); /* Sumador de números de longitud arbitraria expresados como cadena de * caracteres. * * Se supone que ambos operandos contienen una cadena positiva, es decir, * que no tienen signo. */ int SumaStrs (char res[], const char nu1[], const char nu2[]) { int l1, l2, l3, l4; /* Longitudes de las cadenas */ int llevo; /* Llevada de la suma */ int s; /* Suma parcial de dos dígitos más llevada */ l1 = strlen (nu1); /* l1: longitud de nu1 */ l2 = strlen (nu2); /* l2: longitud de nu2 */ l4 = l3 = l1 > l2? l1:l2; /* l3 y l4: el mayor de entre l1 y l2 */ res [l3] = '\0'; /* Ponemos el terminador a la cadena resultante */ llevo = 0; /* Al principio no hay llevada en la suma */ while (l3 > 0) { /* Vamos de derecha a izquierda */ s = Digito (nu1, --l1) + Digito (nu2, --l2) + llevo; /* Suma parcial */ res [--l3] = '0' + s % 10; /* Unidades de s convertidas a letra */ llevo = s / 10; /* La llevada son las decenas de s */ } if (llevo) { if (l4 == TOPE) /* l4 es la longitud de la cadena resultante */ return 1; /* Sobrepasamiento: no me cabe la llevada en res */ DesplazaDcha (res); /* Si no hay sobrepasamiento desplazar */ res [0] = '1'; /* e insertar la llevada */ } return 0; /* Si llego aquí quiere decir que no hay sobrepasamiento */ }
La función Digito
obtiene el dígito numérico (no carácter)
en una posición dada del número,
devolviendo un cero si se trata de una posición negativa.
La definición de esta función puede ser:
/* Devuelve el dígito (int) correspondiente al carácter en la posición pos, * considerando un cero a la izquierda cuando se hace referencia a una * posición negativa. * * Ejemplos: * - Digito ("46", 0) -> 4 * - Digito ("46", 1) -> 6 * - Digito ("46", -2) -> 0 (dos ceros a la izquierda 0046) */ static int Digito (const char *num, int pos) { if (pos < 0) return 0; return num [pos] - '0';/* Ej. '1' - '0' -> 1 ya que 31 - 30 -> 1 */ }
La función DesplazaDcha
copia toda la cadena una posición a la derecha,
lo cual sirve en nuestra función para introducir la última llevada.
La definición de esta función puede ser:
/* Desplaza una cadena a la derecha, manteniendo el primer carácter. * Si antes contenía "Hola" luego contendrá "HHola" */ static void DesplazaDcha (char *num) { int lon; lon = strlen (num); while (lon >= 0) { num [lon + 1] = num [lon]; lon--; } }
Se ilustra un programa principal con una llamada convencional, una llamada con sobrepasamiento y una llamada en la que los operandos se introducen del teclado, teniendo en cuenta el tamaño máximo reservado para las cadenas.
/* 14-001.c (laboratorio) * * Programa que demuestra el uso del Sumador de números naturales positivos * (sin signo) de longitud arbitraria expresados mediante cadenas de caracteres. */ #include <stdio.h> #include <stdlib.h> #include "aritstrs.h" int main (void) { char n1[TOPE+1], n2[TOPE+1], rs[TOPE+1]; int sob; /* Un caso simple */ sob = SumaStrs (rs, "56789", "9521032"); printf (" 56789\n" "+ 9521032\n" "---------\n" " %s\n\n", rs); /* Sobrepasamiento cuando el TOPE es 25: al número mayor le sumamos 1 */ sob = SumaStrs (rs, "9999999999999999999999999", "1"); printf ("(%d)%s\n\n", sob, rs); /* Caso general. Ojo: no introducir un número de mayor longitud que TOPE */ printf ("Introduce un número entero (máximo %d dígitos): ", TOPE); gets (n1); printf ("Introduce otro número entero (máximo %d dígitos): ", TOPE); gets (n2); sob = SumaStrs (rs, n1, n2); /* Pasamos la anchura de la cadena como parámetro: %*s */ printf ("%*s\n+%*s\n---------------------------\n%s%*s\n", TOPE+2, n1, TOPE+1, n2, sob? " 1":" ", TOPE, rs); system ("pause"); return 0; }
El algoritmo para la resta será de similar características.
En este caso no podemos tener un sobrepasamiento
pero sí podemos tener como resultado un número negativo, condición que
será expresada devolviendo el signo (0
positivo, 1
negativo).
Una particularidad de este algoritmo es que vamos a buscar cuál de los dos números es mayor ya que en función de eso se podrá deducir el signo del resultado. Además, siempre tenemos que restar al mayor el menor.
Es buen ejercicio descubrir los entresijos del algoritmo analizando el código resultante.
Si queremos plantear la realización de una biblioteca de operaciones aritméticas con cadenas introduciríamos en el fichero de cabeceras anterior nuestra nueva función, conservando la anterior:
/* AritStrs.h */ * Módulo de aritmética de enteros con cadenas. */ #define TOPE 25 int SumaStrs (char *res, const char *num1, const char *num2); int SubsStrs (char *res, const char *num1, const char *num2);
Podemos introducir la función en el mismo fichero fuente que SumaStrs
.
Una posible implementación de la función SubsStrs
se proporciona a
continuación:
/* Prototipo de otra función local */ static void EliminaCerosIzda (char *num); /* Restador de números de longitud arbitraria expresados como cadena de * caracteres. * * Se supone que ambos operandos contienen una cadena positiva, es decir, * que no tienen signo. */ int SubsStrs (char *res, const char *nu1, const char *n2) { int l1, l2, tmp; char *n1, *n2; int r; int signo; int debo; l1 = strlen (nu1); l2 = strlen (nu2); if (l1 > l2) signo = 0; else if (l2 > l1) signo = 1; else if (strcmp (nu1, nu2) < 0) signo = 1; else signo = 0; if (signo) { n1 = nu2; n2 = nu1; /* Intercambiar longitudes */ tmp = l1; l1 = l2; l2 = tmp; } else { n1 = nu1; n2 = nu2; } res [l1] = '\0'; /* Ponemos el terminador a la cadena resultante */ debo = 0; /* Al principio no debo nada en la resta */ while (l1 > 0) { r = Digito (n1, --l1) - Digito (n2, --l2) - debo; if (r < 0) { r += 10; debo = 1; } else debo = 0; res [l1] = '0' + r % 10; /* Unidades de r convertidas a letra */ } EliminaCerosIzda (res); return signo; }
Además de la función local Digito
cuya codificación se ha proporcionado
anteriormente se ha utilizado la función
EliminaCerosIzda
.
/* Eliminar todos los ceros a la izquierda (menos el último si es 0) */ static void EliminaCerosIzda (char *num) { int n0; /* Número de ceros a la izquierda */ int nd; /* Número de dígitos significativos */ if (num [0] == '0') { /* Si el primer carácter es '0' */ /* Contar ceros */ n0 = 0; while (num [n0] == '0' && num [n0] != '\0') n0++; if (num [n0] == '\0') /* Si todos son ceros */ num [1] = '\0'; else { /* copiar los digitos significativos sobreescribiendo los ceros */ nd = 0; while (num [n0+nd] != '\0') num [nd++] = num [n0+nd]; num [nd] = '\0'; } } }
Se ilustra un programa principal con una llamada convencional, una llamada con resultado negativo y una llamada en la que los operandos se introducen del teclado, teniendo en cuenta el tamaño máximo reservado para las cadenas.
/* 14-002.c * * Programa que demuestra el uso del Restador de números positivos de longitud * arbitraria expresados como cadena de caracteres. */ #include <stdio.h> #include "AritStrs.h" void main (void) { char n1[TOPE+2]; /* Número máximo de dígitos + signo + terminador */ char n2[TOPE+2]; char rs[TOPE+2]; /* Un caso simple */ SubsStrs (rs, "56789", "52103"); printf (" 56789\n" "- 52103\n" "---------\n" " %s\n\n", rs); if (SubsStrs (rs, "1", "21")) printf ("-%s\n\n", rs); /* Caso general. Ojo: no introducir un número de mayor longitud que TOPE */ printf ("Introduce un número entero (máximo %d dígitos): ", TOPE); gets (n1); printf ("Introduce otro número entero (máximo %d dígitos): ", TOPE); gets (n2); if (SubsStrs (rs, n1, n2)) printf ("%12s\n-%11s\n------------\n -%10s\n", n1, n2, rs); else printf ("%12s\n-%11s\n-------------\n%12s\n", n1, n2, rs); }
La resolución consiste básicamente en una llamada a la función de suma
(SumaStrs
)
o a la de resta
(SubsStrs
)
de cadenas, calculando el signo resultante.
Según sean los signos de los operandos n1
y n2
,
la operación a realizar para la suma con signo se detalla en
la tabla 14.1.
n1+n2 | ||||
---|---|---|---|---|
Caso | Signo n1 | Signo n2 | Operación a realizar | Función |
1 | + | + | n1+n2 | SumaStrs |
2 | - | - | -(|n1|+|n2|) | SumaStrs |
3 | - | + | n2-|n1| | SubsStrs |
4 | + | - | n1-|n2| | SubsStrs |
Para saber si un número n
expresado como cadena
es positivo o negativo será suficiente con mirar
si el primer carácter de la cadena es el signo '-'
.
La Tabla 14.2 muestra la condición en ambos casos.
Signo | Verificación | Estilo alternativo |
---|---|---|
Es negativo | n[0] == '-' | *n == '-' |
Es positivo | n[0] != '-' | *n != '-' |
Cuando querramos realizar la llamada a la función de suma
(SumaStrs
)
o a la de resta
(SubsStrs
),
como estas funciones no entienden de signos tendremos que enviarles la subcadena
sin el signo, es decir, si el número n
es negativo realizaremos la llamada con
eliminando el signo, |n|
, mediante
&n[1]
o, lo que es lo mismo, n+1
;
si n
es positivo |n|
es &n[0]
o,
lo que es lo mismo, n
.
Aclarados estos puntos podemos ver una posible resolución de la función de
SumaconSigno
,
que utiliza la función DesplazaDcha
ya introducida y explicada anteriormente
en este capítulo.
No vamos a volver a especificar el prototipo.
int SumaConSigno (char res[], const char nu1[], const char nu2[]) { int signo; if (*nu1 != '-' && *nu2 != '-') /* Caso 1 */ return SumaStrs (nu1, nu2, res); /* La función termina */ if (*nu1 == '-' && *nu2 == '-') { /* Caso 2 */ *res = '-'; return SumaStrs (&nu1[1], &nu2[1], &res[1]); /* La función termina */ } if (*nu1 == '-') signo = SubsStrs (nu2, &nu1[1], res); /* Caso 3 */ else signo = SubsStrs (nu1, &nu2[1], res); /* Caso 4 */ if (signo) { DesplazaDcha (res); *res = '-'; } return 0; }
Según sean los signos de los operandos n1
y n2
,
la operación a realizar para la resta con signo se detalla en la tabla 14.2.
n1-n2 | ||||
---|---|---|---|---|
Caso | Signo n1 | Signo n2 | Operación a realizar | Función |
1 | + | - | n1+|n2| | SumaStrs |
2 | - | + | -(|n1|+n2) | SumaStrs |
3 | + | + | n1-n2 | SubsStrs |
4 | - | - | |n2|-|n1| | SubsStrs |
Todos los casos con suma (SumaStrs
) tienen peligro de sobrepasamiento
y es lo que devolverá esta función.
Por todas las analogías con la función SumaConSigno
el resto de las explicaciones
no aportan gran cosa.
Por ello podemos mostrar una posible resolución de la función SubsConSigno
:
int SubsConSigno (char res[], const char nu1[], const char nu2[]) { int signo; if (*nu1 != '-' && *nu2 == '-') /* Caso 1 */ return SumaStrs (nu1, &nu2[1], res); /* La función termina */ if (*nu1 == '-' && *nu2 != '-') { /* Caso 2 */ *res = '-'; return SumaStrs (&nu1[1], nu2, &res[1]); /* La función termina */ } if (*nu1 != '-') signo = SubsStrs (nu1, nu2, res); /* Caso 3 */ else signo = SubsStrs (&nu1[1], &nu2[1], res); /* Caso 4 */ if (signo) { DesplazaDcha (res); *res = '-'; } return 0; }
Un programa que utilice la aritmética con signo aquí especificada requerirá la definición
de los números con un tamaño suficiente de acuerdo al
máximo número de dígitos TOPE
.
Consecuentemente, la correspondiente cadena tendrá TOPE
caracteres más uno para el signo más
un terminador.
El fichero de cabeceras final AritStrs.h
incluyendo todas las funciones
accesibles podría quedar como sigue:
/* AritStrs.h */ * Módulo de aritmética de enteros con cadenas. */ #define TOPE 25 int SumaStrs (char *res, const char *num1, const char *num2); int SubsStrs (char *res, const char *num1, char *num2); int SumaConSigno (char *res, const char *num1, const char *num2); int SubsConSigno (char *res, const char *num1, const char *num2);
Se ilustra un programa principal con llamadas cubriendo los casos posibles.
/* 14-003.c (laboratorio) * * Programa que demuestra el uso del la aritmética con signo de números * de longitud arbitraria expresados como cadena de caracteres. */ #include <stdio.h> #include <stdlib.h> #include "AritStrs.h" int main (void) { char rs[TOPE+2]; /* Nº máximo + signo + terminador */ SumaConSigno (rs, "12", "10"); printf (" 12 + 10 = %s\n", rs); SumaConSigno (rs, "-12", "-10"); printf ("-12 + -10 = %s\n", rs); SumaConSigno (rs, "-12", "10"); printf ("-12 + 10 = %s\n", rs); SumaConSigno (rs, "12", "-10"); printf (" 12 + -10 = %s\n", rs); SubsConSigno (rs, "12", "-10"); printf (" 12 + -10 = %s\n", rs); SubsConSigno (rs, "-12", "10"); printf ("-12 + 10 = %s\n", rs); SubsConSigno (rs, "12", "10"); printf (" 12 + 10 = %s\n", rs); SubsConSigno (rs, "-12", "-10"); printf ("-12 + -10 = %s\n", rs); system ("pause"); return 0; }