Discussion :

[arundel]

Bonjour à tous,
Je n'avais pas sollicité votre aide depuis quelques temps mais à présent je cale sur un problème d'algo, dont voici une synthèse.

1. Je décris un arbre sous forme de graphe objet dont les sommets sont eux-mêmes des objets (classique)
2. Dans chaque sommet figure une information sous forme d'entier dont la valeur est positive UNIQUEMENT dans les feuilles de l'arbre (au départ de l'algo)
3. Par un parcours en profondeur j'essaie de remonter la plus grande valeur du niveau inférieur (voir exemple ci-après).

ID	Initiale	Finale
"1"	0	30
"11"	0	15
"111"	10	10
"112"	15	15
"12"	0	30
"121"	10	10
"122"	20	20
"123"	30	30

Pb : à quel endroit de la procédure récursive positionner cette récupération ?
En effet à la remontée, après avoir exploré les feuille d'un niveau les feuilles je perds le sommet-père avant d'avoir pu y reporter la valeur maxi.
Par exemple quand maxi = 15, le parcours passe directement à l'ID = "12" avant que j'aie eu la main pour reporter cette valeur dans l'ID="11". Idem pour ID="1"

J'espère avoir été clair dans l'exposé de mon problème.

Merci de votre aide.

Bien cordialement

[tbc92]

Tu parles d'une procédure récursive.
Souvent, ça a cette forme :

Code :

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

1
2
3
4
5
6
7
fct_recursive ( a, b) 
   si b >0 alors 
      call fct_recursive (a+1, b-1)
   sinon 
      print (a,b)
   fin
fin

Tu peux faire cette modification, pour suivre ce qui se passe :

Code :

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

1
2
3
4
5
6
7
8
9
fct_recursive ( a, b) 
   print ( " avant", a, b)
   si b >0 alors 
      call fct_recursive (a+1, b-1)
   sinon 
      print (a,b)
   fin
   print ( " après", a, b)
fin

Et là, tu devrais voir comment t'en sortir.

[APL-AML]

Bonjour,

Je m'intéresse à la présentation de ton tableau...

ID	Initiale	Finale
"1"	0	30
"11"	0	15
"111"	10	10
"112"	15	15
"12"	0	30
"121"	10	10
"122"	20	20
"123"	30	30

Mes tentatives pour créer ce même tableau avec l’éditeur restent vaines.

• Comment la définition de ta table est-elle devenue [TABLE="class:table"] ?
  
  Je suppose que c’est cette définition qui détermine le quadrillage.
  
  
• Comment les cellules de la ligne d’en-tête sont-elles devenues [TH][/TH] ?

J’ai dû zapper quelque chose et j’ai besoin d’une leçon de rattrapage.

Merci à toi d’éclairer ma lanterne.

[Flodelarab]

Bonjour

Pb : à quel endroit de la procédure récursive positionner cette récupération ?

Soit l'objet est capable de stocker ce maximum.
Soit ce maximum est la valeur de retour de la fonction récursive.

[arundel]

Il est bien vrai que la nuit porte conseil. En effet, la solution du sujet que j'ai soumis hier soir était d'une simplicité confondante.
Nul besoin de parcourir le graphe en profondeur, il suffit de reporter les valeurs sur les niveaux supérieurs (à condition qu'elles soient plus grandes) à mesure que le graphe est construit.
Je précise à quoi ça sert : il s'agit de paramétrer les différents niveaux de sous-totalisation automatique dans un tableau Excel, les entiers étant les numéros de ligne donc croissants (ce qui limite le champ d'application de la solution).

Voici le détail de la procédure, objet par objet :

"1"	0
"11"	0
"111"	10

puis report sur les ID "11" et "1", ce qui donne :

"1"	10
"11"	10
"111"	10

"1"	15
"11"	15
"111"	10	inchangé car de même niveau que "112"
"112"	15

on continue avec la séquence des "12" :

"1"	15	(on ne l'écrase pas car 10 < 15)
"12"	10
"121"	10

"1"	20
"12"	20
"121"	10
"122"	20

"1"	30
"12"	30
"121"	10
"122"	20
"123"	30

Voilà !

Pour répondre à APL-AML :
------------------------
Je n'ai malheureusement aucune idée de la manière dont ce tableau a été formaté par le système du forum. Je me suis contenté de préparer mon texte dans le bloc-notes de Windows et de le coller.
Pour compléter ta citation de John Cage, je te propose celle d'Edgar Faure : "L'avantage des situations désespérées c'est qu'elles peuvent toujours s'aggraver ..."

Merci à tous d'avoir regardé.

[Guesset]

Bonjour,

Sauf si c'est un exercice, quel est l'intérêt de faire une démarche en profondeur - et récursive - pour ramener un max ?

Comme l'arbre semble implémenté dans un tableau, un simple parcours linéaire (si le langage le permet comme C ou C++) de tout le tableau ramènera ce max en consommant beaucoup moins de ressources et de temps.

Il en irait différemment si l'arbre était structuré autour d'une relation d'ordre des valeurs (par exemple, plus grand à droite, plus petit à gauche).

Salutations

[arundel]

Bonjour Guesset,
Tu as raison, aucune nécessité de faire un parcours en profondeur sur cet arbre. Je l'avais d'ailleurs admis dans mon 2ème post (voir ci-dessus : "La nuit porte conseil etc.").
En revanche il est pour moi beaucoup plus performant et pratique de travailler avec deux modules de classe pour décrire l'arbre (Sommets et Graphe) plutôt qu'avec un ou plusieurs tableaux mémoire.
Mais au final c'est bien un parcours linéaire qui donne la solution.
Bien coridalement.