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 [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 16:15] Hypathie [Trier un tableau par remontée des bulles] |
||
---|---|---|---|
Ligne 391: | Ligne 391: | ||
=====Trier un tableau par remontée des bulles ===== | =====Trier un tableau par remontée des bulles ===== | ||
+ | |||
+ | |||
+ | ===1) Définition du problème=== | ||
<code> | <code> | ||
- | //exo: tri par remontée des bulles | + | | | |
+ | liste chiffre---> | |----> liste de chiffre | ||
+ | (désordonnée) | | (ordonnée) | ||
+ | </code> | ||
- | I] Procédure "remplir" | ||
- | Procédure remplir ( sortie tab_désordonné : les_chiffres_donnés, | + | ===2) Jeu d'essai=== |
- | sortie tableau_donné : entier ) | + | <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 chiffresOrdonnés: table // Table d'entiers ordonné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 chiffresOrdonnés: table // Tables d'entiers ordonné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 remplir | ||
+ | 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> | ||
+ | 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 | ||
+ | |||
+ | variable | ||
+ | i : entier // indice de parcours du tableau. | ||
+ | cible : entier // variable permettant l'inversion de 2 entiers dans le tableau. | ||
+ | comptinversion : entier // Comptage des inversions | ||
+ | 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 de la case n°1 du tableau supérieur à | ||
+ | // celui de la case n°2 du même tableau alors | ||
+ | |||
+ | |||
+ | cible = table[1] // | ||
+ | table[1] = table[i + 1] // inversion | ||
+ | table[i+1] = cible // | ||
+ | invert := VRAI | ||
+ | |||
+ | Finsi | ||
+ | i := i + 1 // incrémentation pour passer aux entiers suivants. | ||
+ | Fintantque | ||
+ | Jusquà NON invert | ||
+ | |||
+ | Fin | ||
+ | </code> | ||
+ | |||
+ | ====6 bis) Interfaces et programmes des procédures utilisées par le programme principal==== | ||
+ | |||
+ | ===I] Procédure "remplir"=== | ||
+ | <code> | ||
+ | //exo: tri par remontée des bulles | ||
+ | CONSTANTES | ||
+ | constante MAX = 80 // Taille maximal de la table de chiffres | ||
+ | |||
+ | Procédure remplir ( entrée taille_tableau_donné : entier | ||
+ | entrée/sortie ind : entier | ||
+ | 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. | // 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 415: | Ligne 549: | ||
// 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"=== |
- | II] procédure "afficher" | + | <code> |
- | + | Procédure affichage ( entrée table_utilisateur : listechiffre, entrée taille_table : entier ) | |
- | Procédure affichage ( entrée table_utilisateur : listechiffre, entrée taille_tableaffichage : 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. | ||
- | |||
- | |||
Variables | Variables | ||
nombre_chiffre_affichage : entier // compte le nombre de chiffres rentré par l'utilisateur. | nombre_chiffre_affichage : entier // compte le nombre de chiffres rentré par l'utilisateur. | ||
- | Début | + | Début |
nombre_chiffre_affichage := 1 | nombre_chiffre_affichage := 1 | ||
Ligne 464: | Ligne 600: | ||
Fintantque | Fintantque | ||
- | 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]] |