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 [29/11/2014 19:44]
Hypathie [Exo 3 : procédure rechercher un palindrome]
+++ utilisateurs:hypathie:tutos:algo-exo-constructions-d-algorithmes-de-procedure [06/12/2014 11:13]
Hypathie [Exo 3 : procédure rechercher un palindrome]
@@ Ligne 1: / Ligne 1: @@
-======Algo: exo constructions d'algorithmes de procédure======
+======algo-exo-constructions-d-algorithmes-de-procedure======
-  * Objet : S'exercer à la construction d'algorithmes de procédure
+  * Objet : Comment élaborer l'algorithme une procédure ?
   * Niveau requis :  {{tag>débutant avisé}}
   * Commentaires : //Contexte d'utilisation du sujet du tuto. //
@@ Ligne 262: / Ligne 262: @@
 ====1) Moulinette (schéma de la procédure)====
-chaîne ---> | recherche palindrome | ---> palindr : booléen (Vrai ou FAUX)
+chaîne. ---> | recherche palindrome | ---> palindr : booléen (Vrai ou FAUX)
-i : indice
+<code>
+i (indice ->)
    2   3   4   5 | 6 |... | MAX
 ----------------------------------
-| L | A | V | A | L | .
+| L | A | V | A | L | . |
+        j (indice <-|.| )
+</code>
 ====2) Jeu d'essai====
@@ Ligne 280: / Ligne 283: @@
 |'aacab   | ce n'est pas un palindrome |
-====3) Définition des données====
+====3) Définition des données du problème====
 <code>
 CONSTANTES
@@ Ligne 287: / Ligne 290: @@
 TYPE
-chaine =tableau[taille] de caractères\\
+chaine =tableau[taille] de caractères // type crée pour contenir une liste
 VARIABLES
@@ Ligne 295: / Ligne 298: @@
 </code>
 ====4)Interface (notice) de la procédure ====
+<code>
+procédure cherchePalinPoint(entrée         texte : chaine,
+                            entrée sortie  ind1  : entier, ind2 : entier)
+          // Cette procédure permet de dire si une chaine de caractère terminée par un point est un palindrome.
+          // ind1 : c'est l'indice de parcours du texte par le début
+          // ind2 : c'est l'indice de parcours du texte par la fin
+</code>
 ====5)Programme de test ====
