Chap2.2.1-Algos-simples-2p.pdf

(331 KB) Pobierz
Algorithmique & programmation
Chapitre 2 : Vecteurs
Algorithmes de parcours complet
Somme des éléments d’un vecteur
!!
On veut faire la somme de toutes les valeurs
contenues dans un vecteur d’entiers
!!
Pour faire le raisonnement par récurrence, il
faut d’abord trouver
l’hypothèse
!
"!
Faire un dessin
Chapitre 2
2
Somme des éléments d’un vecteur
!!
Dessin
1
2
i-1
i
n
déjà traité!
à traiter!
Chapitre 2
3
Somme des éléments d’un vecteur
!!
On veut faire la somme de toutes les valeurs
contenues dans un vecteur d’entiers
!!
Pour faire le raisonnement par récurrence, il
faut d’abord trouver
l’hypothèse
!
"!
Faire un dessin
"!
en français
!!
À un instant donné, l’algorithme qui fait la somme
des éléments du vecteur à fait la somme des
éléments d’un sous-vecteur V[1..i-1]
"!
formalisée
!!
s
=
!
V[1..i-1]
Chapitre 2
4
Somme des éléments d’un vecteur
!!
Le raisonnement par récurrence
Hypothèse
s
=
!
V[1..i-1]
Q : Quelles sont les situations intéressantes ?!
R : Il y en a deux !!
!
i
=
n+1
"
s
=
!
V[1..n]
"
résultat
=
s
!
!
i
"
n
"
s := s
+
V[i] ; i := i
+
1 ;
!
H
Q : Dans quelle situation retourne-t-on à l"hypothèse ?!
R : Lorsque
i
"
n
!!
Itération
Initialisation
Chapitre 2
tantque i
"
n faire …
s := 0 ; i := 1 ;
!
H
5
Q : Connaît-on un vecteur pour lequel on peut rendre le résultat sans calcul ?!
R : Oui, le
vecteur vide
!
!
Somme des éléments d’un vecteur
!!
Le raisonnement par récurrence
Hypothèse
s
=
!
V[1..i-1]
!
i
=
n+1
"
s
=
!
V[1..n]
"
résultat
=
s
!
!
i
"
n
"
s := s
+
V[i] ; i := i
+
1 ;
!
H
Itération
Initialisation
Chapitre 2
tantque i
"
n faire …
s := 0 ; i := 1 ;
!
H
6
fonction
somme
fonction
somme (d V[1..n] : vecteur) : entier ;
!
spécification
{n
"
0}
!
{résultat =
"
V[1..n]}!
!s,
i : entier ;
!
debfonc
!
Initialisation!
!s
:= 0 ; i := 1 ;!
itération!
!tantque
i
"
n
faire!
! !s
:= s + V[i] ;!
cas retournant à l!hypothèse!
! !i
:= i
+
1 ;!
!finfaire
;!
!{i
>
n, s =
"
V[1..i-1]
#
i=n
+
1, s =
"
V[1..n]}!
produire le résultat!
!retour
s ;
!
finfonc
;!
Chapitre 2
7
fonction
somme
!!
soit V un vecteur d'entier
function
somme (V :
in
vecteur)
return
Integer
is
--
{V vecteur vide ou non} -> {résultat =
"
V}
-- il faut retrouver les bornes !!!
s, i : integer ;
1
de V[1..n] {borne inférieure}
begin
s := 0 ; i := V'First ;
n
de V[1..n] {borne supérieure}
while
i
"
V'Last
loop
s := s + V(i) ;
V(i) remplace V[i]
i := i
+
1 ;
end loop;
--{i
>
n, s =
"
V[1..i-1]
#
i=n
+
1, s =
"
V[1..n]}
retrun
s ;
end
somme
;
Chapitre 2
8
fonction
somme
fonction
somme (d V[1..n] : vecteur) : entier ;
!
spécification
{n
"
0}
!
{résultat =
"
V[1..n]}!
s : entier ;
!
debfonc
!
!s
:= 0 ;!
!pour
i := 1
haut
n
faire!
itération d!un parcours complet!
! !s
:= s + V[i] ;
!
!finfaire
;
!
!retour
s ;
!
finfonc
;!
Chapitre 2
9
fonction
somme
!!
soit V un vecteur d'entier
function
somme (V :
in
vecteur)
return
Integer
is
--
{V vecteur vide ou non} -> {résultat =
"
V}
-- il faut retrouver les bornes !!!
s : integer ;
begin
s := 0 ;
i parcours tous les indices
for
i
in
V'range
loop
s := s + V(i) ;
end loop;
--{i
>
n, s =
"
V[1..i-1]
#
i=n
+
1, s =
"
V[1..n]}
retrun
s ;
end
somme
;
Chapitre 2
10

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin