Vous n'êtes pas identifié(e).
L'icône rouge permet de télécharger chaque page du wiki visitée au format PDF et la grise au format ODT →
Ci-dessous, les différences entre deux révisions de la page.
Les deux révisions précédentes Révision précédente Prochaine révision | Révision précédente Prochaine révision Les deux révisions suivantes | ||
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 06:57] Hypathie [Algo: exo constructions d'algorithmes de procédure] |
||
---|---|---|---|
Ligne 1: | Ligne 1: | ||
- | ======Algo: exo constructions d'algorithmes de procédure====== | + | ======Algo_méthodologie : élaboration d'une procédure ====== |
- | * Objet : S'exercer à la construction d'algorithmes de procédure | + | * Objet : Comment élaborer l'algorithme une procédure ? |
* Niveau requis : {{tag>débutant avisé}} | * Niveau requis : {{tag>débutant avisé}} | ||
* Commentaires : //Contexte d'utilisation du sujet du tuto. // | * Commentaires : //Contexte d'utilisation du sujet du tuto. // | ||
Ligne 262: | Ligne 262: | ||
====1) Moulinette (schéma de la procédure)==== | ====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 ->) | ||
1 2 3 4 5 | 6 |... | MAX | 1 2 3 4 5 | 6 |... | MAX | ||
---------------------------------- | ---------------------------------- | ||
- | | L | A | V | A | L | . | + | | L | A | V | A | L | . | |
- | + | j (indice <-|.| ) | |
+ | </code> | ||
+ | | ||
====2) Jeu d'essai==== | ====2) Jeu d'essai==== | ||
Ligne 280: | Ligne 283: | ||
|'aacab | ce n'est pas un palindrome | | |'aacab | ce n'est pas un palindrome | | ||
- | ====3) Définition des données==== | + | ====3) Définition des données du problème==== |
<code> | <code> | ||
CONSTANTES | CONSTANTES | ||
Ligne 287: | Ligne 290: | ||
TYPE | TYPE | ||
- | chaine =tableau[taille] de caractères\\ | + | chaine =tableau[taille] de caractères // type crée pour contenir une liste |
VARIABLES | VARIABLES | ||
Ligne 299: | Ligne 302: | ||
====5)Programme de test ==== | ====5)Programme de test ==== | ||
- | ====6)Algorithme de la procédure ==== | + | ====6)Algorithme de la procédure Palindrome terminé par un point==== |
+ | |||
+ | <code> | ||
+ | CONSTANTES | ||
+ | taille =80 //nombre max de caractères de la chaine | ||
+ | carterm = '.' // caractère terminateur | ||
+ | |||
+ | TYPES | ||
+ | chaîne =tableau[taille] de caractère | ||
+ | |||
+ | VARIABLES | ||
+ | phrase :chaîne //phrase dont on va déterminer la symétrie | ||
+ | i :entier //indice de parcours de la phrase par le début | ||
+ | j :entier //indice de parcours de la phrase par la fin | ||
- | <code c> | ||
Début | Début | ||
| | ||
Ligne 309: | Ligne 324: | ||
j := 1 | j := 1 | ||
| | ||
- | TantQue phrase[j] <> carterm FAIRE //arrêt sur terminateur | + | TantQue phrase[j] <> carterm FAIRE |
| | ||
- | j := j + 1 | + | j := j + 1 //arrêt car on est sur terminateur |
| | ||
FinTantQue | FinTantQue | ||
| | ||
- | //Parcours dans chaque sens | + | //Parcours par les deux bouts |
- | j := j - 1 | + | j := j - 1 |
i := 1 | i := 1 | ||
| | ||
Ligne 322: | Ligne 337: | ||
| | ||
j := i + 1 | j := i + 1 | ||
- | i := j + 1 | + | i := j - 1 |
FinTantQue | FinTantQue | ||
| | ||
Ligne 336: | Ligne 351: | ||
</code> | </code> | ||
+ | Autre solution : | ||
+ | <code> | ||
+ | CONSTANTES | ||
+ | carterm ='.' | ||
+ | |||
+ | TYPES | ||
+ | phrase =tableau[i,j] de caractères | ||
+ | |||
+ | VARIABLES | ||
+ | i : entier // indice de début du tableau | ||
+ | j : entier //indice de fin | ||
+ | resultat : booléen // VRAI si symétrie | ||
+ | |||
+ | |||
+ | Début | ||
+ | | ||
+ | //initialisation | ||
+ | i := phrase[1] | ||
+ | j := phrase[carterm - 1] | ||
+ | | ||
+ | SI (carterm) ALORS | ||
+ | lire(phrase[i,j]) | ||
+ | | ||
+ | SI (phrase[i] = phrase[j]) ALORS | ||
+ | | ||
+ | resultat = VRAI | ||
+ | |||
+ | i := i + 1 // Parcours dans les deux sens | ||
+ | j := j - 1 | ||
+ | | ||
+ | TQ (i < j) ET (resultat = VRAI) FAIRE | ||
+ | écrire("C'est un palindrome") | ||
+ | FINTQ | ||
+ | |||
+ | SINON | ||
+ | resultat = FAUX | ||
+ | écrire("Ce n'est pas un palindrome") | ||
+ | FINSI | ||
+ | |||
+ | 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] | ||
+ | |||
+ | ///////////////////////// | ||
+ | |||
+ | 1) Analyse du problème : | ||
+ | |||
+ | deux programmes : 1) crée la table de prénom | ||
+ | 2) 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> |