Binomio de Newton, y triángulo de Pascal

Iniciado por Yoel Alejandro, 15 Marzo 2014, 21:21 PM

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

Yoel Alejandro

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  :D. 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:
Código (cpp) [Seleccionar]

#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;
}
Saludos, Yoel.
P.D..-   Para mayores dudas, puedes enviarme un mensaje personal (M.P.)

amchacon

El programa es muy bonito y elegante ^^. ¡Good job!


Aunque si la función pascal devuelve NULL, el main no lo comprueba y lo usa de todas formas. Lo que generaría un error de ejcución.

Por estos olvidos se inventaron las excepciones de C++ ^^
Por favor, no me manden MP con dudas. Usen el foro, gracias.

¡Visita mi programa estrella!

Rar File Missing: Esteganografía en un Rar

leosansan


Al ejecutar tu código tal como está me sale esto:


Citar

Process returned -1 (0xFFFFFFFF)   execution time : 1.164 s
Press any key to continue.



¿Alguna idea al respecto?, ¿O acaso funciona con comandos?. Lo he guardado por si acaso.

¡¡¡¡ Saluditos! ..... !!!!



amchacon

Cita de: leosansan en 15 Marzo 2014, 23:51 PM
Al ejecutar tu código tal como está me sale esto:


¿Alguna idea al respecto?, ¿O acaso funciona con comandos?. Lo he guardado por si acaso.

¡¡¡¡ Saluditos! ..... !!!!


Se te ha activado el primer if del código.

Y si, solo funcionaba por comandos. En el codeblocks se lo puedes meter en project -> "Set programs arguments".

Para que funcione tiene que ser un proyecto, no vale un archivo.
Por favor, no me manden MP con dudas. Usen el foro, gracias.

¡Visita mi programa estrella!

Rar File Missing: Esteganografía en un Rar

leosansan

Cita de: amchacon en 15 Marzo 2014, 23:53 PM
Se te ha activado el primer if del código.

Y si, solo funcionaba por comandos. En el codeblocks se lo puedes meter en project -> "Set programs arguments".

Para que funcione tiene que ser un proyecto, no vale un archivo.

Soy un neófito total con la linea de comandos, sencillamente la odio y sólo por el hecho de ver correr este programa es por lo que me intereso en el tema. Es la vuelta a la edad de piedra xD. >:D

¿Alguien podría explicarme brevemente el sistema de funcionamiento?. Gracias de antemano.


¡¡¡¡ Saluditos! ..... !!!!



amchacon

#5
La línea de comandos es muy util a la hora de comunicarse entre programas. Por eso todavía se sigue usando en la mayoría de programas de consola (linux mayormente xD).

Los comandos simplemente son cadenas de texto separadas por espacios:
Citartexto 1 2 3

De esa forma le pasaría al programa 4 cadenas: "texto","1","2" y "3".

De todas formas y con permiso, traduzco para que no tengas que usar linea de comandos:
Código (cpp) [Seleccionar]
#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];
   puts("Introduce el valor de N: ");
   scanf("%d",&N);
   putchar('\n');

   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;
}
Por favor, no me manden MP con dudas. Usen el foro, gracias.

¡Visita mi programa estrella!

Rar File Missing: Esteganografía en un Rar

Yoel Alejandro

#6
Cita de: amchacon en 15 Marzo 2014, 23:03 PM
Aunque si la función pascal devuelve NULL, el main no lo comprueba y lo usa de todas formas. Lo que generaría un error de ejcución.

Por estos olvidos se inventaron las excepciones de C++ ^^

Bueno aunque ahí la culpa es del programador (yo  ;D), se me pasó ese detallito. Hay que cambiar la línea a:
Código (cpp) [Seleccionar]

if ( ( A = pascal( N ) ) == NULL ) return -1;

y creo que soluciona el problema.




leosansan, el error fue porque te faltó el argumento pasado por línea de comandos. Para solucionarlo simplemente compila y cuando te genere el ejecutable abre una ventana de Símbolo del Sistema, y cámbiate ( con el comando cd) al directorio donde tienes el ejecutable. Por ejemplo, supón que se creó en "C:\Documentos\Leo\bin", entonces pones en la consola

cd C:\Documentos\Leo\bin

(si usas una IDE a veces puede ser difícil inspeccionar dónde exactamente crea el .exe). Luego de ello, teclea por ejemplo:

