Binomio de Newton, y triángulo de Pascal

[ivancea96]

No es recursividad. Guardo datos en una variable, y accedo a ellos. No llamo a la función.

[Yoel Alejandro]

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 a₀, a₁, a₂, ... donde

a₀ = 0, a₁ = 1

y an = a_n-1 + a_n-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í  

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


#include <stdio.h>
#include <stdlib.h>

long long * factorial( int );
int * FilaTrianguloPascal( int );

int main() {

  int *fila;
  int i, n;

  n = 10;
  if ( ( fila = FilaTrianguloPascal( n ) ) == NULL )
     return -1;
  i = 0;
  while ( i < n + 1 )
     printf( "%d ", fila[i++] );

  return 0;
}

/* Calcula los valores de la fila n-esima del triangulo de Pascal */
int * FilaTrianguloPascal( int n ) {

  int i, * fila;
  long long * fact;

  if ( ( fila = (int *) malloc( (n + 1) *sizeof(int) ) ) == NULL )
     return NULL;
  if ( ( fact = factorial( n ) ) == NULL )
     return NULL;

  fila[0] = fila[n] = 1;
  for ( i = 1; i < n; i++ )
     /* fact[k-1] contiene k! */
     fila[i] = fact[n - 1]/ fact[i - 1] / fact[n - i - 1];

  return fila;
}

/* Devuelve en un arreglo de n+1 elementos los números desde
* 0! hasta n!.
* Si no pudo asignar memoria para el arreglo, devuelve NULL.
*/
long long * factorial( int n ) {

  int i;
  long long * vector;

  if ( ( vector = (long long *) malloc( n * sizeof(long long) ) ) == NULL )
     return NULL;

  vector[0] = 1;
  for ( i = 1; i < n; i++ )
     /* vector[i] contiene (i+1)! */
     vector[i] = (i + 1) * vector[i-1];

  return vector;
}

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


   n = 25;
   long long * v = factorial( n );
   i = -1;
   while ( ++i < n )
      printf("%02d! = % 20lld\n", i+1, v[i]);
   printf("\n");

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 eⁿ.
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? 

[ivancea96]

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 ·_·

[Yoel Alejandro]

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.

[leosansan]

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 a₀, a₁, a₂, ... donde

a₀ = 0, a₁ = 1

y an = a_n-1 + a_n-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,  a_n-1 = a₁ +(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 (cpp) [Seleccionar] Expandir


#include<iostream>
#include <iomanip>
#define m   12
using namespace std;

int factorial(int n)
{
   if(n<2)
       return 1;
   else
       return n * factorial(n-1);
}

int combinacion(int n, int r)
{
   if(r==1)
       return n;
   else
   {
       if(n==r)
           return 1;
       else
           return factorial(n) / (factorial(r) * factorial(n - r));
   }
}

int main()
{
   for(int i=0; i<m; i++)
   {
       for(int z=0; z<m-i; z++)
           cout << setw(3) << "";
      for (int j = 0; j <= i; j++)
       cout << setw(6) << combinacion(i,j);

       cout << endl;
   }
   return 0;
}

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

[ivancea96]

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

[amchacon]

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

[Gh057]

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

[eferion]

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

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

[ivancea96]

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.