Discussion :

[jolatouf]

Bonjour,

J'ai un projet de compteur un peu particulier a faire. Je me suis dit que des arbre n-aire serait le plus simple mais j'aurais souhaité des avis externes.

on a un compteur de base qui peut incrémenter et décrémenter (normal jusque la) Ce compteur represente un groupe.

Sur ce groupe on peut faire des sous-groupes. Si un groupe a au moins un sous-groupe, le groupe ne fait plus les incrémentation et décrémentation cela est réalisé dans son (ou ses ) sous-groupe(s). Le nombre de sous-groupe n'est pas déterminer et ne connait pas de limite. Un sous-groupe peut avoir lui même un ou des sous-groupes.

Le compteur de groupe est la somme de ses sous-groupes c'est la raison pour laquelle le groupe ne peut être incrémenter ou décrémenter si il possede des sous-groupes.

exemple:

Code :

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

1
2
3
4
5
6
 
               groupe 1 -> value =12
                        /         \
sous-groupe 2 -> value =7     sous-groupe 3 -> value =5
                                                  \
                                           sous-groupe 4 -> value =5

Le groupe 1 est la somme du sous-groupe 2 et du 3

Les incrémentations et décrémentation se passent dans les sous-groupes 2 et 4

Le sous-groupe 3 et le groupe 1 ne peuvent pas incrémenté et décrémenter de eux même il ne sont que la somme de leur "fils" ou sous-groupe.




Donc j'aimerai savoir si il est interressant de faire mes compteurs dans une structure s'aparentant à un arbre n-aire.

Merci bien

[koala01]

Salut,

La récursivité a de fortes chances de te venir en aide, sur ce coup là...

Cela devrait donner un code ressemlant fort à

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
 
unsigned int Taclasse::Compte()
{
    unsigned int retour=0;
//Le cas de base: il n'y a pas d'enfants, on renvoie donc "1" 
    if(enfants.size()==0)
        retour=1;
    else
    {
         for(unsigned int i=0;i<enfants.size();i++)
         {
              retour+=Compte(enfants[i]);
         }
    }
    return retour;
}

Evidemment, il s'agira d'adatper la boucle à la manière dont tu as choisi de gérer les enfants

[jolatouf]

ok merci,

en fait j'ai regarde et j'ai une structure d'arbre n-aire qui ressemble a ca

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
 
class Noeud {
 
private:
 
            vector<Noeud *> fils;
            int valeur;
 
public:
 
            int Somme()  {
                        if (pasDeFils() != true) {
                                    vector<Noeud *>::iterator it;
                                    int somme = 0;
                                    for (it = fils.begin(); it != fils.end(); it++){
                                                somme += (*it)->Somme();
                                    }
                                    return somme;
                        }
                        else {
                                    return valeur;
                        }
            }
 
            bool pasDeFils() const {
 
                                    return fils.empty();
            }
 
            void AjoutFils (Noeud * f) {
                        fils.push_back(f);
            }
};

C'est a dire que j'ai un noeud avec un vecteur de noeud fils.
j'utilise bien la récursivité pour le calcul de la somme des fils.

[Laurent Gomila]

Juste une petite amélioration, ça fait toujours un peu mal aux yeux :

Code :

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

1
2
3
4
5
6
bool pasDeFils() const {
                        if (fils.size() == 0)
                                    return true;
                        else 
                                    return false;
            }

Code :

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

1
2
3
bool pasDeFils() const {
                        return fils.empty();
            }

[jolatouf]

euh oui tout a fait...

[Jean-Marc.Bourguet]

Une conception alternative consiste à cacher dans le groupe son compte et à le modifier en même tant que les comptes de ses fils. Dans ce cas, il n'est pas nécessaire que le groupe connaisse les fils, juste que les fils connaissent leur père.

En passant,

Juste une petite amélioration, ça fait toujours un peu mal aux yeux :

Code :

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

1
2
3
4
5
6
bool pasDeFils() const {
                        if (fils.size() == 0)
                                    return true;
                        else 
                                    return false;
            }

Outre le fait qu'il y a un membre empty() que tu signales, la logique m'échappe.

Code :

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

1
2
3
bool pasDeFils() const {
  return fils.size() == 0;
}

[jolatouf]

Bonjour,

En fait il faut au moins que le pere sait qu'il a au moins un fils. Car si il n'a pas de fils les opérations d'incrémentation et décrémentation peuvent être effectuer sur lui même sinon celà ce passe dur le fils (voir le fils du fils ->... etc...)

Donc, je pense rajouter une referrence du pere ou au moins une reference à la racine pour que chaque valeur se recalcule à chaque incrémentation et décrémentation. Si un fils change de valeur son père change aussi et le père du père etc...


merci pour les coups de main

Cordialement

[koala01]

Bonjour,

En fait il faut au moins que le pere sait qu'il a au moins un fils. Car si il n'a pas de fils les opérations d'incrémentation et décrémentation peuvent être effectuer sur lui même sinon celà ce passe dur le fils (voir le fils du fils ->... etc...)

Donc, je pense rajouter une referrence du pere ou au moins une reference à la racine pour que chaque valeur se recalcule à chaque incrémentation et décrémentation. Si un fils change de valeur son père change aussi et le père du père etc...


merci pour les coups de main

Cordialement

A vrai dire, il faut surtout voir si tu t'amusera plus souvent à rajouter/retirer des ((arriere)petits)fils ou si tu t'amusera le plus souvent à compter le nombre d'éléments totaux...

En effet, la modification du parent prendra une forme (qui devrait, pour bien faire etre également récursive) du genre de

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
 
void IncrementeNombre()
{
    if(this->Parent!=NULL)
    {
        Parent->Nombre+=1;
    //la récursivité est ici !!!
        Parent->IncrementeNombre();
    }
}
void DecrementeNombre()
 
{
    if(this->Parent!=NULL)
    {
        Parent->Nombre+=1;
    //la récursivité est ici !!!
        Parent->DerementeNombre();
    }
}

L'astuce, c'est que, fatalement, l'appel à une fonction récursive sera plus lent que l'acces direct à une valeur membre...

Si tu remplis une bonne fois pour toutes ton arbre, effectivement, tu aurais intéret à modifier le nombre au fur et à mesure...

Si tu n'as besoin que de temps en temps du nombre d'enfants, tu peux avoir intéret à utiliser la récursivité sur le calcul en lui meme

[jolatouf]

Je rajouterai des fils mais je ne pense pas avoir en supprimer. Et une fois tous les fils créé, je ferait surtoutdes incrément et décrement ensuite.On peut avoir besoin des valeurs des fils comme des grands parents,

et les valeurs dans l'arbre seront mise a jour assez souvent donc j'ai decidé d'utilisé une mise à jour à chaque passage d'incrementation ou décrémentation.

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
 
 
	void Noeud::incremente(int _valeur){
				if (pasDeFils() == true) {
					this->valeur+=_valeur;
 
					this->pere->incrementePere(_valeur);
 
				}else{
					cout<<"ce noeud a un fils et ne peut etre incrementer directement"<<endl;
				}
			}
 
			void Noeud::incrementePere(int _valeur){
				valeur+=_valeur;
				if(this->pere!=NULL)
				{	
 
					this->pere->incrementePere(_valeur);
				}
			}

En fait les méthodes incremente et incrementePere sont casiment identique et en utilisant cela je ne créé qu'une récursivité de la hauteur de l'arbre donc cela semble me convenir pour le moment.