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 Les deux révisions suivantes | ||
|
utilisateurs:hypathie:tutos:algo-exo-constructions-d-algorithmes-de-procedure [06/12/2014 12:12] Hypathie [Trier un tableau par remontée des bulles] |
utilisateurs:hypathie:tutos:algo-exo-constructions-d-algorithmes-de-procedure [06/12/2014 13:23] Hypathie [Trier un tableau par remontée des bulles] |
||
|---|---|---|---|
| Ligne 392: | Ligne 392: | ||
| =====Trier un tableau par remontée des bulles ===== | =====Trier un tableau par remontée des bulles ===== | ||
| + | |||
| + | ===1) Définition du problème=== | ||
| + | |||
| + | <code> | ||
| + | | | | ||
| + | liste désordonnée de chiffre---> | |----> liste ordonnés par ordre croissant | ||
| + | | | | ||
| + | </code> | ||
| + | |||
| + | |||
| + | ===2) Jeu d'essai=== | ||
| + | <code> | ||
| + | Entrée sortie | ||
| + | ------------------------------------ | ||
| + | rien rien | ||
| + | 5 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 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 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 saisie | ||
| + | procédure triBulle | ||
| + | procédure affichage | ||
| + | |||
| + | |||
| + | Début | ||
| + | saisie(chiffresDesordo, nbrchiffre, taille) // appel de la procédure saisie | ||
| + | triBulle(chiffresDesordo, taille) // appelle de la procédure triBulle | ||
| + | affichage(chiffreOrdonnés, taille) // 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** est la liste de chiffres désordonnés rentrée par | ||
| + | l'utilisateur ainsi que la liste de chiffres triés en sortie. | ||
| + | // **taille** est le nombre de chiffres rentrés par l'utilisateur. | ||
| + | // **invert** est vrai quand il y a eu inversion | ||
| + | |||
| + | </code> | ||
| + | ===6) Algorithme de la procédure TrieBulle=== | ||
| + | |||
| + | <code> | ||
| + | variable | ||
| + | i : entier // indice de parcours du tableau. | ||
| + | cible : entier // variable permettant l'inversion de 2 entiers dans le tableau. | ||
| + | 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 "1 " du tableau | ||
| + | //est supérieur à l'entier "2" | ||
| + | // suivant dans le tableau alors. | ||
| + | |||
| + | cible = table[1] | ||
| + | table[1] = table[i + 1] | ||
| + | table[i+1] = cible | ||
| + | invert := VRAI | ||
| + | |||
| + | Finsi | ||
| + | i := i + 1 // incrémentation pour passer aux entiers suivants. | ||
| + | Fintantque | ||
| + | Jusquà invert = faux | ||
| + | |||
| + | Fin | ||
| + | </code> | ||
| + | |||
| + | ===6 bis) Interfaces et programmes des procédures utilisées par le programme principal=== | ||
| <code> | <code> | ||
| //exo: tri par remontée des bulles | //exo: tri par remontée des bulles | ||
| Ligne 443: | Ligne 552: | ||
| II] procédure "afficher" | II] procédure "afficher" | ||
| - | Procédure affichage ( entrée table_utilisateur : listechiffre, entrée taille_tableaffichage : entier ) | + | Procédure affichage ( entrée table_utilisateur : listechiffre, entrée taille_table : entier ) |
| // La procédure permet l'affichage du tableau de chiffre de l'utilisateur et le tableau trié | // La procédure permet l'affichage du tableau de chiffre de l'utilisateur et le tableau trié | ||
| // table_utilisateur est la table de chiffre rentré par l'utilisateur. | // table_utilisateur est la table de chiffre rentré par l'utilisateur. | ||
| - | //liste_chiffre est le type crée (un tableau) | + | //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. | ||
| Ligne 465: | Ligne 574: | ||
| Fin | Fin | ||
| + | </code> | ||
| - | // III] procédure tribulle | ||
| - | |||
| - | Procédure tribulle ( entrée/sortie tablechiffre :liste_chiffres, | ||
| - | entrée tailletablebulle : entier ) | ||
| - | // **la procédure du tri des bulles** permet de ranger une chaîne de chiffres | ||
| - | //désordonnés en ordre croissant. | ||
| - | // **tablechiffre** est la liste de chiffres désordonnés rentrée par | ||
| - | l'utilisateur ainsi que la liste de chiffres triés en sortie. | ||
| - | // **tailletable** est le nombre de chiffres rentrés par l'utilisateur. | ||
| - | |||
| - | Variables | ||
| - | |||
| - | i : entier // indice de parcours du tableau. | ||
| - | cible : entier // variable permettant l'inversion de 2 entiers dans le tableau. | ||
| - | invert : booléen | ||
| - | Début | ||
| - | |||
| - | // parcours jusqu'à qu'il n'y est plus aucune inversion. | ||
| - | |||
| - | |||
| - | i := 1 | ||
| - | invert := FAUX | ||
| - | | ||
| - | Répéter | ||
| - | |||
| - | Tantque ( i < tailletablebulle ) faire | ||
| - | |||
| - | Si tablechiffre [i] > tablechiffre [ i + 1 ] alors // si l'entier "1 " du tableau | ||
| - | //est supérieur à l'entier "2" | ||
| - | // suivant dans le tableau alors. | ||
| - | |||
| - | cible = tablechiffre[1] | ||
| - | tablechiffre[1] = tablechiffre[i + 1] | ||
| - | tablechiffre[i+1] = cible | ||
| - | invert := VRAI | ||
| - | |||
| - | Finsi | ||
| - | |||
| - | i := i + 1 // incrémentation pour passer aux entiers suivants. | ||
| - | Fintantque | ||
| - | |||
| - | Jusquà invert = faux | ||
| - | |||
| - | Fin | ||
| - | </code> | ||
| =====Recherche dichotomique ===== | =====Recherche dichotomique ===== | ||
| VOIR les tris :[[http://axiomcafe.fr/tri-dans-un-tableau]] | VOIR les tris :[[http://axiomcafe.fr/tri-dans-un-tableau]] | ||
