Autor
|
Tema: Binomio de Newton, y triángulo de Pascal (Leído 40,920 veces)
|
ivancea96
Desconectado
Mensajes: 3.412
ASMático
|
No es recursividad. Guardo datos en una variable, y accedo a ellos. No llamo a la función.
|
|
|
En línea
|
|
|
|
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 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í 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: #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: 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 n. 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?
|
|
« Ú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
Mensajes: 3.412
ASMático
|
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
|
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
Mensajes: 1.314
|
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:
#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".
|
|
« Última modificación: 20 Marzo 2014, 17:45 pm por leosansan »
|
En línea
|
|
|
|
ivancea96
Desconectado
Mensajes: 3.412
ASMático
|
El reto era devolver la línea, no el triángulo.
|
|
|
En línea
|
|
|
|
amchacon
Desconectado
Mensajes: 1.211
|
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
|
|
|
|
Gh057
Desconectado
Mensajes: 1.190
|
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
Mensajes: 1.248
|
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 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
Mensajes: 3.412
ASMático
|
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
|
|
|
|
|
Mensajes similares |
|
Asunto |
Iniciado por |
Respuestas |
Vistas |
Último mensaje |
|
|
Calculador de Binomio de Newton [Python]
Scripting
|
CaronteGold
|
9
|
20,957
|
17 Febrero 2022, 20:46 pm
por werty2310
|
|
|
* [Source] Triangulo Pascal
« 1 2 »
Programación Visual Basic
|
BlackZeroX
|
13
|
12,800
|
6 Enero 2010, 03:02 am
por BlackZeroX
|
|
|
[SRC] Triangulo Pascal [by *PsYkE1*]
Programación Visual Basic
|
Psyke1
|
3
|
2,982
|
27 Mayo 2010, 09:14 am
por Psyke1
|
|
|
[C] Imprimir Triangulo de Pascal
Programación C/C++
|
edr89
|
3
|
16,496
|
7 Junio 2013, 09:27 am
por leosansan
|
|
|
Forma triangulo de pascal
Programación C/C++
|
shulpeca
|
0
|
1,808
|
1 Diciembre 2017, 22:47 pm
por shulpeca
|
|