elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Security Series.XSS. [Cross Site Scripting]


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Binomio de Newton, y triángulo de Pascal
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: 1 [2] 3 4 Ir Abajo Respuesta Imprimir
Autor Tema: Binomio de Newton, y triángulo de Pascal  (Leído 40,919 veces)
Yoel Alejandro

Desconectado Desconectado

Mensajes: 254



Ver Perfil WWW
Re: Binomio de Newton, y triángulo de Pascal
« Respuesta #10 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.  


« Última modificación: 16 Marzo 2014, 18:43 pm por yoel_alejandro » En línea

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


Desconectado Desconectado

Mensajes: 1.314


Ver Perfil
Re: Binomio de Newton, y triángulo de Pascal
« Respuesta #11 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:



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




« Última modificación: 17 Marzo 2014, 19:21 pm por leosansan » En línea

Yoel Alejandro

Desconectado Desconectado

Mensajes: 254



Ver Perfil WWW
Re: Binomio de Newton, y triángulo de Pascal
« Respuesta #12 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
En línea

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


Desconectado Desconectado

Mensajes: 1.211



Ver Perfil
Re: Binomio de Newton, y triángulo de Pascal
« Respuesta #13 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 ^^
« Última modificación: 20 Marzo 2014, 13:02 pm por amchacon » En línea

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


Desconectado Desconectado

Mensajes: 3.412


ASMático


Ver Perfil WWW
Re: Binomio de Newton, y triángulo de Pascal
« Respuesta #14 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
En línea

Yoel Alejandro

Desconectado Desconectado

Mensajes: 254



Ver Perfil WWW
Re: Binomio de Newton, y triángulo de Pascal
« Respuesta #15 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:
En línea

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


Desconectado Desconectado

Mensajes: 3.412


ASMático


Ver Perfil WWW
Re: Binomio de Newton, y triángulo de Pascal
« Respuesta #16 en: 20 Marzo 2014, 15:44 pm »

Acaso eso es recursividad?
En línea

Gh057


Desconectado Desconectado

Mensajes: 1.190



Ver Perfil
Re: Binomio de Newton, y triángulo de Pascal
« Respuesta #17 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!
En línea

4 d0nd3 1r4 3l gh057? l4 r3d 3s 74n v4s74 3 1nf1n1t4...
eferion


Desconectado Desconectado

Mensajes: 1.248


Ver Perfil
Re: Binomio de Newton, y triángulo de Pascal
« Respuesta #18 en: 20 Marzo 2014, 15:46 pm »

¿recursividad? ¿donde?

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

amchacon


Desconectado Desconectado

Mensajes: 1.211



Ver Perfil
Re: Binomio de Newton, y triángulo de Pascal
« Respuesta #19 en: 20 Marzo 2014, 15:47 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.
En línea

Por favor, no me manden MP con dudas. Usen el foro, gracias.

¡Visita mi programa estrella!

Rar File Missing: Esteganografía en un Rar
Páginas: 1 [2] 3 4 Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Calculador de Binomio de Newton [Python]
Scripting
CaronteGold 9 20,957 Último mensaje 17 Febrero 2022, 20:46 pm
por werty2310
* [Source] Triangulo Pascal « 1 2 »
Programación Visual Basic
BlackZeroX 13 12,799 Último mensaje 6 Enero 2010, 03:02 am
por BlackZeroX
[SRC] Triangulo Pascal [by *PsYkE1*]
Programación Visual Basic
Psyke1 3 2,981 Último mensaje 27 Mayo 2010, 09:14 am
por Psyke1
[C] Imprimir Triangulo de Pascal
Programación C/C++
edr89 3 16,495 Último mensaje 7 Junio 2013, 09:27 am
por leosansan
Forma triangulo de pascal
Programación C/C++
shulpeca 0 1,808 Último mensaje 1 Diciembre 2017, 22:47 pm
por shulpeca
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines