私はここでこれを見つけました:対角線ストリップの長方形行列のトラバース
#include <stdio.h>
int main()
{
int x[3][4] = { 1, 2, 3, 4,
5, 6, 7, 8,
9, 10, 11, 12};
int m = 3;
int n = 4;
for (int slice = 0; slice < m + n - 1; ++slice) {
printf("Slice %d: ", slice);
int z1 = slice < n ? 0 : slice - n + 1;
int z2 = slice < m ? 0 : slice - m + 1;
for (int j = slice - z2; j >= z1; --j) {
printf("%d ", x[j][slice - j]);
}
printf("\n");
}
return 0;
}
出力：
Slice 0: 1
Slice 1: 5 2
Slice 2: 9 6 3
Slice 3: 10 7 4
Slice 4: 11 8
Slice 5: 12
基本的に各スライスの長さに関する情報を保持する 2 つの追加変数 (z1 と z2) 用のメモリしか必要ないため、これは非常に洗練された方法であることがわかりました。外側のループはスライス番号 ( slice) を移動し、内側のループは index: の各スライスを移動しますslice - z1 - z2。次に必要なその他すべての情報は、アルゴリズムがどこで開始され、マトリックス内をどのように移動するかです。前の例では、最初にマトリックスを下に移動し、一番下に到達した後、右に移動します: (0,0) -> (1,0) -> (2,0) -> (2,1) - > (2,2) -> (2,3)。ここでも、このパターンは変数 z1 と z2 によってキャプチャされます。slice行は、一番下に達するまで数値とともに増加し、その後z2、行インデックスをその位置で一定に保つために使用できる増加を開始します。slice - z2. 各スライスの長さは次のように計算されslice - z1 - z2ます: (slice - z2) - (slice - z1 -z2)(アルゴリズムが m--, n++ の昇順で移動するためマイナス)z1は、内側のループの停止基準です。列インデックスのみが残ります。これは、j が底に達した後は一定であるという事実から便利に継承され、その後、列インデックスは増加し始めます。
前のアルゴリズムは、左上 (0,0) から開始して、左から右へ昇順でのみ移動します。このアルゴリズムが必要になったとき、左下 (m,n) から降順でマトリックスを検索する必要もありました。私はアルゴリズムに非常に夢中になったので、一番下に到達して適応させることにしました。
- スライスの長さは、次の式でわかります。
slice -z1 - z2
- スライスの開始位置: (2,0) -> (1,0) -> (0,0) -> (0,1) -> (0,2) -> (0,3)
- 各スライスの動きは m++ と n++ です
私はそれを次のように描写することが非常に有用であることを発見しました:
- スライス=0 z1=0 z2=0 (2,0) (列インデックス= 行インデックス - 2)
- スライス=1 z1=0 z2=0 (1,0) (2,1) (列インデックス= 行インデックス - 1)
- スライス=2 z1=0 z2=0 (0,0) (1,1) (2,2) (列インデックス= 行インデックス + 0)
- スライス=3 z1=0 z2=1 (0,1) (1,2) (2,3) (列インデックス= 行インデックス + 1)
- スライス=4 z1=1 z2=2 (0,2) (1,3) (列インデックス= 行インデックス + 2)
- スライス=5 z1=2 z2=3 (0,3) (列インデックス= 行インデックス + 3)
以下を導出します: j = (m-1) - slice + z2(j++ を使用) スライス長の式を使用して停止基準を作成します:((m-1) - slice + z2)+(slice -z2 - z1)結果(m-1) - z1
は次のようになります。for (int j = (m-1) - slice + z2; j < (m-1) - z1; j++)
行のインデックスは j でわかります。列のインデックスは、j が定数になり始めたときにのみインクリメントを開始することがわかっています。したがって、式に j を再び含めることは悪い考えではありません。上記の合計の違いから、違いが常に に等しいことに気付き、j - (slice - m +1)他のいくつかのケースでこれをテストすると、これがすべてのケースに当てはまると確信していました（私は数学者ではありません; P）したがって、下降運動のアルゴリズム左下から次のようになります。
#include <stdio.h>
int main()
{
int x[3][4] = { 1, 2, 3, 4,
5, 6, 7, 8,
9, 10, 11, 12};
int m = 3;
int n = 4;
for (int slice = 0; slice < m + n - 1; ++slice) {
printf("Slice %d: ", slice);
int z1 = slice < n ? 0 : slice - n + 1;
int z2 = slice < m ? 0 : slice - m + 1;
for (int j = (m-1) - slice + z2; j <= (m-1) - z1; j++) {
printf("%d ", x[j][j+(slice-m+1)]);
}
printf("\n");
}
return 0;
}
残りの 2 つの方向性はあなたに任せます ^^ (これは順序が実際に重要な場合にのみ重要です)。
このアルゴリズムは非常に頭を悩ませるものであり、その仕組みを知っていると思っていても、お尻を噛まれる可能性があります。しかし、あなたが期待するように文字通りマトリックスを移動するので、それは非常に美しいと思います. たとえば名前など、アルゴリズムについて誰かがもっと知っているかどうかに興味があるので、ここで行ったことが実際に意味があるかどうか、さらに良い解決策があるかどうかを調べることができます。