[PDF] Tri par sélection du maximum [tr04] Examen de synth`ese

View - Download Tri par sélection du maximum [tr04] Examen de synth`ese

Previous PDF

Next PDF

Tri par selection du maximum [tr04]

Examen de synthese

Karine Zampieri, Stephane Riviere

UniscielalgoprogVersion 21 mai 2018

Table des matieres

1 Tri par selection du maximum (7 points)

2

1.1 Representation des donnees(2 points). . . . . . . . . . . . . . . . . . .2

1.2 Tri par selection du maximum(3.5 points). . . . . . . . . . . . . . . .3

1.3 Test(1.5 point). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5

2 References generales

6

Java - Tri par selection du maximum (Solution)Mots-ClesAlgorithmes de tris et rangs, Tri par selection

RequisAxiomatique imperative (sauf Fichiers)

Diculte• ◦ ◦(30 min)Objectif

Cet exercice realise le tri par selection du maximum d'un tableau de reels. 1 Unisciel algoprog { Tri par selection du maximum [tr04]2

1 Tri par selection du maximum (7 points)

1.1 Representation des donnees (2 points)(0.5 point)Denissez la constanteTMAX=200(nombre maximum de valeurs), eventuel-

lement le typeTabValeurscomme etant un tableau deTMAXreels, puis le typeValeurs, structure incluant : •UnTabValeurst memorisant les valeurs.

•Un entiernrepresentant le nombre eectif de valeurs stockees dans le tableau.Validez vos denitions avec la solution.

Solution Java@[pgtrselmax.java]/**

Taille

maximale des tableaux final static int TMAX= 200; /** Type

Valeurs

public static class Valeurs{ public double []t ;publicint n;} (0.5 point) Ecrivez une procedureinitialiserValeurs(v)qui initialise unValeursv a (aucune valeur).Outil Java Il faudra egalement creer le tableau des valeurs.(1 point) Ecrivez une proceduresaisirValeurs(v)qui saisit le nombre de valeurs puis les valeurs et les range dans unValeursv a la maniere de l'exemple :nombrede valeurs ? 5 valeurs ? 12.1 -5.4 65.2 84.3 65.2

Validez vos procedures avec la solution.

Unisciel algoprog { Tri par selection du maximum [tr04]3Solution Java@[pgtrselmax.java]/**

Initialisation

d un

Valeurs

@param out v un

Valeurs

public static void initialiserValeurs(Valeursv ){ v t = newdouble [TMAX];v.n= 0;

Saisie

des donn es d un

Valeurs

@param in out v un

Valeurs

public static void saisirValeurs(Valeursv ){

Scanner

input = newScanner(System.in);//attention :on ne v érifiepas que n est dans [1.. TMAX]

System

out print

Nombre

de valeurs v n input nextInt

System

out print

Valeurs

for(intj= 0; j < v .n; ++j){ v t j input nextDouble

1.2 Tri par selection du maximum (3.5 points)

On veut remettre lesnvaleurs du tableau dans l'ordre croissant. •Dans la derniere case du tableau, il faut donc mettre la plus grande des valeurs. On cherche le numero de casekou elle se trouve et on echange alors les contenus de la derniere case et de la casek. •Dans l'avant derniere case, il faut y mettre la deuxieme plus grande valeur, a savoir la plus grande valeur sans tenir compte de la derniere case (puisque la plus grande valeur est dans la derniere case). On cherche son numero de caseket on echange les contenus de l'avant derniere case etk. •En continuant ce raisonnement et en remarquant que l'on peut s'arr^eter a la pre- miere case, on arrive a l'algorithme suivant :nfin<- n -1 Pourj<- nfin à 1 pas-1Faire|k <- Chercher le num érode la case contenant la plus grande valeur des cases num ro 0 jusqu la case j changer les contenus des cases j etksij<> k FinPour (1.5 point) Ecrivez une fonctionindiceDuMax(v,k)qui calcule et renvoie lenumero de casede la plus grande valeur d'unValeursv de la case0a la casek(exclus). Unisciel algoprog { Tri par selection du maximum [tr04]4(0.5 point) Ecrivez une procedureechangerCase(v,i1,i2)qui echange le contenu des cases

numeroi1eti2d'unValeursv (les indicesi1eti2etant valides).(1.5 point)Deduisez une proceduretrierValeurs(v)qui trie les valeurs d'unValeursv

avec l'algorithme decrit auparavant.Validez votre fonction et vos procedures avec la solution.

Solution Java@[pgtrselmax.java]/**

Indice

du maximum d un

Valeurs

@param in v un

Valeurs

@param in k un entier valide dans [0.. TMAX @return

Indice

du maximum de v [0.. k public static int indiceDuMax(finalValeursv ,intk){ le r sultat intimax= 0; //valeur du maximum doublevmax= v .t[imax];//parcourt les cases de 1 jusqu "àk ( exclus) for(intj= 1; j < k ; ++j){ si on trouve mieux on actualise le imax et sa valeur if(vmax< v .t[j]){ imax j vmax v t imax returnimax;}

Permute

des cases d un

Valeurs

@param in out v un

Valeurs

@param in i1 un entier valide c d dans [0.. t n @param in i2 un entier valide public static void echangerCase(Valeursv ,inti1,inti2){ doubletmp= v .t[i1];v.t[i1] =v .t[i2]; v t i2 tmp Tri d un

Valeurs

@param in out v un

Valeurs

Unisciel algoprog { Tri par selection du maximum [tr04]5publicstatic void trierValeurs(Valeursv ){ intnfin= v .n- 1; for(intj= nfin ;j >= 1; -- j){ intk= indiceDuMax (v,j+ 1); if(j!= k ){ echangerCase v j k

1.3 Test (1.5 point)(1 point)

Ecrivez une procedureafficherValeurs(v)qui ache les valeurs stockees dans unValeursv a la maniere de l'exemple :nombrede valeurs : 5 valeurs : 12.1 -5.4 65.2 84.3 65.2

Validez votre procedure avec la solution.

Solution Java@[pgtrselmax.java]/**

Affichage

d un

Valeurs

@param in v un

Valeurs

public static void afficherValeurs(finalValeursv ){

System

out println

Nombre

de valeurs v n

System

out print

Valeurs

for(intj= 0; j < v .n; ++j){

System

out print v t j

System

out println (0.5 point) Ecrivez un programme qui saisit desValeurs, les ache puis les re-ache triees.Validez votre programme avec la solution.

Unisciel algoprog { Tri par selection du maximum [tr04]6Solution Java@[pgtrselmax.java]publicstatic void main(String[]args ){

Valeurs

vals = newValeurs();initialiserValeurs(vals); saisirValeurs vals trierValeurs vals afficherValeurs vals

2 References generales

Comprend

quotesdbs_dbs5.pdfusesText_10

[PDF] algorithme de tri par selection pdf

[PDF] algorithme de tri par selection recursive

[PDF] algorithme de tri pdf

[PDF] algorithme de tri rapide

[PDF] algorithme du plus court chemin

[PDF] algorithme du plus court chemin dans un graphe

[PDF] algorithme du plus court chemin java

[PDF] algorithme du plus court chemin python

[PDF] algorithme et langage c

[PDF] algorithme et programmation

[PDF] algorithme et programmation en language c

[PDF] algorithme et programmation en pascal

[PDF] algorithme et programmation en pascal pdf

[PDF] algorithme et programmation python

[PDF] algorithme et structure de données 1