Discussion :

[fred61]

Bonjour,

J'essai d'écrire une fonction permettant de calculer toutes les positions possibles d'éléments de différentes taille sur une grille (voir schéma ci-dessus). L'ordre des éléments ne doit pas changer.

Je pense que la meilleure façon serait d'écrire une fonction récursive, d'abord décaler le dernier élément d'une case vers la droite jusqu'à la fin de la ligne, puis ensuite décaler le deuxième élément d'une case vers la droite, et recalculer toute les positions du premier et ainsi de suite jusqu'à avoir fait le tour des positions possibles (j'espère ne pas être trop confu).

J'ai vraiment du mal avec les fonctions récursives, si vous avez une idée de la façon dont je pourrai l'écrire ça pourrait m'avancer un peu ?

Je vous remercie.

[fred61]

J'ai oublié de préciser, le nombre d'éléments et leurs tailles peuvent varier, donc je pense qu'on peut entrer ces informations en argument de la fonction

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
int nb_de_positions_possibles(int nombre_elements, int * taille)
{
 
}

Ou taille est un tableau contenant la taille (en case) de chaque éléments, dans l'ordre d'apparition.

C'est vraiment le genre de problème qui me font mal à la tête, j'ai souvent l'habitude de vouloir faire trop compliqué, si vous avez une idée à me suggérer ?
Merci.

[gangsoleil]

J'essai d'écrire une fonction permettant de calculer toutes les positions possibles d'éléments de différentes taille sur une grille (voir schéma ci-dessus). L'ordre des éléments ne doit pas changer.

J'ai beau retrourner cette phrase dans tous les sens, je ne comprends pas ce que tu dois faire : comment calculer toutes les positions différentes si l'ordre est fixe ??

[Sve@r]

Bonjour

C'est pas compliqué: les éléments de couleur ne sont pas fixés entre eux. Ils peuvent "glisser" de façon individuelle le long du "rail" selon leurs longueurs respectives et selon l'espace libre qu'il y a après (la zone blanche n'est pas un élément, c'est un espace vide...)

J'avais déjà fait une fonction de ce genre quand je m'étais amusé à résoudre le jeu du logigraphe. Effectivement on est obligé de passer par une fonction récursive...

J'ai oublié de préciser, le nombre d'éléments et leurs tailles peuvent varier, donc je pense qu'on peut entrer ces informations en argument de la fonction

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
int nb_de_positions_possibles(int nombre_elements, int * taille)
{
 
}

Ou taille est un tableau contenant la taille (en case) de chaque éléments, dans l'ordre d'apparition.

Tu n'es pas obligé de stocker le nombre d'éléments. Etant donné qu'il ne peut pas y avoir d'élément de taille "0", tu peux utiliser cette valeur "0" comme indicateur de fin de tableau. Exemple pour celui de ton image: {3, 2, 1, 2, 4, 0}.
Ensuite tu initialises une boucle qui prend un élément précis et qui le déplacera à chaque itération d'un cran vers la droite tant qu'il y a des espaces. Et à chaque itération tu réappelles cette fonction mais en lui passant l'élément à déplacer (d'abord le dernier puis l'avant dernier puis ...)
Un truc de ce genre

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
fonction(tableau_d_elements, elementX)
{
    pour (i=0; i < nb_d_espaces; i++)
    {
        deplacer elementX d'une position vers la droite
        si (x != 1)
        {
            fonction(tableau_d_elements, elementX-1)
        }
    }
    remettre elementX à sa position iintiale
}

[picodev]

Hello,

Le problème peut être approché différemment aussi. Au lieu considérer à déplacer tes éléments sur ta grille, tu pourrais te demander comment répartir les cases blanches entre tes éléments. Pour l'image de ton premier post on aurait 0 case blanche entre le début de la grille et l'élément orange, 0 entre l'orange et jaune, 0 entre le jaune et le magenta, 0 entre le magenta et le vert, 0 entre le vert et le cyan, 9 entre le cyan et la fin de la grille. Tu te retrouves avec le tuple (0,0,0,0,0,9). Le tuple (1,2,3,0,2,1) est une autre solution, soit 1 case blanche entre le début de la grille et l'élément orange, 2 entre l'orange et le jaune, etc.
Si on note n le nombre de cases blanches (n=taille de la grille - somme des tailles des éléments) et m le nombre d'intervalles (m=1+nombre d'éléments), ton problème se réduit à parcourir toutes les partitions de n en m parties ordonnées.
Je n'ai pas fait de recherches avec google mais il doit sans doute y avoir de la littérature sur ce problème.

[Médinoc]

Ooh, cela m'a l'air d'une très bonne idée.

[fred61]

Merci Sve@r pour ton algo, j'ai commencer à essayer de le développer cet après-midi mais j'ai pas encore terminé.

L'idée de picodev me parait vraiment pas mal, je pense que ça sera plus facile à développer, et surement moins gourmand en temps.

En tout cas merci pour tout, je vous tiens au courant si j'ai réussi à faire quelque chose de fonctionnel.