En el proceso de estudiar los conceptos básicos de la algoritmización y la programación como estudiante a mediados de la década de 2000, me encontré con una tarea bastante conocida de completar una matriz en "espiral". El punto es, comenzando desde la posición [1, 1], moviéndose en el sentido de las agujas del reloj, llenar una matriz cuadrada de un valor dado con números en orden ascendente. Tomó alrededor de dos horas resolverlo.
El algoritmo de llenado en sí era trivial, los bucles, en total, consistían en N 2 iteraciones, asumiendo que pasaban por todos los elementos de la matriz en el orden requerido, mientras aumentaban el valor del iterador en 1 y lo llenaban con el elemento actual de la matriz. La ruta comenzó desde el elemento [1, 1], luego se mueve horizontalmente hacia el elemento superior derecho [1, N], luego hacia la esquina inferior derecha [N, N], luego hacia la esquina inferior izquierda [N, 1] y termina el primer círculo una columna por debajo del punto de partida [2, 1]. Posteriormente, el mismo movimiento circular tuvo lugar en el siguiente círculo interior, y así sucesivamente hasta el centro de la matriz.
Internet, representada por varios foros, comunidades, sitios dedicados a esta área, está repleta de soluciones específicas en varios lenguajes de programación, de los cuales la humanidad ha inventado mucho durante más de medio siglo. Al mismo tiempo, el mecanismo para llenar la matriz presentada anteriormente es el principal y más efectivo tanto desde el punto de vista de una persona como desde el punto de vista de una computadora (si tiene un punto de vista).
Algún tiempo después de resolver con éxito el problema, luego de reevaluar mis propias habilidades, me pregunté: ¿es posible desarrollar una fórmula universal que permita, en función del tamaño de la matriz y las coordenadas de la celda, calcular su valor de acuerdo con la condición del problema - es decir, finalmente llenar la matriz, iterando sobre los elementos de manera "tradicional" con dos bucles anidados de 1 a N sin usar un 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);
…
Por supuesto, puede intentar expandir una sola fórmula, reemplazando variables adicionales con expresiones basadas solo en i, j y N, y tratar de reducirla mediante métodos matemáticos. Pero créeme, lo intenté, resultó ser algo tan inconcebible (media página) que decidí dejarlo como está.
(PD. No funciona solo para N = 1, ya que se produce un error de división por cero. Pero como dice el refrán, "un poquito no cuenta").