Inscription / Connexion Nouveau Sujet
Niveau première
Partager :

DM de maths : Algorithme de tri

Posté par
Juliedemp
31-12-12 à 12:08

Bonjour à vous ! J'espère je vous avez passé de bonnes fêtes ! Malheureusement, vacance en premièresS ne rime pas avec ... Vacances ^^
J'ai un dm de maths à rendre et j'ai beaucoup de mal, c'est un algorithme et je n'y comprend pas grand chose .
Quelqu'un saurait-il m'aider ?
Merci d'avance 0


Enoncé :

Entrées :
Saisir n : entier naturel supérieur à 2.
Saisir une liste de réels : x1, x2, ....., xn.

Traitement :

Pour i de 1 jusqu'à n-1
j prend la valeur n.

    Tant que i<j.

         Si xj<xj-1 alors
         échanger xj et xj-1 dans la liste
         Fin si
    
    j prend la valeur j-1
    Fin Tant que

Fin Pour


Sortie
Afficher la liste x1, x2, .... , xn.

Les consignes pour ce devoir sont :
A) faire fonctionner cet algorithme.

B) Appliquer l'algorithme à d'autres liste et indiquer le rôle de cet algorythme .

Voilà

Posté par
fontaine6140
re : DM de maths : Algorithme de tri 31-12-12 à 16:07

Bonjour,
Ce programme s'appelle un bubble sort (tri en bulles).


Comme je n'aime pas introduire par le clavier des valeurs,
le programme les génère automatiquement.



1   VARIABLES
2     N EST_DU_TYPE NOMBRE
3     X EST_DU_TYPE LISTE
4     I EST_DU_TYPE NOMBRE
5     J EST_DU_TYPE NOMBRE
6     T EST_DU_TYPE NOMBRE
7   DEBUT_ALGORITHME
8     N PREND_LA_VALEUR ALGOBOX_ALEA_ENT(3,50)
9     POUR I ALLANT_DE 1 A N
10      DEBUT_POUR
11      X[I] PREND_LA_VALEUR ALGOBOX_ALEA_ENT(1,2*N)
12      FIN_POUR
13    AFFICHER "N="
14    AFFICHER N
15    POUR I ALLANT_DE 1 A N
16      DEBUT_POUR
17      AFFICHER X[I]
18      AFFICHER " "
19      FIN_POUR
20    AFFICHER " "
21    POUR I ALLANT_DE 1 A N-1
22      DEBUT_POUR
23      J PREND_LA_VALEUR N
24      TANT_QUE (I<J) FAIRE
25        DEBUT_TANT_QUE
26        SI (X[J]<X[J-1]) ALORS
27          DEBUT_SI
28          T PREND_LA_VALEUR X[J]
29          X[J] PREND_LA_VALEUR X[J-1]
30          X[J-1] PREND_LA_VALEUR T
31          FIN_SI
32        J PREND_LA_VALEUR J-1
33        FIN_TANT_QUE
34      FIN_POUR
35    POUR I ALLANT_DE 1 A N
36      DEBUT_POUR
37      AFFICHER X[I]
38      AFFICHER " "
39      FIN_POUR
40    AFFICHER " "
41  FIN_ALGORITHME

 DM  de maths : Algorithme de tri

Posté par
Juliedemp
re : DM de maths : Algorithme de tri 01-01-13 à 10:48

Bonjour à vous,
Tout d'abord merci d'avoir prit la peine de répondre !
Alors oui je ne sais pas du tout ce qu'est le tri en bulle ^^
Mais j'ai oublié de le noter, dans ma consigne il est dit de prendre n=4 et la liste : 7,3,6,1
Alors je ne comprend pas trop, et j'aimerais savoir ce que l'on fai concrètement dans des tris en bulles, enfin une explication que je comprenne ce que je fais ^^
Merci encore, à bientôt

Posté par
fontaine6140
re : DM de maths : Algorithme de tri 01-01-13 à 12:59

Bonjour,

Regarde l'image de cette page:

Posté par
Juliedemp
re : DM de maths : Algorithme de tri 01-01-13 à 13:23

Je suis désolée, mais même avec ce site, je ne comprend toujours pas . C'est vraiment très aimable de votre part en tout cas d'essayer de m'aider !
Quel est le but de cet algorithme ? Je ne comprend pas mon énoncé enfaite, et ce que représente n, ainsi que la liste ^^" !

Posté par
fontaine6140
re : DM de maths : Algorithme de tri 01-01-13 à 16:41


Es-tu capable d'ordonner (en utilisant la relation d'ordre "<" )une liste de nombres (réels)? Cela s'appelle trier par ordre croissant.

Voici une liste [7,3] de longueur 2 (il y a deux réels)
triée par ordre croissant cela donne la liste [3,7] de longueur 2
triée par ordre décroissant cela donne la liste [7,3] de longueur 2.

On travaille avec la liste [7,3,6,1] sa longueur est n?
Que vaut n?
Comment trier par ordre croissant une liste?

Etape n°1:
On compare les termes de la liste du dernier jusqu'au premier :
On prend le dernier terme de la liste (1)  que l'on compare au précédent (6)
1<6?
si oui on échange les termes 1 et 6 : la liste devient [7,3,1,6]
On le compare l'avant dernier de la liste (1) avec le précédent (3)
1<3?
si oui on échange les termes 1 et 3 : la liste devient [7,1,3,6]
On le compare l'avant avant dernier de la liste (1) avec le précédent (7)
1<7?
si oui on échange les termes 1 et 7 : la liste devient [1,7,3,6]
On a terminé l'étape n°1 car on comparé jusqu'au 1 terme:
Un chose est sûr: le plus petit est placé en première position.
le reste est dans le desordre! (une liste de longueur n-1 reste à trier)

Etape n°2
On recommence l'étape n°1 avec une liste restreinte à n-1 termes (les derniers de la liste précédente)
On doit donc comparer le dernier terme de la liste jusqu'au deuxième (le 1 er étant bien placé)
...
Etape n°3 (voir étape 2)

Une liste de longueur 1 est déjà triée:
il y a donc n-1 étapes.


J'espère que mes explications sont claires , je me peux pas faire mieux (désolé).

Posté par
Juliedemp
re : DM de maths : Algorithme de tri 01-01-13 à 16:53

Oui je crois que c'est beaucoup plus clair maintenant, merci énormément !
Je vous souhaite une excellente fin de journée, et encore une fois merci merci !!

Posté par
fontaine6140
re : DM de maths : Algorithme de tri 01-01-13 à 16:58

De rien



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1741 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !