Треугольник C ++ Паскаля

Ваш алгоритм содержит пару ненужных предикатов для базовых случаев. Проще говоря:

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

Это, конечно, предполагает, что вы гарантируете, что аргументы, переданные функции, являются неотрицательными целыми числами; вы всегда можете включить утверждение, если не можете наложить такую ​​гарантию извне функции.

Треугольник Паскаля - это, по сути, сумма двух значений непосредственно над ним ...

           1
         1   1
       1   2   1
     1   3   3   1

и т.д

• В этом случае единицы получаются путем добавления 1 над ним с пробелом (0).
• Для кода все единицы заняты либо в первом столбце (0), либо когда (col == row)

Для этих двух граничных условий мы кодируем специальные случаи (для инициализации). Основная часть кода (рекурсивная часть) - это собственно логика.

(Условие 'row == 1' необязательно)

Самый оптимизированный способ - это:

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);
}

В отличие от алгоритма Фокса, он предотвращает рекурсивные вызовы значений, которые можно легко вычислить прямо из входных значений.

Обратитесь к странице с исходным кодом:

#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;
  }

Результатом будет,

Программа "Треугольник Паскаля"

Введите количество рядов: 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

Треугольник Паскаля можно получить, добавив две записи над текущей.

  | 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

и т. д., например, столбец 2, строка 3 = столбец 2, строка 2 + столбец 1, строка 2, где случаи следующие:

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

Вот код @ kathir-softwareandfinance с более читаемыми и значимыми именами переменных.

#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;
}

Вот как работает рекурсия

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

Если вам нужно часто получать значение и если у вас достаточно памяти:

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

Использование тройного подхода для оптимизации; требуется только 1 команда возврата.

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

см. объяснение