+<code>
+CONSTANTES
+constante MAX =80 //nombre max de caractères de la chaîne (Pour pouvoir créer le type chaine, car un tableau est toujours de taille fixe.
+constante FIN ='.' // caractère terminaleur de la chaîne (Un tableau peut ne pas être tout rempli)
-====6)Algorithme de la procédure ====
+TYPES
+Type chaine =tableau[MAX] de caractères // type crée pour contenir une liste
-<code c>
+VARIABLES
-  Début
+variable possPalin : chaine // phrase où une symétrie est recherchée
+variable indiceDeb : entier //
-    écrire('Donnez une phrase."
+variable indiceFin : entier // indice de parcours de la phrase depuis la fin.
-    lire(phrase)
+PROCEDURES
-    j := 1
+procédure cherchePalinPoint(entrée         texte : chaine,
+                            entrée sortie  ind1  : entier, ind2 : entier
-    TantQue  phrase[j] <> carterm FAIRE //arrêt sur terminateur
+                            sortie result : booléen)
+          // Cette procédure permet de dire si une chaine de caractère terminée par un point est un palindrome.
-          j := j + 1
+          // ind1 : c'est l'indice de parcours du texte par le début
+          // ind2 : c'est l'indice de parcours du texte par la fin
-    FinTantQue
+Début
-    //Parcours dans chaque sens
+     // Saisie de la phrase :
-    j := j - 1
+     ECRIRE ('Entrez votre phrase et n'oubliez pas de la terminer par un point.'
-    i := 1
+     LIRE(phrase)
+     indiceDeb := possPalin[1]
-    TantQue (i<j) ET (phrase[i] = phrase[j]) FAIRE
+     indiceFin := possPalin[MAX-1]
+     result    := booléen
-        j := i + 1
-        i := j + 1
+    // Recherche d'un palindrome fini par un point :
-    FinTantQue
+    cherchePalinPoint(entrée possPalin:chaine , entrée/sortie ind1:entier, entrée/sortie ind2:entier, sortie result:bool)
+    SI result = VRAI
-    //Affichage du résultat
+        ECRIRE('La phrase', possPalin 'est un palindrome.')
-    SI i >= j ALORS // Fin du parcours
-       écrire("C'est un palindrome")
     SINON
-       ecrire("Ce n'est pas un palindrome")
+        ECRIRE('La phrase', possPalin 'n'est pas un palindrome.')
-    FinSI
+    FINSI
+Fin
-  Fin
 </code>
+====6)Algorithme de la procédure Palindrome terminé par un point====
+<code>
+procédure cherchePalinPoint(entrée         texte : chaine,
+                            entrée sortie  ind1  : entier, ind2 : entier
+                            sortie result: booléen)
+          // Cette procédure permet de dire si une chaine de caractère terminée par un point est un palindrome.
+          // ind1 : c'est l'indice de parcours du texte par le début
+          // ind2 : c'est l'indice de parcours du texte par la fin
+CONSTANTE
+MAX : 80
+TYPE chaine = tableau[MAX] de caractères
+VARIABLES
+i    : entier
+j    : entier
+palindrome : booléen
+TERM : '.' : caractère
+ début
+  i := chaine[1]
+  j := chaine[TERM - 1]
+    SI chaine[i] < chaine[j] ALORS
+    palindrome := VRAI
+      TQ (i < j) ET chaine[i] = chaine[j])
+	 i := i + 1
+	 j := j - 1
+      FinTQ
+    SINON
+         palindrome := FAUX
+    FINSI
+ fin
+</code>
+=====Recherche dichotomique =====
+VOIR les tris :[[http://axiomcafe.fr/tri-dans-un-tableau]]
+<code>
+// recherche dichotomique
+GENERALITE
+méthode de recherche par dichotomie : exemple
+i  |	a	|	b	|	c	|	d	|	e	| ...| j
+i = début
+j = fin
+milieu = tab(i[1] + i[n]) / 2
+	si cible > milieu alors
+	   cible est à chercher sur tab[milieu][j]
+	si cible < milieu  alors
+	   cible est à chercher sur tab[i][j]
+/////////////////////////
+) Analyse du problème :
+   deux programmes : 1) crée la table de prénom
+) chercher un prenom dans la table
+       entrée            Faire_table         sortie                     prénom cherché
+---------------------------------------------------------------------------------------------------------
+                       |  enregistre       |                           |
+les prénoms            |  et numérote      |-> une table               | résultat : prénom dans la table
+                       |  les prénoms      |   de prenoms numérotés    |            ou
+                       |   entrés          |    (max 10)               |            pas dans la table
+----------------------------------------------------------------------------------------------------------
+////////////////////////////////////////////////////////////////////
+PROGRAMME crée la table de prénom et enregister le prenom recherché
+/////////////////////////////////////////////////////////////////////
+On sait que la taille de la table de prénom est égale au nombre de prénoms entrés
+CONSTANTES
+nombre_de_prenom = 10 // taille max de la table
+taille_prenom = 15 // taille max d'un prenom
+TYPE
+prenom =tableau[nombre_de_prenom] de caractère
+table =tableau[nombre_de_prenom] de prenom
+VARIABLES
+i                : entier // compteur de prénoms entrée
+nombre_de_prenom : entier // Nombre de prenoms entrés par l'utilisateur
+table_prenom     : table de prenom
+prenom           : prenom  // prénom cherché
+resultat         : entier
+début
+    i := 0 // Pas encore de prénom entrés
+    écrire("combien de prenom ?")
+    lire(nombre_de_prenom)
+    TANTQUE ( i < nombre_de_prenom ) FAIRE
+            i := i + 1
+            écrire(Entrez un prénom, svp.)
+            lire( table_prenom[i] )
+    FINTANTQUE
+   // enregistrer le prénom à chercher
+   ecrire(Pour quel nom voulez-vous l'indice ?)
+   lire(prenom)
+   //appel procédure cherche_prenom
+   chercher_prenom(table , nombre_de_prenom, prenom , resultat)
+   SI resultat = 0 ALORS
+      écrire ("Le prénom n'est pas dans la liste")
+   SINON
+      écrire ("Le prénom est dans la table au n° ", resultat)
+fin
+//////////////////////////////////////////////////////////////////////
+Programme chercher le prénom
+/////////////////////////////////////////////////////////////////////
+VARIABLES
+indice_début : entier // Début de table de prénom
+indice_fin   : entier // fin de la table de prénom
+indice_moyen : entier // milieu de la table de prénom
+TYPE
+prenom =tableau[nombre_de_prenom] de caractère
+table =tableau[nombre_de_prenom] de prenom
+procédure chercher_prenom(entrée tableEnregistrée :table
+                          entrée taille :entier
+                          entrée prenom_cherché :prenom
+                          sortie indice : entier)
+                     // taille c'est place du prénom par rapport à la taille totale de la table de prénom
+                     // cible c'est le n° du prenom dans la table de prénom
+ début
+     indice_début := 1
+     indice_fin   := taille
+     cible        := (indice_début + indice_fin) DIV 2
+      TANTQUE (indice_début < indice_fin) ET (table [cible] <> prenom_cherché) FAIRE
+           SI tableEnregistrée[cible] > prenom_cherché ALORS
+               indice_fin = cible - 1 //du milieu à la fin de la table de prénom
+           SINON
+                indice_début := cible + 1 //du début jusqu'au milieu de la table de prénom
+           FINSI
+           cible := (indice_début + indice_fin) DIV 2
+       FINTANTQUE
+       SI (indice_début > indice_fin ) OU ( table [cible] <> prenom_cherché) ALORS
+          cible := 0
+       FINSI
+ fin
+</code>

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

Debian-facile

Différences

Pied de page des forums