Binomio de Newton, y triángulo de Pascal

[Gh057]

ahora bien, dicho concepto entonces me trastoca los libros... si una recurrencia se toma como una recursividad, la función factorial realizada por sumatoria (entiéndase por iteraciones) no representaría en sí una recursividad también?

dicho de otro modo cualquier sumatoria n, n+1,n+2... nn sería recursivo; implica acceder al valor anterior de n para continuar la serie...

[eferion]

ahora bien, dicho concepto entonces me trastoca los libros... si una recurrencia se toma como una recursividad, la función factorial realizada por sumatoria (entiéndase por iteraciones) no representaría en sí una recursividad también?

dicho de otro modo cualquier sumatoria n, n+1,n+2... nn sería recursivo; implica acceder al valor anterior de n para continuar la serie...

Esto más o menos viene a resumir lo que he expuesto.

[ivancea96]

Dicho esto, supongo que amchacon se refería a hacerlo por cualquier método menos por el método de sumar.



Tenía pendiente hacer esto. Aquí está:

Código (cpp) [Seleccionar] Expandir

#include <iostream>
#include <vector>

using namespace std;

class factorial{
    vector<uint32_t> mul, div;
    bool divided;

    public: static void f(vector<uint32_t> &v, uint32_t n){
        for(uint32_t i=2; i<(n/2)+1;)
            if(n%i==0){
                v.push_back(i);
                n/=i;
            }else ++i;
            v.push_back(n);
    }
public:
    factorial():divided(false){mul.clear(); div.clear();}

    int getMulCount()const{return mul.size();}
    uint32_t getMul(int n)const{if(n>=0 && n<mul.size()) return mul[n]; else return 0;}
    vector<uint32_t> getMul()const{return mul;}
    void addMul(uint32_t m){mul.push_back(m);divided=false;}
    void addMulFactorial(uint32_t f){if(f)for(int i=1; i<=f; i++) mul.push_back(i);divided=false;}

    int getDivCount()const{return div.size();}
    uint32_t getDiv(int n)const{if(n>=0 && n<div.size()) return div[n]; else return 0;}
    vector<uint32_t> getDiv()const{return div;}
    void addDiv(uint32_t d){div.push_back(d);divided=false;}
    void addDivFactorial(uint32_t f){if(f)for(int i=1; i<=f; i++) div.push_back(i);divided=false;}

    void fact(){factMul();factDiv();}
    void factMul(){
        vector<uint32_t> temp(mul);
        mul.clear();
        for(int i=0; i<temp.size(); i++)
            f(mul, temp[i]);
        for(int i=0; i<mul.size();)
            if(mul[i]==1)
                mul.erase(mul.begin()+i);
            else ++i;
    }
    void factDiv(){
        vector<uint32_t> temp(div);
        div.clear();
        for(int i=0; i<temp.size(); i++)
            f(div, temp[i]);
        for(int i=0; i<div.size();)
            if(div[i]==1)
                div.erase(div.begin()+i);
            else ++i;
    }
    void divide(){
        fact();
        for(int i=0; i<mul.size(); i++)
            for(int j=0; j<div.size(); j++)
                if(mul[i]==div[j]){
                    mul.erase(mul.begin()+i);
                    div.erase(div.begin()+j);
                    --i; --j;
                    break;
                }
        divided=true;
    }
    uint64_t get(){
        uint64_t t=1;
        if(!divided) divide();
        for(int i=0; i<mul.size(); i++)
            t*=mul[i];
        for(int i=0; i<div.size(); i++)
            t/=div[i];
        return t;
    }
    void clear(){mul.clear(); div.clear();divided=false;}
};

void FilaTrianguloPascal(uint64_t *&arr, uint32_t n){
    factorial f;
    arr = new uint64_t[n+1];
    for(int i=0; i<=n; i++){
        f.addMulFactorial(n);
        f.addDivFactorial(i);
        f.addDivFactorial(n-i);
        f.divide();
        arr[i] = f.get();
        f.clear();
    }
}

int main(){
    uint64_t *v;
    for(int i=0; i<10; i++){
        FilaTrianguloPascal(v, i);
        for(int j=0; j<=i; j++)
            cout << v[j] << " ";
        if(i) delete[] v;
        else delete v;
        cout << endl;
    }
}

[leosansan]

....xD PEDAZO DE CÓDIGOS.....

...............para este viaje no hacen falta tantas alforjas...............