binomio 5

para que te calcule con N=5.

........
Si no quieres hacer nada de eso (o no te funciona), sólo modifica el main() para que pida el valor de N con scanf(), y ya  :D

..........
(EDITO)

No me había dado cuenta que amchacon ya arregló el código para que no requiera argumentos por línea de comandos. Thanks!!

Y gracias también por los elogios a mi programa  :D
Saludos, Yoel.
P.D..-   Para mayores dudas, puedes enviarme un mensaje personal (M.P.)

leosansan

#7
Cita de: yoel_alejandro en 15 Marzo 2014, 21:21 PM

Hace un tiempo un usuario .............
.
¡!!Fui yo, fui yo, leosansan!!!

Cita de: yoel_alejandro en 15 Marzo 2014, 21:21 PM

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.....


Pero es que era lo  que yo te propuse, imprimir el triángulo de Pascal y es justo lo que no hace tu código. Era un reto y te has saltado su objetivo. ;)

Cita de: yoel_alejandro en 15 Marzo 2014, 21:21 PM

así que para añadir más gusto decidí ir más allá y generar el binomio de Newton de un exponente arbitario.


Obtener el desarrollo del binomio no genera ningún problema a partir del triángulo de Pascal. Además creo que tienes algún bug, si no mira las salidas de tu código para N=5, N=15 y N=25:



Citar

N=5

(a + b)^5 es:

5     4       3 2      2 3      4    5
a  + 5a b + 10a b  + 10a b  + 5ab  + b

Process returned 0 (0x0)   execution time : 0.097 s
Press any key to continue.


N=15


(a + b)^15 es:

15      14        13 2       12 3        11 4        10 5        9 6        8 7
       7 8        6 9        5 10        4 11       3 12       2 13       14
15
a   + 15a  b + 105a  b  + 455a  b  + 1365a  b  + 3003a  b  + 5005a b  + 6435a b
+ 6435a b  + 5005a b  + 3003a b   + 1365a b   + 455a b   + 105a b   + 15ab   +
b

Process returned 0 (0x0)   execution time : 1.285 s
Press any key to continue
.


N=25


(a + b)^25 es:

25      24        23 2        22 3         21 4         20 5          19 6
    18 7           17 8           16 9           15 10           14 11
 13 12           12 13           11 14           10 15           9 16
8 17          7 18          6 19         5 20         4 21        3 22       2
23       24    25
a   + 25a  b + 300a  b  + 2300a  b  + 12650a  b  + 53130a  b  + 177100a  b  + 48
0700a  b  + 1081575a  b  + 2042975a  b  + 3268760a  b   + 4457400a  b   + 520030
0a  b   + 5200300a  b   + 4457400a  b   + 3268760a  b   + 2042975a b   + 1081575
a b   + 480700a b   + 177100a b   + 53130a b   + 12650a b   + 2300a b   + 300a b
  + 25ab   + b

Process returned 0 (0x0)   execution time : 1.160 s
Press any key to continue.


Por un lado no sé que son esos números que salen encima del binomio y faltan los exponentes de las potencias los del binomio..

Y ahora compara con las salidas del que código colgaré después:

Citar

N=5


                      (a+b)^5 =
+ 1 a^5 b^0 + 5 a^4 b^1 + 10 a^3 b^2 + 10 a^2 b^3 + 5 a^1 b^4 + 1 a^0 b^5

Process returned 0 (0x0)   execution time : 1.662 s
Press any key to continue.

N=15


                   

                       (a+b)^15 =
+ 1 a^15 b^0 + 15 a^14 b^1 + 105 a^13 b^2 + 455 a^12 b^3 + 1365 a^11 b^4 + 3003
a^10 b^5 + 5005 a^9 b^6 + 6435 a^8 b^7 + 6435 a^7 b^8 + 5005 a^6 b^9 + 3003 a^5
b^10 + 1365 a^4 b^11 + 455 a^3 b^12 + 105 a^2 b^13 + 15 a^1 b^14 + 1 a^0 b^15

Process returned 0 (0x0)   execution time : 0.175 s
Press any key to continue.


N=25



                       (a+b)^25 =
