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.

[fred61]

Si je reprends l'idée de Picodev, dans mon exemple : tuple (0,0,0,0,0,9)

il faut dans mon algorithme que je calcule toutes les combinaisons possibles de 6 nombres dont la somme est égale à 9.

(0,0,0,0,0,9)
(0,0,0,0,1,8)
(0,0,0,0,2,7)
...
(1,1,1,1,1,4)
...

Je me creuse pas mal la tête mais j'avoue bloquer un peu (beaucoup), si vous avez des idées ou un point de départ je suis preneur.

Merci.

[Médinoc]

Tu peux peut-être oublier le dernier nombre, et faire des combinaisons de nombres dont la somme est inférieure ou égale à 9. Cela t'évitera d'avoir un chiffre au comportement "spécial".

[picodev]

Si on note P(n,m) l'ensemble des tuples de longueur m dont la somme des éléments vaut n alors on peut remarquer que :

P(0,m)={(0, 0, ..., 0)}
P(n,1) ={(n)}
P(n,m)={ (0,P(n-0,m-1)), (1,P(n-1,m-1)), ..., (i,P(n-i,m-1)), ..., (n,P(0,m-1)) }

Un algo qui implémente cette idée pourrait être :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
procedure Partition( part : tableau[1..m], somme : entier, index : entier )
début
  si somme == 0 alors
    remplir part avec des 0 à partir de index
    visiter part
  sinon si index=m alors
    part[m]=somme
    visiter part
  sinon
    pour i de 0 à n faire
      si somme>=i alors
         part[index]=i
         Partition(part, somme-i, index+1)
      fin si
    fin pour
  fin si
fin

En gros, c'est à affiner ...

[fred61]

Merci pour vos idées, j'ai transcris le code en c, apparemment c'est fonctionnel, je vous mets le code ci-dessous, ça pourra toujours servir à quelqu'un un jour.

Si vous avez les remarques sur le code elles sont les bienvenues :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 
#include <stdio.h>
 
int nb_de_possibilite=0;
 
//simple fonction qui affiche le tableau et passe a la ligne
void afftab(int * tab, int taille)
{
    int i ;
    for(i=0;i<=taille-1;i++) printf("%d;", tab[i]) ;
	printf("\n");
}
 
 
//m est le nombre d'elements du tableau
//somme est la somme des elements
int partition(int * tab, int somme, int index, int m, int s)
{
     int i, total=0 ;     
 
     if(s==0)
     {
		for(i=0;i<=m;i++) tab[i]=0 ;		
		afftab(tab, m);	
     }
     else if(index==m)
     {
	      tab[m]=s ;
		  for(i=0;i<=m-1;i++) total+=tab[i] ;
		  if(total==s) { afftab(tab, m); nb_de_possibilite++;}
     }
     else
     {
		for(i=0;i<=somme;i++)
		{
		   if(somme>=i)
			   {
				  tab[index]=i;
			      partition(tab, somme-i, index+1, m, s);
			   }
		}
     }
 
}
 
int main(void)
{
 
    int tab[32], i;
    int somme, nb;
	for(i=0;i<=31;i++) tab[i]=0 ;
 
	printf("Entrer la somme des elements : ") ;
    scanf("%d", &somme);
	printf("Entrer le nombre d'elements (max 32) : ")  ;
	scanf("%d", &nb);
 
    partition(tab, somme, 0, nb, somme) ;	
 
    printf("Nombre de solutions possibles : %d\n", nb_de_possibilite) ;
    return 0;
}

Encore merci.

[Sve@r]

Si vous avez les remarques sur le code elles sont les bienvenues :

Ta variable "nb_de_possibilite" n'a aucun besoin d'être mise en globale (d'ailleurs c'est le cas dans 99,98% des programmes)...

[fred61]

Tu pense que ça serait mieux de mettre un pointeur dessus et de passer le pointeur à la fonction ?

[Sve@r]

Exact. En fait, les globales sont généralement une très mauvaise idée. Dans un petit code comme le tien ce n'est pas grave mais dans un projet tu obscurcis l'analyse de son comportement. Surtout quand son nom n'est pas assez significatif tu as le risque de créer une variable locale qui va la masquer quand tu as besoin de sa valeur ou inversement tu la modifies accidentellement dans une sous-fonction alors que la fonction appelante a désespérément besoin de la valeur qu'il y avait et qui n'y est plus au retour de la sous-fonction. Et même avec un nom bien significatif qui ne laisse pas de place à l'ambigüité, tu as le risque de lui voir prendre la mauvaise valeur et de galérer pour retrouver l'origine du bug.
Les globales ont une utilité puisqu'elles ont été créées (tout comme le "goto") mais quand on peut faire sans, c'est au minimum tout aussi bien et c'est souvent bien mieux. Il vaut mieux essayer de prendre assez vite l'habitude de ne pas en mettre (ou de ne pas céder systématiquement à la facilité apparente qu'elles apportent).