我正在寻找一个解释帕斯卡三角递归版本如何工作的答案。
以下是帕斯卡三角递归返回行。
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));
}
}
我理解算法的工作原理，但我想知道递归是如何工作的。
您的算法在基本情况下包含了一些不必要的谓词。可以更简单地表述如下：
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
等等，我正在将您的文本翻译成中文。
对于这两种边界条件，我们会在特殊情况下进行编码（初始化）。代码的主要部分（递归部分）是实际的逻辑。
（条件“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
c = c * (y - x) / (x + 1); 这行代码是一个简单的数学表达式，它将变量 c 乘以 (y - x) 的差值，然后除以 (x + 1)。这个表达式可以用于计算某些算法或公式中的值。 - Muhammad Umer从当前位置的上方两个条目相加可以得到帕斯卡三角形。
| 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);
#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
使用三元运算法来进行优化；只需要一个 return 命令。
int f(int i, int j) {
return (
(i <= 1 || !j || j == i) ? 1 :
(f(i - 1, j - 1) + f(i - 1, j))
);
}
查看解释