No processo de estudar os fundamentos da algoritmização e programação como um estudante em meados dos anos 2000, me deparei com uma tarefa bastante conhecida de preencher uma matriz em "espiral". O ponto é, partindo da posição [1, 1], movendo no sentido horário, preencher uma matriz quadrada de um determinado valor com números em ordem crescente. Demorou cerca de duas horas para resolvê-lo.
O algoritmo de preenchimento em si era trivial, os loops, no total, consistindo em N 2 iterações, assumiram passar por todos os elementos do array na ordem necessária, aumentando o valor do iterador em 1 e preenchendo-o com o elemento atual de o Matrix. A rota começou a partir do elemento [1, 1], então se move horizontalmente para o elemento superior direito [1, N], então para baixo para o canto inferior direito [N, N], então para o canto inferior esquerdo [N, 1] e termina o primeiro círculo uma coluna abaixo do ponto inicial [2, 1]. Mais tarde, o mesmo movimento circular ocorreu no próximo círculo interno e assim por diante até o centro da matriz.
A Internet, representada por diversos fóruns, comunidades, sites dedicados a esta área, está repleta de soluções específicas em várias linguagens de programação, das quais a humanidade muito inventou ao longo de meio século. Ao mesmo tempo, o mecanismo de preenchimento da matriz apresentada acima é o principal e mais eficaz tanto do ponto de vista de uma pessoa quanto do ponto de vista de um computador (se este tiver um ponto de vista).
Algum tempo depois de resolver o problema com sucesso, na esteira de reavaliar minhas próprias habilidades, me perguntei: é possível desenvolver uma fórmula universal que permita, com base no tamanho da matriz e nas coordenadas da célula, calcular sua valor de acordo com a condição do problema - ou seja, em última análise, preencha o array, iterando sobre os elementos de maneira "tradicional" com dois loops aninhados de 1 a N sem usar um contador.
, , , , .
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);
…
Você pode, é claro, tentar expandir uma única fórmula, substituindo variáveis adicionais por expressões baseadas apenas em i, j e N, e tentar reduzi-la por métodos matemáticos. Mas acredite, eu tentei, acabou sendo algo tão inconcebível (meia página) que resolvi deixar como está.
(PS. Não funciona apenas para N = 1, pois ocorre um erro de divisão por zero. Mas, como diz o ditado, "um pouco não conta").