+ 1 a^25 b^0 + 25 a^24 b^1 + 300 a^23 b^2 + 2300 a^22 b^3 + 12650 a^21 b^4 + 53
130 a^20 b^5 + 177100 a^19 b^6 + 480700 a^18 b^7 + 1081575 a^17 b^8 + 2042975 a^
16 b^9 + 3268760 a^15 b^10 + 4457400 a^14 b^11 + 5200300 a^13 b^12 + 5200300 a^1
2 b^13 + 4457400 a^11 b^14 + 3268760 a^10 b^15 + 2042975 a^9 b^16 + 1081575 a^8
b^17 + 480700 a^7 b^18 + 177100 a^6 b^19 + 53130 a^5 b^20 + 12650 a^4 b^21 + 230
0 a^3 b^22 + 300 a^2 b^23 + 25 a^1 b^24 + 1 a^0 b^25

Process returned 0 (0x0)   execution time : 1.431 s
Press any key to continue.
                                   

En la página web no sé si lo anterior sale exacto, pero para muestra una imagen de uno de los triángulos:


Y perdonen el signo más que sale al principio pero estoy perezoso, sólo había que considerar el caso del primer sumando a parte xD, algo tenemos que dejar para otras ocasiones.

Cita de: yoel_alejandro en 15 Marzo 2014, 21:21 PM

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



Creo que habría que explicar, aunque sea brevemente, de donde salen esos número, no es plan de ponerse a multiplicar binomio tras binomio para comprobarlo.

Todo lo anterior se basa en la fórmula debida a Newton, como no, para el desarrollo de un binomio conocido por ello como binomio de Newton y que tiene esta expresión:



donde" esos" paréntesis son los llamados números combinatorios que se calculan, al menos en principio, a través de factoriales:


donde Vm,n son las llamadas variaciones de m elementos tomados n a n y Pn son las permutaciones de n elementos (consultar la Wikipedia para mayor información).

¿Y hay que calcular los factoriales necesariamente para hallar esos números combinatorios?. Pues si nos fijamos un poquitito vemos que podemos darles el esquinazo:



Observar que podemos evitar el cálculo de los factoriales sin más que multiplicar, en el caso del número combinatorio Cm,n, tantos factores en el numerador como indica n empezando por m y disminuyendo cada factor en una unidad, pero aún quedaría en el denominador el factorial de n.

¿Y no se podría evitar tanto cálculo para obtener los coeficientes del binomio de Newton?. Pues si, si nos fijamos en un pequeño detalle cuando los ordenamos en forma de triángulo:



¿No te dice nada?. No te preocupes ya que solamente hay que recordar un par de propiedades de los números combinatorios:


Si miras el triángulo anterior observarás que los números que aparecen en los extremos del triángulo son de este tipo, lo que implica que son iguales a uno.

Pero, ¿y los interiores?. También estamos de suerte ya que hay otra propiedad interesante:



Si la miras con atención viene a decir que cada elemento interior del triángulo es justito la suma de los dos que tiene encima, a su derecha y a su izquierda.

Con todo lo anterior se puede ya escribir el triángulo, y con ello calcular de forma simple, los coeficientes del binomio de Newton. Vuelve a fijarte en la figura que sigue y observa los dos hechos anteriores:



Si ya sé que tiene forma de pirámide,esos son cosas mías, tú fíjate en la mitad superior de la pirámide que es el triángulo de Pascal, es decir de coeficientes del ya tan nombrado binomio de Newton. Por cierto, ¿a qué está chula la pirámide?.

Y con lo explicado para los que no lo sabían o no recordaban ya están sin excusas para desarrollar códigos que generen el triángulo de Pascal. Puede hacerse con factoriales o sin ellos, usando arrays unidimensionales, bidimensionales o no usar arrays, con funciones o sin funciones, con recursividad o sin ella, en  su elección estará la gracia y la mayor o menor eficiencia del código desarrollado, eso si procurando en lo posible que sea cortito y sin añadidos innecesarios, tampoco hay que sacar la artillería pesada para obtenerlo.¡¡¡Animensen señores y señoras!!!,

Y para que no se diga cuelgo un código que genera el dichosito triángulo y, por esta vez el binomio de Newton desarrollado pero que , insisto, no era el objetivo que yo planteaba ya que era desarrollar códigos que impriman sencillamente el triángulo. Una vez que lo obtienes el desarrollo del binomio es pan comido por lo que no lo veo interesante,

