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 18:15] Hypathie [Exo 1 : procédure compter le nombre de caractères dans une phrase] |
utilisateurs:hypathie:tutos:algo-exo-constructions-d-algorithmes-de-procedure [06/12/2014 10:52] 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é}} | * Niveau requis : {{tag>débutant avisé}} | ||
* Commentaires : //Contexte d'utilisation du sujet du tuto. // | * Commentaires : //Contexte d'utilisation du sujet du tuto. // | ||
* Débutant, à savoir : [[:doc:systeme:commandes:le_debianiste_qui_papillonne|Utiliser GNU/Linux en ligne de commande, tout commence là !.]] :-) | * Débutant, à savoir : [[:doc:systeme:commandes:le_debianiste_qui_papillonne|Utiliser GNU/Linux en ligne de commande, tout commence là !.]] :-) | ||
- | ===== Exo 1 : procédure "compter le nombre de caractères dans une phrase" ===== | + | ===== Exo 1 : procédure "compter le nombre de caractères dans une chaîne" ===== |
- | Soit une chaîne de caractères terminée par un caractère '.'.\\ Donnez l'algorithme d'un programme qui comporte le nombre d'occurrences d'une lettre donnée ( 'a' par exemple) dans cette chaîne. | + | //**Soit une chaîne de caractères terminée par un caractère '.'.\\ Donnez l'algorithme d'un programme qui compte la longueur de cette chaîne ("." non compris).**// |
====1) Définir la procédure (la moulinette)==== | ====1) Définir la procédure (la moulinette)==== | ||
- | chaine de caractère ------->| calcul des caractères de la chaîne |------> nombre de lettres de la phrase | + | chaine de caractères ---->| calcul des caractères de la chaîne |---> nombre de lettres de la phrase |
====2) Définition des données==== | ====2) Définition des données==== | ||
Ligne 62: | Ligne 61: | ||
<code c> | <code c> | ||
- | CONSTANTE | + | CONSTANTES |
point = '.' // caractère d'arrêt | point = '.' // caractère d'arrêt | ||
| | ||
nbremax = 100 // nombre max de caractères | nbremax = 100 // nombre max de caractères | ||
| | ||
- | TYPE | + | TYPES |
chaine = tableau [n] caractere | chaine = tableau [n] caractere | ||
- | VARIABLE | + | VARIABLES |
chainedecaractere : chaine | chainedecaractere : chaine | ||
nombredelettre : entier | nombredelettre : entier | ||
- | procédure compterchainedecaractère (entrée chainedecaractère : chaine ; | + | PROCEDURES |
+ | procédure compterchainedecaractère (entrée chainedecaractère : chaine ; | ||
sortie nombredecaractère : entier) | sortie nombredecaractère : entier) | ||
Ligne 122: | Ligne 122: | ||
<note tip> | <note tip> | ||
- | Ne pas faire "parler la procédure" : elle ne fait de plus que ce qu'elle permet. | + | Ne pas faire "parler la procédure" : elle ne doit rien faire de plus que ce qu'elle permet fait dans tout programme qui l'utilisera. |
</note> | </note> | ||
===== Exo 2 : procédure "compter occurrences de deux caractères successifs" ===== | ===== Exo 2 : procédure "compter occurrences de deux caractères successifs" ===== | ||
+ | //**Rechercher si deux lettres choisies par l'utilisateur sont dans une phrase entrée par l'utilisateur.**// | ||
+ | |||
+ | ====1) Schéma de la procédure (la moulinette)==== | ||
+ | <code> | ||
+ | schéma procédure | ||
+ | | | | ||
+ | phrase ----------->|cherche si deux |------> si caractère1 ET caractère2 sont dans la phrase et successifs | ||
+ | | | alors terminateur | ||
+ | |lettres succ | deuxlettres = VRAIE | ||
+ | caractère 1 ------->| dans | | ||
+ | caractère 2 ------> | cette phrase | | ||
+ | |||
+ | </code> | ||
+ | |||
+ | ====2) Définition des données==== | ||
+ | |||
+ | <code> | ||
+ | CONSTANTES\\ | ||
+ | terminateur = '.' // caractère d'arrêt\\ | ||
+ | |||
+ | | ||
+ | TYPES\\ | ||
+ | chainetableau tableau[MAX] caractère\\ | ||
+ | |||
+ | VARIABLES\\ | ||
+ | phrase : caractère\\ | ||
+ | car1 : caractère\\ | ||
+ | car2 : caractère\\ | ||
+ | nbr : entier\\ | ||
+ | </code> | ||
+ | |||
+ | ====3) Jeu d'essai==== | ||
+ | |||
+ | ^phrase ^terminateur ^caractère1 ^caractère2 ^nombre ^ | ||
+ | |blablobli. | <nowiki>'.'</nowiki> | "l" | "r" | 0 | | ||
+ | |bonjour. | <nowiki>'.'</nowiki> | "b" | "." | 0 | | ||
+ | |blablo. | <nowiki>'.'</nowiki> | "b" | "l" | 2 | | ||
+ | |blablobli. | <nowiki>'.'</nowiki> | "b" | "l" | 3 | | ||
+ | |||
+ | | ||
+ | ====4) Interface (définir la procédure)==== | ||
+ | |||
+ | //vérifier si une phrase contient deux lettres// | ||
+ | |||
+ | PROCEDURE | ||
+ | |||
+ | <code> | ||
+ | procédure DeuxLettresID ( entrée phrase : chainetableau ;\\ | ||
+ | sortie nbreoccurrence : entier )\\ | ||
+ | |||
+ | // CompterDeuxLettres : procédure qui recherche deux lettres successives et définies extérieurement dans une phrase terminée par un point\\ | ||
+ | // phrase : phrase saisie par l'utilisateur\\ | ||
+ | //nbreoccurrence : décompte du nombre d'occurrence de mot contenant deux lettres successives\\ | ||
+ | </code> | ||
+ | ''chainetableau'' : c'est le type créé\\ | ||
+ | |||
+ | ====5) Programme de test==== | ||
+ | <code c> | ||
+ | CONSTANTES | ||
+ | max = 100 | ||
+ | |||
+ | TYPES | ||
+ | chaine tableau[MAX] caractère | ||
+ | |||
+ | VARIABLES | ||
+ | phrase : chaine | ||
+ | lettre 1 : caractère | ||
+ | lettre 2 : caractère | ||
+ | nbreoccurrence : entier | ||
+ | |||
+ | |||
+ | début | ||
+ | |||
+ | écrire ("entrez une phrase terminée par un point") | ||
+ | |||
+ | lire (phrase) | ||
+ | |||
+ | écrire ("entrez une première lettre") | ||
+ | |||
+ | lire (lettre 1) | ||
+ | |||
+ | écrire ("entrez une deuxième lettre") | ||
+ | |||
+ | lire (lettre 2) | ||
+ | |||
+ | DeuxLettresID ( entrée phrase : chainetableau , sortie nbreoccurrence : entier ) | ||
+ | | ||
+ | écrire ("le nombre d'occurrences des lettres choisies dans la phrase donnée est", nbreoccurrence") | ||
+ | |||
+ | fin | ||
+ | </code> | ||
+ | |||
+ | ====6) Procédure compter deux lettres==== | ||
+ | |||
+ | <code c> | ||
+ | CompterDeuxLettres( lettre phrase chaine | ||
+ | entrée | ||
+ | car1 : caractère | ||
+ | car2 : caractère | ||
+ | FIN : caractère | ||
+ | sortie occurrence : entier | ||
+ | |||
+ | VARIABLE | ||
+ | |||
+ | i : entier | ||
+ | occurrence : 0 | ||
+ | |||
+ | début | ||
+ | |||
+ | i := 1 | ||
+ | occurrence := 0 | ||
+ | |||
+ | tantque (phrase [i] <> FIN) | ||
+ | |||
+ | si (phrase[i] = car1) | ||
+ | |||
+ | si (phrase [i + 1] = car2 | ||
+ | |||
+ | occurrence + 1 | ||
+ | |||
+ | finsi | ||
+ | |||
+ | finsi | ||
+ | |||
+ | i := i + 1 | ||
+ | | ||
+ | fintantque | ||
+ | |||
+ | fin | ||
+ | |||
+ | </code> | ||
===== Exo 3 : procédure "rechercher un palindrome" ===== | ===== Exo 3 : procédure "rechercher un palindrome" ===== | ||
+ | //**Procédure pour déterminer si une chaîne de caractère terminée par un point est un palindrome.**// | ||
+ | ====1) Moulinette (schéma de la procédure)==== | ||
+ | |||
+ | chaîne. ---> | recherche palindrome | ---> palindr : booléen (Vrai ou FAUX) | ||
+ | |||
+ | <code> | ||
+ | i (indice ->) | ||
+ | 1 2 3 4 5 | 6 |... | MAX | ||
+ | ---------------------------------- | ||
+ | | L | A | V | A | L | . | | ||
+ | j (indice <-|.| ) | ||
+ | </code> | ||
+ | | ||
+ | ====2) Jeu d'essai==== | ||
+ | |||
+ | ^ ^ ^ | ||
+ | | '.' | c'est un palindrome | | ||
+ | | 'a.' | c'est un palindrome | | ||
+ | |'aa.' | c'est un palindrome | | ||
+ | | 'aba.' | c'est un palindrome | | ||
+ | | 'acb' | ce n'est pas un palindrome | | ||
+ | | 'aacba.'| ce n'est pas un palindrome | | ||
+ | |'aacab | ce n'est pas un palindrome | | ||
+ | |||
+ | ====3) Définition des données du problème==== | ||
+ | <code> | ||
+ | CONSTANTES | ||
+ | taille =80 //nombre max de caractères de la chaîne | ||
+ | carterm ='.' // caractère terminaleur de la chaîne | ||
+ | |||
+ | TYPE | ||
+ | chaine =tableau[taille] de caractères // type crée pour contenir une liste | ||
+ | |||
+ | VARIABLES | ||
+ | phrase : chaine // phrase où une symétrie est recherchée | ||
+ | i : entier // | ||
+ | j : entier // indice de parcours de la phrase depuis la fin. | ||
+ | </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. | ||
+ | constanteFIN ='.' // caractère terminaleur de la chaîne (Un tableau peut ne pas être tout rempli) | ||
+ | |||
+ | TYPES | ||
+ | Type chaine =tableau[MAX] de caractères // type crée pour contenir une liste | ||
+ | |||
+ | VARIABLES | ||
+ | variable phrase : chaine // phrase où une symétrie est recherchée | ||
+ | variable i : entier // | ||
+ | variable j : entier // indice de parcours de la phrase depuis la fin. | ||
+ | |||
+ | PROCEDURES | ||
+ | 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 | ||
+ | |||
+ | Début | ||
+ | // Saisie de la phrase : | ||
+ | ECRIRE ('Entrez votre phrase et n'oubliez pas de la terminer par un point.' | ||
+ | LIRE(phrase) | ||
+ | i := palindrome[1] | ||
+ | j := palindrome[MAX-1 | ||
+ | |||
+ | // Recherche d'un palindrome fini par un point : | ||
+ | cherchePalinPoint(entrée phrase:chaine , entrée/sortie i:entier, entrée/sortie j:entier) | ||
+ | SI i >= j ALORS | ||
+ | ECRIRE('La phrase', phrase 'est un palindrome.') | ||
+ | SINON | ||
+ | ECRIRE('La phrase', phrase 'n'est pas un palindrome.') | ||
+ | FINSI | ||
+ | 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) | ||
+ | // 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 | ||
+ | |||
+ | TERM : '.' : caractère | ||
+ | |||
+ | |||
+ | début | ||
+ | i := chaine[1] | ||
+ | j := chaine[TERM - 1] | ||
+ | |||
+ | SI chaine[i] < chaine[j] | ||
+ | TQ (i < j et chaine[i] = chaine[j]) | ||
+ | i := i + 1 | ||
+ | j := j - 1 | ||
+ | FinTQ | ||
+ | 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> |