Debian
Debian-France
Debian-Facile
Debian-fr.org
Forum-Debian.fr
Debian ?
Communautés
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 | ||
|
utilisateurs:hypathie:tutos:algo-exo-constructions-d-algorithmes-de-procedure [06/12/2014 13:23] Hypathie [Trier un tableau par remontée des bulles] |
utilisateurs:hypathie:tutos:algo-exo-constructions-d-algorithmes-de-procedure [06/12/2014 17:08] (Version actuelle) Hypathie [Recherche dichotomique] |
||
|---|---|---|---|
| Ligne 397: | Ligne 397: | ||
| <code> | <code> | ||
| | | | | | | ||
| - | liste désordonnée de chiffre---> | |----> liste ordonnés par ordre croissant | + | liste chiffre---> | |----> liste de chiffre |
| - | | | | + | (désordonnée) | | (ordonnée) |
| </code> | </code> | ||
| Ligne 422: | Ligne 422: | ||
| VARIABLES | VARIABLES | ||
| variable chiffresDesordo : table //Table d'entiers désordonnés | 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 nbrchiffre : entier // Nombres de chiffres | ||
| variable taille : entiers // Taille de la table de chiffres désordonnés en entrée | variable taille : entiers // Taille de la table de chiffres désordonnés en entrée | ||
| Ligne 438: | Ligne 439: | ||
| VARIABLES | VARIABLES | ||
| variable chiffresDesordo : table //Table d'entiers désordonnés | 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 nbrchiffre : entier // Nombres de chiffres | ||
| variable taille : entiers // Taille de la table de chiffres désordonnés en entrée | variable taille : entiers // Taille de la table de chiffres désordonnés en entrée | ||
| // et ordonnée en sortie | // et ordonnée en sortie | ||
| PROCEDURES | PROCEDURES | ||
| - | procédure saisie | + | procédure remplir ( entrée taille_tableau_donné : entier |
| - | procédure triBulle | + | entrée/sortie ind : entier |
| - | procédure affichage | + | 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 | Début | ||
| saisie(chiffresDesordo, nbrchiffre, taille) // appel de la procédure saisie | saisie(chiffresDesordo, nbrchiffre, taille) // appel de la procédure saisie | ||
| - | triBulle(chiffresDesordo, taille) // appelle de la procédure triBulle | + | triBulle(taille, chiffresDesordo) // appelle de la procédure triBulle |
| - | affichage(chiffreOrdonnés, taille) // appelle de la procédure affichage | + | affichage(taille, chiffreOrdonnés) // appelle de la procédure affichage |
| Fin | Fin | ||
| Ligne 461: | Ligne 488: | ||
| entrée/sortie chiffreOrdonnés : table) | entrée/sortie chiffreOrdonnés : table) | ||
| - | // **la procédure du tri des bulles** permet de ranger une chaîne de chiffres | + | // La procédure du tri des bulles permet de ranger une chaîne de chiffres |
| //désordonnés en ordre croissant. | //désordonnés en ordre croissant. | ||
| - | // **chiffresDesordo** est la liste de chiffres désordonnés rentrée par | + | // 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. | l'utilisateur ainsi que la liste de chiffres triés en sortie. | ||
| - | // **taille** est le nombre de chiffres rentrés par l'utilisateur. | + | // taille : C'est le nombre de chiffres rentrés par l'utilisateur. |
| - | // **invert** est vrai quand il y a eu inversion | + | |
| </code> | </code> | ||
| ===6) Algorithme de la procédure TrieBulle=== | ===6) Algorithme de la procédure TrieBulle=== | ||
| <code> | <code> | ||
| - | variable | + | procédure tribulle( entrée taille : entier |
| - | i : entier // indice de parcours du tableau. | + | entrée/sortie chiffresDesordo : table |
| - | cible : entier // variable permettant l'inversion de 2 entiers dans le tableau. | + | entrée/sortie chiffreOrdonnés : table) |
| - | invert : booléen // Permet de déterminé s'il y a ou non inversion | + | // 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 | Début | ||
| Ligne 483: | Ligne 518: | ||
| Répéter | Répéter | ||
| Tantque ( i < taille ) faire | Tantque ( i < taille ) faire | ||
| - | SI table[i] > table[ i + 1 ] ALORS // si l'entier "1 " du tableau | + | SI table[i] > table[ i + 1 ] ALORS // si l'entier de la case n°1 du tableau supérieur à |
| - | //est supérieur à l'entier "2" | + | // celui de la case n°2 du même tableau alors |
| - | // suivant dans le tableau alors. | + | |
| - | cible = table[1] | + | cible = table[1] // |
| - | table[1] = table[i + 1] | + | table[1] = table[i + 1] // inversion |
| - | table[i+1] = cible | + | table[i+1] = cible // |
| invert := VRAI | invert := VRAI | ||
| Finsi | Finsi | ||
| - | i := i + 1 // incrémentation pour passer aux entiers suivants. | + | i := i + 1 // incrémentation pour passer aux entiers suivants. |
| Fintantque | Fintantque | ||
| - | Jusquà invert = faux | + | Jusquà NON invert |
| Fin | Fin | ||
| </code> | </code> | ||
| - | ===6 bis) Interfaces et programmes des procédures utilisées par le programme principal=== | + | ====6 bis) Interfaces et programmes des procédures utilisées par le programme principal==== |
| + | |||
| + | ===I] Procédure "remplir et afficher tableau désordonné"=== | ||
| <code> | <code> | ||
| //exo: tri par remontée des bulles | //exo: tri par remontée des bulles | ||
| + | CONSTANTES | ||
| + | constante MAX = 80 // Taille maximal de la table de chiffres | ||
| - | I] Procédure "remplir" | + | Procédure remplir ( entrée taille_tableau_donné : entier |
| - | + | entrée/sortie ind : entier | |
| - | Procédure remplir ( sortie tab_désordonné : les_chiffres_donnés, | + | entrée/sortie chiffre_donnés : entier |
| - | sortie tableau_donné : entier ) | + | sortie liste_désordonnée : table |
| - | + | ||
| // La procédure remplir permet de récupérer les données saisies par l'utilisateur. | // La procédure remplir permet de récupérer les données saisies par l'utilisateur. | ||
| - | // les_chiffres_donnés : c'est la table de chiffres rentrés par l'utilisateur. | + | // chiffres_donnés : compteur de chiffres entrés |
| - | // taille_tableau_donné : c'est la taille de la table. | + | // 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 | Variables | ||
| - | taille_finale : entier // nombre de tous les chiffres rentrés par l'utilisateur. | + | 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 | + | chiffre_donnés : entier // les chiffres rentrés par l'utilisateur pour mettre |
| - | //quelque chose dans la tableau | + | //quelque chose dans le tableau |
| - | //(l'utilisateur ne rentre pas forcément 80 chiffres) | + | //(l'utilisateur ne rentre pas forcément 80 chiffres) |
| + | ind : entier // indice de parcours de table | ||
| + | liste_désordonnée : table | ||
| Début | Début | ||
| Ligne 524: | Ligne 570: | ||
| // l'utilisateur rentre la taille de la table d'entier et ses valeurs. | // l'utilisateur rentre la taille de la table d'entier et ses valeurs. | ||
| - | Répéter | + | Répéter |
| - | Ecrire ( 'Quel sera le nombre de nombres à trier?' ) // taille du tableau à trier | + | Ecrire ( 'Quel sera le nombre de nombres à trier?' ) // taille du tableau à trier |
| //( sup à 0 , | //( sup à 0 , | ||
| // non égal à 1, | // non égal à 1, | ||
| // stric inf à 80) | // stric inf à 80) | ||
| - | Lire ( taille_finale ) | + | Lire ( taille_finale ) |
| - | Jusquà ( taille_finale >= 0 ) et ( taille_finale < = MAX ) | + | Jusquà ( taille_finale >= 0 ) et ( taille_finale < = MAX ) |
| - | Ecrire ( "Vous allez entrer", taille_finale, "chiffres" ) | + | Ecrire ('Saisissez le chiffre n°)', ind ) |
| // remplir le tableau | // remplir le tableau | ||
| - | chiffre_donnés := 1 // initialisation l'utilisateur n'a pas encore donné ses chiffres à trier | + | 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 | + | Tantque (chiffre_donnés <= taille_finale) Faire |
| - | Ecrire ( 'Veuillez donner un autre entier" ) // on demande ensuite les entiers à l'utilisateur | + | Ecrire ('Veuillez donner un entier') // on demande ensuite les entiers à l'utilisateur |
| - | // pour chaque case du tableau. | + | // pour chaque case du tableau. |
| - | Lire ( taille_finale [ chiffre_donnés ] ) | + | |
| - | chiffre_donnés := chiffre_donnés + 1 // Incrémentation pour mettre les autres | + | Lire (liste_désordonnée[ind]) |
| - | //entiers dans le tableau. | + | chiffre_donnés := chiffre_donnés + 1 // Incrémentation pour mettre les autres |
| - | Fintantque | + | //entiers dans le tableau. |
| + | ind := ind + 1 | ||
| + | Fintantque | ||
| + | ecrire('Voici la liste des chiffres que vous avez entré',(liste_désordonnée[i]) | ||
| Fin | Fin | ||
| + | </code> | ||
| - | /////////////////////////////////////////////////////////////////////// | + | ===II] procédure "afficher tableau ordonné"=== |
| - | II] procédure "afficher" | + | <code> |
| + | Procédure affichage_tableau_ordonné ( entrée table_Rangée : table | ||
| + | entrée taille_table : entier) | ||
| + | | ||
| - | Procédure affichage ( entrée table_utilisateur : listechiffre, entrée taille_table : entier ) | + | // La procédure permet l'affichage du tableau trié |
| - | + | // table_Rangée est la table de chiffres ordonnés. | |
| - | // La procédure permet l'affichage du tableau de chiffre de l'utilisateur et le tableau trié | + | // table est le type crée (un tableau) |
| - | // table_utilisateur est la table de chiffre rentré par l'utilisateur. | + | |
| - | //listechiffre est le type crée (un tableau) | + | |
| // taille_table définie la taille de la table. | // taille_table définie la taille de la table. | ||
| + | Type listeChiffre | ||
| - | + | Variable taille_table : entier // compte le nombre de chiffres rentré par l'utilisateur. | |
| - | Variables | + | |
| - | nombre_chiffre_affichage : entier // compte le nombre de chiffres rentré par l'utilisateur. | + | |
| - | Début | + | Début |
| - | nombre_chiffre_affichage := 1 | + | Ecrire ( "le tableau rangé est ",table_Rangée[taille_table]) |
| - | + | Fin | |
| - | Tantque ( nombre_chiffre_affichage <= taille_tableaffichage ) Faire | + | |
| - | Ecrire ( ",liste_chiffre, [",nombre_chiffre_affichage," ] = ",taille_table [nombre_chiffre_affichage] ) | + | |
| - | nombre_chiffre_affichage := nombre_chiffre_affichage + 1 | + | |
| - | Fintantque | + | |
| - | + | ||
| - | Fin | + | |
| </code> | </code> | ||
| Ligne 724: | Ligne 769: | ||
| fin | 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> | </code> | ||
