Nombre maximal de séquences particulières d'éléments dans le tableau 3D

Question

Pour une affectation de structures de données, j'ai donc dû initialiser chaque élément dans un tableau 3D alloué statiquement avec l'une des cinq couleurs choisies au hasard. Le tableau était de type ColorEnum, qui a été déclarée comme ceci:

---

ENUM ColorEnum {ROUGE, ORANGE, JAUNE, VERT, BLEU};

---

Ma tâche était de trouver les indices des éléments qui composent une séquence particulière d'éléments (ce qui signifie chaque élément de la séquence est en contact avec logiquement l'élément suivant dans la séquence soit côte à côte à l'autre, de haut en bas , ou d'avant en arrière). Une séquence complète serait une séquence dans laquelle un élément ROUGE touche un élément ORANGE qui touche un élément JAUNE qui touche un élément VERT qui touche un élément BLEU. Pour être en contact, tout un côté des deux éléments doit être adjacent, pas seulement un bord ou un coin. Donc chaque élément pourrait toucher au maximum 6 autres éléments. Un élément individuel peut être utilisé dans plus d'une séquence. Afin de stocker les indices des éléments dans une séquence, j'ai utilisé un tableau de structures 1D alloué statiquement qui contiendrait les indices de ligne, de colonne et de profondeur de l'élément. Afin de stocker chaque séquence, j'ai utilisé un autre tableau 1D alloué statiquement des tableaux qui contiennent les indices des éléments dans une séquence. Pour arriver à ma question, afin d'utiliser le moins de mémoire possible, j'ai besoin de savoir quelle taille allouer au tableau de tableaux. Je voudrais que cette taille soit égale au nombre maximum de ces séquences ROUGE, ORANGE, JAUNE, VERT, BLEU mais je ne sais pas comment déterminer ce nombre. Est-ce que des génies de maths là-bas veulent me donner un coup de main? Ma mission est depuis longtemps terminée. J'ai eu un 94/100, mais cette question m'embête. J'apprécie l'aide.

Answer 1

Le nombre maximal de séquences possibles dépendra des dimensions de votre réseau 3D et (bien sûr) du remplissage de la grille. En regardant sous un angle combinatoire, j'essaierais de trouver le remplissage le plus efficace d'une telle grille 3D. Cependant, l'allocation du maximum est supposé le pire des cas et vous seriez mieux avec des vecteurs comme @Kevin a commenté.

Un remplissage de la grille qui me semble efficace est de remplir les 6 positions adjacentes d'un bloc avec 3 de ses couleurs précédentes et 3 de ses couleurs suivantes (donc un bloc jaune aurait 3 blocs orange et 3 verts comme voisins). Si vous remplissez les voisins (arrière, droit, haut) avec la couleur suivante et les voisins (avant, gauche, bas) avec la couleur précédente, la structure émergente permet d'utiliser 1 bloc dans beaucoup de séquences. Si une couleur n'a pas de couleur suivante/précédente, juste la couleur précédente/suivante.

En 2D, vous auriez quelque chose comme ça (de ColorNames abrégé)

BGYOROYGBGYOROYGB 
GBGYOROYGBGYOROYG 
YGBGYOROYGBGYOROY 
OYGBGYOROYGBGYORO 
ROYGBGYOROYGBGYOR 

Le nombre de séquences utilisant le R est 2^4 en bas à gauche, la quantité de séquences en utilisant l'un des milieu R de (en un champ infini) est 2^5. Le nombre exact exact de séquences dans un champ 3D peut alors être calculé pour ce modèle, en tenant compte des limites (et probablement d'un schéma différent sur les bords car il y aura une perte)

Ma méthode de remplissage est juste un moyen de remplir la grille, d'autres possibilités existent et pourraient même être meilleures.