Hace un tiempo un usuario me rcomendó escribir y compartir un programa que trabaje sobre el triángulo de Pascal. La verdad no es difícil generar el triángulo, así que para añadir más gusto decidí ir más allá y generar el binomio de Newton de un exponente arbitario. Pero antes de proseguir en este tema vamos a señalar algunas consideraciones teóricas (tal vez para quiénes ya olvidaron sus clases de mate, jeje).
En álgebra, al desarrollar (a+b)^2, obtenemos:
a^2 + 2ab + b^2
y para (a+b)^3:
a^3 + 3a^2b + 3ab^2 + b^3
Pues bien, lo que se quiere es el desarrollo para una potencia entera positiva cualquiera, y que lo imprima "con formato". Es decir, una línea para la base y otra para los exponentes:
3 2 2 3
a + 3a b + 3ab + b
Para obtener el desarrollo general necesitamos el triángulo de Pascal (
http://es.wikipedia.org/wiki/Tri%C3%A1ngulo_de_Pascal). Las tres primeras líneas del triángulo son:
1
1 1
1 2 1
y se construye de esta manera: todas las filas empiezan y terminan con 1, además de la tercera filas en adelante cada elemento se obtiene sumando los dos que tiene directamente arriba, uno a la derecha y otro a la izquierda. En la tercera fila, el "2" se obtuvo sumando 1 + 1 de este modo. Vamos con 4 filas:
1
1 1
1 2 1
1 3 3 1
y ahora el primer "3" de la 4ta fila es la suma 1 + 2 de los elementos que tiene arriba suyo, el otro "3" es la suma 2 + 1, y así sucesivamente.
Pues bien, el j-ésimo elemento de la i-ésima fila del triángulo (empezando los índices en cero) se llama coeficiente
binomial que por falta de una mejor simbología en este portal representaré como <i,j>. Con ésto, el binomio
(a + b)^N se desarrolla como la suma desde
i=0 hasta
i=N de los términos de la forma
<N,i> * a^(N-i) * b^i. O sea, por ejemplo:
(a + b)^3 = <3,0>*a^3 + <3,1>*a^2*b + <3,2>*a*b^2 + <3,3>*b^3
los coeficientes binomiales <3,j> no son más que los elementos de la cuarta fila del triángulo:
1
1 1
1 2 1
1 3 3 1
por tanto
(a + b)^3 = 1*a^3 + 3*a^2*b + 3*a*b^2 + 1*b^3
= a^3 + 3a^2b + 3ab^2 + b^3
y por supuesto, para desarrollar el binomio de orden N necesitamos construir el triángulo de N+1 filas.
Bueno, y ya
. La parte de hacer todos los cálculos no encierra nada que no se pueda comprender leyendo el código fuente, y sus respectivos comentarios. Lo más desafiante (para mí) fue hacer la presentación "formateada" que expliqué antes. Usando algúun tipo de función
gotoxy() o su equivalente es fácil, pues nos movemos a la línea de arriba para escribir los exponentes, y a la de abajo para el resto de la expresión. Sin embargo esta función no es portable por lo que decidí no usarla.
En su lugar pensé hacer algo similar a cómo las pantallas LCD que los aparatitos electrónicos. Una matriz de celdas donde cada celda permite representar un carácter. Un programa debe calcular todas las letras y mandar a imprimirlas. Bueno, ..... creo que la idea quedó clara, se debe disponer una matriz "
board" o tablero de dos filas, e ir rellenando los caracteres adecuados. Luego que se tenga toda la expresión formada, se imprimen con funciones estándares.
El problema es que se debe calcular en tiempo de ejecución el ancho total de las líneas, dependiendo de la potencia del binomio que se quiera. Tomar en cuenta también que los números ocupan un ancho fijo, porque para potencias grandes pueden ser de una, dos, tres cifras, etc. También tener presente que los coeficientes iguales a 1
no se imprimen, como tampoco los exponentes iguales a 1. Este programa, tal como está desarrollado, está limitado a expresiones cuyo ancho sea menor o igual que la pantall (no hace "salto" de línea).
Otra dificultad fue hacerlo enteramente en C (sin usar clases), por eso malloc() y free() por varias partes, jeje. El argumento (potencia del binomio) está pasado como argumento de la línea de comandos. Así que probándolo con potencia 3:
./binomio 3
nos da:
(a + b)^3 es:
3 2 2 3
a + 3a b + 3ab + b
y para divertirnos un poco, con potencia 7:
(a + b)^7 es:
7 6 5 2 4 3 3 4 2 5 6 7
a + 7a b + 21a b + 35a b + 35a b + 21a b + 7ab + b
Vamos con el código:
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
int ** pascal( const int );
int ** tartaglia( const int );
void destroy_pascal( int **, const int );
void destroy_tartaglia( int **, const int );
int digits( int );
int main(int argc, char* argv[]) {
int **A, N;
int i;
int width, col;
char *board[2];
/* Verificando integridad de los datos */
if ( argc < 2 )
return -1;
N = atoi( argv[1] );
if ( N < 0 ) {
printf("Solo para N >= 0\n");
return -1;
}
if ( N == 0 ) {
printf("a + b\n");
return -1;
}
/* Coeficientes de pascal */
A = pascal( N );
/* Calculamos el ancho total de la cadena */
width = 0;
for ( i = 0; i <= (float)N/2; i++ ) {
if ( i == 0 ) /* terminos a^N, y b^N */
width += 2 * ( 1 + digits(N) );
if ( i == 1 ) /* terminos a^(N-1)*b, y a*b^(N-1) */
width += 2 * ( 2 + digits(A[N][i]) + digits(N-1) );
if ( i > 1 ) /* terminos a^(N-i)*b^i */
if ( !(N % 2) && i == (float)N/2 )
/* termino central se suma solo una vez */
width += 2 + digits(A[N][i]) + digits(N-1) + digits(i);
else
/* y los restantes, dos veces */
width += 2 * ( 2 + digits(A[N][i]) + digits(N-1) + digits(i) );
}
/* cadenas " + " */
width += 3 * N;
/* Representacion final */
if ( ( board[0] = malloc( (width + 1) * sizeof(char) ) ) == NULL )
return -1;
if ( ( board[1] = malloc( (width + 1) * sizeof(char) ) ) == NULL )
return -1;
memset( board[0], ' ', width + 1);
memset( board[1], ' ', width + 1);
col = 0;
for ( i = 0; i <= N; i++) {
if ( A[N][i] != 1 ) { /* binomial N sobre i */
col += sprintf( board[1] + col, "%d", A[N][i] );
board[1][col] = ' ';
}
if ( N - i > 0 ) /* base 'a' */
board[1][col++] = 'a';
if ( N - i > 1 ) { /* exponente N - i */
col += sprintf( board[0] + col, "%d", N - i);
board[0][col] = ' ';
}
if ( i > 0 ) /* base 'b' */
board[1][col++] = 'b';
if ( i > 1 ) { /* exponente i */
col += sprintf( board[0] + col, "%d", i);
board[0][col] = ' ';
}
if ( i < N ) {
col += sprintf( board[1] + col, " + ");
board[1][col] = ' ';
}
}
board[0][width] = '\0';
board[1][width] = '\0';
printf( "(a + b)^%d es:\n\n%s\n%s\n", N, board[0], board[1] );
/* Liberando memoria, y saliendo */
free( board[0] );
free( board[1] );
destroy_pascal( A, N);
return 0;
}
/* Construye una matriz que contiene los numeros del triangulo
* de Pascal o Tartaglia de orden N > = 0, con N + 1 filas.
* La matriz es tal que A[i][j] corresponde al binomial (i : j).
* Se devolverá NULL si N < 0, o si no se pudo asignar memoria
* para construir la matriz.
*/
int ** pascal( const int N ) {
int **A;
int i, j;
if ( N < 0 ) return NULL;
if ( ( A = malloc( (N + 1) * sizeof(int *) ) ) == NULL ) return NULL;
for ( i = 0; i < N + 1; i++ )
if ( ( A[i] = malloc( (i + 1) * sizeof(int) ) ) == NULL ) return NULL;
for ( i = 0; i < N + 1; i++ ) {
A[i][0] = 1;
A[i][i] = 1;
/* solo se ejecuta si i > 1 */
for ( j = 1; j < i; j++ )
A[i][j] = A[i-1][j-1] + A[i-1][j];
}
return A;
}
/* Destruye el objeto creado por la función pascal() */
void destroy_pascal( int ** A, const int N ) {
int i;
if ( N < 0 ) return;
for ( i = N; i >= 0; i-- ) {
free( A[i] );
A[i] = NULL;
}
free( A );
A = NULL;
}
/* Un sinónimo de pascal( N ) */
int ** tartaglia( const int N ) {
return pascal( N );
}
/* Un sinónimo de destroy_pascal( N ) */
void destroy_tartaglia( int ** A, const int N ) {
return destroy_pascal( A, N );
}
/* Calcula la cantidad de cifras o digitos que conforman un
* numero entero no negativo;
*/
int digits( int N ) {
int count = 1;
if ( N < 0 ) return 0;
if ( N == 0 ) return 1;
while ( ( N = (N / 10) ) > 0 )
count++;
return count;
}
Mostrar Mensajes
