Triángulo de C++ Pascal

recursion pascals-triangle

Question

Estoy buscando una explicación de cómo funciona la versión recursiva del triángulo de Pascal

La siguiente es la línea de retorno recursiva para el triángulo de Pascal.

int get_pascal(const int row_no,const int col_no)
{
    if (row_no == 0)
    {
        return 1;
    }
    else if (row_no == 1)
    {
        return 1;
    }
    else if (col_no == 0)
    {
        return 1;
    }
    else if (col_no == row_no)
    {
        return 1;
    }
    else
    {
        return(get_pascal(row_no-1,col_no-1)+get_pascal(row_no-1,col_no));
    }
}

Obtengo cómo funciona el algoritmo Lo que me pregunto es cómo funciona la recursión.

Answer 1

Así es como funciona la recursividad

We call v(i, j), it calls v(i - 1, j), which calls v(i - 2, j) and so on, 
until we reach the values that are already calculated (if you do caching), 
or the i and j that are on the border of our triangle.

Then it goes back up eventually to v(i - 1, j), which now calls v(i - 2, j - 1), 
which goes all the way to the bottom again, and so on.   

....................................................................
                  _ _ _ _ call v(i, j) _ _ _ _ _
                 /                              / 
                /                                /
               /                                  /   
           call v(i - 1, j)                     v(i - 1, j - 1)
         /                 /                   /               /
        /                   /                 /                 /
 call v(i - 2, j)  v(i - 2, j - 1)    v(i - 2, j - 1)    v(i - 2, j - 2)
....................................................................

Si necesita obtener el valor a menudo, y si tiene suficiente memoria:

class PascalTriangle
  # unlimited size cache

  public 

  def initialize
    @triangle = Array.new  
  end

  def value(i, j)
    triangle_at(i, j)
  end

  private

  def triangle_at(i, j)
    if i < j
      return nil 
    end

    if @triangle[i].nil?        
      @triangle[i] = Array.new(i + 1)
    else
      return @triangle[i][j]
    end

    if (i == 0 || j == 0 || i == j)
      @triangle[i][j] = 1
      return @triangle[i][j]
    end

    @triangle[i][j] = triangle_at(i - 1, j) + triangle_at(i - 1, j - 1)
  end
end

Answer 2

El triángulo de Pascal es esencialmente la suma de los dos valores inmediatamente superiores ...

           1
         1   1
       1   2   1
     1   3   3   1

etc

• En esto, los 1 se obtienen al sumar el 1 sobre el espacio en blanco (0)
• Para el código, todos los 1 están ocupados en la primera columna (0) o cuando (col == fila)

Para estas dos condiciones de borde, codificamos en casos especiales (para inicialización). El fragmento principal del código (la parte recursiva) es la lógica real.

(La condición ''fila == 1'' no es necesaria)

Answer 3

El triángulo de Pascal puede obtenerse agregando las dos entradas arriba del actual.

| 0 1 2 3 column --+---------------------------------------------- 0 | 1 (case 1) 1 | 1 (case 2) 1 (case 2) 2 | 1 (case 3) 2 (sum) 1 (case 4) 3 | 1 (case 3) 3 (sum) 3 (sum) 1 (case 4) row

etc., por ejemplo columna 2, fila 3 = columna 2, fila 2 + columna 1, fila 2, donde los casos son los siguientes:

if (row_no == 0) // case 1
{
    return 1;
}
else if (row_no == 1) // case 2
{
    return 1;
}
else if (col_no == 0) // case 3
{
    return 1;
}
else if (col_no == row_no) // case 4
{
    return 1;
}
else // return the sum
    return pascalRecursive(height-1,width)+pascalRecursive(height-1,width-1);

Answer 4

Consulte la página para el código fuente:

#include <stdio.h>
int main()
{
  int n, x, y, c, q;
  printf("Pascal Triangle Program/n");
  printf("Enter the number of rows: ");
  scanf("%d",&n);

  for (y = 0; y < n; y++)
  {
        c = 1;
        for(q = 0; q < n - y; q++)
        {
              printf("%3s", " ");
        }
        for (x = 0; x <= y; x++)
        {
              printf("   %3d ",c);
              c = c * (y - x) / (x + 1);
        }
        printf("/n");
  }
  printf("/n");
  return 0;
  }

La salida sería,

Programa del triángulo de Pascal

Ingrese el número de filas: 11

                                  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

Answer 5

Su algoritmo contiene un par de predicados innecesarios para los casos base. Puede decirse más simplemente de la siguiente manera:

int pascal(int row, int col) {
  if (col == 0 || col == row) {
    return 1;
  } else {
    return pascal(row - 1, col - 1) + pascal(row - 1, col);
  }
}

Por supuesto, esto supone que está garantizando que los argumentos pasados ​​a la función son enteros no negativos; siempre puede incluir una afirmación si no puede imponer dicha garantía desde fuera de la función.

Answer 6

La forma más optimizada es esta:

int pascal(int row, int col) {
  if (col == 0 || col == row) return 1;
  else if(col == 1 || (col + 1) == row) return row;
  else return pascal(row - 1, col - 1) + pascal(row - 1, col);
}

A diferencia del algoritmo de Fox, previene las llamadas recursivas de valores que se pueden calcular fácilmente desde los valores de entrada.

Answer 7

Usando el enfoque ternario para la optimización; solo se necesita 1 comando de retorno.

int f(int i, int j) {
    return (
       (i <= 1 || !j || j == i) ? 1 :
       (f(i - 1, j - 1) + f(i - 1, j))
    );
}

ver explicación

Answer 8

Aquí está el código de @ kathir-softwareandfinance con nombres de variables más legibles y con más significado

#include <stdio.h>

int main()
{
  int nOfRows, cols, rows, value, nOfSpace;
  printf("Pascal Triangle Program/n");
  printf("Enter the number of rows: ");
  scanf("%d",&nOfRows);

  for (rows = 0; rows < nOfRows; rows++)
  {
    value = 1;
    for(nOfSpace = 0; nOfSpace < nOfRows - rows; nOfSpace++)
    {
        printf("%3s", " ");
    }

    for (cols = 0; cols <= rows; cols++)
    {
        printf("  %3d ",value);
        value = value * (rows - cols) / (cols + 1);
    }
    printf("/n");
  }
  printf("/n");

  return 0;
}