L'icône rouge permet de télécharger chaque page du wiki visitée au format PDF et la grise au format ODT →

Différences

Ci-dessous, les différences entre deux révisions de la page.

--- utilisateurs:hypathie:tutos:algo-exo-constructions-d-algorithmes-de-procedure [06/12/2014 11:13]
Hypathie [Exo 3 : procédure rechercher un palindrome]
+++ utilisateurs:hypathie:tutos:algo-exo-constructions-d-algorithmes-de-procedure [06/12/2014 17:08] (Version actuelle)
Hypathie [Recherche dichotomique]
@@ Ligne 379: / Ligne 379: @@
     SI chaine[i] < chaine[j] ALORS
     palindrome := VRAI
-      TQ (i < j) ET chaine[i] = chaine[j])
+      TQ (i < j) ET (chaine[i] = chaine[j])
 	 i := i + 1
 	 j := j - 1
@@ Ligne 390: / Ligne 390: @@
 </code>
+=====Trier un tableau par remontée des bulles =====
+===1) Définition du problème===
+<code>
+                                   |    |
+                 liste chiffre---> |    |----> liste de chiffre
+                  (désordonnée)    |    |       (ordonnée)
+</code>
+===2) Jeu d'essai===
+<code>
+Entrée                       sortie
+------------------------------------
+rien                         rien
+                             0
+5293741                       123479
+</code>
+===3) Définition des données du programme TriBulle===
+<code>
+CONSTANTES
+constante MAX = 80
+TYPES
+table =Tableau[MAX] de entiers
+VARIABLES
+variable chiffresDesordo : table    //Table d'entiers désordonnés
+variable chiffresOrdonnés: table    // Table d'entiers ordonnés
+variable nbrchiffre      : entier   // Nombres de chiffres
+variable taille          : entiers  // Taille de la table de chiffres désordonnés en entrée
+                                    // et ordonnée en sortie
+</code>
+===Programme de test de la procédure TriBulle===
+<code>
+CONSTANTES
+constante MAX = 80
+TYPES
+table =Tableau[MAX] de entiers
+VARIABLES
+variable chiffresDesordo : table    //Table d'entiers désordonnés
+variable chiffresOrdonnés: table    // Tables d'entiers ordonnés
+variable nbrchiffre      : entier   // Nombres de chiffres
+variable taille          : entiers  // Taille de la table de chiffres désordonnés en entrée
+                                    // et ordonnée en sortie
+PROCEDURES
+procédure remplir ( entrée        taille_tableau_donné : entier
+                    entrée/sortie  ind                 : entier
+                    entrée/sortie  chiffre_donnés      : entier
+                    sortie         liste_désordonnée   : table
+    // La procédure remplir permet de récupérer les données saisies par l'utilisateur.
+    // chiffres_donnés : compteur de chiffres entrés
+    // taille_tableau_donné : c'est  la taille choisie par l'utilisateur de la table.
+    // chiffre_donnés       : c'est pour arrêter la saisie d'un nouvel élément
+    //                          quand il y a autant que chiffres_donnés.
+    // ind : c'est l'indice de parcours de la table.
+    // liste_désordonnée   : c'est la table de chiffre toute remplie qui a été saisie.
+procédure procédure tribulle( entrée         taille          : entier
+                    entrée/sortie  chiffresDesordo : table
+                    entrée/sortie  chiffreOrdonnés : table)
+    // La procédure du tri des bulles permet de ranger une chaîne de chiffres
+    //      désordonnés en ordre croissant.
+    // chiffresDesordo : C'est la liste de chiffres désordonnés rentrée par
+    //                     l'utilisateur ainsi que la liste de chiffres triés en sortie.
+    // taille : C'est le nombre de chiffres rentrés par l'utilisateur.
+    // invert :  C'est vrai quand il y a eu inversion.
+procédure Procédure affichage_tableau_ordonné ( entrée table_Rangée : table
+                                                entrée taille_table : entier)
+    // La procédure permet l'affichage du tableau trié
+    // table_Rangée est la table de chiffres ordonnés.
+    // table est le type crée (un tableau)
+    // taille_table définie  la taille de la table.
+Début
+  saisie(chiffresDesordo, nbrchiffre, taille) // appel de la procédure saisie
+  triBulle(taille, chiffresDesordo)           // appelle de la procédure triBulle
+  affichage(taille, chiffreOrdonnés)          // appelle de la procédure affichage
+Fin
+</code>
+===5) Interface de la procédure TrieBulle===
+<code>
+Procédure tribulle ( entrée         taille          : entier
+                     entrée/sortie  chiffresDesordo : table
+                     entrée/sortie  chiffreOrdonnés : table)
+// La procédure du tri des bulles permet de ranger une chaîne de chiffres
+//désordonnés en ordre croissant.
+// chiffresDesordo : C'est la liste de chiffres désordonnés rentrée par
+   l'utilisateur ainsi que la liste de chiffres triés en sortie.
+// taille : C'est le nombre de chiffres rentrés par l'utilisateur.
+</code>
+===6) Algorithme de la procédure TrieBulle===
+<code>
+procédure tribulle( entrée         taille          : entier
+                    entrée/sortie  chiffresDesordo : table
+                    entrée/sortie  chiffreOrdonnés : table)
+// La procédure du tri des bulles permet de ranger une chaîne de chiffres
+//désordonnés en ordre croissant.
+// chiffresDesordo : C'est la liste de chiffres désordonnés rentrée par
+   l'utilisateur ainsi que la liste de chiffres triés en sortie.
+// taille : C'est le nombre de chiffres rentrés par l'utilisateur.
+VARIABLES
+variable i              : entier   // indice de parcours du tableau.
+variable cible          : entier  // variable permettant l'inversion de 2 entiers dans le tableau.
+variable comptinversion : entier // Comptage des inversions
+variable invert         : booléen // Permet de déterminé s'il y a ou non inversion
+ Début
+    // parcours jusqu'à qu'il n'y est plus aucune inversion.
+    i := 1
+    invert := FAUX
+    Répéter
+      Tantque ( i < taille ) faire
+	 SI table[i] > table[ i + 1 ] ALORS // si l'entier de la case n°1 du tableau supérieur à
+                                            // celui de la case n°2 du même tableau alors
+		cible = table[1]             //
+		table[1] = table[i + 1]      //  inversion
+		table[i+1] = cible           //
+		invert := VRAI
+	 Finsi
+      i := i + 1                            // incrémentation pour passer aux entiers suivants.
+      Fintantque
+    Jusquà NON invert
+ Fin
+</code>
+====6 bis) Interfaces et programmes des procédures utilisées par le programme principal====
+===I] Procédure "remplir et afficher tableau désordonné"===
+<code>
+//exo: tri par remontée des bulles
+CONSTANTES
+constante MAX = 80  // Taille maximal de la table de chiffres
+Procédure remplir ( entrée        taille_tableau_donné : entier
+                    entrée/sortie  ind                 : entier
+                    entrée/sortie  chiffre_donnés      : entier
+                    sortie         liste_désordonnée   : table
+// La procédure remplir permet de récupérer les données saisies par l'utilisateur.
+// chiffres_donnés : compteur de chiffres entrés
+// taille_tableau_donné : c'est  la taille choisie par l'utilisateur de la table.
+// chiffre_donnés       : c'est pour arrêter la saisie d'un nouvel élément
+                          quand il y a autant que chiffres_donnés.
+// ind : c'est l'indice de parcours de la table.
+// liste_désordonnée   : c'est la table de chiffre toute remplie qui a été saisie.
+Type table = tableau[MAX] d'entiers
+Variables
+taille_finale    : entier	 // nombre de tous les chiffres rentrés par l'utilisateur.
+chiffre_donnés   : entier  // les chiffres rentrés par l'utilisateur pour mettre
+                                 //quelque chose dans le tableau
+                                 //(l'utilisateur ne rentre pas forcément 80 chiffres)
+ind               : entier // indice de parcours de table
+liste_désordonnée : table
+Début
+    // l'utilisateur rentre la taille de la table d'entier et ses valeurs.
+  Répéter
+     Ecrire ( 'Quel sera le nombre de nombres à trier?' ) // taille du tableau à trier
+                                                                     //( sup à 0 ,
+                                                                     //  non égal à 1,
+                                                                     //  stric inf à 80)
+     Lire ( taille_finale )
+  Jusquà ( taille_finale >= 0 )  et ( taille_finale < = MAX )
+  Ecrire ('Saisissez le chiffre n°)', ind )
+    // remplir le tableau
+  chiffre_donnés := 0 // initialisation l'utilisateur n'a pas encore donné ses chiffres à trier
+  ind =1              // initialisation de l'indice de parcours
+  Tantque  (chiffre_donnés <= taille_finale) Faire
+	 Ecrire ('Veuillez donner un entier')       // on demande ensuite les entiers à l'utilisateur
+                                                  // pour chaque case du tableau.
+	 Lire (liste_désordonnée[ind])
+	 chiffre_donnés := chiffre_donnés + 1	  // Incrémentation pour mettre les autres
+                                                  //entiers dans le tableau.
+         ind := ind + 1
+  Fintantque
+  ecrire('Voici la liste des chiffres que vous avez entré',(liste_désordonnée[i])
+Fin
+</code>
+===II] procédure "afficher tableau ordonné"===
+<code>
+Procédure affichage_tableau_ordonné ( entrée table_Rangée : table
+                                      entrée taille_table : entier)
+// La procédure permet l'affichage du tableau trié
+// table_Rangée est la table de chiffres ordonnés.
+// table est le type crée (un tableau)
+// taille_table définie  la taille de la table.
+Type listeChiffre
+Variable taille_table : entier  // compte le nombre de chiffres rentré par l'utilisateur.
+  Début
+	Ecrire ( "le tableau rangé est ",table_Rangée[taille_table])
+  Fin
+</code>
 =====Recherche dichotomique =====
@@ Ligne 539: / Ligne 769: @@
  fin
+</code>
+=====Rechercher un mot dans une phrase=====
+====1) schéma du problème====
+<code>
+SCHEMA :
+phrase ----------------------------->       |		|
+                                            |		|
+mot à chercher---------------------->       |	 	| ---> mot dans phrase oui ou non
+                                            |		|
+Longueur du mot à chercher---------->       |		|
+</code>
+====Jeu d'essai ====
+<code>
+phrase		              Mot_cherché    longueur_Mot_Cherché     Trouvé
+.			       coucou                6                  VRAI
+.                              ' '                   0                  VRAI
+coucou le chat                 le                    2                  VRAI
+coucou le chat                 couii                 5                  FAUX
+le                             chat                  4                  FAUX
+</code>
+====PROCEDURE TROUVER UN MOT====
+===1) Algorithme de principe ===
+<code>
+DEBUT
+  Avoir une phrase
+  Avoir un mot à chercher
+  Avoir la longueur de ce mot cherché
+	REPETER
+		PRENDRE un mot dans la phrase
+		SI  mot de la phrase = mot cherché ALORS
+		     comparer les deux mots
+		FinSi
+	JUSQU'A avoir trouvé le mot cherché OU avoir parcouru toute la phrase
+FIN
+</code>
+===2)PROGRAMME DE TEST===
+<code>
+CONSTANTES
+TERM = '.'
+ESPACE = ' '
+MaxPhrase = 80
+MaxMot    = 15
+TYPES
+phrase_tableau =Tableau [MaxPhrase] de caractères
+mot_tableau =Tableau [MaxMot] de caractères
+VARIABLES
+phraseSaisie : phrase_tableau
+motSaisi      : mot_tableau
+lgMotCherché : entier
+MotTrouvé : booléen
+PROCEDURES
+TrouverMot(entrée      phrase : phrase_tableau
+                     entrée      mot     : mot_tableau
+                     entrée     lgMotCherché : entier
+	         sortie         Trouvé           : booléen
+Début
+	ECRIRE ('Donnez une phrase de moins de', MaxPhrase, 'caractères et un mot
+		de',  MaxMot, 'n'oubliez pas le point.')
+	LIRE(phraseSaisie)
+	ECRIRE('Donnez un mot à cherché de moins de', MaxMot)
+	LIRE(motSaisi )
+	ECRIRE('Donner la longueur du mot à cherché.')
+	LIRE(lgMotCherché)
+	SI MotTrouvé :=  TrouverMot(phraseSaisie, MotSaisi, lgMotCherché, trouvé)
+                        ALORS
+	           ECRIRE('Le mot, motSaisi 'est dans dans la phrase.')
+               SINON
+	            ECRIRE('Le mot, motSaisi 'n'est pas dans dans la phrase.')
+            FINSI
+Fin
+</code>
+=== 3)PROCEDURES TROUVER UN MOT===
+<code>
+rouverMot( entrée     phrase       : phrase_tableau
+                    entrée      mot           : mot_tableau
+	        entrée      longueur   : entier
+	        sortie       trouvé       : booléen )
+VARIABLES :
+position : entier // Indice de parcours de la phrase
+longueur : entier  // Longueur du mot analysé dans la phrase
+trouvé1 : booléen  // Vrai si la mot est trouvé
+PROCEDURES
+prendreMot( Entrée             phrase             : phrase_tableau
+                     Entrée             mot 	        : mot_tableau
+	         Entrée/Sortie   indice             : entier
+                     Sortie              longueurMot  :   entier
+	         Sortie              trouvé1           : booléen  )
+      // Cette procédure regarde s'il y a un mot suivant à partir de la position de l'indice i placé
+      // après    le dernier mot analysé dans la phrase où l'on cherche un mot.
+     // Phrase : c'est la phrase dans laquelle on cherche un mot
+    // mot : c'est le mot qu'on cherche à trouver dans la phrase
+   // indice : c'est l'indice de parcours de la phrase à partir duquel on commence la recherche
+  // longueurMot : c'est la longueur du mot trouvé est que l'indice qui le traverse va permettre d'en
+  //                            la taille.
+//// Le programme est page suivante.
+comparerMot( Entrée             phrase             : phrase_tableau
+                         Entrée            position          : entier
+	             Entrée            longueurMot   : entier
+	             Entrée            mot    : mot_tableau
+	             Sortie             trouvé2           : booléen  )
+	// Cette procédure vérifie que le mot trouvé dans la phrase est de taille égale au mot cherché.
+           // Phrase : c'est la phrase dans laquelle on cherche un mot.
+         //  longueurMot : c'est la longueur unique pour les deux mots.
+       // mot : c'est le mot cherché
+     // trouvé2 : c'est le résultat de la comparaison entre les deux mots.
+//// Le programme est page suivante.
+Début
+position := 0
+longueur:= 0
+trouvéA : =  prendreMot(phrase, position, longueur)
+TantQ   trouvéA:= VRAI
+	SI      longueur = longueurMot         ALORS
+		trouvéB:= comparerMot( phrase, position,  longueurMot, mot)
+	FINSI
+FIN
+</code>
+===PROCEDURES  prendreMot===
+<code>
+prendreMot( Entrée             phrase             : phrase_tableau
+                     Entrée             mot 	        : mot_tableau
+	         Entrée/Sortie   indice             : entier
+                     Sortie              longueurMot  :   entier
+	         Sortie              trouvé1           : booléen  )
+      // Cette procédure regarde s'il y a un mot suivant à partir de la position de l'indice i placé
+      // après    le dernier mot analysé dans la phrase où l'on cherche un mot.
+     // Phrase : c'est la phrase dans laquelle on cherche un mot
+    // mot : c'est le mot qu'on cherche à trouver dans la phrase
+   // indice : c'est l'indice de parcours de la phrase à partir duquel on commence la recherche
+  // longueurMot : c'est la longueur du mot trouvé est que l'indice qui le traverse va permettre d'en
+  //                            la taille.
+PROGRAMME  prendreMot
+Début
+	TQ texte[indice] = espace FAIRE
+		indice := indice + 1
+	FinTQ
+	lg := 0
+	Si (texte[indice] <> espace) ET (texte[indice] <> TERM) ALORS
+		indice := indice + 1
+		lg     := lg + 1
+		trouvé2:= VRAI
+	Sinon
+		 trouvé2:= FAUX
+	FinTQ
+Fin
+</code>
+=== comparerMot===
+<code>
+comparerMot( Entrée             phrase             : phrase_tableau
+                         Entrée            position          : entier
+	             Entrée            longueurMot   : entier
+	             Entrée            mot    : mot_tableau
+	             Sortie             trouvé2           : booléen  )
+	// Cette procédure vérifie que le mot trouvé dans la phrase est de taille égale au mot cherché.
+           // Phrase : c'est la phrase dans laquelle on cherche un mot.
+         //  longueurMot : c'est la longueur unique pour les deux mots.
+       // mot : c'est le mot cherché
+     // trouvé2 : c'est le résultat de la comparaison entre les deux mots.
+//// Le programme est page suivante.
+VARIABLES
+k : entier // début du mot repéré
+i : entier // début du mot cherché
+reponse : booléen // Vrai si tout le mot cherché est identique
+	Début
+		TQ ( k <= long ) ET (phrase[i] = mot[k] FAIRE
+			k := k + 1
+			i := i + 1
+		FinTQ
+		SI ( k > long ) ALORS       // cette condition peut s'écrire
+			reponse := VRAI     //  reponse := (k>long)
+			reponse := FAUX
+		FinSi
+	Fin
 </code>

utilisateurs/hypathie/tutos/algo-exo-constructions-d-algorithmes-de-procedure.1417860781.txt.gz · Dernière modification: 06/12/2014 11:13 par Hypathie

Debian-facile

Différences

Pied de page des forums