[DEBUTANT]algorithme recursif de mise a jour de chiffres

**eclipse012** · 31/10/2006, 16h06

je suis un peu debutante dans le domaine de la recursivite

voila, je traite une arborescence de types de documents

dont le schema general est le suivant

Code :

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

1
2
3
4
5
6
7
8
 
type parent A 
   sous type a
      sous sous type 1
   sous type b
      sous sous type 1
      sous sous type 2
type parent B

c'est juste un exemple pour dire que on a une arborescence de types et que chaque type peut avoir autant de sous types "qu'il veut " et ainsi de suite

dans ma base de donnée , j'ai un attribut ordre type asoocié a chaque type et je dois ecrire une fonnction qui met a jour cet ordre dans la base de deonnées

de la sorte

Code :

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

1
2
3
4
5
6
7
8
9
10
parent 1
 
   sous 0
      sous sous 0
      sous sous 1
   sous 1
   sous 2
      sous sous 0
 
parent 2

a chaque fois que on entre dans un sous niveau et que on examine les fils d'un type chauque fils a son sompteur qui debute a zero a chaque fois

je n'arrive pas trop a ecrire mon algo avant d'ecrire la fonction est ce que vous pouvez m'aider svp?

je debute en algorithmique donc peut etre ce n'est pas la bonne syntaxe mais voila comment je pensais proceder:

*on a le tableau des types
pour chaque type du tableau, on regarde si il a des fils et on appelle de maniere recursive la fonction de mise a jour sur les fils
si le type courant a un fils on met a jour l'ordre (cad le numero ) du fils
sinon on s'arrete

est ce que quelqu'un peut l'aider a corriger er reformuler cet algorithme? merci

euh si je n'ai pas ete claire au niveau de ma question demandez moi svp

**nletteron** · 31/10/2006, 16h34

Je ne comprend pas très très bien.

Tu as un arbre et tu veux parcourir toutes les branches et les mettre à jour si le noeud à un fils ? Mise à jour d'un numéro en fait juste ?

Si c'est ce cas tu as des algorithmes qu'on appelle parcours en largeur ou en profondeur qui permettent ce genre de choses.

http://fr.wikipedia.org/wiki/Algorit..._en_profondeur

http://fr.wikipedia.org/wiki/Algorit...urs_en_largeur

**eclipse012** · 02/11/2006, 10h19

bonjour,

tout d'abord merci pour votre réponse !
en fait ce n'est pas un arbre ou une structure arborescente en tant que telle que je traite donc je ne peux pas appliquer les algos que vous m'avez donné.

en fait voila ma liste de types , il y a des types parents et des types fils ....

j'ai mis en rose les types parent en fait j'aimerai bien ecrire une fonction (qui je crois doit etre recursive) et qui mette a jour les numero pour chaque type de la maniere dont je l'ai mis en noir a cote

en fait dans ma base de données j'ai une table type_document qui contient une colonne ordre_type

et j'aimerai bien que tous les ordres soient mis a jour

pour ca je voulais d'abord ecrire un alogrithme recursif et j'ai besoin de votre aide

quand je dis que je suis debutante je suis vraiment dé-débutante est ce que a partir de l'ago de mon post precedent vous puvez m'aider a le corriger svp?

merci

j'espere avoir ete un peu plus claire

**SWOTR** · 03/11/2006, 12h07

Bon... voici comment j'envisage une solution, de la manière dont je cerne le problème :

En premier lieu, il est nécessaire quelque part dans la table d'identifier le père de chaque type(avec une valeur null pour les types racines).
Connaissant cette information,

Pour chaque type:
- Classer les lignes ayant ce type pour père (critère à ta discrétion)
- Pour chaque ligne obtenue :
- - Donner au champ ordre le numéro d'apparition de la ligne.
-
Fin

pas vraiment récursif, et ça suggère l'utilisation de procédures extérieures à SQL (PL/SQL, PHP, Perl...), mais c'est tout ce que je vois comme ça...

J'espère que ça t'aura aidé

**Sivrît** · 03/11/2006, 12h42

Effectivement en SQL ce n'est pas vraiment possible (numéroter en SQL est presque impossible) mais je crois (j'espère

) que ce n'était pas la question.

Par contre avec un peu de code ça doit être assez facile.

D'abord il faut sortir les données de 'type_document' en les triant par parent (je suppose qu'il y a une colonne pour) plus un autre critère, genre :

Code SQL :

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

SELECT * FROM type_document ORDER BY id_parent, libelle_type

