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