En étudiant les bases de l'algorithmique et de la programmation en tant qu'étudiant au milieu des années 2000, je suis tombé sur une tâche assez connue consistant à remplir une matrice "en spirale". Le point est, à partir de la position [1, 1], en se déplaçant dans le sens des aiguilles d'une montre, remplir une matrice carrée d'une valeur donnée avec des nombres dans l'ordre croissant. Il a fallu environ deux heures pour le résoudre.
L'algorithme de remplissage lui-même était trivial, les boucles, au total, constituées de N 2 itérations, supposaient de parcourir tous les éléments du tableau dans l'ordre requis, tout en augmentant la valeur de l'itérateur de 1 et en le remplissant avec l'élément courant de la matrice. L'itinéraire a commencé à partir de l'élément [1, 1], puis se déplace horizontalement vers l'élément supérieur droit [1, N], puis vers le coin inférieur droit [N, N], puis vers le coin inférieur gauche [N, 1] et termine le premier cercle une colonne en dessous du point de départ [2, 1]. Plus tard, le même mouvement circulaire a eu lieu dans le cercle intérieur suivant, et ainsi de suite jusqu'au centre de la matrice.
Internet, représenté par divers forums, communautés, sites dédiés à ce domaine, regorge de solutions spécifiques dans divers langages de programmation, dont l'humanité a beaucoup inventé en un demi-siècle. Dans le même temps, le mécanisme de remplissage de la matrice présenté ci-dessus est le principal et le plus efficace tant du point de vue d'une personne que du point de vue d'un ordinateur (s'il a un point de vue).
Quelque temps après avoir réussi à résoudre le problème, après avoir réévalué mes propres capacités, je me suis demandé : est-il possible de développer une formule universelle qui permette, en fonction de la taille de la matrice et des coordonnées de la cellule, de calculer son valeur en fonction de la condition du problème - c'est-à-dire, au final, remplir le tableau, en itérant sur les éléments de manière "traditionnelle" avec deux boucles imbriquées de 1 à N sans utiliser de compteur.
, , , , .
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);
…
Vous pouvez, bien sûr, essayer de développer une seule formule, en remplaçant des variables supplémentaires par des expressions basées uniquement sur i, j et N, et essayer de la réduire par des méthodes mathématiques. Mais croyez-moi, j'ai essayé, cela s'est avéré être quelque chose de tellement inconcevable (une demi-page) que j'ai décidé de le laisser tel quel.
(PS. Cela ne fonctionne pas seulement pour N = 1, puisqu'une erreur de division par zéro se produit. Mais comme le dit le proverbe, "un petit peu ne compte pas").