Foro de elhacker.net

Programación => Programación C/C++ => Mensaje iniciado por: Yoel Alejandro en 15 Marzo 2014, 21:21 pm


Título: Binomio de Newton, y triángulo de Pascal
Publicado por: Yoel Alejandro en 15 Marzo 2014, 21:21 pm
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 (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
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <string.h>
  4.  
  5. int ** pascal( const int );
  6. int ** tartaglia( const int );
  7. void destroy_pascal( int **, const int );
  8. void destroy_tartaglia( int **, const int );
  9. int digits( int );
  10.  
  11. int main(int argc, char* argv[]) {
  12.  
  13.    int **A, N;
  14.    int i;
  15.    int width, col;
  16.    char *board[2];
  17.  
  18.    /* Verificando integridad de los datos */
  19.    if ( argc < 2 )
  20.       return -1;
  21.    N = atoi( argv[1] );
  22.  
  23.    if ( N < 0 ) {
  24.       printf("Solo para N >= 0\n");
  25.       return -1;
  26.    }
  27.    if ( N == 0 ) {
  28.       printf("a + b\n");
  29.       return -1;
  30.    }
  31.  
  32.    /* Coeficientes de pascal */
  33.    A = pascal( N );
  34.  
  35.    /* Calculamos el ancho total de la cadena */
  36.    width = 0;
  37.    for ( i = 0; i <= (float)N/2; i++ ) {
  38.       if ( i == 0 ) 			/* terminos a^N, y b^N */
  39.          width += 2 * ( 1 + digits(N) );
  40.       if ( i == 1 ) 			/* terminos a^(N-1)*b, y a*b^(N-1) */
  41.          width += 2 * ( 2 + digits(A[N][i]) + digits(N-1) );
  42.       if ( i > 1 ) 			/* terminos a^(N-i)*b^i */
  43.          if ( !(N % 2) && i == (float)N/2 )
  44.             /* termino central se suma solo una vez */
  45.             width += 2 + digits(A[N][i]) + digits(N-1) + digits(i);
  46.          else
  47.             /* y los restantes, dos veces */
  48.             width += 2 * ( 2 + digits(A[N][i]) + digits(N-1) + digits(i) );
  49.    }
  50.    /* cadenas " + " */
  51.    width += 3 * N;
  52.  
  53.    /* Representacion final */
  54.    if ( ( board[0] = malloc( (width + 1) * sizeof(char) ) ) == NULL )
  55.       return -1;
  56.    if ( ( board[1] = malloc( (width + 1) * sizeof(char) ) ) == NULL )
  57.       return -1;
  58.  
  59.    memset( board[0], ' ', width + 1);
  60.    memset( board[1], ' ', width + 1);
  61.    col = 0;
  62.    for ( i = 0; i <= N; i++) {
  63.       if ( A[N][i] != 1 ) {	/* binomial N sobre i */
  64.          col += sprintf( board[1] + col, "%d", A[N][i] );
  65.          board[1][col] = ' ';
  66.       }
  67.       if ( N - i > 0 )			/* base 'a' */
  68.          board[1][col++] = 'a';
  69.       if ( N - i > 1 ) { 		/* exponente N - i */
  70.          col += sprintf( board[0] + col, "%d", N - i);
  71.          board[0][col] = ' ';
  72.       }
  73.       if ( i > 0 )	 			/* base 'b' */
  74.          board[1][col++] = 'b';
  75.       if ( i > 1 ) {			/* exponente i */
  76.          col += sprintf( board[0] + col, "%d", i);
  77.          board[0][col] = ' ';
  78.       }
  79.       if ( i < N ) {
  80.          col += sprintf( board[1] + col, " + ");
  81.          board[1][col] = ' ';
  82.       }
  83.    }
  84.    board[0][width] = '\0';
  85.    board[1][width] = '\0';
  86.    printf( "(a + b)^%d es:\n\n%s\n%s\n", N, board[0], board[1] );
  87.  
  88.    /* Liberando memoria, y saliendo */
  89.    free( board[0] );
  90.    free( board[1] );
  91.    destroy_pascal( A, N);
  92.    return 0;
  93. }
  94.  
  95. /* Construye una matriz que contiene los numeros del triangulo
  96.  * de Pascal o Tartaglia de orden N > = 0, con N + 1 filas.
  97.  * La matriz es tal que A[i][j] corresponde al binomial (i : j).
  98.  * Se devolverá NULL si N < 0, o si no se pudo asignar memoria
  99.  * para construir la matriz.
  100.  */
  101. int ** pascal( const int N ) {
  102.  
  103.    int **A;
  104.    int i, j;
  105.  
  106.    if ( N < 0 ) return NULL;
  107.  
  108.    if ( ( A = malloc( (N + 1) * sizeof(int *) ) ) == NULL ) return NULL;
  109.    for ( i = 0; i < N + 1; i++ )
  110.       if ( ( A[i] = malloc( (i + 1) * sizeof(int) ) ) == NULL ) return NULL;
  111.  
  112.    for ( i = 0; i < N + 1; i++ ) {
  113.       A[i][0] = 1;
  114.       A[i][i] = 1;
  115.       /* solo se ejecuta si i > 1 */
  116.       for ( j = 1; j < i; j++ )
  117.          A[i][j] = A[i-1][j-1] + A[i-1][j];
  118.    }
  119.  
  120.    return A;
  121. }
  122.  
  123. /* Destruye el objeto creado por la función pascal() */
  124. void destroy_pascal( int ** A, const int N ) {
  125.  
  126.    int i;
  127.  
  128.    if ( N < 0 ) return;
  129.  
  130.    for ( i = N; i >= 0; i-- ) {
  131.       free( A[i] );
  132.       A[i] = NULL;
  133.    }
  134.    free( A );
  135.    A = NULL;
  136. }
  137.  
  138. /* Un sinónimo de pascal( N ) */
  139. int ** tartaglia( const int N ) {
  140.  
  141.    return pascal( N );
  142. }
  143.  
  144. /* Un sinónimo de destroy_pascal( N ) */
  145. void destroy_tartaglia( int ** A, const int N ) {
  146.  
  147.    return destroy_pascal( A, N );
  148. }
  149.  
  150. /* Calcula la cantidad de cifras o digitos que conforman un
  151.  * numero entero no negativo;
  152.  */
  153. int digits( int N ) {
  154.  
  155.    int count = 1;
  156.  
  157.    if ( N < 0 ) return 0;
  158.    if ( N == 0 ) return 1;
  159.  
  160.    while ( ( N = (N / 10) ) > 0 )
  161.       count++;
  162.  
  163.    return count;
  164. }

Título: Re: Binomio de Newton, y triángulo de Pascal
Publicado por: amchacon en 15 Marzo 2014, 23:03 pm
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++ ^^

Título: Re: Binomio de Newton, y triángulo de Pascal
Publicado por: leosansan en 15 Marzo 2014, 23:51 pm

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


(http://st.forocoches.com/foro/images/smilies/aaaaa.gif)

Título: Re: Binomio de Newton, y triángulo de Pascal
Publicado por: amchacon en 15 Marzo 2014, 23:53 pm
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! ..... !!!!


(http://st.forocoches.com/foro/images/smilies/aaaaa.gif)
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.

Título: Re: Binomio de Newton, y triángulo de Pascal
Publicado por: leosansan en 16 Marzo 2014, 00:31 am
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! ..... !!!!


(http://st.forocoches.com/foro/images/smilies/aaaaa.gif)

Título: Re: Binomio de Newton, y triángulo de Pascal
Publicado por: amchacon en 16 Marzo 2014, 00:38 am
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:
Citar
texto 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
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <string.h>
  4.  
  5. int ** pascal( const int );
  6. int ** tartaglia( const int );
  7. void destroy_pascal( int **, const int );
  8. void destroy_tartaglia( int **, const int );
  9. int digits( int );
  10.  
  11. int main(int argc, char* argv[])
  12. {
  13.  
  14.     int **A, N;
  15.     int i;
  16.     int width, col;
  17.     char *board[2];
  18.     puts("Introduce el valor de N: ");
  19.     scanf("%d",&N);
  20.     putchar('\n');
  21.  
  22.     if ( N < 0 )
  23.     {
  24.         printf("Solo para N >= 0\n");
  25.         return -1;
  26.     }
  27.     if ( N == 0 )
  28.     {
  29.         printf("a + b\n");
  30.         return -1;
  31.     }
  32.  
  33.     /* Coeficientes de pascal */
  34.     A = pascal( N );
  35.  
  36.     /* Calculamos el ancho total de la cadena */
  37.     width = 0;
  38.     for ( i = 0; i <= (float)N/2; i++ )
  39.     {
  40.         if ( i == 0 ) /* terminos a^N, y b^N */
  41.             width += 2 * ( 1 + digits(N) );
  42.         if ( i == 1 ) /* terminos a^(N-1)*b, y a*b^(N-1) */
  43.             width += 2 * ( 2 + digits(A[N][i]) + digits(N-1) );
  44.         if ( i > 1 ) /* terminos a^(N-i)*b^i */
  45.             if ( !(N % 2) && i == (float)N/2 )
  46.                 /* termino central se suma solo una vez */
  47.                 width += 2 + digits(A[N][i]) + digits(N-1) + digits(i);
  48.             else
  49.                 /* y los restantes, dos veces */
  50.                 width += 2 * ( 2 + digits(A[N][i]) + digits(N-1) + digits(i) );
  51.     }
  52.     /* cadenas " + " */
  53.     width += 3 * N;
  54.  
  55.     /* Representacion final */
  56.     if ( ( board[0] = malloc( (width + 1) * sizeof(char) ) ) == NULL )
  57.         return -1;
  58.     if ( ( board[1] = malloc( (width + 1) * sizeof(char) ) ) == NULL )
  59.         return -1;
  60.  
  61.     memset( board[0], ' ', width + 1);
  62.     memset( board[1], ' ', width + 1);
  63.     col = 0;
  64.     for ( i = 0; i <= N; i++)
  65.     {
  66.         if ( A[N][i] != 1 )  	/* binomial N sobre i */
  67.         {
  68.             col += sprintf( board[1] + col, "%d", A[N][i] );
  69.             board[1][col] = ' ';
  70.         }
  71.         if ( N - i > 0 )	/* base 'a' */
  72.             board[1][col++] = 'a';
  73.         if ( N - i > 1 )   /* exponente N - i */
  74.         {
  75.             col += sprintf( board[0] + col, "%d", N - i);
  76.             board[0][col] = ' ';
  77.         }
  78.         if ( i > 0 )	/* base 'b' */
  79.             board[1][col++] = 'b';
  80.         if ( i > 1 )  	/* exponente i */
  81.         {
  82.             col += sprintf( board[0] + col, "%d", i);
  83.             board[0][col] = ' ';
  84.         }
  85.         if ( i < N )
  86.         {
  87.             col += sprintf( board[1] + col, " + ");
  88.             board[1][col] = ' ';
  89.         }
  90.     }
  91.     board[0][width] = '\0';
  92.     board[1][width] = '\0';
  93.     printf( "(a + b)^%d es:\n\n%s\n%s\n", N, board[0], board[1] );
  94.  
  95.     /* Liberando memoria, y saliendo */
  96.     free( board[0] );
  97.     free( board[1] );
  98.     destroy_pascal( A, N);
  99.     return 0;
  100. }
  101.  
  102. /* Construye una matriz que contiene los numeros del triangulo
  103.  * de Pascal o Tartaglia de orden N > = 0, con N + 1 filas.
  104.  * La matriz es tal que A[i][j] corresponde al binomial (i : j).
  105.  * Se devolverá NULL si N < 0, o si no se pudo asignar memoria
  106.  * para construir la matriz.
  107.  */
  108. int ** pascal( const int N )
  109. {
  110.  
  111.     int **A;
  112.     int i, j;
  113.  
  114.     if ( N < 0 ) return NULL;
  115.  
  116.     if ( ( A = malloc( (N + 1) * sizeof(int *) ) ) == NULL ) return NULL;
  117.     for ( i = 0; i < N + 1; i++ )
  118.         if ( ( A[i] = malloc( (i + 1) * sizeof(int) ) ) == NULL ) return NULL;
  119.  
  120.     for ( i = 0; i < N + 1; i++ )
  121.     {
  122.         A[i][0] = 1;
  123.         A[i][i] = 1;
  124.         /* solo se ejecuta si i > 1 */
  125.         for ( j = 1; j < i; j++ )
  126.             A[i][j] = A[i-1][j-1] + A[i-1][j];
  127.     }
  128.  
  129.     return A;
  130. }
  131.  
  132. /* Destruye el objeto creado por la función pascal() */
  133. void destroy_pascal( int ** A, const int N )
  134. {
  135.  
  136.     int i;
  137.  
  138.     if ( N < 0 ) return;
  139.  
  140.     for ( i = N; i >= 0; i-- )
  141.     {
  142.         free( A[i] );
  143.         A[i] = NULL;
  144.     }
  145.     free( A );
  146.     A = NULL;
  147. }
  148.  
  149. /* Un sinónimo de pascal( N ) */
  150. int ** tartaglia( const int N )
  151. {
  152.  
  153.     return pascal( N );
  154. }
  155.  
  156. /* Un sinónimo de destroy_pascal( N ) */
  157. void destroy_tartaglia( int ** A, const int N )
  158. {
  159.  
  160.     return destroy_pascal( A, N );
  161. }
  162.  
  163. /* Calcula la cantidad de cifras o digitos que conforman un
  164.  * numero entero no negativo;
  165.  */
  166. int digits( int N )
  167. {
  168.  
  169.     int count = 1;
  170.  
  171.     if ( N < 0 ) return 0;
  172.     if ( N == 0 ) return 1;
  173.  
  174.     while ( ( N = (N / 10) ) > 0 )
  175.         count++;
  176.  
  177.     return count;
  178. }
  179.  

Título: Re: Binomio de Newton, y triángulo de Pascal
Publicado por: Yoel Alejandro en 16 Marzo 2014, 01:03 am
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
  1. 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

Título: Re: Binomio de Newton, y triángulo de Pascal
Publicado por: leosansan en 16 Marzo 2014, 12:37 pm
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:

(http://i1280.photobucket.com/albums/a497/leosansan/GRAFICOS1/binomioNewtondesarrollo_zps9e5968de.jpg)

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:

(http://i1280.photobucket.com/albums/a497/leosansan/GRAFICOS1/binomioNewton1_zpsaf0be03e.jpg)

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

(http://i1280.photobucket.com/albums/a497/leosansan/binomioNewton2_zps0142cae9.jpg)

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:

(http://i1280.photobucket.com/albums/a497/leosansan/binomioNewton3_zpsd6d8f275.jpg)

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:
(http://i1280.photobucket.com/albums/a497/leosansan/binomioNewton6_zps2dd8e920.jpg)

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

(http://i1280.photobucket.com/albums/a497/leosansan/binomioNewton5_zps76cf0d82.jpg)

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:

(http://i1280.photobucket.com/albums/a497/leosansan/binomioNewton4_zps0f9a9e44.jpg)

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:

(http://i1280.photobucket.com/albums/a497/leosansan/pascalpiramide_zps35289e63.jpg)

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 (http://foro.elhacker.net/programacion_cc/c_rombo_con_asteriscos-t409663.0.html), 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
  1. #include <stdio.h>
  2.  
  3. int main(){
  4.   int i=0,j,l=0,m=0,k=1,n=15;
  5.   /*do{
  6.     printf("\nIntroduzca la potencia a calcular (mayor que cero): \n");
  7.     scanf("%d",&n);
  8.     }while ( n < 0 );*/
  9.     n=2*n+3;
  10.     char a[ ]="a^",b[ ]="b^";
  11.     int A[n][n];
  12.     for ( i=0;i<n;i++)
  13.       for ( j=0;j<n;j++)
  14.         A[i][j]=0;
  15.     A[0][n/2]=1;
  16.     i=1;
  17.     while (i<=n/2){
  18.       for ( j=(n/2)-i;j<=i+(n/2);j++){
  19.         if (j==(n/2)-i || j==i+(n/2))
  20.           A[i][j]=1;
  21.         else
  22.           A[i][j]=A[i-1][j-1]+A[i-1][j+1];
  23.       }
  24.       i++;
  25.     }
  26.     for ( i=0;i<n/2;i++){
  27.       printf("\t\n");
  28.       for ( j=0;j<n;j++){
  29.         if (A[i][j]==0)
  30.           printf("%3c",' ');
  31.         else if (A[i][j]!=0)
  32.          printf("%3d",A[i][j]);
  33.       }
  34.     }
  35.     printf("\n\n\t\t\t(a+b)^%d = \n",(n-3)/2);
  36.     i=1,k=0,l=1;
  37.     while (i<=n/2){
  38.  
  39.       for ( j=(n-3)/2-i;j<=i+(n-3)/2+2;j++){
  40.           if (A[i][j]!=0){
  41.           if (i==(n-3)/2){
  42.             if (j==(n-3)/2-i)
  43.             printf("%d %s%d %s%d",A[i][j],a,l-k,b,k);
  44.               else
  45.                 printf(" + %d %s%d %s%d",A[i][j],a,l-k,b,k);
  46.           }
  47.  
  48.           k++;
  49.           }
  50.       }
  51.       l++,k=0,i++;
  52.      }
  53.     putchar ('\n');
  54.     return 0;
  55. }

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


(http://st.forocoches.com/foro/images/smilies/aaaaa.gif)

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

Y uno muy muy grande

(http://i1280.photobucket.com/albums/a497/leosansan/binomiotrianguloGRANDE_zps052250ec.jpg)

Título: Re: Binomio de Newton, y triángulo de Pascal
Publicado por: ivancea96 en 16 Marzo 2014, 13:02 pm
Coeficientes binomiales en C++ :D
Que casualidad que ayer me dió por hacer esto, para un reto de ProjetEuler (http://projecteuler.net)

Código
  1. uint64_t binomial(uint32_t n, uint32_t k){
  2.     if(k>n) return 0;
  3.     static vector< vector<uint64_t> > v;
  4.     if(v.size()<=n)
  5.         for(uint32_t i=v.size(); i<=n; i++){
  6.             v.push_back(vector<uint64_t>());
  7.             for(uint32_t j=0; j<=i; j++)
  8.                 if(j==0 || j==i)
  9.                     v[i].push_back(1);
  10.                 else
  11.                     v[i].push_back(v[i-1][j]+v[i-1][j-1]);
  12.         }
  13.     return v[n][k];
  14. }

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:

Título: Re: Binomio de Newton, y triángulo de Pascal
Publicado por: leosansan en 16 Marzo 2014, 15:51 pm

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


(http://st.forocoches.com/foro/images/smilies/aaaaa.gif)


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
  1. /** Resumen de los metodos públicos:
  2.  
  3. - Constructor(int n = 0): Genera un triangulo de pascal de tamanyo N
  4. - Constructor(triangulo_pascal): Constructor copia.
  5. - 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
  6. - getSize(): Devuelve el tamanyo actual del triangulo
  7. - resize(int n): Reconstruye el triangulo para un ancho n
  8. - clear(): Borra el triangulo dejandolo con un tamanyo 0.
  9. - toString(): Obtiene una expresion escrita del triangulo.
  10.  
  11. Operadores:
  12.  
  13. triangulo_pascal = triangulo_pascal   /** asignacion *
  14. triangulo_pascal == triangulo_pascal  /** iguales? *
  15. triangulo_pascal != triangulo_pascal  /** diferentes? *
  16. **/
  17.  
  18. class triangulo_pascal
  19. {
  20.     int** Matriz;
  21.     int TAM;
  22.     string texto;
  23.  
  24.     int contar_cifras() const
  25.     {
  26.         int cifras = 1;
  27.         int aux = Matriz[TAM-1][TAM/2];
  28.  
  29.         while (aux > 9)
  30.         {
  31.             cifras++;
  32.             aux /= 10;
  33.         }
  34.  
  35.         return cifras;
  36.     }
  37.  
  38.     void generar(const int n)
  39.     {
  40.         TAM = n;
  41.         Matriz = new int*[n];
  42.         Matriz[0] = new int[1];
  43.         Matriz[0][0] = 1;
  44.  
  45.         for (int i = 1; i < n;i++)
  46.         {
  47.             Matriz[i] = new int[i+1];
  48.  
  49.             Matriz[i][0] = 1;
  50.             for (int j = 1; j < i;j++)
  51.             {
  52.                 Matriz[i][j] = Matriz[i-1][j-1]+Matriz[i-1][j];
  53.             }
  54.             Matriz[i][i] = 1;
  55.         }
  56.  
  57.         generarString();
  58.     }
  59.  
  60.     void generarString()
  61.     {
  62.         stringstream ss;
  63.  
  64.         const int size = contar_cifras();
  65.  
  66.         for (int i = 0; i < TAM;i++)
  67.         {
  68.             for (int k = 0; k <= (TAM-i-2);k++)
  69.                 ss<<" ";
  70.  
  71.             ss<<Matriz[i][0];
  72.  
  73.             for (int j = 1; j <= i;j++)
  74.             {
  75.                 ss<<" ";
  76.  
  77.                 ss<<setw(size)<<Matriz[i][j];
  78.             }
  79.  
  80.             ss<<endl;
  81.         }
  82.  
  83.         texto = ss.str();
  84.     }
  85. public:
  86.     triangulo_pascal(int n = 0)
  87.     {
  88.         if (n != 0)
  89.         {
  90.             generar(n);
  91.         }
  92.         else Matriz = NULL;
  93.     }
  94.  
  95.     triangulo_pascal(const triangulo_pascal &a)
  96.     {
  97.         if (a.getSize() != 0)
  98.             generar(a.getSize());
  99.         else Matriz = NULL;
  100.     }
  101.  
  102.     triangulo_pascal& operator=(const triangulo_pascal &a)
  103.     {
  104.         if (a.getSize() != 0)
  105.             generar(a.getSize());
  106.         else Matriz = NULL;
  107.     }
  108.  
  109.     bool operator==(const triangulo_pascal &b)
  110.     {
  111.         return TAM == b.TAM;
  112.     }
  113.  
  114.     bool operator!=(const triangulo_pascal &c)
  115.     {
  116.         return TAM != c.TAM;
  117.     }
  118.  
  119.     int getPosicion(int x,int y) const
  120.     {
  121.         if (y < TAM || (x > y)) throw "Error, fuera de rango";
  122.         return Matriz[x][y];
  123.     }
  124.  
  125.     int getSize() const { return TAM;}
  126.  
  127.     void resize(int n)
  128.     {
  129.         if (n < 0) throw "Error, tamanyo negativo";
  130.  
  131.         clear();
  132.  
  133.         if (n == 0){return;}
  134.  
  135.         generar(n);
  136.     }
  137.  
  138.     void clear()
  139.     {
  140.         if (Matriz == NULL) return;
  141.  
  142.         for (int i = 0; i < TAM;i++)
  143.             delete[] Matriz[i];
  144.  
  145.         delete[] Matriz;
  146.  
  147.         Matriz = NULL;
  148.         TAM = 0;
  149.     }
  150.  
  151.     string toString() const
  152.     {
  153.         return texto;
  154.     }
  155.  
  156.     operator string()
  157.     {
  158.         return toString();
  159.     }
  160.  
  161.     ~triangulo_pascal()
  162.     {
  163.         clear();
  164.     }
  165. };
  166.  

De la cual, podemos hacer algunas pruebas:

Código
  1. int main()
  2. {
  3.     triangulo_pascal mi_triangulo(5);
  4.  
  5.     cout<<mi_triangulo.toString()<<endl;
  6.     mi_triangulo.resize(4);
  7.     cout<<mi_triangulo.toString()<<endl;
  8.  
  9.     triangulo_pascal segundo(1);
  10.  
  11.     if (mi_triangulo != segundo)
  12.     {
  13.         cout<<"Son diferentes :("<<endl<<endl;
  14.     }
  15.  
  16.     cout<<(string)segundo<<endl; // otra forma de pasarlo a string es usando los casts
  17.     return 0;
  18. }
  19.  

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.

Título: Re: Binomio de Newton, y triángulo de Pascal
Publicado por: Yoel Alejandro en 16 Marzo 2014, 17:52 pm
Leosansan, para que puedas observar el binomio "bien" debes usar una fuente ancho constante de las letras (teletipo), o en el caso de este foro encerrado por las etiquetas [ tt ]. Con ello, para N=5:

(a + b)^5 es:

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


Claro, indiqué que la salida no sale correcta si la longitud del desarrollo del binomio excede de una línea en la terminal que uses. Tu terminal por lo visto hace scroll horizontal, por lo que no "salta" las líneas que excedan del ancho de pantalla, y entonces las expresiones muy largas se siguen viendo bien. No así la mía ue tiene un ancho fijo.

Imprimir el triángulo no es problema, pues ya tengo la función que lo genera, sólo un par de for ya lo imprimes. Aclaro que por razones de eficiencia sólo ocupo la parte "triangular izquierda" de la matriz, pues sólo se usan los números combinatorios <i,j> para j=0 hasta j=i. Entonces la matriz queda con forma de triángulo rectángulo y no isósceles. Esto puede parecer raro, pero es común en la programación de métodos numéricos  ;)

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

Y por cierto, hablando del tema de la eficiencia, demás está decir que generar los combinatorios mediante suma recursiva de la fila anterior es mejor que hacerlo con factoriales.

Aclamo tu profusa explicación sobre combinatorios, triángulo de Pascal y binomio de Newton, es exactamente como dices. No quise poner imágenes aquí porque a veces entorpecen un poco la carga de la página (los archivos de imágenes pueden ser voluminosos), por eso cambié a una representación sucinta de los binomiales como <i,j>, aunque menos visual que la tuya. Sabes que soy un minimalista, jeje.

========================================
EDITO (réplica)

Pues bien, para cumplir con el objetivo planteado de imprimir el triángulo creo que lo más simple sería obtener la longitud de la línea más larga del triángulo (para ello la función auxiliar line_width()), restarle la longitud de la línea actual, y tomar el cociente entero de dividir entre dos. Esta sería la separación entre el margen izquierdo y la primera posición donde vamos  empezar a imprimir la línea. Bueno ....... ya se capta la idea.

Salida (N = 10) :

                 1
                1 1
               1 2 1
              1 3 3 1
             1 4 6 4 1
           1 5 10 10 5 1
         1 6 15 20 15 6 1
        1 7 21 35 35 21 7 1
      1 8 28 56 70 56 28 8 1
    1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1

No se si lo quieres de otra forma ..., o si ya pude terminar con bendito triángulo jajaja  :laugh: (broma). El código:
Código
  1. int line_width( int **, int );
  2. void print( int **, int );
  3.  
  4. int main( ) {
  5.  
  6. /* ......... (resto del programa) ................. */
  7. /* Imprimir el triangulo */
  8.    print( A, N );
  9.    putchar('\n');
  10. /* ..........(resto del programa) .............. */
  11. }
  12.  
  13. /* Calcula el ancho impresa de una linea del triangulo de Pascal */
  14. int line_width( int ** A, int i ) {
  15.  
  16.    int j, width = 0;
  17.  
  18.    if ( i > 0 ) {		/* lineas 1 en adelante */
  19.       for ( j = 0; j <= i; j++ )
  20.          width += digits( A[i][j] );
  21.       width += i;		/* (los espacios en blanco) */
  22.       return width;
  23.    }
  24.    else if ( i == 0 )	/* linea cero */
  25.       return 1;
  26.    else 						/* argumento negativo */
  27.       return 0;
  28. }
  29.  
  30. /* Imprime el triangulo de Pascal de orden N */
  31. void print( int **A, int N ) {
  32.  
  33.    int MAX_width, width, i, j;
  34.  
  35.    /* linea mas ancha del triangulo */
  36.    MAX_width = line_width( A, N );
  37.  
  38.    for ( i = 0; i <= N; i++ ) {
  39.       width = line_width( A, i );	/* linea actual */
  40.       j = 0;
  41.       while ( j++ < (MAX_width - width)/2 )
  42.          putchar(' ');
  43.       for ( j = 0; j <= i; j++ )
  44.          printf( "%d ", A[i][j] );
  45.       putchar('\n');
  46.    }
  47. }
  48.  

Título: Re: Binomio de Newton, y triángulo de Pascal
Publicado por: leosansan en 17 Marzo 2014, 17:49 pm
¡¡¡CHACHO, menudos pedazos de código!!!

Si planteé un reto es porque los códigos que me imaginaba pondrían no sobrepasarían las 50 o 60 lineas, pero más de 200 es una pasada para el objetivo propuesto. Pero todo hay que decirlo: os lo habéis currado de lo lindo.

Yo me esperaba lo que denomino "códigos cortitos e imaginativos".

Por ahora no hemos logrado ni lo uno ni lo otro.

Voy a corregir lo primero, cortito y más eficiente.

Código
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. int main(){
  4.   unsigned int i,j,n=21,N;
  5.   char tamanyo_consola[80];
  6.   /*do{
  7.     printf("\nIntroduzca la potencia a calcular (0-23): \n");
  8.     fflush( stdout );
  9.     scanf("%u",&n);
  10.     }while ( n < 0  || n > 23);*/
  11.   N = 2 *(++n)  - 1; /* numero de columnas*/
  12.   sprintf(tamanyo_consola, "MODE %d,%d",(int) (4.5*N+1),2*N);
  13.   system(tamanyo_consola);
  14.   unsigned int a[n][N+1];
  15.   for (i=0;i<=n-1;i++)
  16.     for (j=0;j<=(N);j++)
  17.       a[i][j] = 0;
  18.   a[0][n-1] =  1;
  19.   for (i=1;i<=n-1;i++)
  20.     for (j=n-1-i;j<=n-1+i;j+=2)
  21.         a[i][j] = a[i-1][j-1] + a[i-1][j+1];
  22.   for (i=0;i<=n-1;i++){
  23.     for (j=0;j<=n-1+i;j++){
  24.       if (a[i][j]==0)
  25.         printf("    ");
  26.       else
  27.         printf("%4u",a[i][j]);
  28.     }
  29.     putchar ('\n');
  30.   }
  31.   return 0;
  32. }

Para hacer el código más potente a la hora de representar el triángulo he introducido el system MODE que ajusta el tamaño de la consola al tamaño del triángulo, al menos para el intervalo considerado y de acuerdo al tamaño de mi monitor. Si estáis en Linux el tamaño del triángulo máximo que se vería bien en consola creo que es 13:

Código
  1. #include <stdio.h>
  2. int main(){
  3.   unsigned int i,j,n=13,N;
  4.   /*do{
  5.     printf("\nIntroduzca la potencia a calcular (0-13): \n");
  6.     fflush( stdout );
  7.     scanf("%u",&n);
  8.     }while ( n < 0  || n > 13);*/
  9.   N = 2 *(++n)  - 1; /* numero de columnas*/
  10.   unsigned int a[n][N+1];
  11.   for (i=0;i<=n-1;i++)
  12.     for (j=0;j<=(N);j++)
  13.       a[i][j] = 0;
  14.   a[0][n-1] =  1;
  15.   for (i=1;i<=n-1;i++)
  16.     for (j=n-1-i;j<=n-1+i;j++)
  17.         a[i][j] = a[i-1][j-1] + a[i-1][j+1];
  18.   for (i=0;i<=n-1;i++){
  19.     for (j=0;j<=n-1+i;j++){
  20.       if (a[i][j]==0)
  21.         printf("    ");
  22.       else
  23.         printf("%4u",a[i][j]);
  24.     }
  25.     putchar ('\n');
  26.   }
  27.   return 0;
  28. }

Y una muestra de la salida para 15:

(http://i1280.photobucket.com/albums/a497/leosansan/GRAFICOS1/binomiotriangulo15_zps3a334f42.jpg)

Observad bien el triángulo anterior, es fundamental para que entendáis lo que sigue.

* 1*
En mi código veréis la linea:

Código
  1. a[0][n-1] =  1;

increíble pero cierto sólo hace falta definir "un elemento como uno", ya la ley de recurrencia se encarga de los demás. Esta es la primera diferencia con respecto a los otros códigos. Lo veo más sencillo y eficiente.

* 2 *
No es necesario aplicar la ley de recurrencia a todos los elementos de la matriz, basta con aplicarlo a los elementos a derecha e izquierda de la linea vertical que pasa por el vértice y de dos en dos para no aplicarlo a los ceros intermedios. Ello está considerado en la linea:

Código
  1. for (j=n-1-i;j<=n-1+i;j+=2)

El ahorro de operaciones es considerable y aumenta dicho ahorro con el tamaño del triángulo.

En concreto, y puestos a hacer números, el total de números a aplicar la ley de recurrencia teniendo en cuenta ese detalle es de (n+1)*(n+2)/2, mientras que si no se tiene en cuenta el total de operaciones a realizar es (2*n+1)*(n+1) lo que da una diferencia entre ambos métodos de (n+1)*n*3/2.

Aplicado al caso concreto de 15:

---> teniendo en cuenta la simetría se aplica la ley de recurrencia 136 veces.

---> sin tenerlo en cuenta se aplica la ley de recurrencia "496" veces.

Una diferencia de 360 veces de más. Por eso mi comentario de que el método que propongo, además de ser bastante más cortito, es más eficiente.

Pero, ¿realmente es necesario usar un array bidimensional?. En realidad es poco eficiente ya que desaprovechamos de él muchas de las posiciones, todos los ceros que no se usan.

Y es el reto que lanzo: conseguir el triángulo con un array unidimensional, así no desaprovechamos ningún elemento del array. ¡Ánimo!, no es tan difícil .... y lo de dibujarlo es lo de menos, lo realmente interesante es como conseguir ese array unidimensional.

Y por último una petición: los códigos "cortitos", porfi.

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


(http://st.forocoches.com/foro/images/smilies/aaaaa.gif)

Título: Re: Binomio de Newton, y triángulo de Pascal
Publicado por: Yoel Alejandro en 18 Marzo 2014, 21:31 pm
Sorry, mi código es largo. Pero recuerda que no sólo imprime el triángulo sino que hace el arte adicional de imprimir el desarrollo del binomio en dos líneas (una para la base y otra para el exponente), aunque eso no era exactamente lo se había pedido. Sólo quise ir más allá e imitar un poco la función "pretty" de despliegue por consola de expresiones algebraicas de algunos paquetes como Maple, Matlab.

Y bueno ..... la verdad ya yo me rindo con este tema, jajaja. Que sigan otros  ;D

Título: Re: Binomio de Newton, y triángulo de Pascal
Publicado por: amchacon en 20 Marzo 2014, 12:51 pm
Un reto para animar el tema.

Diseñar la siguiente función:
Código
  1. void FilaTrianguloPascal(long long Vector[],int n)

Lo que hace es obtener la fila N del triangulo de pascal (la guarda en el array vector).

A ver quien es capaz de diseñar esa función con las siguientes condiciones:

- Que no use recursividad, debe sacar la fila del tirón.
- Que funcione para n => 0 && n <= 67. Para que os hagaís una idea de la numeración:

Citar
Fila 0 = 1
Fila 1 = 1 1
Fila 2 = 1 2 1
Fila 3 = 1 3 3 1

Ahí queda la cosa. Cabe decir que tiene trampa ^^

Título: Re: Binomio de Newton, y triángulo de Pascal
Publicado por: ivancea96 en 20 Marzo 2014, 15:05 pm
¿Así?

Código
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. void FilaTrianguloPascal(uint64_t *&arr,int n){
  7.     if(n<0) return;
  8.     static vector< vector<uint64_t> > v;
  9.     if(v.size()<=n)
  10.         for(uint32_t i=v.size(); i<=n; i++){
  11.             v.push_back(vector<uint64_t>());
  12.             for(uint32_t j=0; j<=i; j++)
  13.                 if(j==0 || j==i)
  14.                     v[i].push_back(1);
  15.                 else
  16.                     v[i].push_back(v[i-1][j]+v[i-1][j-1]);
  17.         }
  18.     arr = new uint64_t[n+1];
  19.     for(int i=0; i<=n; i++)
  20.         arr[i] = v[n][i];
  21. }
  22.  
  23. #define NUM 10
  24.  
  25. int main(){
  26.     uint64_t *v;
  27.     FilaTrianguloPascal(v, NUM);
  28.     for(int i=0; i<=NUM; i++)
  29.         cout << v[i] << " ";
  30. }

Usé unsigned long long, sinó no entran los valores.
También puse una puntero al array, para que se haga la petición de memoria desde la misma función. Es se puede cambiar si se desea :3

Título: Re: Binomio de Newton, y triángulo de Pascal
Publicado por: Yoel Alejandro en 20 Marzo 2014, 15:43 pm
ivance, te saliste del reto!!! No puedes usar recursividad:

push_back(v[i-1][j]+v[i-1][j-1]);

 :rolleyes:

Título: Re: Binomio de Newton, y triángulo de Pascal
Publicado por: ivancea96 en 20 Marzo 2014, 15:44 pm
Acaso eso es recursividad?

Título: Re: Binomio de Newton, y triángulo de Pascal
Publicado por: Gh057 en 20 Marzo 2014, 15:46 pm
jejejej tengo entendido que para que sea recursivo, debe llamarse a si misma, y tener un flag de corte... aquí no lo veo... para mí es válido XD saludos!

Título: Re: Binomio de Newton, y triángulo de Pascal
Publicado por: eferion en 20 Marzo 2014, 15:46 pm
¿recursividad? ¿donde?

Hace un uso un poco extraño del vector... pero por lo demás...

Título: Re: Binomio de Newton, y triángulo de Pascal
Publicado por: amchacon en 20 Marzo 2014, 15:47 pm
Cita de: yoel_alejandro en 20 Marzo 2014, 15:43 pm
ivance, te saliste del reto!!! No puedes usar recursividad:

push_back(v[i-1][j]+v[i-1][j-1]);

 :rolleyes:
Exactamente. Esta generando el triángulo recursivamente.

Y cabe en un long long a secas.

PD: No hace falta pasar un puntero. Se puede asumir que el array tiene el tamaño adecuado (y n tiene un valor correcto).

Aunque bueno, tampoco pasa nada si lo compruebas.

Título: Re: Binomio de Newton, y triángulo de Pascal
Publicado por: ivancea96 en 20 Marzo 2014, 16:05 pm
No es recursividad. Guardo datos en una variable, y accedo a ellos. No llamo a la función.

Título: Re: Binomio de Newton, y triángulo de Pascal
Publicado por: Yoel Alejandro en 20 Marzo 2014, 16:19 pm
En informática decimos "recursividad" para referirnos a una función que se llama a sí misma. Pero en el tema de las sucesiones numéricas, la "recursividad" es cuando los términos de la sucesión se generan a partir de los términos anteriores. Por ejemplo la famosa sucesión de Fibonacci a0, a1, a2, ... donde

a0 = 0, a1 = 1

y an = an-1 + an-2 para n>=2 (cada término es la suma de los dos anteriores). Queda entonces:

0,  1,  2,  3,  5,  8,  ...

(ver más en http://es.wikipedia.org/wiki/Sucesi%C3%B3n_de_Fibonacci (http://es.wikipedia.org/wiki/Sucesi%C3%B3n_de_Fibonacci)). Esta es una sucesión por recursividad, mismo método por el que podemos obtener los coeficientes del triangulo de Pascal, pero tenemos prohibido hacerlo por ahí  ;D

Voy con mi propuesta. No se si la intención del problema era usar la clase <vector>, pero yo lo hice en C básico. La fórmula el i-ésimo número en la n-ésima filas del triángulo es:

    n!    
----------
 i! (n-1)!

por lo tanto creé una función que genera los factoriales desde 1! hasta n! (se adopta que 0! = 1 por convencionalismo) en un arreglo de n números del tipo long long. Luego es fácil obtener los binomiales. Queda extenso el código primero porque no se usan plantillas de clase, y segundo porque se verifica la asignación dinámica de memoria:
Código
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. long long * factorial( int );
  5. int * FilaTrianguloPascal( int );
  6.  
  7. int main() {
  8.  
  9.    int *fila;
  10.    int i, n;
  11.  
  12.    n = 10;
  13.    if ( ( fila = FilaTrianguloPascal( n ) ) == NULL )
  14.       return -1;
  15.    i = 0;
  16.    while ( i < n + 1 )
  17.       printf( "%d ", fila[i++] );
  18.  
  19.    return 0;
  20. }
  21.  
  22. /* Calcula los valores de la fila n-esima del triangulo de Pascal */
  23. int * FilaTrianguloPascal( int n ) {
  24.  
  25.    int i, * fila;
  26.    long long * fact;
  27.  
  28.    if ( ( fila = (int *) malloc( (n + 1) *sizeof(int) ) ) == NULL )
  29.       return NULL;
  30.    if ( ( fact = factorial( n ) ) == NULL )
  31.       return NULL;
  32.  
  33.    fila[0] = fila[n] = 1;
  34.    for ( i = 1; i < n; i++ )
  35.       /* fact[k-1] contiene k! */
  36.       fila[i] = fact[n - 1]/ fact[i - 1] / fact[n - i - 1];
  37.  
  38.    return fila;
  39. }
  40.  
  41. /* Devuelve en un arreglo de n+1 elementos los números desde
  42.  * 0! hasta n!.
  43.  * Si no pudo asignar memoria para el arreglo, devuelve NULL.
  44.  */
  45. long long * factorial( int n ) {
  46.  
  47.    int i;
  48.    long long * vector;
  49.  
  50.    if ( ( vector = (long long *) malloc( n * sizeof(long long) ) ) == NULL )
  51.       return NULL;
  52.  
  53.    vector[0] = 1;
  54.    for ( i = 1; i < n; i++ )
  55.       /* vector[i] contiene (i+1)! */
  56.       vector[i] = (i + 1) * vector[i-1];
  57.  
  58.    return vector;
  59. }

NOTA: Amchacon, me gustó este reto porque parece ser muy conciso en sus objetivos. Modifiqué el prototipo de FilaTrianguloPascal para que retornara el vector creado en lugar de recibir el puntero por argumento. Al menos si estamos programando en C me parece más lógico este procedimiento porque la función asigna la memoria dinámicamente y posiblemente relocalice el puntero, entonces ¿qué sentido tiene pasar un puntero como argumento para que la función te devuelva otro? En todo caso se puede pasar el puntero por referencia, un doble puntero long long **, ......... pero ya eso es muy complicado puff, preferí que la función devolviera el puntero final de una vez.

====================================
EDITO:

Hay un detalle con el desbordamiento de los números. Me parece que el tipo long long alcanza para almacenar los números de la fila del triángulo, más no los factoriales requeridos como paso intermedio para el cálculo. Modifiqué el main() para que imprimiera los factoriales solamente:
Código
  1.    n = 25;
  2.    long long * v = factorial( n );
  3.    i = -1;
  4.    while ( ++i < n )
  5.       printf("%02d! = % 20lld\n", i+1, v[i]);
  6.    printf("\n");
  7.  
Véase lo que sucede a partir de 21!:

 15! =        1307674368000
 16! =       20922789888000
 17! =      355687428096000
 18! =     6402373705728000
 19! =   121645100408832000
 20! =  2432902008176640000
 21! = -4249290049419214848
 22! = -1250660718674968576
 23! =  8128291617894825984

A mí me parece desbordamiento ... Y es de recordar que los valores de la función factorial creen muy rápido, incluso más rápido que los valores de la función exponencial en.
Cambiemos al tipo unsigned long long, a ver qué pasa. Modificando el prototipo de factorial() y la cadena de formato de printf():

15! =        1307674368000
16! =       20922789888000
17! =      355687428096000
18! =     6402373705728000
19! =   121645100408832000
20! =  2432902008176640000
21! = 14197454024290336768
22! = 17196083355034583040
23! =  8128291617894825984
24! = 10611558092380307456
25! =  7034535277573963776

Pasa algo extraño del 22! al 23!. E incluso si pedimos imprimir los binomiales, da números negtivos:

1 -1 -17 -110 -497 -1692 -4513 -9671 -16924 -24446 -29335 -29335 -24446 -16924 -9671 -4513 -1692 -497 -110 -17 -1 1


¿Qué opinan de ésto?  :huh:

Título: Re: Binomio de Newton, y triángulo de Pascal
Publicado por: ivancea96 en 20 Marzo 2014, 16:29 pm
En programación, una función es recursiva si tiene una condición de retorno, y en los demás retornos se llama a si misma ·_·

Título: Re: Binomio de Newton, y triángulo de Pascal
Publicado por: Yoel Alejandro en 20 Marzo 2014, 16:40 pm
Claro ivance, pero lo que el autor del tema quiere decir es calcular los números de una fila del triángulo sin usar los valores de las filas anteriores.

Título: Re: Binomio de Newton, y triángulo de Pascal
Publicado por: leosansan en 20 Marzo 2014, 16:41 pm
Cita de: yoel_alejandro en 20 Marzo 2014, 16:19 pm
En informática decimos "recursividad" para referirnos a una función que se llama a sí misma. Pero en el tema de las sucesiones numéricas, la "recursividad" es cuando los términos de la sucesión se generan a partir de los términos anteriores. Por ejemplo la famosa sucesión de Fibonacci a0, a1, a2, ... donde

a0 = 0, a1 = 1

y an = an-1 + an-2 para n>=2 (cada término es la suma de los dos anteriores). Queda entonces:

0,  1,  2,  3,  5,  8,  ...

.......................................................

¡¡¡PERO POR DIOS!!! , en que lugar estas dejando las Matemáticas.

Estimado yoel_alejandro eso que comentas tampoco es recursividad en matemáticas, es lo que se llama ley de recurrencia en contraposición a la llamada fórmula del término general. Es como si la fórmula que da el término general de una sucesión aritmética,  an-1 = a1 +(n-1)d quisieras pasarla como recurrencia, que no recursividad. Pues no, es lo que llamamos fórmula del término general y, aunque está obtenida a partir de un término anterior, no por ello se acuña en Mates el término recursividad, al menos por estos lares, no sé si por ahí le cambiáis el nombre.

Así que NO,  ivancea96 no a aplicado recursividad., pero.....

¡¡¡ivancea96 OS LA HA PEGADO!!!

y de paso yoel_alejandro

ya que ambos NO DIBUJAN EL TRIÄNGULO, tan sólo escriben una línea de una potencia, más exactamente la 10. ¡¡¡Trampocillos!!!, que son unos trampocillos.

Eso sí, a partir de lo que tiene si que pueden aplicar fácilmente recursividad para obtener el dichosito triángulo, tan sólo tendrán que ajustar los espacios, que no es poco.

Casi, casi cuela, pero NO......

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


(http://st.forocoches.com/foro/images/smilies/aaaaa.gif)

EDITO: Esto SI es un triángulo de Pascal con recursividad el clásico podríamos llamarlo y "cortito" xD:


Código
  1. #include<iostream>
  2. #include <iomanip>
  3. #define m   12
  4. using namespace std;
  5.  
  6. int factorial(int n)
  7. {
  8.     if(n<2)
  9.         return 1;
  10.     else
  11.         return n * factorial(n-1);
  12. }
  13.  
  14. int combinacion(int n, int r)
  15. {
  16.     if(r==1)
  17.         return n;
  18.     else
  19.     {
  20.         if(n==r)
  21.             return 1;
  22.         else
  23.             return factorial(n) / (factorial(r) * factorial(n - r));
  24.     }
  25. }
  26.  
  27. int main()
  28. {
  29.     for(int i=0; i<m; i++)
  30.     {
  31.         for(int z=0; z<m-i; z++)
  32.             cout << setw(3) << "";
  33.        for (int j = 0; j <= i; j++)
  34.         cout << setw(6) << combinacion(i,j);
  35.  
  36.         cout << endl;
  37.     }
  38.     return 0;
  39. }

Pero no es lo siguiente que había propuesto, a partir de un array unidimensional. Aunque ya puestos, también se admite uno con recursividad a partir de números combinatorios, pero a partir de Vm,n/Pn. Todo es ponerse a ello ....si te interesa y "estas preparado" en programación, que el  lenguaje ya sé que lo domináis a fondo  que todo es empezar, no hace falta buscar retos muy complejos.

Y el código que pongo es primitivo, como el de yoel_alejandro porque usa factoriales y su cálculo se "sale" de las posibilidades del C/C++ en cuanto se aumenta más allá de trece o por ahí y, claro, salen números "raritos".

Título: Re: Binomio de Newton, y triángulo de Pascal
Publicado por: ivancea96 en 20 Marzo 2014, 16:44 pm
El reto era devolver la línea, no el triángulo.

Título: Re: Binomio de Newton, y triángulo de Pascal
Publicado por: amchacon en 20 Marzo 2014, 16:59 pm
Estoy en el movil, así que voy a prescindir de los quotes y ser muy breve:

@Alejandro: La solución no es correcta porque no funciona para n > 20.

Hay una simplificación del numero combinatorio en algunos casos, eso te debería permitir un correcto funcionamiento hasta n = 40.

@Leosan: Cuando en una sucesión expreso un término respecto al anterior, se le llama recurrencia. La recurrencia no es mas que una aplicación matemática de la recursividad.

Cualquier algoritmo recursivo que se postre se puede representar con una recurrencia (y viceversa).

Título: Re: Binomio de Newton, y triángulo de Pascal
Publicado por: Gh057 en 20 Marzo 2014, 17:10 pm
interesantísimo punto el que indicas amchacon, no tomaba la recurrencia matemática como una función recursiva clásica en informática (uno de los puntos si o si presentes es la llamada a sí misma en ella). por lo cual te agradezco la aclaración . saludos

Título: Re: Binomio de Newton, y triángulo de Pascal
Publicado por: eferion en 20 Marzo 2014, 17:12 pm
El caso es que en programación, al menos hasta donde yo alcanzo, por recursividad se entiende al proceso mediante el cual una función o algoritmo se llama a sí mismo para obtener un resultado.

Reutilizar valores anteriores, al menos en programación, no se entiende por recursividad.

Entre otras cosas en programación SIEMPRE reutilizas valores anteriores:

ejemplo típico: un bucle

Código
  1. for( i=0; i< 20; i++ )

Estás reutilizando el valor anterior de i... la alternativa es escribir las iteraciones a pelo.

Esto es recursividad??? no creo.

y qué diferencia hay entre esto y reutilizar los valores de un vector??

* que los valores del vector han sido calculados ?? el de i también, no se llega a i=5 por arte de magia.

* que los valores del vector se necesitan para la solución final ?? el valor de i también... si no se podría prescindir de esta variable.

Esta es, a grandes rasgos, mi opinión al respecto


Título: Re: Binomio de Newton, y triángulo de Pascal
Publicado por: ivancea96 en 20 Marzo 2014, 17:14 pm
Opino lo mismo que Eferion. Cierto es, que muchas cosas se pueden tratar como recursivas.
Para evitar esto, se pone un límite: Las recursivas son las que se llaman a si mismas.

Título: Re: Binomio de Newton, y triángulo de Pascal
Publicado por: Gh057 en 20 Marzo 2014, 17:24 pm
ahora bien, dicho concepto entonces me trastoca los libros... si una recurrencia se toma como una recursividad, la función factorial realizada por sumatoria (entiéndase por iteraciones) no representaría en sí una recursividad también?

dicho de otro modo cualquier sumatoria n, n+1,n+2... nn sería recursivo; implica acceder al valor anterior de n para continuar la serie...

Título: Re: Binomio de Newton, y triángulo de Pascal
Publicado por: eferion en 20 Marzo 2014, 17:27 pm
Cita de: Gh057 en 20 Marzo 2014, 17:24 pm
ahora bien, dicho concepto entonces me trastoca los libros... si una recurrencia se toma como una recursividad, la función factorial realizada por sumatoria (entiéndase por iteraciones) no representaría en sí una recursividad también?

dicho de otro modo cualquier sumatoria n, n+1,n+2... nn sería recursivo; implica acceder al valor anterior de n para continuar la serie...


Esto más o menos viene a resumir lo que he expuesto.

Título: Re: Binomio de Newton, y triángulo de Pascal
Publicado por: ivancea96 en 20 Marzo 2014, 17:37 pm
Dicho esto, supongo que amchacon se refería a hacerlo por cualquier método menos por el método de sumar.


Tenía pendiente hacer esto. Aquí está:

Código
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. class factorial{
  7.     vector<uint32_t> mul, div;
  8.     bool divided;
  9.  
  10.     public: static void f(vector<uint32_t> &v, uint32_t n){
  11.         for(uint32_t i=2; i<(n/2)+1;)
  12.             if(n%i==0){
  13.                 v.push_back(i);
  14.                 n/=i;
  15.             }else ++i;
  16.             v.push_back(n);
  17.     }
  18. public:
  19.     factorial():divided(false){mul.clear(); div.clear();}
  20.  
  21.     int getMulCount()const{return mul.size();}
  22.     uint32_t getMul(int n)const{if(n>=0 && n<mul.size()) return mul[n]; else return 0;}
  23.     vector<uint32_t> getMul()const{return mul;}
  24.     void addMul(uint32_t m){mul.push_back(m);divided=false;}
  25.     void addMulFactorial(uint32_t f){if(f)for(int i=1; i<=f; i++) mul.push_back(i);divided=false;}
  26.  
  27.     int getDivCount()const{return div.size();}
  28.     uint32_t getDiv(int n)const{if(n>=0 && n<div.size()) return div[n]; else return 0;}
  29.     vector<uint32_t> getDiv()const{return div;}
  30.     void addDiv(uint32_t d){div.push_back(d);divided=false;}
  31.     void addDivFactorial(uint32_t f){if(f)for(int i=1; i<=f; i++) div.push_back(i);divided=false;}
  32.  
  33.     void fact(){factMul();factDiv();}
  34.     void factMul(){
  35.         vector<uint32_t> temp(mul);
  36.         mul.clear();
  37.         for(int i=0; i<temp.size(); i++)
  38.             f(mul, temp[i]);
  39.         for(int i=0; i<mul.size();)
  40.             if(mul[i]==1)
  41.                 mul.erase(mul.begin()+i);
  42.             else ++i;
  43.     }
  44.     void factDiv(){
  45.         vector<uint32_t> temp(div);
  46.         div.clear();
  47.         for(int i=0; i<temp.size(); i++)
  48.             f(div, temp[i]);
  49.         for(int i=0; i<div.size();)
  50.             if(div[i]==1)
  51.                 div.erase(div.begin()+i);
  52.             else ++i;
  53.     }
  54.     void divide(){
  55.         fact();
  56.         for(int i=0; i<mul.size(); i++)
  57.             for(int j=0; j<div.size(); j++)
  58.                 if(mul[i]==div[j]){
  59.                     mul.erase(mul.begin()+i);
  60.                     div.erase(div.begin()+j);
  61.                     --i; --j;
  62.                     break;
  63.                 }
  64.         divided=true;
  65.     }
  66.     uint64_t get(){
  67.         uint64_t t=1;
  68.         if(!divided) divide();
  69.         for(int i=0; i<mul.size(); i++)
  70.             t*=mul[i];
  71.         for(int i=0; i<div.size(); i++)
  72.             t/=div[i];
  73.         return t;
  74.     }
  75.     void clear(){mul.clear(); div.clear();divided=false;}
  76. };
  77.  
  78. void FilaTrianguloPascal(uint64_t *&arr, uint32_t n){
  79.     factorial f;
  80.     arr = new uint64_t[n+1];
  81.     for(int i=0; i<=n; i++){
  82.         f.addMulFactorial(n);
  83.         f.addDivFactorial(i);
  84.         f.addDivFactorial(n-i);
  85.         f.divide();
  86.         arr[i] = f.get();
  87.         f.clear();
  88.     }
  89. }
  90.  
  91. int main(){
  92.     uint64_t *v;
  93.     for(int i=0; i<10; i++){
  94.         FilaTrianguloPascal(v, i);
  95.         for(int j=0; j<=i; j++)
  96.             cout << v[j] << " ";
  97.         if(i) delete[] v;
  98.         else delete v;
  99.         cout << endl;
  100.     }
  101. }

Título: Re: Binomio de Newton, y triángulo de Pascal
Publicado por: leosansan en 21 Marzo 2014, 07:43 am
....xD PEDAZO DE CÓDIGOS.....

...............para este viaje no hacen falta tantas alforjas...............

Amigo ivancea96 para obtener esta salida:

Citar
1
1   1
1   2   1
1   3   3   1
1   4   6   4   1
1   5  10  10   5   1
1   6  15  20  15   6   1
1   7  21  35  35  21   7   1
1   8  28  56  70  56  28   8   1
1   9  36  84 126 126  84  36   9   1
1  10  45 120 210 252 210 120  45  10   1
1  11  55 165 330 462 462 330 165  55  11   1
1  12  66 220 495 792 924 792 495 220  66  12   1
1  13  78 286 715 1287 1716 1716 1287 715 286  78  13   1
1  14  91 364 1001 2002 3003 3432 3003 2002 1001 364  91  14   1
1  15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105  15   1
1  16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120  16   1

aunque podrías haber hecho trampas, cosa que no has hecho, usando [ center ] para que saliera el triángulo isósceles que pedimos en este reto:

Citar
1
1   1
1   2   1
1   3   3   1
1   4   6   4   1
1   5  10  10   5   1
1   6  15  20  15   6   1
1   7  21  35  35  21   7   1
1   8  28  56  70  56  28   8   1
1   9  36  84 126 126  84  36   9   1
1  10  45 120 210 252 210 120  45  10   1
1  11  55 165 330 462 462 330 165  55  11   1
1  12  66 220 495 792 924 792 495 220  66  12   1
1  13  78 286 715 1287 1716 1716 1287 715 286  78  13   1
1  14  91 364 1001 2002 3003 3432 3003 2002 1001 364  91  14   1
1  15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105  15   1
1  16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120  16   1

Como decía, para obtener esa salida creo que no hace falta un código tan extenso/complejo. Este que te pongo a continuación hace lo mismo que el tuyo y es considerablemente más "cortito", exactamente una décima parte:

Código
  1. #include <stdio.h>
  2. int main(void){
  3.   unsigned  int a,b,k,n,filas=16;
  4.   for(n = 0; n <= filas; n++){
  5.     putchar ('1');
  6.     for(k = b = 1, a = n; b <= n; b++, a--)
  7.       printf("%3u " ,k = k * a / b);
  8.     putchar('\n');
  9.   }
  10.   return 0;
  11. }


¡Ah!, que tenía que tener esta forma:

Citar
                   1
                  1   1
                1   2   1
              1   3   3   1
            1   4   6   4   1
          1   5  10  10   5   1
        1   6  15  20  15   6   1
      1   7  21  35  35  21   7   1
    1   8  28  56  70  56  28   8   1
  1   9  36  84 126 126  84  36   9   1


Conste que con las etiquetas quote sale algo deformado, pero al ejecutarlo en consola sale perfecto:

Código
  1. #include <stdio.h>
  2. int main(void){
  3.   unsigned  int i,a,b,k,n,filas=13;
  4.   for(n = 0; n <= filas; n++){
  5.     for (i=0;i<filas-n;i++)
  6.       printf("   ");
  7.       putchar ('1');
  8.     for(k = b = 1, a = n; b <= n; b++, a--)
  9.       printf("%5u " ,k = k * a / b);
  10.     putchar('\n');
  11.   }
  12.   return 0;
  13. }


Bueno está bien, tú usabas un array. Pues yo también:

Código
  1. #include <stdio.h>
  2. #define N   16
  3. int main(void){
  4.   unsigned  int a,b,k,n,comb[N+1][N+1];
  5.   for(a = 0; a <= N; a++)
  6.     for(b = 0; b <= N; b++)
  7.       (b==0) ? (comb[a][b]=1) :(comb[a][b]=0);
  8.   for(n = 0; n <= N; n++)
  9.     for(k = b = 1, a = n; b <= n; b++, a--){
  10.       k = k * a / b;
  11.       comb[n][b]=k ;
  12.     }
  13.   for(a = 0; a <= N; a++){
  14.     for(b = 0; b <= N; b++)
  15.       if (comb[a][b]!=0)
  16.         printf("%3u " ,comb[a][b]);
  17.     putchar('\n');
  18.   }
  19.    return 0;
  20. }

Como ves sigue siendo "cortito". ;)

Dándole vueltas al triángulo de Pascal y viendo que el "cálculo directo" con factoriales tiene el inconveniente de los mencionados factoriales, se observa que los números combinatorios que forman el triángulo son, por ejemplo:
Citar

(7 0)=1  

(7 0)=1  

(7 1)=7/1
  
(7 2)=7/1 *6/2 =7*6/1*2
 
(7 3)=/1 *6/2* 5/3 =7*6*5/1*2*3
 
(7 4)=7/1 *6/2* 5/3* 4/4= 7*6*5*4/1*2*3*4 =7*6*5/1*2*3 = (7 3)
 
(7 5)=7/1 *6/2* 5/3 *4/4* 3/5= 7*6*5*4*3/1*2*3*4*5 = 7*6/1*2= (7 2)
 
(7 6)=7/1 *6/2*5/3*4/4*3/5*2/6= 7*6*5*4*3*2/1*2*3*4*5*6= 7/1= (7 1)
 
(7 7) = 1 = (7 0)=1


es decir, 1*n/i, donde n va disminuyendo e i aumentando, de manera que se evita el cálculo de los factoriales. Además son simétricos con lo que se puede, y debe  por eficiencia, calcular la segunda mitad directamente y obtenerlos  de acuerdo a otra propiedad de los números combinatorios:

(http://i1280.photobucket.com/albums/a497/leosansan/GRAFICOS1/binomioNewton7_zps5ce6b3db.jpg)


 Con esta idea
salen los siguientes códigos, con array y sin él::

Código
  1. #include <stdio.h>
  2. #define N   13
  3. int main(void){
  4.   unsigned  int i,a,b,k,n,comb[N+1][N+1];
  5.   for(a = 0; a <= N; a++)
  6.     for(b = 0; b <= N; b++)
  7.       (b==0) ? (comb[a][b]=1) :(comb[a][b]=0);
  8.   for(n = 0; n <= N; n++)
  9.     for(k = b = 1, a = n; b <= n; b++, a--){
  10.       if (b>N/2)
  11.         comb[n][b]=comb[n][n-b];
  12.        else {
  13.         k = k * a / b;
  14.         comb[n][b]=k ;
  15.        }
  16.     }
  17.   for(a = 0; a <= N; a++){
  18.     for(i = 0; i < N-a; i++)
  19.       printf("  " );
  20.     for(b = 0; b <= N; b++)
  21.       if (comb[a][b]!=0)
  22.         printf("%3u " ,comb[a][b]);
  23.     putchar('\n');
  24.   }
  25.    return 0;
  26. }

Código
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. int comb(int n,int k);
  5.  
  6. int main(){
  7.   int i,j,k;
  8.   int n = 11;
  9.   /*do{
  10.     printf("\nIntroduzca la potencia a calcular (mayor que cero): \n");
  11.     scanf("%d",&n);
  12.     }while ( n < 0 );
  13.     n++;*/
  14.     char tamanyo_consola[80];
  15.     sprintf(tamanyo_consola, "MODE %d,%d", n*6+10+1,40);
  16.     system(tamanyo_consola);
  17.     for (i = 0; i < n; i++){
  18.       for ( j = 1; j <n-i; j++)
  19.       printf ("   ")  ;
  20.       for (k = 0; k <= i; k++)
  21.         printf ("%6d",comb(i,k));
  22.       printf ("\n");
  23.     }
  24.     return 0;
  25. }
  26. int comb(int n,int k){
  27.   if (n < 0 || k < 0 || k > n)
  28.     return 0;
  29.   if (k>n/2)
  30.     k=n-k;
  31.   int c = 1;
  32.   for ( k; k>=1; k--,n--)
  33.     c*=n/k;
  34.   return c;
  35. }

Como en otros códigos anteriores hago uso del system (MODE)  para que la ventana de la consola se ajuste de forma automática al tamaño del triángulo. Y como no podía ser menos, al menos una imagen, sí ya sé que empieza a estar muy vista pero es que" me fascina la belleza de los números", con color o sin ellos:


(http://i1280.photobucket.com/albums/a497/leosansan/GRAFICOS1/binomiotriangulo20color_zps13cf19da.jpg)


(http://i1280.photobucket.com/albums/a497/leosansan/GRAFICOS1/binomiotriangulo20_zpsb4b5f7c8.jpg)


Y sólo quedan 24 horas para obtener el triángulo a partir de un array unidimensional. ¡¡¡Vamos Ánimo!!!

Cita de: eferion en 20 Marzo 2014, 17:12 pm
El caso es que en programación, al menos hasta donde yo alcanzo, por recursividad se entiende al proceso mediante el cual una función o algoritmo se llama a sí mismo para obtener un resultado.

Reutilizar valores anteriores, al menos en programación, no se entiende por recursividad.
..............................

Totalmente de acuerdo, y en Cálculo/Matemáticas tampoco se llama a eso recursividad sino recurrencia, como bien recordó amchacon,  cuando los valores de un término se obtienen a partir de otros anteriores. Otra cosa es cuando la ley o fórmula de recurrencia la apliques de forma iterada, entonces si podemos hablar, incluso matemáticamente, de recursividad. Todo es cuestión de semántica y saber emplear las palabras adecuadas.

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


(http://st.forocoches.com/foro/images/smilies/aaaaa.gif)

Título: Re: Binomio de Newton, y triángulo de Pascal
Publicado por: Yoel Alejandro en 21 Marzo 2014, 14:54 pm
Leosansan:

1. Recuerda que el tema en realidad lo abrí yo, y puse la descripción del mismo. Ahora quieres cambiarme el problema, y encima reprochas a los demás y a mí porque el problema no se conduce como TÚ quieres. Te recomiendo dos cosas: (a) Ve al psicólogo. (b) Abre tu propio tema..

2. Recursión, recurrencia o recursividad se pueden considerar palabras de significados similares. No hay por qué hacer tanto escándalo (a no ser con el objeto de descalificar a los demás). La fuente http://es.wikipedia.org/wiki/Recursi%C3%B3n (http://es.wikipedia.org/wiki/Recursi%C3%B3n) aclara:
Citar
Recurrencia, recursión o recursividad es la forma en la cual se especifica un proceso basado en su propia definición. Siendo un poco más precisos, y para evitar el aparente círculo sin fin en esta definición:
Un problema que pueda ser definido en función de su tamaño, sea este N, pueda ser dividido en instancias más pequeñas (< N) del mismo problema y se conozca la solución explícita a las instancias más simples, lo que se conoce como casos base, se puede aplicar inducción sobre las llamadas más pequeñas y suponer que estas quedan resueltas.
En otras palabras, la definición para el caso de "N" se basa en la definición para los casos desde "1" hasta "N-1", algunos de los cuales están predefinidos de cierta manera. No obstante, la misma fuente dice que el término correcto en nuestra lengua es "recurrencia".

3. El empleo de la palabra "recursión" viene de boca de amchacón quién dijo: "Que no use recursividad, debe sacar la fila del tirón." Analizando el contexto de sus palabras, más allá de lo linguístico, cualquiera con buena intención puede inferir lo que quiso decir: Que los números de una fila del triángulo no se calculen usando los números de filas anteriores. Lo que traté fue dar respuesta a ese planteamiento, mismo que también fue comprendido por ivance96.

4. Este no es un foro de matemáticas (que quede claro), pero ya mencionas tanto ese tema te pongo de ejercicio investigar las siguientes demostraciones:
(a) El elemento unidad en R es único.
(b) La propiedad anterior es válida para toda ley de composición interna que sea conmutativa.
(c) El límite de una función real de variable real, si existe, es único.
Por lo menos te puedo decir que yo las conozco y te las puedo dar sin siquiera mirar el libro (sin ánimo de ofender, pues es mi profesión y se supone que lo haga, tal como un cirujano debe ser capaz de operar, un aviador de volar, etc., sin ver el manual). ¿Tú puedes responder las mismas preguntas? Si lo haces eres un verdadero matemático, capaz de citar y comprender definiciones, y realizar demostraciones. De otro modo, por favor DEJA la diatriba y comentarios del tipo:
Citar
¡¡¡PERO POR DIOS!!! , en que lugar estas dejando las Matemáticas.
dirigidos hacia mí. Sino deberé presentar una queja a los moderadores del foro.

Título: Re: Binomio de Newton, y triángulo de Pascal
Publicado por: Gh057 en 21 Marzo 2014, 15:04 pm
buenos días, si me permiten solo voy a hacer tan solo una crítica constructiva de este subforo, al cual realmente me apasiona pero sin embargo personalmente me ha desanimado de hacer algún humilde aporte o contestar algún post (no preguntas ya que no hago, de hecho todavía no he hecho en ningún foro por más que hace un tiempo que lo frecuento, un poco porque me gusta buscar la respuesta por mí mismo o simplemente por tímido) por un tiempo largo; pareciera que a veces se deja de lado el nivel de código (que es realmente exquisito en algunos usuarios) y se empieza a medir el nivel de testosterona...

relax! and don't do it... jejej disfruten de este espacio, e intenten contagiar esa pasión a los demás, como la que yo siento cada vez que veo un muy buen post.
un cordial saludo para todos!

Título: Re: Binomio de Newton, y triángulo de Pascal
Publicado por: Yoel Alejandro en 21 Marzo 2014, 16:54 pm
Gh057, tienes razón y me disculpo, .... pero a veces se desborda la adrenalina. Ahora, dejando las emociones negativas a un lado y concentrándome en lo positivo  :D voy a retomar el asunto, para que así no se pierdan la pasión y la sutileza porque aquí hay muchas cosas valiosas que no merecen perderse por una tontería.

Amchacón planteó que el código puede optimizarse para que no ocurra el desbordamiento. La enigmática palabra "optimizar" estuvo dando vueltas en mi cabeza desde que fue pronunciada, jajaja. Porque la verdad es que yo estaba enfocando este programa de una manera simplista y a lo "bestia".

Veamos, la fórmula del combinatorio <n,i> es:

    n!
----------
 i! (n-i)!

Dicha fórmula es algebraicamente concisa, pero numéricamente ineficiente. Analizando en sus entresijos la podemos llevar a:

 n * (n - 1) * (n - 2) * ... * (n - i + 1) * (n - i) * (n - i - 1) * ... * 1
------------------------------------------------------------------------------
            [1 * 2 * ... * i ] [(n - i) * (n - i - 1) * ... * 1]

y vemos como términos de n! se cancelan con términos de (n-i)!, quedando:

 n * (n - 1) * (n - 2) * ... * (n - i + 1)
----------------------------------------------
               1 * 2 * ... * i

y es lo que queremos.

Uno puede pensar en un "for" doble para evaluar productos, algo como:
Código
  1. for ( i = 1; i < n; i++ ) {
  2.     A = B = 1;
  3.     for ( j = i; j <= i; j++ ) {
  4.         A *= n - j + 1;
  5.         B *= j;
  6.     }
  7.     comb[i] = A / B;
  8.  
... pero repasemos aún más la situación. Escribiendo cómo va quedando el numerador para i = 1, i = 2, i = 3, ..., vemos cómo podemos reutilizar los resultados de un valor de "i" para el otro:

i=1: n
i=2: n * (n - 1)
i=3: n * (n - 1) * (n - 2)

así que podemos empezar con A = 1, y luego con cada "i" hacemos A *= (n - i + 1). Y de manera similar con el denominador. Nos ahorramos un "for". Además, aprovechamos el hecho de que la mitad izquierda de la fila es simétrica con la derecha. Nos queda un código tan simple como
Código
  1. long long * FilaTrianguloPascal( int n ) {
  2.  
  3.    int i, j;
  4.    long long A, B, * fila;
  5.  
  6.    if ( ( fila = (long long *) malloc( (n + 1) *sizeof(long long) ) ) == NULL )
  7.       return NULL;
  8.  
  9.    fila[0] = fila[n] = 1;
  10.  
  11.    A = 1;		/* numerador */
  12.    B = 1;		/* denominador */
  13.    for ( i = 1; i < n; i++ ) {
  14.       /* mitad izquierda de la fila */
  15.       if ( i <= n / 2 ) {
  16.          A *= n - i + 1;
  17.          B *= i;
  18.          fila[i] = A / B;
  19.       }
  20.       /* mitad derecha */
  21.       else
  22.          fila[i] = fila[n - i];
  23.    }
  24.  
  25.    return fila;
  26. }
que probé y produce los resultados correctos, por ejemplo para n=18:

1 18 153 816 3060 8568 18564 31824 43758 48620 43758 31824 18564 8568 3060 816 153 18 1

¿Más o menos así era como se quería?


Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines