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

 

 


Tema destacado: ¿Eres nuevo? ¿Tienes dudas acerca del funcionamiento de la comunidad? Lee las Reglas Generales


+  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 2 Visitantes 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 41,104 veces)
ivancea96


Desconectado Desconectado

Mensajes: 3.412


ASMático


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


En línea

Yoel Alejandro

Desconectado Desconectado

Mensajes: 254



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


« Última modificación: 20 Marzo 2014, 16:38 pm por yoel_alejandro » 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 #22 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 ·_·
En línea

Yoel Alejandro

Desconectado Desconectado

Mensajes: 254



Ver Perfil WWW
Re: Binomio de Newton, y triángulo de Pascal
« Respuesta #23 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.
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 #24 en: 20 Marzo 2014, 16:41 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! ..... !!!!



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

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

ivancea96


Desconectado Desconectado

Mensajes: 3.412


ASMático


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

El reto era devolver la línea, no el triángulo.
En línea

amchacon


Desconectado Desconectado

Mensajes: 1.211



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


Desconectado Desconectado

Mensajes: 1.190



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

En línea

ivancea96


Desconectado Desconectado

Mensajes: 3.412


ASMático


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

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]
Python
CaronteGold 9 21,096 Último mensaje 17 Febrero 2022, 20:46 pm
por werty2310
* [Source] Triangulo Pascal « 1 2 »
Programación Visual Basic
BlackZeroX 13 12,829 Último mensaje 6 Enero 2010, 03:02 am
por BlackZeroX
[SRC] Triangulo Pascal [by *PsYkE1*]
Programación Visual Basic
Psyke1 3 3,023 Último mensaje 27 Mayo 2010, 09:14 am
por Psyke1
[C] Imprimir Triangulo de Pascal
Programación C/C++
edr89 3 16,526 Último mensaje 7 Junio 2013, 09:27 am
por leosansan
Forma triangulo de pascal
Programación C/C++
shulpeca 0 1,836 Último mensaje 1 Diciembre 2017, 22:47 pm
por shulpeca
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines