🚱 👩‍❤️‍💋‍👨 🙃 「らせん状マトリックス」を充填する別の方法 🤴🏾 👩🏼‍⚖️ 😟

2000 年代半ばに学生としてアルゴリズム化とプログラミングの基礎を研究している過程で、「らせん状の」行列を埋めるというかなり有名なタスクに出会いました。ポイントは、[1, 1] の位置から時計回りに移動して、指定された値の正方行列に昇順の数値を入力することです。解決するのに2時間ほどかかりました。

充填アルゴリズム自体は取るに足らないもので、ループは合計で N ²回の反復で構成され、配列のすべての要素を必要な順序で通過することを想定しています。マトリックス。ルートは要素 [1, 1] から始まり、次に右上の要素 [1, N] に水平に移動し、次に右下隅 [N, N] に下がり、次に左下隅 [N, 1] に移動します。開始点 [2, 1] の 1 列下で最初の円を終了します。その後、同じ円の動きが次の内側の円で行われ、行列の中心まで繰り返されました。

この分野に特化したさまざまなフォーラム、コミュニティ、サイトに代表されるインターネットには、人類が半世紀以上にわたって発明してきたさまざまなプログラミング言語の特定のソリューションが豊富にあります。同時に、上記のマトリックスを埋めるためのメカニズムは、人の観点からもコンピューターの観点からも（視点がある場合）、主で最も効果的です。

問題をうまく解決してからしばらくして、自分の能力を再評価した結果、私は疑問に思いました: マトリックスのサイズとセルの座標に基づいて、その計算を可能にする普遍的な数式を開発することは可能ですか?問題の条件に応じた値 - つまり、最終的に配列を埋め、カウンターを使用せずに 1 から N までの 2 つのネストされたループを使用して要素を「従来の」方法で繰り返します。

, , , , .

18 , «», «» (https://habr.com/ru/post/261773), - , .

, , .

( , , , , ).

, : [i, j] , . - .

: ( ) , ..

: . , .

, , , , .

1) «» «», .

2) , , , . .

3) .

: N – ().

1 . . , [1, 1] [1, N], [N, N]. , .. [2, 1].

, C++, ( , ). , , .

, 5x5 ( “a”), 1 N. .

#include <iostream>
using namespace std;
int main()
{
    int N = 5;          //   
    int a[N][N];        //   
    for (int ik = 0; ik < N; ik++)
        for (int jk = 0; jk < N; jk++)
            a[ik][jk] = 0;          //    
                                      
    for (int ik = 0; ik < N; ik++){     //  " "
        for (int jk = 0; jk < N; jk++){
            if (!(ik == 0 || ik == N - 1 || jk == 0 || jk == N - 1)) 
                continue;      //       ""
            int i = ik + 1;     //       
            int j = jk + 1;     //     ( 1  N)  
            	//  ...      
        }   
    }     

   for (int ik = 0; ik < N; ik++){          // " "
        for (int jk = 0; jk < N; jk++){
           printf( "%02d ", a[ik][jk]);	//    
        }
        cout << endl;
    }  
    return 0;
}

, , , (i + j) 1 . 2, E_1,2 = 3 .. (i + j) . Xs = i + j - 1, . :

…
int Xs = (i + j – 1);
a[ik][jk] = Xs;
…

. , .

a[ik][jk] = Xs

, [5, 5] , 1.

, (i = 5, j = 4) 10. , ( N * 4 - 4 = 16 2) Xs.

a_1,2 = 4N – 4 + 2 – Xs = 4N – Xs - 2.

…
int Xs = i + j - 1;     
a[ik][jk] = 4 * N - Xs - 2;
…

, – .

, .

1. a_i,j = Xs = i + j - 1; [1, 1] [N, N].

2. a_i,j = 4*N – 2 - X; [N, N] [2, 1].

, . , - , , (y = |x|) .

, :

F₁ 1 i, j [1, 1] … [N, N] , – 0. , F₂ , , 1 [N, N - 1] … [2, 1], 0 [1, 1] … [N, N].

switcher, i j, , .

-1, 0 / 1 . F₁ F₂ .

, i j, . ?

a[ik][jk].