Y por cierto, este código no ha sido desarrollado para este fin sino para el tema de los rombos con asteriscos, pero ya que lo tenía a mano lo he adaptado para este fin por lo que no está muy optimizado .....ya vendrán otros más guays:


Código (cpp) [Seleccionar]

#include <stdio.h>

int main(){
 int i=0,j,l=0,m=0,k=1,n=15;
 /*do{
   printf("\nIntroduzca la potencia a calcular (mayor que cero): \n");
   scanf("%d",&n);
   }while ( n < 0 );*/
   n=2*n+3;
   char a[ ]="a^",b[ ]="b^";
   int A[n][n];
   for ( i=0;i<n;i++)
     for ( j=0;j<n;j++)
       A[i][j]=0;
   A[0][n/2]=1;
   i=1;
   while (i<=n/2){
     for ( j=(n/2)-i;j<=i+(n/2);j++){
       if (j==(n/2)-i || j==i+(n/2))
         A[i][j]=1;
       else
         A[i][j]=A[i-1][j-1]+A[i-1][j+1];
     }
     i++;
   }
   for ( i=0;i<n/2;i++){
     printf("\t\n");
     for ( j=0;j<n;j++){
       if (A[i][j]==0)
         printf("%3c",' ');
       else if (A[i][j]!=0)
        printf("%3d",A[i][j]);
     }
   }
   printf("\n\n\t\t\t(a+b)^%d = \n",(n-3)/2);
   i=1,k=0,l=1;
   while (i<=n/2){

     for ( j=(n-3)/2-i;j<=i+(n-3)/2+2;j++){
         if (A[i][j]!=0){
         if (i==(n-3)/2){
           if (j==(n-3)/2-i)
           printf("%d %s%d %s%d",A[i][j],a,l-k,b,k);
             else
               printf(" + %d %s%d %s%d",A[i][j],a,l-k,b,k);
         }

         k++;
         }
     }
     l++,k=0,i++;
    }
   putchar ('\n');
   return 0;
}


Insisto en que es una adaptación rápida de lo hecho con otro objetivo pero no quería dejar pasar la ocasión de animar al personal.


¡¡¡¡ Saluditos! ..... !!!!



Y gracias a yoel_alejandro por iniciar el tema y su más que interesante aporte.

Y uno muy muy grande


ivancea96

Coeficientes binomiales en C++ :D
Que casualidad que ayer me dió por hacer esto, para un reto de ProjetEuler

Código (cpp) [Seleccionar]
uint64_t binomial(uint32_t n, uint32_t k){
    if(k>n) return 0;
    static vector< vector<uint64_t> > v;
    if(v.size()<=n)
        for(uint32_t i=v.size(); i<=n; i++){
            v.push_back(vector<uint64_t>());
            for(uint32_t j=0; j<=i; j++)
                if(j==0 || j==i)
                    v[i].push_back(1);
                else
                    v[i].push_back(v[i-1][j]+v[i-1][j-1]);
        }
    return v[n][k];
}


Además, guarda el vector de forma static para que próximas busquedas sean instantáneas.
Podría ponerle "if(n==k || k==0) return 1;" y etc, pero así para muchas iteraciones, ahorra tiempo. :D C:

leosansan

#9

Muy buena aportación ivancea96.

Pero permite me un par de observaciones:

* por qué usar uint64_t , que creo que es para números grandes. corrígeme si estoy en in error, please.. Si es lo que digo al no hacer uso de los factoriales los números combinatorios son más bien "normalitos", a no er que "n" sea muy alto.

* Si te fijas haces casi el doble de operaciones de las que son necesarias. Observa que la matriz o triángulo es simétrico respecto de la línea que pasa por su centro con lo que podrías "calcular" la mitad izquierda y por "igualación" respecto de sus simétricos obtener la mitad derecha.

Y a ver si te animas y cuelgas un código que dibuje el triángulo, ese es el aunténtico reto de este tema.


¡¡¡¡ Saluditos! ..... !!!!




APORTACIÓN DE AMCHACON

Cita de: amchacon en 16 Marzo 2014, 14:02 PM
Chachi ^^. Un paso curioso sería hacerlas animadas (borrando y reescribiendola con otra posición cada x tiempo).

Yo de florituras en la pantalla, ni se me dan bien ni me gustan mucho. Por no dejar el tema a medias he hecho algo más de mi gusto: Una class Triangulo_Pascal:

