Chap2.4.1-Insertion-2p.pdf

(235 KB) Pobierz
Algorithmique & programmation
Chapitre 2 : Vecteurs
Algorithmes de mise à jour
Insertion
Mise à jour
!!
Deux opérations
"!
Insertion
"!
Suppression
!!
Deux types de vecteurs
"!
Vecteur non trié
"!
Vecteur trié
!!
Note : on supposera toujours que
n
<
nmax
"!
insertion toujours possible
Chapitre 2.4.1
2
Insertion dans un vecteur non trié
!!
On insère l’élément à la fin
procédure
insertfin(dr V[1..n]: vecteur; d elem : t) ;!
spécification
{n
!
0}
!
{ajout d'un élément à la fin de V}!
debproc!
!n
:= n+1 ;!
!V[n]
:= elem ;!
finproc
;
Chapitre 2.4.1
3
Insertion dans un vecteur trié
!!
Après l’insertion le vecteur doit rester trié
!!
On procède en deux étapes
1.!
Chercher la place que doit occuper l’élément à
insérer
"!
fonction
posit
2.!
Effectuer l’insertion de l’élément par décalage
"!
procédure
insertplace
Chapitre 2.4.1
4
procédure
insertion
procédure
insertion(dr V[1..n]:vecteur ; d elem : t) ;!
spécification
{n
!
0, V[1..n] trié}
!
!
{insertion de elem dans V tel que V reste trié}!
!p
: entier ;
!
debproc!
!si
n = 0
alors
!
!
!{insertion
dans un vecteur vide}!
! !V[1]
:= elem ;!
! !n
:= 1 ;!
!sinon !
!
!
!{n
>
0}!
! !p
:= posit (V[1..n], elem) ;!
! ! !
!
!{V[1..p-1]
"
elem
<
V[p..n], p
#
[1..n+1]}!
! !inserplace
(V[1..n], elem, p) ;!
!finsi
;!
finproc
;!
Chapitre 2.4.1
5
Recherche de la place
!!
On cherche un indice p (p
!
[1..n+1]) tel que :
V[1..p-1]
"
elem
<
V[p..n]
!!
C‘est-à-dire
"!
la place la plus « à droite » possible
#!
minimum de décalages pour l'insertion
!!
Méthode
"!
Recherche séquentielle
!!
On commencera à droite !
"!
Recherche dichotomique
Chapitre 2.4.1
6
Recherche séquentielle de la place
!!
Si p vaut 1 on a fini
"!
V[1]
>
elem
!!
Sinon, on cherche p dans [2..n+1]
"!
En schématisant :
1
2
i
i+1
n
à traiter!
déjà traité!
V[1]
"
elem
<
V[i+1..n]!
"!
On s’arrêtera dès que V[i]
"
elem
Chapitre 2.4.1
7
Recherche séquentielle de la place
!!
Raisonnement par récurrence
Hypothèse
V[1]
"
elem
<
V[i+1..n]
!
V[i]
"
elem
!
V[i]
>
elem
Itération
Initialisation
"
p := i
+
1 ;
!
"
i := i - 1 ;
!
H
tantque (V[i]
>
elem) faire …
!
V[1]
>
elem
!
V[1]
"
elem
Chapitre 2.4.1
"
p := 1 ;
!
"
i := n ;
!
H
8
fonction
posit
séquentielle
fonction
posit (d V[1..n] : vecteur ; d elem : t) : entier ;!
spécification
{n > 0, V[1..n] trié}
!"
{résultat = p, p
#
[1..n+1], V[1..p-1]
"
elem
<
V[p..n]}!
!
p, i : entier ;
!
debfonc!
!si
V[1]
>
elem
alors
!
!
p := 1 ;
!
!
!
!{elem
<
V[p..n]}!
!sinon !
!
!{V[1]
"
elem}!
!
i := n ;
!
!
!
!{V[1]
"
elem
<
V[i+1..n]}!
!
tantque
V[i]
>
elem
faire
!
!{V[1]
"
elem
<
V[i..n]}!
! !
i := i - 1 ;
!
!
!
{V[1]
"
elem
<
V[i+1..n]}
!
!
finfaire
;
!
!
!
!{V[1..i]
"
elem
<
V[i+1..n]}
!
!
p := i
+
1 ;!
!finsi
;!
!retour
p ;
!
!
{V[1..p-1]
"
elem
<
V[p..n], p
#
[1..n+1]}!
finfonc
;!
Chapitre 2.4.1
9
Recherche dichotomique de la place
!!
Traiter d’abord le cas p
=
n
+
1
!!
Ensuite, on cherche p dans [1..n] tel que
V[1..p-1]
"
elem
<
V[p..n]
"!
En schématisant :
"
elem!
1
inf
m
sup
>
elem!
n
????????!
Chapitre 2.4.1
10

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin