パスカルの三角形の再帰バージョンがどのように機能するかについての説明を探しています
以下は、パスカルの三角形の再帰的な戻り行です。
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);
}
}
もちろん、これは、関数に渡される引数が負でない整数であることを保証していることを前提としています。関数の外部からそのような保証を課すことができない場合は、いつでもアサーションを含めることができます。
パスカルの三角形は、本質的にそのすぐ上にある 2 つの値の和です。.
1
1 1
1 2 1
1 3 3 1
等
これら 2 つの境界条件については、特殊なケース (初期化用) でコーディングします。コードの主要部分 (再帰部分) は実際のロジックです。
(条件「row == 1」は必要ありません)
ソースコードについては、次のページを参照してください。
#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
パスカルの三角形は、現在のエントリの上に 2 つのエントリを追加することで取得できます。
| | 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);
これは、より読みやすく、より意味のある変数名を使用した@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
最適化のための三元アプローチの使用; 必要な return コマンドは 1 つだけです。
int f(int i, int j) {
return (
(i <= 1 || !j || j == i) ? 1 :
(f(i - 1, j - 1) + f(i - 1, j))
);
}
説明を見る