Après dans le code on parcourt la liste en incrémentant un compteur que l'on remet à 0 à chaque fois que le parent change :

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
 
compteur := 0
parent := "aucun"
 
pour type dans resultat_sql
faire
   si type.parent != parent
   faire
      parent := type.parent
      compteur := 0
   fin si
 
   type.ordre := compteur
   compteur := compteur + 1
fin pour

Mais c'est pas récursif pour un sous

(quoi, j'aime la récursivité !)

**eclipse012** · 03/11/2006, 14h05

ahhh tout d'abord un enorme merci d'avoir pris le temps de repondre! vraiment; j'ai l'air desesperée MAIS c'est que je le suis vraiment

voila ce que j'ai comme dirait-on "tenté" comme fonction en php:

<?php
function update_ordre_type ($tab){                                      //met a jour l'ordre dans le tableau des types
$childArray = array();                                                       //tableau des fils

foreach ($tab as $id => $element) {                                 //pour chaque type du niveau courant du tableau des types      
$cpt=0;
$tmp = update_ordre_type($element["childs"]);             //on met a jour l'ordre de des types fils
if ($tmp != NULL) {                                                      //si il reste des types fils a examiner
      $cpt ++;
      $requete= "UPADTE type_document set ordre_type =".$cpt."WHERE TYPE_PARENT=".$element['id'];
      $resultat=db_send_query($lang_error['sql update failed'], $requete);
      $element['childs'] = $tmp;                                                                               // affecte le nouveau tableau des types
      $childArray[$element['id']] = $element;
      }
}
if(sizeof($childArray)>0) return $childArray;
      else
            return NULL;      
}
?>

Colorez votre code PHP sur les forums grâce à Developpez.com
mr sivrit j'ai failli dire quel bel algo sauf que comme vous l'avez dit ce n'est pas recursif, et bien que je sois debutante en recursivité, je sais que dans mon cas , c'est bel et bien du recursif que je devrais ecrire

que pensez vous de ma fonction svp? est ce qu'elle peut effectivement mettre a jour les types de la maniere dont je l'ai mis dans la photo 2?

merci

ps je voulais juste ajouter que j'ai deja une colonne type parent dans ma table type_document:

**Sivrît** · 03/11/2006, 17h36

Je ne fais pas vraiment de PHP (le forum correspondant serait peut-être plus approprié) mais voilà ce que je tenterais :

Code php :

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
 
function update_ordre_type ($tab){
   if($tab==NULL) return NULL;
 
   $childArray = array();  
   $cpt = 0; // La numérotation semble commencer à 0
 
   foreach ($tab as $element) {
      $element["childs"] = update_ordre_type($element["childs"]); // on met à jours les fils
 
      $requete = "UPDATE type_document SET ordre_type =".$cpt." WHERE num_type=".$element['id'];
      $resultat = db_send_query($lang_error['sql update failed'], $requete);
 
      $childArray[$cpt] = $element;
      $cpt ++;
   }
 
   if(sizeof($childArray)>0)
      return $childArray;
   else
      return NULL;      
}

Je ne promet pas que la syntaxe est bonne, moi et le php...

mais l'idée doit y être.

Ce code suppose que l'on ait une arborescence à mettre à jour (c'est bien un arbre ça !) au lancement de la fonction, que $element["childs"] contienne le tableau des fils de l'élément et que $element['id'] contienne son NUM_TYPE.

Et surtout il ne faut pas de cycle dans les types sinon on obtient une boucle infini.

Il faudrait peut-être aussi ajouter un truc dans le genre "$element['order']=$cpt;"

**eclipse012** · 06/11/2006, 09h38

bonjour!

merci beauuuuuucoup !
je vais tester ca ....en plus pour vous dire , je ne suis pas dutout pro en php mais d'apres le peu que je sais

, je crois que la syntaxe est correcte

merci encore

edit :

ca marcheeeeeee!!!!

ah enfin je respire ! j'exagere mais c'est vrai que je suis miserablement perdue sur ca depuis 5 jours

je voulais jsute vous demander si ca ne vous derange pas et si vous avez le temps , d'expliquer un peu avec des phrases svp pour que je sois sure de bien comprendre comment ca marche et comme ca je pourrai me servir "de votre maniere de penser les algo" pour les prochaines fonctions a ecrire et pour que je m'ameliore en recursivite

merci!!!!

[DEBUTANT]algorithme recursif de mise a jour de chiffres

Algorithmes et structures de données

Discussions similaires

Partager

Partager