Binomio de Newton, y triángulo de Pascal

[Yoel Alejandro]

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  (broma). El código:

Código (cpp) [Seleccionar] Expandir


int line_width( int **, int );
void print( int **, int );

int main( ) {

/* ......... (resto del programa) ................. */
/* Imprimir el triangulo */
   print( A, N );
   putchar('\n');
/* ..........(resto del programa) .............. */
}

/* Calcula el ancho impresa de una linea del triangulo de Pascal */
int line_width( int ** A, int i ) {

   int j, width = 0;

   if ( i > 0 ) { /* lineas 1 en adelante */
      for ( j = 0; j <= i; j++ )
         width += digits( A[i][j] );
      width += i; /* (los espacios en blanco) */
      return width;
   }
   else if ( i == 0 ) /* linea cero */
      return 1;
   else /* argumento negativo */
      return 0;
}

/* Imprime el triangulo de Pascal de orden N */
void print( int **A, int N ) {

   int MAX_width, width, i, j;

   /* linea mas ancha del triangulo */
   MAX_width = line_width( A, N );

   for ( i = 0; i <= N; i++ ) {
      width = line_width( A, i ); /* linea actual */
      j = 0;
      while ( j++ < (MAX_width - width)/2 )
         putchar(' ');
      for ( j = 0; j <= i; j++ )
         printf( "%d ", A[i][j] );
      putchar('\n');
   }
}


[leosansan]

¡¡¡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 (cpp) [Seleccionar] Expandir


#include <stdio.h>
#include <stdlib.h>
int main(){
 unsigned int i,j,n=21,N;
 char tamanyo_consola[80];
 /*do{
   printf("\nIntroduzca la potencia a calcular (0-23): \n");
   fflush( stdout );
   scanf("%u",&n);
   }while ( n < 0  || n > 23);*/
 N = 2 *(++n)  - 1; /* numero de columnas*/
 sprintf(tamanyo_consola, "MODE %d,%d",(int) (4.5*N+1),2*N);
 system(tamanyo_consola);
 unsigned int a[n][N+1];
 for (i=0;i<=n-1;i++)
   for (j=0;j<=(N);j++)
     a[i][j] = 0;
 a[0][n-1] =  1;
 for (i=1;i<=n-1;i++)
   for (j=n-1-i;j<=n-1+i;j+=2)
       a[i][j] = a[i-1][j-1] + a[i-1][j+1];
 for (i=0;i<=n-1;i++){
   for (j=0;j<=n-1+i;j++){
     if (a[i][j]==0)
       printf("    ");
     else
       printf("%4u",a[i][j]);
   }
   putchar ('\n');
 }
 return 0;
}

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 (cpp) [Seleccionar] Expandir


#include <stdio.h>
int main(){
 unsigned int i,j,n=13,N;
 /*do{
   printf("\nIntroduzca la potencia a calcular (0-13): \n");
   fflush( stdout );
   scanf("%u",&n);
   }while ( n < 0  || n > 13);*/
 N = 2 *(++n)  - 1; /* numero de columnas*/
 unsigned int a[n][N+1];
 for (i=0;i<=n-1;i++)
   for (j=0;j<=(N);j++)
     a[i][j] = 0;
 a[0][n-1] =  1;
 for (i=1;i<=n-1;i++)
   for (j=n-1-i;j<=n-1+i;j++)
       a[i][j] = a[i-1][j-1] + a[i-1][j+1];
 for (i=0;i<=n-1;i++){
   for (j=0;j<=n-1+i;j++){
     if (a[i][j]==0)
       printf("    ");
     else
       printf("%4u",a[i][j]);
   }
   putchar ('\n');
 }
 return 0;
}

Y una muestra de la salida para 15:

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 (cpp) [Seleccionar] Expandir

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 (cpp) [Seleccionar] Expandir

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

[Yoel Alejandro]

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 

[amchacon]

Un reto para animar el tema.

Diseñar la siguiente función:

Código (cpp) [Seleccionar] Expandir

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:

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

[ivancea96]

¿Así?

Código (cpp) [Seleccionar] Expandir

#include <iostream>
#include <vector>

using namespace std;

void FilaTrianguloPascal(uint64_t *&arr,int n){
    if(n<0) return;
    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]);
        }
    arr = new uint64_t[n+1];
    for(int i=0; i<=n; i++)
        arr[i] = v[n][i];
}

#define NUM 10

int main(){
    uint64_t *v;
    FilaTrianguloPascal(v, NUM);
    for(int i=0; i<=NUM; i++)
        cout << v[i] << " ";
}

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

[Yoel Alejandro]

ivance, te saliste del reto!!! No puedes usar recursividad:

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

[ivancea96]

Acaso eso es recursividad?

[Gh057]

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!

[eferion]

¿recursividad? ¿donde?

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

[amchacon]

ivance, te saliste del reto!!! No puedes usar recursividad:

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

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.