Amigo ivancea96 para obtener esta salida:

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
1  11  55 165 330 462 462 330 165  55  11   1
1  12  66 220 495 792 924 792 495 220  66  12   1
1  13  78 286 715 1287 1716 1716 1287 715 286  78  13   1
1  14  91 364 1001 2002 3003 3432 3003 2002 1001 364  91  14   1
1  15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105  15   1
1  16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120  16   1

aunque podrías haber hecho trampas, cosa que no has hecho, usando [ center ] para que saliera el triángulo isósceles que pedimos en este reto:

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
1  11  55 165 330 462 462 330 165  55  11   1
1  12  66 220 495 792 924 792 495 220  66  12   1
1  13  78 286 715 1287 1716 1716 1287 715 286  78  13   1
1  14  91 364 1001 2002 3003 3432 3003 2002 1001 364  91  14   1
1  15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105  15   1
1  16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120  16   1

Como decía, para obtener esa salida creo que no hace falta un código tan extenso/complejo. Este que te pongo a continuación hace lo mismo que el tuyo y es considerablemente más "cortito", exactamente una décima parte:

Código (cpp) [Seleccionar] Expandir

#include <stdio.h>
int main(void){
 unsigned  int a,b,k,n,filas=16;
 for(n = 0; n <= filas; n++){
   putchar ('1');
   for(k = b = 1, a = n; b <= n; b++, a--)
     printf("%3u " ,k = k * a / b);
   putchar('\n');
 }
 return 0;
}




¡Ah!, que tenía que tener esta forma:

                   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

Conste que con las etiquetas quote sale algo deformado, pero al ejecutarlo en consola sale perfecto:

Código (cpp) [Seleccionar] Expandir

#include <stdio.h>
int main(void){
 unsigned  int i,a,b,k,n,filas=13;
 for(n = 0; n <= filas; n++){
   for (i=0;i<filas-n;i++)
     printf("   ");
     putchar ('1');
   for(k = b = 1, a = n; b <= n; b++, a--)
     printf("%5u " ,k = k * a / b);
   putchar('\n');
 }
 return 0;
}


Bueno está bien, tú usabas un array. Pues yo también:

Código (cpp) [Seleccionar] Expandir

#include <stdio.h>
#define N   16
int main(void){
 unsigned  int a,b,k,n,comb[N+1][N+1];
 for(a = 0; a <= N; a++)
   for(b = 0; b <= N; b++)
     (b==0) ? (comb[a][b]=1) :(comb[a][b]=0);
 for(n = 0; n <= N; n++)
   for(k = b = 1, a = n; b <= n; b++, a--){
     k = k * a / b;
     comb[n][b]=k ;
   }
 for(a = 0; a <= N; a++){
   for(b = 0; b <= N; b++)
     if (comb[a][b]!=0)
       printf("%3u " ,comb[a][b]);
   putchar('\n');
 }
  return 0;
}

Como ves sigue siendo "cortito".

Dándole vueltas al triángulo de Pascal y viendo que el "cálculo directo" con factoriales tiene el inconveniente de los mencionados factoriales, se observa que los números combinatorios que forman el triángulo son, por ejemplo:

(7 0)=1  

(7 0)=1  

(7 1)=7/1
 
(7 2)=7/1 *6/2 =7*6/1*2

(7 3)=/1 *6/2* 5/3 =7*6*5/1*2*3

(7 4)=7/1 *6/2* 5/3* 4/4= 7*6*5*4/1*2*3*4 =7*6*5/1*2*3 = (7 3)

(7 5)=7/1 *6/2* 5/3 *4/4* 3/5= 7*6*5*4*3/1*2*3*4*5 = 7*6/1*2= (7 2)

(7 6)=7/1 *6/2*5/3*4/4*3/5*2/6= 7*6*5*4*3*2/1*2*3*4*5*6= 7/1= (7 1)

(7 7) = 1 = (7 0)=1

es decir, 1*n/i, donde n va disminuyendo e i aumentando, de manera que se evita el cálculo de los factoriales. Además son simétricos con lo que se puede, y debe  por eficiencia, calcular la segunda mitad directamente y obtenerlos  de acuerdo a otra propiedad de los números combinatorios:

Con esta idea
salen los siguientes códigos, con array y sin él::

Código (cpp) [Seleccionar] Expandir

#include <stdio.h>
#define N   13
int main(void){
 unsigned  int i,a,b,k,n,comb[N+1][N+1];
 for(a = 0; a <= N; a++)
   for(b = 0; b <= N; b++)
     (b==0) ? (comb[a][b]=1) :(comb[a][b]=0);
 for(n = 0; n <= N; n++)
   for(k = b = 1, a = n; b <= n; b++, a--){
     if (b>N/2)
       comb[n][b]=comb[n][n-b];
      else {
       k = k * a / b;
       comb[n][b]=k ;
      }
   }
 for(a = 0; a <= N; a++){
   for(i = 0; i < N-a; i++)
     printf("  " );
   for(b = 0; b <= N; b++)
     if (comb[a][b]!=0)
       printf("%3u " ,comb[a][b]);
   putchar('\n');
 }
  return 0;
}

