C++ Pascal的三角形

Question

我正在寻找关于pascal三角形的递归版本如何工作的解释

以下是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));
    }
}

我得到了算法的工作原理我想知道递归是如何工作的.

Answer 1

您的算法包含一些基本案例的不必要谓词.可以更简单地说明如下:

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

这当然假设您保证传递给函数的参数是非负整数; 如果你不能从函数之外强加这样的保证,你总是可以包含一个断言.

Answer 2

帕斯卡的三角形基本上是它上面两个值的总和....

           1
         1   1
       1   2   1
     1   3   3   1

等等

• 在这里,1是通过在空白空间(0)上面添加1来获得的
• 对于代码,所有1都在第一列(0)或(col ==行)中占用

对于这两种边界条件,我们在特殊情况下进行编码(用于初始化).代码的主要部分(递归部分)是实际的逻辑.

(条件'row == 1'不是必需的)

Answer 3

最优化的方式是这个：

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

与 Fox 的算法不同，它可以防止对值的递归调用，这些值可以很容易地从输入值中计算出来。

Answer 4

帕斯卡三角形可以通过将当前项之上的两项相加得到。

  | 0 1 2 3 列
--+--------------------------------------------------------
0 | 1（案例1）
1 | 1（情况 2） 1（情况 2）
2 | 1（情况 3） 2（总和） 1（情况 4）
3 | 1（情况 3） 3（总和） 3（总和） 1（情况 4）

排

等等，例如第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);