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

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

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

leosansan

#11
¡¡¡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]

#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]

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

amchacon

#13
Un reto para animar el tema.

Diseñar la siguiente función:
Código (cpp) [Seleccionar]
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:

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

¡Visita mi programa estrella!

Rar File Missing: Esteganografía en un Rar

ivancea96

¿Así?

Código (cpp) [Seleccionar]
#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]);

:rolleyes:
Saludos, Yoel.
P.D..-   Para mayores dudas, puedes enviarme un mensaje personal (M.P.)

ivancea96


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!
4 d0nd3 1r4 3l gh057? l4 r3d 3s 74n v4s74 3 1nf1n1t4...

eferion

¿recursividad? ¿donde?

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

amchacon

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

¡Visita mi programa estrella!

Rar File Missing: Esteganografía en un Rar