Código (cpp) [Seleccionar] Expandir

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

int comb(int n,int k);

int main(){
 int i,j,k;
 int n = 11;
 /*do{
   printf("\nIntroduzca la potencia a calcular (mayor que cero): \n");
   scanf("%d",&n);
   }while ( n < 0 );
   n++;*/
   char tamanyo_consola[80];
   sprintf(tamanyo_consola, "MODE %d,%d", n*6+10+1,40);
   system(tamanyo_consola);
   for (i = 0; i < n; i++){
     for ( j = 1; j <n-i; j++)
     printf ("   ")  ;
     for (k = 0; k <= i; k++)
       printf ("%6d",comb(i,k));
     printf ("\n");
   }
   return 0;
}
int comb(int n,int k){
 if (n < 0 || k < 0 || k > n)
   return 0;
 if (k>n/2)
   k=n-k;
 int c = 1;
 for ( k; k>=1; k--,n--)
   c*=n/k;
 return c;
}

Como en otros códigos anteriores hago uso del system (MODE)  para que la ventana de la consola se ajuste de forma automática al tamaño del triángulo. Y como no podía ser menos, al menos una imagen, sí ya sé que empieza a estar muy vista pero es que" me fascina la belleza de los números", con color o sin ellos:

Y sólo quedan 24 horas para obtener el triángulo a partir de un array unidimensional. ¡¡¡Vamos Ánimo!!!

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

Totalmente de acuerdo, y en Cálculo/Matemáticas tampoco se llama a eso recursividad sino recurrencia, como bien recordó amchacon,  cuando los valores de un término se obtienen a partir de otros anteriores. Otra cosa es cuando la ley o fórmula de recurrencia la apliques de forma iterada, entonces si podemos hablar, incluso matemáticamente, de recursividad. Todo es cuestión de semántica y saber emplear las palabras adecuadas.

¡¡¡¡ Saluditos! ..... !!!!

[Yoel Alejandro]

Leosansan:

1. Recuerda que el tema en realidad lo abrí yo, y puse la descripción del mismo. Ahora quieres cambiarme el problema, y encima reprochas a los demás y a mí porque el problema no se conduce como TÚ quieres. Te recomiendo dos cosas: (a) Ve al psicólogo. (b) Abre tu propio tema..

2. Recursión, recurrencia o recursividad se pueden considerar palabras de significados similares. No hay por qué hacer tanto escándalo (a no ser con el objeto de descalificar a los demás). La fuente http://es.wikipedia.org/wiki/Recursi%C3%B3n aclara:

Recurrencia, recursión o recursividad es la forma en la cual se especifica un proceso basado en su propia definición. Siendo un poco más precisos, y para evitar el aparente círculo sin fin en esta definición:
Un problema que pueda ser definido en función de su tamaño, sea este N, pueda ser dividido en instancias más pequeñas (< N) del mismo problema y se conozca la solución explícita a las instancias más simples, lo que se conoce como casos base, se puede aplicar inducción sobre las llamadas más pequeñas y suponer que estas quedan resueltas.

En otras palabras, la definición para el caso de "N" se basa en la definición para los casos desde "1" hasta "N-1", algunos de los cuales están predefinidos de cierta manera. No obstante, la misma fuente dice que el término correcto en nuestra lengua es "recurrencia".

3. El empleo de la palabra "recursión" viene de boca de amchacón quién dijo: "Que no use recursividad, debe sacar la fila del tirón." Analizando el contexto de sus palabras, más allá de lo linguístico, cualquiera con buena intención puede inferir lo que quiso decir: Que los números de una fila del triángulo no se calculen usando los números de filas anteriores. Lo que traté fue dar respuesta a ese planteamiento, mismo que también fue comprendido por ivance96.

4. Este no es un foro de matemáticas (que quede claro), pero ya mencionas tanto ese tema te pongo de ejercicio investigar las siguientes demostraciones:
(a) El elemento unidad en R es único.
(b) La propiedad anterior es válida para toda ley de composición interna que sea conmutativa.
(c) El límite de una función real de variable real, si existe, es único.
Por lo menos te puedo decir que yo las conozco y te las puedo dar sin siquiera mirar el libro (sin ánimo de ofender, pues es mi profesión y se supone que lo haga, tal como un cirujano debe ser capaz de operar, un aviador de volar, etc., sin ver el manual). ¿Tú puedes responder las mismas preguntas? Si lo haces eres un verdadero matemático, capaz de citar y comprender definiciones, y realizar demostraciones. De otro modo, por favor DEJA la diatriba y comentarios del tipo:

