hg S’enregistrer Bac Tunisie Algorithmique et programmation : BAC INFORMATIQUE En Tunisie forum informatique Tunisie

Bac Tunisie Algorithmique et programmation : BAC INFORMATIQUE En Tunisie  forum informatique Tunisie Index du Forum

hg Bac Tunisie Algorithmique et programmation TIC réseaux php javascript sql access activités programmation c
hg
FAQ FAQ Rechercher Rechercher Membres Membres Groupes Groupes Profil Profil Se connecter pour vérifier ses messages privés Messages Privés Connexion Connexion


 Forum de l'excellence et l'excellence en innovation 
Pour participer à notre Forum, vous devez
 
inscrire sur notre forum a partir d'ici
 
  NB :
Les membres ''zéro messages'' seront supprimés automatiquement après un nombre de jours donné !!!!
             
   
 
  
forum d'aide informatique : internet, réseau, programmation informatique ...
Mise en oeuvre de la récursivité
 
 
Poster un nouveau sujet   Répondre au sujet    Bac Tunisie Algorithmique et programmation : BAC INFORMATIQUE En Tunisie forum informatique Tunisie Index du Forum -> Algorithmique & programmation -> Récursivité
hg Sujet précédent :: Sujet suivant   hd
Auteur Message
najouta


Hors ligne

Inscrit le: 22 Nov 2008
Messages: 20
Féminin
Point(s): 227
Moyenne de points: 0

Posté le: Sam 22 Nov - 14:53 (2008)    Sujet du message: Mise en oeuvre de la récursivité Répondre en citant

PublicitéSupprimer les publicités ?
Etant donné un problème (peut-être de nature récursive) comment construire un algorithme récursif de résolution?

Plusieurs points doivent être considérés:
  1. Décomposer le problème en sous-problèmes ; ceci fixera l'algorithme et permettra de vérifier que le problème peut être résolu de manière récursive.

  2. Déterminer quelles sont les données nécessaires à l'obtention de la solution du problème.

  3. Trouver une (des) condition(s) de terminaison de l'algorithme. Ceci se fait en considérant un (des) cas simple(s) où l'algorithme donne la solution sans appels récursifs. Tout algorithme récursif doit être fini!


Illustrons tout cela par un exemple:
Citation:

Soit une liste chaînée par pointeurs . Chaque élément de cette liste contient un nombre entier. Ecrire une procédure donnant la somme des nombres de la liste.





Les structures de données nécessaires à la liste sont
Citation:

Code:
[b]type[/b] lien = ^element;     (* pour le chaînage, convention t_ non utilisée ici *)
      element = [b]record[/b]
                   nombre : integer; (* nombre à considérer *)
                   suivant : lien;   (* lien de chaînage *)
                [b]end;[/b]

[b]var[/b]  tête_de_liste : lien;   (* pointe sur le premier élément de la liste *)
     somme_finale : integer; (* somme des nombres *)





Décomposons le problème en sous-problèmes:
Citation:

a) considérer l'élément courant de la liste
b) additionner sa valeur à la somme des valeurs des éléments déjà parcourus
c) passer à l'élément suivant de la liste




On voit alors que les données nécessaires au calcul de la somme sont
Citation:

- le nombre contenu dans chaque élément (évident)
- les sommes partielles
- le pointeur repérant l'élément courant




Ecrivons partiellement la procédure demandée:
Citation:

Code:
[b]procedure[/b] parcours_somme  ((* paramètres à définir *)) ;
(* parcourt la liste récursivement en additionnant les valeurs des éléments *)

[b]begin[/b] (* parcours_somme *)

  (* considérer l'élément courant *)

  (* additionner la valeur à la somme des valeurs des éléments déjà parcourus *)
  somme := somme + courant^.nombre;

  (* passer à l'élément suivant *)
  parcours_somme ( (* paramètres effectifs *) );

[b]end;[/b] (* parcours_somme *)





On voit maintenant que les paramètres de la procédure sont la somme partielle ainsi qu'un pointeur sur l'élément courant. Donc
Citation:

Code:
[b]procedure[/b] parcours_somme ( courant : lien;
                            [b]var[/b] somme : integer );
(* parcourt la liste récursivement en additionnant les valeurs des éléments *)

[b]begin[/b] (* parcours_somme *)

  (* considérer l'élément courant *)

  (* additionner la valeur à la somme des valeurs des éléments déjà parcourus *)
  somme := somme + courant^.nombre;

  (* passer à l'élément suivant *)
  parcours_somme ( courant^.suivant, somme );

[b]end;[/b] (* parcours_somme *)





Il reste à trouver une condition de terminaison de l'algorithme: le parcours est terminé lorsque la fin de la liste est atteinte, ce qui s'exprime au moyen du pointeur courant. Finalement
Citation:

Code:
[b]procedure[/b] parcours_somme ( courant : lien;
                            [b]var[/b] somme : integer );
(* parcourt la liste récursivement en additionnant les valeurs des éléments *)

[b]begin[/b] (* parcours_somme *)

  (* considérer l'élément courant: stop si la fin de liste est atteinte *)
  [b]if[/b] courant <> [b]nil then[/b]
  [b]begin[/b]

    (* additionner la valeur à la somme des valeurs des éléments déjà parcourus *)
    somme := somme + courant^.nombre;

    (* passer à l'élément suivant *)
    parcours_somme ( courant^.suivant, somme );

  [b]end;[/b]

[b]end;[/b] (* parcours_somme *)





Remarques:

  1. L'appel de cette procédure se fait par

           parcours_somme ( tete_de_liste, somme_finale );

    avec somme_finale  initialisée à 0 avant!
  2. Cette procédure se comporte normalement même si la liste est vide, c'est-à-dire si tete_de_liste  vaut nil .


 
Revenir en haut
najouta


Hors ligne

Inscrit le: 22 Nov 2008
Messages: 20
Féminin
Point(s): 227
Moyenne de points: 0

Posté le: Sam 22 Nov - 14:54 (2008)    Sujet du message: Mise en oeuvre de la récursivité Répondre en citant

jallai dire merci

 
Revenir en haut
Contenu Sponsorisé






Posté le: Aujourd’hui à 17:20 (2016)    Sujet du message: Mise en oeuvre de la récursivité

 
Revenir en haut
Montrer les messages depuis:   
bg bd
Poster un nouveau sujet   Répondre au sujet    Bac Tunisie Algorithmique et programmation : BAC INFORMATIQUE En Tunisie forum informatique Tunisie Index du Forum -> Algorithmique & programmation -> Récursivité Toutes les heures sont au format GMT + 1 Heure
 
Page 1 sur 1

 
Sauter vers:  
Index | créer forum gratuit | Forum gratuit d’entraide | Annuaire des forums gratuits | Signaler une violation | Conditions générales d'utilisation