…
int Xs = i + j - 1;     
a[ik][jk] = j – i;
…

, 0, [1][1] [N][N] 0. N N. switcher.

…
int switcher =  (j - i + N) / N;
a[ik][jk] =  switcher; //     switcher
…

, F₁ F_2. F₁ , , .. F₁ (switcher) = switcher. F₁ (switcher) * Xs [1, 1] [N, N], . , . switcher – 1, .. F_2.(switcher) = |switcher – 1|.

, :

…
a[ik][jk] =  switcher * Xs + abs(switcher - 1) * (4 * N - 2 - Xs);
…

, , .

2 . .

. , , , ? if (!(ik == 0 || ik == N - 1 || jk == 0 || jk == N - 1)) continue;

, , , , . , , . , 1, . , .

, [2, 2] 03 17, . , , « » . .. ( ) .

, . , , . , Turbo Pascal – ( ).

, :

…
a[ik][jk] =  abs(N / 2 + 1 -  i);
…

, .

. , , .

Ic, Jc (c center).

…
Ic = abs(i -  N / 2  - 1);
Jc = abs(j -  N / 2  - 1);
…

, .

, - – .

…
a[ik][jk] =  Ic + Jc;
…

, – , . . , Ic Jc.

…
a[ik][jk] =  Ic - Jc;
…

. , , .

…
a[ik][jk] =  abs(Ic – Jc) + Ic + Jc;
…

. , , . , . Ring.

…
Ring = N / 2 -  (abs(Ic – Jc) + Ic + Jc) / 2; 
a[ik][jk] =  Ring;
…

. , N = 6 , ( , ).

N = 6

. : ? - .

, Ic Jc. N = 6, Ic = |i - N / 2 - 1|.

. , 1 3- ( ).

…
Ic = abs(i - N / 2  - 1) + (i - 1) / (N /2) * ((N-1) % 2);
…

N, .

Jc.

…
Jc = abs(j - N / 2  - 1) + (j - 1)/(N /2) * ((N-1) % 2);
…

. Ring 6.

… 
a[ik][jk] =  Ring;
…

. .

3 . . ( ).

, :

…
a[ik][jk] =  switcher * Xs + abs(switcher - 1) * (4 * N - 2 - Xs);
…

: «» (.. 1), , ( [1,2] [2,2], 16 17)

, - . , – .

, Xs ( ) , .

Xs = (i – Ring) + (j – Ring) – 1.

…
a[ik][jk] =  switcher * Xs + abs(switcher - 1) * (4 * N - 2 - Xs);
…

. , . , 4 * N - 2 - Xs , , N – 2 * Ring. .

…
a[ik][jk] =  switcher * (Xs) + abs(switcher - 1) * (4 * (N - 2 * Ring) - 2 - Xs); 
…

, . – , , .

, . :

Coef = N² – (N – 2Ring)²

((a−b)²=a²−2ab+b²), 4Ring(N - Ring).

…
a[ik][jk] =  Coef + switcher * (Xs) + abs(switcher - 1) * (4 * (N - 2 * Ring) - 2 - Xs);
…

…
int switcher =  (j - i + N) / N;
int Ic = abs(i - N / 2  - 1) + (i - 1)/(N /2) * ((N-1) % 2);
int Jc = abs(j - N / 2  - 1) + (j - 1)/(N /2) * ((N-1) % 2);
int Ring = N / 2 - (abs(Ic - Jc) + Ic + Jc) / 2;
int Xs = i - Ring + j - Ring - 1;    
int Coef =  4 * Ring * (N - Ring);
a[ik][jk] =  Coef + switcher * Xs + abs(switcher - 1) * (4 * (N - 2 * Ring) - 2 - Xs);
…

もちろん、追加の変数を i、j、N のみに基づいた式に置き換えて、1 つの数式を拡張し、数学的方法でそれを削減しようとすることもできます。しかし、信じてください、試してみましたが、それは非常に考えられないもの (半分のページ) であることが判明したので、そのままにしておくことにしました。

(追伸。ゼロ除算エラーが発生するため、N = 1 の場合にのみ機能しません。ただし、ことわざにあるように、「少しはカウントされません」)。

「らせん状マトリックス」を充填する別の方法

More articles: