CM2 .pdf

---

À propos / Télécharger Aperçu

---

Ce document au format PDF 1.4 a été généré par TeX / pdfTeX-1.40.10, et a été envoyé sur fichier-pdf.fr le 31/08/2011 à 22:53, depuis l'adresse IP 90.42.x.x. La présente page de téléchargement du fichier a été vue 1849 fois.
Taille du document: 331 Ko (13 pages).
Confidentialité: fichier public

Aperçu du document

---

Sommaire

Notes de Cours du module FLIN101

1

Listes simplement chaînées
Introduction
Algorithmes itératifs simples pour des Listes d’entiers
Listes vs tableaux

2

Récursivité
Introduction
Exemples simples de procédures récursives numériques
Récursivité et tableaux
Récursivité et Listes
Récursivité et dessin

Algorithmique et Maple – L1
M. Leclère

P. Janssen

J.F. Vilarem

Université Montpellier 2

Octobre 2010

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

Algorithmique et Maple – L1

11/08

1 / 57

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

Algorithmique et Maple – L1

11/08

2 / 57

Suites indexée, tableau
Définition
En algorithmique, il est courant de manipuler des types élaborés à partir de
types de base. Par exemple array ... of Entier est construit à partir du
type de base Entier et du constructeur array.
Ces nouveaux types sont définis par :
des constructeurs. Ce sont des opérations qui construisent les éléments
du type. Par exemple array construit un tableau.
des accesseurs. Ce sont les fonctions qui permettent d’accéder aux
différentes parties des éléments du type. Par exemple taille.

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

Une suite (U)I indexée par I est une fonction définie sur I. Classiquement
I est un intervalle de N : 1, 2, ..., n. La suite est U1 , U2 , ..., Uk , ..., Un . Uk
est l’élément de la suite de rang (ou indice) k .
La même valeur v peut être celle de deux éléments Uk et Ui . On parlera
d’occurrences de v dans la suite.
U : [1, 5] −→ N
n 7−→
(n mod 3) + 1
Un tableau T est une structuration des données permettant de
représenter des suites. L’index est toujours 1, 2, ...taille(T ).

T

2

3

1

2

3

À la différence d’une suite, un tableau a ses éléments non
nécessairement initialisés, et modifiables.
Par exemple, après T[2] := 6;, on a :

T
Algorithmique et Maple – L1

11/08

4 / 57

2

6

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

1

2

3

Algorithmique et Maple – L1

11/08

5 / 57

Liste chaînée

Exemples de listes
Dans la suite, on désigne liste, une liste simplement chaînée.

Exemple
La liste vide :

Définition
Une liste simplement chaînée est une suite d’éléments dans laquelle
l’indexation disparaît pour être remplacée par un enchaînement ou chaînage
(notion de « suivant »).

Une liste non vide comporte au moins un élément et un chaînage avec
.
Quelle est la longueur (nombre d’éléments) d’une liste ? Quel est le 5ème
élément d’une liste (s’il existe) ?
Impossible de répondre sans parcourir éventuellement toute la liste. Ce
parcours utilise le chaînage. On parle de balayage de la liste.

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

Algorithmique et Maple – L1

11/08

6 / 57

Pour simplifier on considère des « Listes simplement chaînées dont les
éléments sont des entiers » et on les appelle Listes.

11/08

7 / 57

Une variable L est déclarée de type Liste par : L : Liste;
Soit L de type Liste, dont les éléments successifs sont (3, 5, 14)
et dont le balayage a été représenté par :

Le nom du type est Liste.
Les valeurs du type, les listes, sont construites à partir de :
la liste vide, notée Vide, représentée par
le constructeur consL : N × Liste −→ Liste
n, L 7−→ L0
où L0 est la liste dont le premier élément est n chaîné avec la liste L

L’affectation de cette valeur à L, peut être réalisée par l’affectation :

On accède aux constituants d’une liste avec :

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

Algorithmique et Maple – L1

Définition

Définition (Le type Liste)

EstVide : Liste −→
L 7−→
first : Liste \ {Vide}
L
succ : Liste \ {Vide}
L

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

Dans un souci de simplification, la valeur de la liste :

Booleen
true si L est vide false sinon
−→ N
7−→ le premier élément de L
−→ Liste
7−→ la liste L privée de sa tête

Algorithmique et Maple – L1

est représentée par la suite de ses éléments, encadrée par [] :
et on admettra l’affectation à une variable M déclarée de type Liste :