¡¡¡PERO POR DIOS!!! , en que lugar estas dejando las Matemáticas.

dirigidos hacia mí. Sino deberé presentar una queja a los moderadores del foro.

[Gh057]

buenos días, si me permiten solo voy a hacer tan solo una crítica constructiva de este subforo, al cual realmente me apasiona pero sin embargo personalmente me ha desanimado de hacer algún humilde aporte o contestar algún post (no preguntas ya que no hago, de hecho todavía no he hecho en ningún foro por más que hace un tiempo que lo frecuento, un poco porque me gusta buscar la respuesta por mí mismo o simplemente por tímido) por un tiempo largo; pareciera que a veces se deja de lado el nivel de código (que es realmente exquisito en algunos usuarios) y se empieza a medir el nivel de testosterona...

relax! and don't do it... jejej disfruten de este espacio, e intenten contagiar esa pasión a los demás, como la que yo siento cada vez que veo un muy buen post.
un cordial saludo para todos!

[Yoel Alejandro]

Gh057, tienes razón y me disculpo, .... pero a veces se desborda la adrenalina. Ahora, dejando las emociones negativas a un lado y concentrándome en lo positivo   voy a retomar el asunto, para que así no se pierdan la pasión y la sutileza porque aquí hay muchas cosas valiosas que no merecen perderse por una tontería.

Amchacón planteó que el código puede optimizarse para que no ocurra el desbordamiento. La enigmática palabra "optimizar" estuvo dando vueltas en mi cabeza desde que fue pronunciada, jajaja. Porque la verdad es que yo estaba enfocando este programa de una manera simplista y a lo "bestia".

Veamos, la fórmula del combinatorio <n,i> es:

   n!
----------
i! (n-i)!

Dicha fórmula es algebraicamente concisa, pero numéricamente ineficiente. Analizando en sus entresijos la podemos llevar a:

n * (n - 1) * (n - 2) * ... * (n - i + 1) * (n - i) * (n - i - 1) * ... * 1
------------------------------------------------------------------------------
           [1 * 2 * ... * i ] [(n - i) * (n - i - 1) * ... * 1]

y vemos como términos de n! se cancelan con términos de (n-i)!, quedando:

n * (n - 1) * (n - 2) * ... * (n - i + 1)
----------------------------------------------
              1 * 2 * ... * i

y es lo que queremos.

Uno puede pensar en un "for" doble para evaluar productos, algo como:

Código (cpp) [Seleccionar] Expandir


for ( i = 1; i < n; i++ ) {
    A = B = 1;
   for ( j = i; j <= i; j++ ) {
        A *= n - j + 1;
        B *= j;
    }
    comb[i] = A / B;

... pero repasemos aún más la situación. Escribiendo cómo va quedando el numerador para i = 1, i = 2, i = 3, ..., vemos cómo podemos reutilizar los resultados de un valor de "i" para el otro:

i=1: n
i=2: n * (n - 1)
i=3: n * (n - 1) * (n - 2)

así que podemos empezar con A = 1, y luego con cada "i" hacemos A *= (n - i + 1). Y de manera similar con el denominador. Nos ahorramos un "for". Además, aprovechamos el hecho de que la mitad izquierda de la fila es simétrica con la derecha. Nos queda un código tan simple como

Código (cpp) [Seleccionar] Expandir


long long * FilaTrianguloPascal( int n ) {

  int i, j;
  long long A, B, * fila;

  if ( ( fila = (long long *) malloc( (n + 1) *sizeof(long long) ) ) == NULL )
     return NULL;

  fila[0] = fila[n] = 1;

  A = 1; /* numerador */
  B = 1; /* denominador */
  for ( i = 1; i < n; i++ ) {
     /* mitad izquierda de la fila */
     if ( i <= n / 2 ) {
        A *= n - i + 1;
        B *= i;
        fila[i] = A / B;
     }
     /* mitad derecha */
     else
        fila[i] = fila[n - i];
  }

  return fila;
}
que probé y produce los resultados correctos, por ejemplo para n=18:

1 18 153 816 3060 8568 18564 31824 43758 48620 43758 31824 18564 8568 3060 816 153 18 1

¿Más o menos así era como se quería?