Cours d
24 pages
Breton
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Cours d'Algorithmique-Programmation 2e partie (IAP2 ...

-

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
24 pages
Breton

Description

Cours d’Algorithmique-Programmation
e2 partie (IAP2): programmation imp´erative et
structures de donn´ees simples
Compl´ements sur les tableaux + Pointeurs en C
Sandrine Blazy
er` e- 1 ann´ee
7 novembre 2007
e
S.Blazy (ENSIIE) Cours d’Algorithmique-Programmation 2 partie (IAP2):7pnovembrogramm reation2007imp´erat 1i/ve24et structures de donn´ees simples 1 Tris par s´election
Matrices
Le type pointeur sur ´el´ement
Pointeurs et arguments
argc et argv
e
S.Blazy (ENSIIE) Cours d’Algorithmique-Programmation 2 partie (IAP2):7pnovembrogramm reation2007imp´erat 2i/ve24et structures de donn´ees simples Tri par s´election
Principe
On cherche le plus petit ´el´ement du vecteur et on l’´echange avec le
premier ´el´ement puis on trie le reste.
Plus pr´ecis´ement et it´erativement, `a la i-`eme ´etape du tri d’un vecteur de
longueur n, on cherche l’indice j du plus petit ´el´ement du sous-vecteur
d’indice compris entre i et n−1 et on ´echange cet ´el´ement avec l’´el´ement
d’indice i. L’´echange n’est effectivement r´ealis´e que si ce plus petit
´el´ement n’est pas d´ej`a en i.
e
S.Blazy (ENSIIE) Cours d’Algorithmique-Programmation 2 partie (IAP2):7pnovembrogramm reation2007imp´erat 3i/ve24et structures de donn´ees simples Tri par s´election
Interfaces
/∗ Interface
indice min sous vecteur: vecteur−> int
post calcule l’indice du plus petit ´el´ement du vecteur
∗/
/∗ Interface
tri selection: vecteur−> vecteur
post trie le tableau dans l’ordre croissant
∗/
e
S.Blazy (ENSIIE) Cours ...

Sujets

Informations

Publié par
Nombre de lectures 210
Langue Breton

Exrait