11/08

8 / 57

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

Algorithmique et Maple – L1

11/08

9 / 57

Exemples

Longueur d’une liste

Exemple (Manipulations élémentaires)

Pour calculer la longueur d’une liste on utilise :

L,M:Liste; L := [2, 5, 7];

Propriété

EstVide(L); a pour valeur

Une liste non vide comporte au moins un élément et un chaînage avec
.

EstVide(M); a pour valeur
first(L); a pour valeur
succ(L);a pour valeur

d’où le schéma

first(succ(L)); a pour valeur

lg := 0 ;
tant que on n’est pas au bout de la liste L faire
L := ........;
lg := ........ ;
fin tq;
renvoyer lg ;

M := succ(succ(L)); first(M); a pour valeur
succ(M); a pour valeur
EstVide(succ(M)); a pour valeur
first(succ(M)); a pour valeur
consL(9,L); a pour valeur

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

Algorithmique et Maple – L1

11/08

10 / 57

Longueur d’une liste

0
1
2
3

lg := 0 ;
tant que on n’est pas au bout
de la liste L faire
L := ........ ; lg := ........ ;
fin tq;
renvoyer lg ;

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

L

3

fin de ligne

Algorithmique et Maple – L1

5

14

Val(lg)

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

Algorithmique et Maple – L1

11/08

12 / 57

11/08

14 / 57

Algorithme : LongueurListe
Données : L : Liste
Résultat : La longueur de la liste L
lg :Entier, M :Liste;
début
lg := 0 ; M := L ;
tant que non( EstVide(M)) faire
M := ........ ; lg := ........ ;
fin tq;
renvoyer lg ;
fin algorithme

[]
Val(L)

1 LongueurListe := proc(L::Liste)::integer ;
2 local lg :: integer , M :: Liste ;
3 lg := 0 ; M := L ;
4 while( not( EstVide(M))) do
5
M := _________; lg := _________ ;
6 end do;
7 return lg ;
8 end proc;
11/08

13 / 57

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

Algorithmique et Maple – L1

Appartenance à une liste

Appartenance à une liste [Un peu faux]

Soit la liste L = [3, 5, 4, 6, 4, 7]. On cherche si 4 appartient à L.

Remarque

1

En fait 4 a plusieurs occurrences dans L, ici les éléments de rangs 3 et 5.

2

Pour savoir si 4 appartient à L on utilise :

Propriété

3

Une liste non vide comporte au moins un élément et un chaînage avec une
liste :

L := [3, 5, 4];

tant que on n’est pas au
bout de la liste L faire
si first(L)=4 alors
renvoyer ...... ;
sinon
L :=.............. ;
fin si;
fin tq;

fin ligne

"au bout"

first(L)=4

Val(L)

On teste si 4 est le premier élément de L,
Si oui, on renvoie
Si non, on recommence avec

Que se passe-t-il si L = [3, 5, 6] ?

et il n’y a pas d’erreur ? On s’arrête toujours ?

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

Algorithmique et Maple – L1

11/08

15 / 57

Appartenance à une liste [Un peu mieux]

1
2

3

4

tant que on n’est pas au
bout de la liste L faire
si first(L)=4 alors
renvoyer ...... ;
sinon
L :=.............. ;
fin si;
fin tq;
renvoyer .............. ;

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

"au bout"

Algorithmique et Maple – L1

11/08

16 / 57

Appartenance à une liste
Algorithme : AppListe
Données : x : Entier, L : Liste
Résultat : Le booleen x ∈ L
M :Liste;
début
M := L ;
tant que non( EstVide(M)) faire
si first(M)=x alors
renvoyer ............ ;
sinon
M := .............
fin si;
fin tq;
renvoyer ........... ;
fin algorithme

L := [3, 5, 6];
fin ligne

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

first(L)=4

Val(L)

Un style plus « élégant » s’interdira une sortie d’itération utilisant renvoyer.
Il faudra un peu de soin.
Algorithmique et Maple – L1

11/08

17 / 57

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

Algorithmique et Maple – L1

11/08

18 / 57

Appartenance à une liste.

1

2

Appartenance à une liste.

Algorithme : AppListe_Esthétique_Mais_Faux
Données : x : Entier, L : Liste
Résultat : Le booleen x ∈ L
M :Liste;
début
M := L ;
tant que (first(M) 6= x) et non( EstVide(M)) faire
M :=succ(M)
fin tq;
renvoyer ???? ;
fin algorithme

1

2

Que se passe-t-il en ligne 1 si x n’est pas élément de L ?
Remède :
Que renvoyer en ligne 2 sachant que :

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

Algorithmique et Maple – L1

11/08

19 / 57

Algorithme : AppListe_V2
Données : x : Entier, L : Liste
Résultat : Le booleen x ∈ L
M :Liste;
début
M := L ;
tant que ......................... faire
M :=succ(M)
fin tq;
renvoyer ..................... ;
fin algorithme

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

Algorithmique et Maple – L1

11/08

20 / 57

Exemple (Construction dynamique d’une suite)
Soit n un entier positif, on souhaite construire la suite des diviseurs de n.

Introduction (Listes vs tableaux)
Pourquoi «ajouter» les listes alors que les tableaux semblent une
structuration des données suffisante ?

a
b

Certaines « opérations sur les suites » sont plus faciles en utilisant des
tableaux :

c

D’autres « opérations sur les suites » sont plus faciles en utilisant des
listes :

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

L := Vide ;
pour K de 1 à n faire
si ((n mod K) = 0 ) alors
L := consL(K,L) ;
fin si;
fin pour;

n := 6;
fin ligne

K

(K |n)

Val(L)

Que se passe-t-il si on exécute l’itération :
pour K de n à 1 par pas de -1 faire
... ;
fin pour;
Quels est le problème quand on utilise un tableau pour construire la liste
des diviseurs de n ?
Algorithmique et Maple – L1

11/08

22 / 57

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

Algorithmique et Maple – L1

11/08

23 / 57

Récurrence
Exemple
La récurrence est « naturellement » présente en Mathématiques comme en
Informatique. Dans les définitions d’objets, comme dans celles des fonctions.

Je définis Liste par récurrence, en disant : Une Liste est soit :
Cas de Base : la constante Vide
Équation de récurrence : consL( Objet, Liste ), où Objet est un
élément d’un type défini ailleurs.

Définition
On définit objet par récurrence en spécifiant :
Les cas de base : des constantes donnant la valeur de objet sans faire
appel à la récurrence.

Par application de la définition on reconnait des objets qui sont des listes,
étendues à des listes de ... Objet, où Objet est un type quelconque, par
exemple Liste.

Les équations de récurrence : des définitions de objet qui font appel à
d’autres valeurs de objet.
Une récurrence sera dite correcte si dans l’utilisation des équations de
récurrence, la suite des appels récursifs est finie. C’est à dire si le processus
d’appel de la définition, qui appelle la définition avec une deuxième valeur, qui
appelle la définition avec une troisème valeur, qui ..., se termine toujours.

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

Algorithmique et Maple – L1

11/08

25 / 57

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

Algorithmique et Maple – L1

11/08

26 / 57

Factorielle
Exemple

Exemple

Je définis ExprB par récurrence, en disant : Un ExprB est soit :

Je définis la fonction factorielle, en disant : factorielle s’applique à
un entier n ∈ N :

Cas de Base1 : une constante
Cas de Base2 : un symbole

Cas de Base : factorielle(0) renvoie 1

Équation de récurrence1 : ( ExprB operation ExprB ), où
operation est un symbole d’opération binaire définie ailleurs.
Équation de récurrence2 : fonction ( ExprB , ExprB ) où
fonction est un symbole de fonction à deux paramètres définie ailleurs.
Par application de la définition on reconnait des objets qui sont des ExprB :

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

Équation de récurrence : Pour n > 0 factorielle(n) renvoie le
résultat de n * factorielle( n -1)
La manière de spécifier ceci en Mathématiques est, en utilisant la notation
postfixée n! pour factorielle(n) :
∀n > 0,
ou bien

Algorithmique et Maple – L1

11/08

27 / 57

factorielle : N

−→

n

7−→

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

0!

= .........

n!

= ...............

N


si n = 0

Algorithmique et Maple – L1

alors 1
sinon n * factorielle(n-1)

11/08

29 / 57

0

1
2
3

Algorithme : Fact
Données : n ∈ N
Résultat : n !
début
si n =0 alors
renvoyer ........
sinon
renvoyer
.............. ;
fin si;
fin algorithme

Exemple

Propriété

Propriété

Pour toute valeur de l’entier n ∈ N le calcul de Fact(n) termine. En effet la
suite des valeurs de l’argument est la suite n, n-1, n-2, ...
décroissante, admettant pour minimum 0. Et on connait la valeur de Fact(0)
pour ce cas de base.

La définition a l’air correcte pour un entier positif, mais ...

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

Je définis la fonction probleme, en disant : probleme s’applique à un entier
n∈Z:
Cas de Base : probleme(0) renvoie 1

Équation de récurrence : Pour n > 0 probleme(n) renvoie le résultat de
n * probleme( n - 2)
La manière de spécifier ceci en Mathématiques pour probleme(n) : est
probleme : Z −→ 
N
si n = 0 alors 1
n > 0 7−→
sinon n * probleme(n-2)

Algorithmique et Maple – L1

11/08

30 / 57

Algorithmique et Maple – L1

11/08

31 / 57

11/08

33 / 57

Récurrence en Maple

Exemple
Coefficient binomial

La traduction d’un algorithme défini par récurrence est directe :

Ondéfinit le coefficient binomial

n
pour n, p ∈ N, n > p > 0 par :
p
 
n
Si p = 0 :
= .........
0
 
n
Si p = n :
= .........
n
Sinon,
  n > p > 0:
n
= ....................
p

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

1 CB :=proc(n::integer,p::integer)::integer;
2 description
3 "calcule le coefficient binomial n,p";
4 if n=p or p=0 then
5
return _______;
6 else
7
return CB(____,____)+CB(____,___);
8 end if;
9 end proc;

Algorithme : CB
Données :n, p
 ∈ N, n > p > 0
n
Résultat :
p
début
si p=0 ou n=p alors
renvoyer .........
sinon
renvoyer CB(..... ,
.....) +CB(.... ,
.....) ;
fin si;
fin algorithme

Algorithmique et Maple – L1

On l’utilise ensuite avec l’instruction CB(5,2); qui renvoie 10.
Mais certainement pas avec l’instruction CB(100,50);.
CB(100,50); devrait renvoyer comme résultat :
100891344545564193334812497256 ...

11/08

32 / 57

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

Algorithmique et Maple – L1

Propriété

Principe du tri-fusion récursif d’un tableau

On montre que la spécification de la récurrence est correcte car toutes les
suites des appels récursifs, à partir d’un couple (n,p), sont finies et se
terminent sur l’un des cas de base.
Pour s’en convaincre il suffit d’observer sur le graphique ci-dessous, que
dans le plan à coordonnées entières, ces suites représentent des trajets qui
terminent soit sur la première diagonale (n=p), soit sur l’axe horizontal
(p=0).

Pour trier un tableau :
Cas de base : Si le tableau est vide ou a un seul élément, alors il est trié.
Sinon, couper le tableau en deux sous–tableaux
Trier récursivement chaque sous–tableau
Fusionner les deux sous–tableaux triés
12 31 18 51 12 23 17 32 82 44 21 67 29

(n=p)
M( np )

...
...
0

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

n

Algorithmique et Maple – L1

11/08

34 / 57

fusion de deux tableaux triés

1
2
3
4
5
6
7

1 fusion:=proc(T::array(integer),
2
S::array(integer))::array(integer);
3 description "T et S étant des tableaux triés,
4
retourne un tableau trié contenant les
5
éléments de T et de S";
6 local R::array,i::integer,j::integer,k::integer;
7 R:=array(1..taille(T)+taille(S));

Algorithmique et Maple – L1

Algorithmique et Maple – L1

i=3

11/08

37 / 57

11/08

36 / 57

11/08

38 / 57

i:=1;j:=1;k:=1;
while i<= taille(T) and j<= taille(S) do
if T[i]<S[j] then R[k]:= T[i]; i:= i+1;
else R[k]:= S[j]; j:= j+1;
end if ;
k:= k+1;
end do;

j=2

T 12 12 18 23 31 51

Prendre le plus petit élément entre l’élément courant de T et celui de S, le
mettre dans R à l’indice courant, augmenter l’indice courant dans R,
augmenter l’indice du plus petit choisi.
On itère ceci jusqu’à ce qu’on ait parcouru l’un des 2 tableaux complètement.

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

S 17 21 29 32 44 67 82

R 12 12 17
k=4

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

Algorithmique et Maple – L1

Tri-fusion récursif d’un tableau

1 while i<= taille(T) do
2
R[k]:=T[i]; k:=k+1; i:=i+1;
3 end do;
4 while j<= taille(S) do
5
R[k]:=S[j]; k:=k+1; j:=j+1;
6 end do;
7 return eval(R);
8 end proc;

i=7

trifusion := proc(T::array(integer)) ::array(integer);
description "Retourne un tableau trié",
"contenant les mêmes éléments que T";
local A::array,AA::array,B::array,
BB::array,milieu::integer,i::integer;
if taille(T)=1 then return eval(T);
else
milieu := iquo(taille(T) + 1, 2);
A:=array(1..milieu);B:=array(1..taille(T)-milieu);
for i from 1 to milieu do A[i]:=T[i]; end do;
for i from 1 to taille(T)-milieu do
B[i]:=T[milieu + i ];
end do;
AA:=trifusion(A); BB:=trifusion(B);
return fusion(AA,BB);
end if;
end proc;

j=6

T 12 12 18 23 31 51

S 17 21 29 32 44 67 82

R 12 12 17 18 21 23 29 31 32 44 51
k=12

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

Algorithmique et Maple – L1

11/08

39 / 57

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

Algorithmique et Maple – L1

11/08

40 / 57

Longueur d’une liste
0

1

Version récursive

2

Je définis la fonction LgListe, en disant : LgListe s’applique à une liste
L ∈ Liste :

3

Cas de Base : Vide renvoie ...

Équation de récurrence : Pour L 6= Vide :
LgListe(L) renvoie le résultat de 1 + ............

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

Algorithme : LgListe
Données : L ∈ Liste
Résultat : La longueur de L
début
si EstVide(L) alors
renvoyer .........
sinon
renvoyer 1 +
..............
fin si;
fin algorithme

Propriété
Pour toute valeur de la liste L le calcul de LgListe(L) termine.
En effet la liste L est construite par un nombre n d’applications du
constructeur consL.
L est donc consL(x, L1 ). Si le calcul termine pour L1 alors il termine pour L.
Par récurrence sur n, avec comme cas de base n = 0 pour la liste vide dont
on connait la longueur, le calcul termine pour L.

Algorithmique et Maple – L1

11/08

42 / 57

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

Algorithmique et Maple – L1

11/08

43 / 57

Schéma de récurrence avec des Listes

Appartenance à une liste

Définition (L’énoncé du problème)

Reproduction du schéma

On se donne une fonction
récurrence f ?

f : Liste × ...
(L, ...)

−→
7−→

...
...

Comment spécifier par

On indique la valeur de VB = f (L, ...) quand l’argument L est la liste vide
ou, parfois, réduite à un élément.
Dans un deuxième (troisième) cas, le(s) cas de base ayant été traîté(s), L
est non vide. On suppose calculée V = f (succ(L), ...) et on cherche la
valeur du résultat qui va utiliser V et first(L).

D’où le schéma
f : Liste × ...

−→

(L, ...)

7−→

...

 si EstVide(L)


M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

alors VB
sinon un calcul avec
f (succ(L), ...) et first(L)

Algorithmique et Maple – L1

11/08

44 / 57

début
si EstVide(L) alors
renvoyer
sinon
renvoyer
fin si;
fin algorithme

Algorithme : AppListe
Données : x : Entier, L : Liste
Résultat : Le booleen x ∈ L
début
si EstVide(L) alors
renvoyer
sinon
renvoyer
fin si;
fin algorithme
M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

Algorithmique et Maple – L1

L1

3

5

[]

L2

2

7

9

concat(L 1,L2)

Procédure Maple Appartenance à une liste
AppListe := proc(x::anything, L::Liste)::boolean;
if EstVide(L)
then return
else return
end if;
end proc;

Algorithmique et Maple – L1

Autrement on calcule

11/08

45 / 57

Concaténer deux listes

Algorithme d’appartenance à une liste

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

AppListe : Z × Liste −→ Booleen
(x, L) 7−→ un booleen
Quand L est vide, on renvoie

3

5

[]
2

7

[]

9

concatener : Liste × Liste −→ Liste
(L1 , L2 ) 7−→ la concaténation de L1 avec L2
Quand L1 est vide, on renvoie
Autrement on calcule la liste
Puis on renvoie :

11/08

46 / 57

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

Algorithmique et Maple – L1

.

11/08

47 / 57

Insérer un élément dans une liste triée
Définition (L’énoncé du problème)

si EstVide(L1) alors
renvoyer
sinon
renvoyer
fin si;

On se donne une liste triée d’entiers L, par exemple [2,5,7,9] et un entier
x par exemple 3.
Comment insérer x dans la liste L de façon à renvoyer une nouvelle liste triée,
dans l’exemple [2,3,5,7,9] ?

Le schéma de l’algorithme insérerTrié

Procédure Maple concatener

Quand L est la liste vide on renvoie
Ex : insérerTrié(3,[])
Autrement on distingue 2 cas :

concatener:=proc(L1::Liste,L2::Liste)::Liste;
if EstVide(L1)
then return
else return
end if;
end proc;

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

Algorithmique et Maple – L1

Si x < first(L) on renvoie
Ex : insérerTrié(3,[5,7,9])
Et sinon, on exécute la récurrence sur succ(L), c’est à dire on calcule
.
Puis on renvoie
.
Ex : insérerTrié(3,[1,2,9]). On calcule
.
11/08

48 / 57

Algorithme : insérerTrié
Données : x : Entier, L : Liste. L est triée croissante
Résultat : La liste triée par insertion de x dans L
début
si EstVide(L) alors
renvoyer
sinon si x < first(L) alors
renvoyer
sinon
renvoyer
fin si;
fin algorithme

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

Algorithmique et Maple – L1

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

Algorithmique et Maple – L1

,

11/08

49 / 57

11/08

51 / 57

Procédure Maple insérerTrié
insérerTrié:=proc(x::anything,L::Liste)::Liste;
if EstVide(L)
then return
elif ( x < first(L) )
then return
else return
end if;
end proc;

11/08

50 / 57

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

Algorithmique et Maple – L1

Dessin de lignes polygonales

Graphique récursif

Définition (Points, lignes polygonales)

Définition (L’énoncé du problème)
On se donne un point P, un réel c et un entier n. Il s’agit de définir la ligne
polygonale permettant de dessiner n carrés emboîtés à partir du point P
suivant le principe décrit ci–dessous :

Le point du plan A(x, y ) sera représenté par la liste [x,y].
Si on représente le point B(z, t) par la liste [z,t], le segment AB sera
représenté par la liste : [[x,y],[z,t]].

c

Enfin, si on représente le point C(u, v ) par la liste [u,v], la ligne
polygonale fermée ABCA sera représentée par la liste :
[[x,y],[z,t],[u,v],[x,y]]

On définit un point
M(x, y ) par la liste
[x,y], et une ligne polygonale par une liste de
points.

C[2, 2]

2

1

B[3, 1]

n=6

A est
AB est
ABCA est

A [1, 0.5]
1

2

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

3

Algorithmique et Maple – L1

P
11/08

53 / 57

Principe de l’algorithme

Algorithmique et Maple – L1

Algorithmique et Maple – L1

11/08

54 / 57

L’algorithme de dessin récursif
Algorithme : dessin
Données : n ∈ N (le nombre de carrés emboîtés),
P le point de départ (une liste de deux réels)
c ∈ R le coté du carré extérieur
Résultat : Une ligne polygonale
début
si n = 0 alors
renvoyer
sinon si n=1 alors
renvoyer
sinon
renvoyer concatener([ ], concatener(dessin( , , ), [
]))
fin si;
fin algorithme

avec pour l’appel récursif :

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

11/08

55 / 57

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

Algorithmique et Maple – L1

11/08

56 / 57

Le programme Maple de dessin récursif
1 dessin:=proc(n::integer,
2
P::Liste,c::float)::Liste;
3 local x::float,y::float,
4
L0::Liste,
5
L1::Liste,L2::Liste,L3::Liste;
6 x:=first(P);y:=first(succ(P));
7 L0 := [P,[x,y+c],[x+c,y+c],[x+c,y],P];
8 L1 := [P,[x,y+c],[x+c,y+c],[x+c,y],
9
[x+c/2,y],[x+c/4,y+c/4]];
10 if n = 0 then return []
11 elif n = 1 then return L0;
12 else L2:=dessin(n - 2,[x+c/4,y+c/4],c/2);
13
L3:=[[x,y+c/2],[x+c/2,y+c],
14
[x+c,y+c/2],[x+c/2,y],P];
15
return concatener(L1,concatener(L2,L3));
16 end if;
17 end proc:

M. Leclère, P. Janssen, J.F. Vilarem (Université Montpellier 2)

Algorithmique et Maple – L1

11/08

57 / 57



Sur le même sujet..

---