Código (cpp) [Seleccionar]
/** Resumen de los metodos públicos:

- Constructor(int n = 0): Genera un triangulo de pascal de tamanyo N
- Constructor(triangulo_pascal): Constructor copia.
- getPosicion(int x,int y): Devuelve el valor en la posicion en la posicion x,y. Lanza una excepcion si es una posición incorrecta
- getSize(): Devuelve el tamanyo actual del triangulo
- resize(int n): Reconstruye el triangulo para un ancho n
- clear(): Borra el triangulo dejandolo con un tamanyo 0.
- toString(): Obtiene una expresion escrita del triangulo.

Operadores:

triangulo_pascal = triangulo_pascal   /** asignacion *
triangulo_pascal == triangulo_pascal  /** iguales? *
triangulo_pascal != triangulo_pascal  /** diferentes? *
**/

class triangulo_pascal
{
   int** Matriz;
   int TAM;
   string texto;

   int contar_cifras() const
   {
       int cifras = 1;
       int aux = Matriz[TAM-1][TAM/2];

       while (aux > 9)
       {
           cifras++;
           aux /= 10;
       }

       return cifras;
   }

   void generar(const int n)
   {
       TAM = n;
       Matriz = new int*[n];
       Matriz[0] = new int[1];
       Matriz[0][0] = 1;

       for (int i = 1; i < n;i++)
       {
           Matriz[i] = new int[i+1];

           Matriz[i][0] = 1;
           for (int j = 1; j < i;j++)
           {
               Matriz[i][j] = Matriz[i-1][j-1]+Matriz[i-1][j];
           }
           Matriz[i][i] = 1;
       }

       generarString();
   }

   void generarString()
   {
       stringstream ss;

       const int size = contar_cifras();

       for (int i = 0; i < TAM;i++)
       {
           for (int k = 0; k <= (TAM-i-2);k++)
               ss<<" ";

           ss<<Matriz[i][0];

           for (int j = 1; j <= i;j++)
           {
               ss<<" ";

               ss<<setw(size)<<Matriz[i][j];
           }

           ss<<endl;
       }

       texto = ss.str();
   }
public:
   triangulo_pascal(int n = 0)
   {
       if (n != 0)
       {
           generar(n);
       }
       else Matriz = NULL;
   }

   triangulo_pascal(const triangulo_pascal &a)
   {
       if (a.getSize() != 0)
           generar(a.getSize());
       else Matriz = NULL;
   }

   triangulo_pascal& operator=(const triangulo_pascal &a)
   {
       if (a.getSize() != 0)
           generar(a.getSize());
       else Matriz = NULL;
   }

   bool operator==(const triangulo_pascal &b)
   {
       return TAM == b.TAM;
   }

   bool operator!=(const triangulo_pascal &c)
   {
       return TAM != c.TAM;
   }

   int getPosicion(int x,int y) const
   {
       if (y < TAM || (x > y)) throw "Error, fuera de rango";
       return Matriz[x][y];
   }

   int getSize() const { return TAM;}

   void resize(int n)
   {
       if (n < 0) throw "Error, tamanyo negativo";

       clear();

       if (n == 0){return;}

       generar(n);
   }

   void clear()
   {
       if (Matriz == NULL) return;

       for (int i = 0; i < TAM;i++)
           delete[] Matriz[i];

       delete[] Matriz;

       Matriz = NULL;
       TAM = 0;
   }

   string toString() const
   {
       return texto;
   }

   operator string()
   {
       return toString();
   }

   ~triangulo_pascal()
   {
       clear();
   }
};


De la cual, podemos hacer algunas pruebas:

Código (cpp) [Seleccionar]
int main()
{
   triangulo_pascal mi_triangulo(5);

   cout<<mi_triangulo.toString()<<endl;
   mi_triangulo.resize(4);
   cout<<mi_triangulo.toString()<<endl;

   triangulo_pascal segundo(1);

   if (mi_triangulo != segundo)
   {
       cout<<"Son diferentes :("<<endl<<endl;
   }

   cout<<(string)segundo<<endl; // otra forma de pasarlo a string es usando los casts
   return 0;
}


El mayor fallo que tiene es la función para pasarlo a string, que aunque siempre genera el triangulo, lo hace un poco "raro" para algunos valores de N.