y(azSIENBlS.ogirdlAuosrEIC)rammProgque-thmipe2noitatcurseruodede´nnster0270/142
Cours d’Algorithmique-Programmation 2 e partie(IAP2):programmationimp´erativeet structuresdedonne´essimples
Sandrine Blazy
Compl´ementssurlestableaux+PointeursenC
7 novembre 2007
` - 1 ere anne´e
essimples7novemb
onedsdreimsseen´von7selp002erbmecuutsrt72/24
Letypepointeursur´el´ement
Pointeurs et arguments
argc et argv
1 Tris par selection ´
Matrices
SiqhmitorlgAsduroC)EIISNE(yzalB.2epitnomaamorrgeuP-
denoerdscuutsrtov7nesplimsseen´
Pluspre´cise´mentetit´erativement,a`la i -e`me´etapedutridunvecteurde longueur n , on cherche l’indice j dupluspetit´ele´mentdusous-vecteur d’indice compris entre i et n 1eton´echangecete´le´mentavecle´l´ement d’indice i .Le´changenesteectivementre´alise´quesicepluspetit ´ele´mentnestpasde´j`aen i .
Oncherchelepluspetite´l´ementduvecteuretonle´changeavecle premiere´l´ementpuisontrielereste.
42/37002erbmeursdAlgNSIIE)CoeuP-orrgrotimhqip2emaamontiTpari´erstcelPnoicnirepi.Blazy(ES
embr7novplesssim4
/ Interface tri selection : vecteur > vecteur post t r i e le tableau dans l ’ordre croissant /
/ Interface indice min sous vecteur : vecteur > int postcalculelindicedupluspetite´l´ementduvecteur /
472/2e00rTpielecars´Intetionsecafrpe2noitresductun´eeedonsrtSla.B(EzyIINShmique-Programma)EoCrudsAglroti
odede´nnisseelpmstctruesur
let rec supprimer e l = match l with | [ ] > [ ] | x : : l ’ > i f x=e then l ’ else x : : ( supprimer e l ’ ) ; ;
let rec indice min sous vecteur l = match l with | [ ] > failwith ”indice min sous vecteur : l i s t e vide” | [x] > x | x : : l ’ > min x (indice min sous vecteur l ’ ) ; ;
l ’ ) ; ;
let rec tri selection l = match l with | [ ] > [ ] | − > let m = indice min sous vecteur l in letl=supprimermlinm::(tris´election
42
Triparse´lection d’une liste, en Caml
vembs7no075/re20Programmation2epdlAogirhtimuq-ey(azSIEN)CIErsoulB.S
02erbmev
int indice min sous vecteur( int t [ ] , int imin = debut; int i ; for ( i = debut+1; i < =fin;i++) { i f (t [ i ] < t [ imin]) imin = i ; } return imin ; }
42/670sies´ennnos7lempurtctsedodruse
int debut,
int fin ) {
S.Blazy(lAdsruoC)EIISNEogPre-qumithrigo2npetaoiarmmpirT´sraelectionduntablae,uneC
[]nt:iontiecelisrtecafretnI/Cnetionelecars´Tripelistiecvo/tridsiortnasrolcerdleaudansrieletabiopdsott>nitv>70/742vembre20mples7nohtimogirdlAuosratiorammProgque-}};pmet=]j[t;]j)CIESIENy(azBlS.tsurtcnn´eessiuresdedope2ni,j;;intemp;intt=i;0of(r+i)+<i;nt[nt(ion){tnin],cidnitni1n=nifecefin);if(j>i){tme=p[t]it;i[=][t=i{jicndinemussotcev(rue,i,tidni
20078/24
Tripars´election:bilan
Contrairementauxfonctionsdetridelistesquiretournentunelistetri´ee, les fonctions de tri de vecteurs agissent par effet de bord : elles modifient levecteurquileurestpass´eenargumenteta`landutraitement,ce vecteuresttrie´.Onditquellestravaillent en place .
Comparaison :laversionsurlesvecteursestconsid´erablementplussimple. Eneet,nousnousrestreignonsauxe´le´mentsautresquelepluspetit simplementenincre´mentantlindice i apr`esavoire´change´lepluspetit ´el´ementavecceluidindice i alors que pour les listes, il nous faut parcourir a`nouveaulalistepourallersupprimercepluspetit´el´ement.
ispmel7sonevbmerdeesurctes´enndourtspeoi2nargotammuqimrP-egoAlthriou)Cdrs(yNEISEI.SlBza
pmel7sonevbmer02079/24
Letypepointeursure´l´ement
Pointeurs et arguments
argc et argv
Trispars´election
2 Matrices
tstcuresurdode´ennsies2npelAdsruoimhtirogogPre-quioatmmraNEISEIC).SlBza(y
IIE)CoursdAlgornr;0S}B.alyzE(SNtures2eontimapeuqimhtimargorP-
int main (void) { int ma matrice [NB LIG] [NB COL] ; for ( i=0; i < NBLIG;i++) for ( j=0; j < NBCOL;j++) ma matrice [ i ] [ j ] = i+j ;
#define NB LIG 10 #define NB COL 20
0/24
Matrices n × p De´nition
n lignes, p colonnes untableaua` n lignes,chaquelignee´tantun tableau (vecteur) de p e´l´ements.
Matrice = tableau de dimension 2.
bre20071n7semevosseelpmiedsdn´onuctrretu
e2noitampturetruconn´sdedse2br7100241/
Remarque : on aurait pu omettre 4, mais pas 5.
Lesvaleurssontrang´eesligneparligne.
Matrices Initialisation
sseelpmin7semevo
int t [4][5] = { { 0,1,2,3,4 } , { 10,11,12,13,14 } , { 20,21,22,23,24 } , { 30,31,32,33,34 } , } ;
alyzE(SNSB.AsdorlgE)IIurCoorP-margmhtieuqi
  • Accueil Accueil
  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • BD BD
  • Documents Documents