Aide pour une fonction récursive.

Version imprimable

18/01/2015, 23h17
fred61

1 pièce(s) jointe(s)

Aide pour une fonction récursive.

Pièce jointe 166549

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.
19/01/2015, 00h30
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:

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.
19/01/2015, 09h25
gangsoleil

Citation:

Envoyé par fred61

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 ??

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...
Citation:
Envoyé par 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:

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:

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 }

19/01/2015, 12h39
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.
19/01/2015, 15h31
Médinoc

Ooh, cela m'a l'air d'une très bonne idée.
19/01/2015, 18h50
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.
19/01/2015, 21h28
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.
19/01/2015, 22h04
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".

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:

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 ...

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:

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.

20/01/2015, 21h34
Sve@r

Citation:

Envoyé par fred61

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)...
20/01/2015, 22h53
fred61

Tu pense que ça serait mieux de mettre un pointeur dessus et de passer le pointeur à la fonction ?
21/01/2015, 08h39
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).