C++ 帕斯卡三角形
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1763954/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
C++ Pascal's triangle
提问by starcorn
I'm looking for an explanation for how the recursive version of pascal's triangle works
我正在寻找有关帕斯卡三角形的递归版本如何工作的解释
The following is the recursive return line for pascal's triangle.
以下是帕斯卡三角形的递归返回线。
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));
}
}
I get how the algorithm works What I wonder is how the recursion does the work.
我知道算法是如何工作的 我想知道递归是如何工作的。
回答by pmcs
Your algorithm contains a couple of unnecessary predicates for the base cases. It can be stated more simply as follows:
您的算法包含一些针对基本情况的不必要的谓词。可以更简单地表述如下：
int pascal(int row, int col) {
if (col == 0 || col == row) {
return 1;
} else {
return pascal(row - 1, col - 1) + pascal(row - 1, col);
}
}
This of course assumes that you're guaranteeing that the arguments passed to the function are non-negative integers; you can always include an assertion if you can't impose such a guarantee from outside the function.
这当然假设您保证传递给函数的参数是非负整数；如果您不能从函数外部强加这样的保证，您总是可以包含一个断言。
回答by Fox
Pascal's triangle is essentially the sum of the two values immediately above it....
帕斯卡三角形本质上是它上面两个值的总和......
1
1 1
1 2 1
1 3 3 1
etc
等等
- In this, the 1's are obtained by adding the 1 above it with the blank space (0)
- For code, all the 1's are occupied in either the first column (0), or when the (col == row)
- 在这种情况下，1 是通过将 1 与空格 (0) 相加而获得的
- 对于代码，所有 1 都被占用在第一列 (0) 中，或者当 (col == row)
For these two border conditions, we code in special cases (for initialization). The main chunk of the code (the recursive part) is the actual logic.
对于这两个边界条件，我们在特殊情况下（用于初始化）进行编码。代码的主要部分（递归部分）是实际的逻辑。
(The condition 'row == 1' is not necessary)
（条件 'row == 1' 不是必需的）
回答by Jacobian
The most optimized way is this one:
最优化的方式是这个：
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);
}
Unlike Fox's algorithm it prevents recursive calls for values which can be easily computed right from the input values.
与 Fox 的算法不同，它可以防止对值的递归调用，这些值可以很容易地从输入值中计算出来。
回答by Kathir Softwareandfinance
Refer to the page for the source code:
源码见页面：
#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;
}
The output would be,
输出将是，
Pascal Triangle Program
帕斯卡三角计划
Enter the number of rows: 11
输入行数：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
回答by Abdulrhman.Z
Here is the code of @kathir-softwareandfinancewith more readable and more meaning variable names
这是@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;
}
回答by Abdulrhman.Z
Pascal's triangle can be got from adding the two entries above the current one.
帕斯卡三角形可以通过在当前条目之上添加两个条目来获得。
| 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., for example column 2, row 3 = column 2, row 2 + column 1, row 2, where the cases are as follows:
等等，例如第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);
回答by glebm
Here is how the recursion works
这是递归的工作原理
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)
....................................................................
If you need to get the value often, and if you have enough memory:
如果您需要经常获取该值，并且您有足够的内存：
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
回答by Jim22150
Using ternary approach for optimization; only 1 return command needed.
使用三元方法进行优化；只需要 1 个返回命令。
int f(int i, int j) {
return (
(i <= 1 || !j || j == i) ? 1 :
(f(i - 1, j - 1) + f(i - 1, j))
);
}
see explanation
看说明
