[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:

[DEBUTANT]algorithme recursif de mise a jour de chiffres

Algorithmes et structures de données

Vue hybride

Discussions similaires

Partager

Partager