Dalam proses mempelajari dasar-dasar algoritme dan pemrograman sebagai mahasiswa di pertengahan tahun 2000-an, saya menemukan tugas yang cukup terkenal untuk mengisi matriks "spiral". Intinya adalah, mulai dari posisi [1, 1], bergerak searah jarum jam, mengisi matriks persegi dari nilai yang diberikan dengan angka dalam urutan menaik. Butuh waktu sekitar dua jam untuk menyelesaikannya.
Algoritma pengisian itu sendiri sepele, loop, secara total, terdiri dari N 2 iterasi, diasumsikan melalui semua elemen array dalam urutan yang diperlukan, sambil meningkatkan nilai iterator sebesar 1 dan mengisinya dengan elemen saat ini dari matriks. Rute dimulai dari elemen [1, 1], kemudian bergerak horizontal ke elemen kanan atas [1, N], lalu turun ke sudut kanan bawah [N, N], lalu ke sudut kiri bawah [N, 1] dan mengakhiri lingkaran pertama satu kolom di bawah titik awal [2, 1]. Kemudian, gerakan melingkar yang sama terjadi di lingkaran dalam berikutnya, dan seterusnya hingga ke pusat matriks.
Internet, diwakili oleh berbagai forum, komunitas, situs yang didedikasikan untuk area ini, penuh dengan solusi spesifik dalam berbagai bahasa pemrograman, yang telah banyak ditemukan oleh umat manusia selama lebih dari setengah abad. Pada saat yang sama, mekanisme pengisian matriks yang disajikan di atas adalah yang utama dan paling efektif baik dari sudut pandang seseorang maupun dari sudut pandang komputer (jika memiliki sudut pandang).
Beberapa waktu setelah berhasil memecahkan masalah, setelah mengevaluasi kembali kemampuan saya sendiri, saya bertanya-tanya: apakah mungkin untuk mengembangkan formula universal yang memungkinkan, berdasarkan ukuran matriks dan koordinat sel, untuk menghitungnya nilai sesuai dengan kondisi masalah - yaitu, akhirnya mengisi array, iterasi elemen " tradisional "cara dengan dua loop bersarang dari 1 ke N tanpa menggunakan penghitung.
, , , , .
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, E1,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.
a1,2 = 4N – 4 + 2 – Xs = 4N – Xs - 2.
…
int Xs = i + j - 1;
a[ik][jk] = 4 * N - Xs - 2;
…
, – .
, .
1. ai,j = Xs = i + j - 1; [1, 1] [N, N].
2. ai,j = 4*N – 2 - X; [N, N] [2, 1].
, . , - , , (y = |x|) .
, :
F1 1 i, j [1, 1] … [N, N] , – 0. , F2 , , 1 [N, N - 1] … [2, 1], 0 [1, 1] … [N, N].
switcher, i j, , .
-1, 0 / 1 . F1 F2 .
, 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
…
, F1 F2. F1 , , .. F1 (switcher) = switcher. F1 (switcher) * Xs [1, 1] [N, N], . , . switcher – 1, .. F2.(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 = N2 – (N – 2Ring)2
((a−b)2=a2−2ab+b2), 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);
…
Anda tentu saja dapat mencoba memperluas satu rumus, mengganti variabel tambahan dengan ekspresi yang hanya didasarkan pada i, j dan N, dan mencoba menguranginya dengan metode matematika. Tapi percayalah, saya mencoba, ternyata menjadi sesuatu yang sangat tak terbayangkan (setengah halaman) sehingga saya memutuskan untuk membiarkannya apa adanya.
(PS. Ini tidak bekerja hanya untuk N = 1, karena kesalahan pembagian dengan nol terjadi. Tapi seperti kata pepatah, "sedikit tidak masuk hitungan").