1. 概要

このチュートリアルでは、正方形のスパイラルで行列の要素をトラバースするためのアルゴリズムを学習します。

2. スパイラルとは何ですか？

スパイラルは、中心と呼ばれる点から始まり、その周りを曲がるにつれて徐々に遠くなる曲線です。 極平面では、スパイラルは、角度を半径に関連付ける連続単調関数の形式を持ちます。 これは、最も一般的なスパイラルの1つ、アルキメデスのスパイラルのグラフです。

任意の形状の表面に広がる計算スパイラルの一般化されたアルゴリズムも存在します。 ただし、行列のループの場合、わずかに異なる定義が必要です。

3. スパイラルとマトリックス

行列に関連して、その要素をループするスパイラルはスクエアスパイラルと呼ばれます。 正方形のスパイラルは次のような形をしています。

連続関数として定義することはできないため、代わりに手続き的に定義することができます。 行列をその要素の1つからスパイラル状にトラバースすることを想像すると、それがどのように機能するかを理解するのは直感的です。 このサンプルマトリックスを使用してみましょう。

正方形のスパイラルを生成するために、要素が1から開始してトラバースする必要がある順序を数字で示すことができます。 スパイラルでマトリックスをトラバースすることは、1つのコーナーから開始し、すべての要素をループして、中央で終了することにより、マトリックスをベクトル化することに対応します。

または、代わりに、中央から開始して、コーナーの1つで終了することによって：

トラバーサルは、一方向にステップごとに移動し、次に回転し、さらにステップを移動し、次に回転し、次にカウンターをインクリメントして繰り返すことによって発生します。 また、中心からコーナーへのトラバーサルがトラバーサルの単純な反転であり、これが時計回りと反時計回りの両方のスパイラルに有効であることに注意してください。

4. 非正方行列

行列が非正方形で、のような行と列がある場合は、いくつかの追加の手順が必要になります。 最初にそれをサイズの正方行列に拡張し、次に正方形に存在するが長方形の行列には存在しないすべての要素をスキップします。

次に、このトラバーサルを実行するアルゴリズムを調べます。 その前の最後の注意：行と列を座標系として使用する代わりに、原点をマトリックスの中心にシフトする方が実用的です。 これは、とが奇数の場合、原点を次のように配置することを意味します。

4. センターからコーナーへのトラバース

これで、行列を原点からコーナーまで、正方形のスパイラルでトラバースするアルゴリズムを研究できます。 1つを作成するには、中心を基準にした現在の要素の座標を格納する2つのポインターと、2つの方向ベクトルを定義する必要があります。 アルゴリズムは次のとおりです。

上記の例のように、3 x 5の行列で実行すると、アルゴリズムは予想される順序でトラバーサルを生成します。

2番目のifステートメントをわずかに変更するだけで、反時計回りの回転を定義することもできます。

そして予想通り、これは3×7の行列の出力です。

5. コーナーからセンターへのトラバース

代わりに、マトリックスをコーナーから中央にトラバースしたい場合は、上記で行った考慮事項を参照できます。 私たちがする必要があるのは、トラバースの順序をリストに保存してから、それを逆にすることだけです。

たとえば、これは5×7マトリックスの逆スパイラルトラバーサルです。

6. 結論

この記事では、正方形のスパイラルパターンで行列の要素をループする方法を学びました。