Dossier Python Algo .pdf



Nom original: Dossier Python Algo.pdf

Ce document au format PDF 1.5 a été généré par TeX / MiKTeX pdfTeX-1.40.11, et a été envoyé sur fichier-pdf.fr le 24/11/2017 à 21:39, depuis l'adresse IP 90.126.x.x. La présente page de téléchargement du fichier a été vue 445 fois.
Taille du document: 553 Ko (41 pages).
Confidentialité: fichier public


Aperçu du document


Cours d'algorithmique

(et notions de Python 3)
BTS SIO 1 U22

Alain

Satabin

Lycée Monge
Charleville-Mézières

juin 2012 (version 1.0)
octobre 2012 (version 1.1)
novembre 2013 (version 1.2)

Table des matières

1 Préliminaires indispensables
1.1

1.2

De quoi est-il question ?

4

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.1.1

Dé nition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.1.2

Commentaires excessivement importants . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.1.3

Quelques exemples de la vie courante . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.1.4

Tout petit déjà . . . ! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.1.5

Quelques règles méthodologiques dont on ne dérogera point ! . . . . . . . . . . . . . . .

4

Et l'informatique dans tout ça ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.2.1

Petit point d'histoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.2.2

Machine et algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

2 Variables et opérateurs
2.1

2.2

2.3

Utilisation des variables

6
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2.1.1

Les conventions d'écriture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2.1.2

A ectation d'une variable

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2.1.3

Évaluation à la main . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2.1.4

Typage et transtypage de variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

2.1.5

Lecture / Écriture

7

2.1.6

Schéma d'écriture d'un algorithme

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

Opérateurs de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

2.2.1

Sur les variables réelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

2.2.2

Sur les variables entières . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

2.2.3

Sur les chaînes de caractères . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

2.2.4

Sur les booléens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

Quelques fonctions utiles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

2.3.1

Sur les nombres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

2.3.2

Sur les chaînes de caractères . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

2.3.3

Transtypage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

3 Structures de contrôle
3.1

3.2

10

Traitement conditionnel

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

3.1.1

Traitement simple

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

3.1.2

Traitement étendu

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

3.1.3

Imbrication

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

3.2.1

La boucle "Tant Que" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

3.2.2

La boucle "Pour" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

3.2.3

Imbrication

14

Les boucles

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4 Les tableaux
4.1

15

Deux exemples pour se faire une idée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

4.1.1

15

Un exemple à une dimension

U22 - Algorithmique - Chapitre n°0

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Page 1/40

4.1.2
4.2

4.3

Un exemple à deux dimensions

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

La théorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

4.2.1

Des variables à tiroirs . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

4.2.2

Taille d'un tableau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

4.2.3

A ectation directe

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

4.2.4

Extension d'un tableau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

Exemples rédigés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

4.3.1

Test de lancer de dés : un tableau de taille xée . . . . . . . . . . . . . . . . . . . . . .

17

4.3.2

Analyse d'une série de notes : un tableau à taille variable

. . . . . . . . . . . . . . . .

18

4.3.3

Le triangle de Pascal : un tableau à deux dimensions . . . . . . . . . . . . . . . . . . .

19

5 Procédures et Fonctions
5.1

5.2

5.3

5.4

20

La sous-traitance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

5.1.1

Pourquoi ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

5.1.2

La division des tâches

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

5.1.3

Éviter la répétition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21

5.1.4

Fonctionnement général

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21

5.1.5

Syntaxe

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

Deux espèces de sous-algorithme

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

5.2.1

La procédure

5.2.2

La fonction

5.2.3

Des sous-algorithmes adaptables

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

5.2.4

Conventions d'écriture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

Fonctions et procédures avec arguments

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

5.3.1

Le passage d'arguments

5.3.2

Un exemple de procédure avec deux arguments

. . . . . . . . . . . . . . . . . . . . . .

25

5.3.3

Un classique : la fonction factorielle . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

La portée des variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

5.4.1

Quel est le problème ?

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

5.4.2

Variables globales et locales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

5.4.3

Visibilité des variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

5.4.4

Le comportement des homonymies

29

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6 La récursivité
6.1

6.2

6.3

30

La magie de l'auto-référence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

30

6.1.1

Un petit exemple ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

30

6.1.2

Une fonction auto-référentielle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

30

6.1.3

Comment ça marche ?

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

30

La solution est en vous . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

6.2.1

Dé nition de la récursivité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

6.2.2

Je vous demande de vous arrêter ! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

6.2.3

Fonctionne avec pile

32

6.2.4

La fonction factorielle, le retour !

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

Ré exions sur le procédé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

6.3.1

32

Le piège classique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

U22 - Algorithmique - Chapitre n°0

Page 2/40

6.3.2

À utiliser avec modération . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

6.3.3

En bouquet nal : les tours de Hanoï . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

A Les bases du Python 3

35

A.1

Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

A.2

Commentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

A.3

Structure générale

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

A.4

A ectation

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

A.5

Chaînes de caractères . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

A.6

Saisie

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

A.7

A chage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

B Opérations et fonctions élémentaires en Python 3
B.1

Opérations et opérateurs de base

B.2

Fonctions

36

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

36

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

36

C Structures de contrôle élémentaires en Python 3

37

C.1

Traitement conditionnel simple

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37

C.2

Traitement conditionnel étendu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37

C.3

Boucle Tant que

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37

C.4

Boucle Pour . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37

D Les tableaux en Python 3
D.1

D.2

38

Tableau à une dimension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

D.1.1

Déclaration

38

D.1.2

Accès aux données

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

D.1.3

A ectation dynamique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Tableau à deux dimensions

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

D.2.1

Déclaration

D.2.2

Accès aux données

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

D.2.3

A ectation dynamique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

E Dé nition de procédure et fonction en Python 3

39

E.1

Procédure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39

E.2

Fonction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39

F Codes Ascii de 32 à 127

U22 - Algorithmique - Chapitre n°0

40

Page 3/40

U22 - Chapitre n° 1
Préliminaires indispensables

1.1 De quoi est-il question ?
1.1.1 Définition
Un

algorithme

1.1.2

est une séquence ordonnée d'instructions exécutées de façon logique, mais non intelligente.

Commentaires excessivement importants

Un algorithme possède un début et une n et doit se terminer en un temps ni.
Les instructions composant un algorithme sont su samment simples pour être compréhensibles par l'exécutant (homme ou machine). On les appelle alors des

instructions élémentaires.

Logique et non intelligente signi e que l'exécutant (homme ou machine) doit appliquer strictement les
instructions les unes après les autres, sans se poser la question de la justesse du résultat, ni de la façon dont
il est obtenu. Si l'algorithme est bien fait, le résultat est correct dans tous les cas de gure !
Le concepteur d'un algorithme (donc vous !) doit dominer l'action globale à réaliser et doit en même temps
être capable de la décomposer en une suite d'actes élémentaires compréhensibles par l'exécutant qui, lui, est
un profane dans le domaine. Cela n'est pas toujours une opération aisée !

1.1.3

Quelques exemples de la vie courante

Exemple 1
Exemple 2
Exemple 3
Exemple 4

1.1.4

: Une recette de cuisine.
: Une notice de montage.
: Un guide de réparation.
: Un itinéraire.

Tout petit déjà . . . !

Dès l'école primaire vous avez fréquemment manipulé la notion d'algorithme. Lorsque, par exemple, à partir
des tables d'addition des nombres à 1 chi re vous avez appris à additionner deux nombres quelconques . . .
et ensuite en apprenant à faire des multiplications.
En géométrie vous avez également rencontré bon nombre d'algorithmes : par exemple en apprenant le protocole de construction d'une médiatrice d'un segment avec une règle et un compas.

1.1.5 Quelques règles méthodologiques dont on ne dérogera point !
Article 1 : Véri ez sur des cas simples que vous avez compris le problème à résoudre et que vous savez le
faire à la main

Article 2 :

Décomposez votre résolution du problème en actions de plus en plus simples . . . jusqu'à atteindre
un niveau élémentaire que l'exécutant comprendra

Article 3 :
Article 4 :
Article 5 :
Article 6 :
Article 7 :
1.
2.
3.
4.
5.

Choisissez intelligemment les noms de variable

1

que vous serez amenés à dé nir

Ne supposez jamais que l'exécutant va supposer quelque chose
Mettez des titres et des commentaires

2

3

Testez votre algorithme à la main sur des cas particuliers simples
N'hésitez jamais à tout reprendre à zéro !

4

5

les variables sont à un algorithme ce que les personnages sont à un roman ou un lm
l'exécutant possède un vocabulaire limité et est obéissant, mais bête !
cela n'a aucune utilité pour le bon fonctionnement de l'algorithme, mais le rend plus lisible et plus compréhensible
le concepteur doit être capable de simuler le comportement d'un exécutant bête et discipliné !
rien de plus horrible et incertain qu'un algorithme bidouillé et rustiné de toutes parts !

U22 - Algorithmique - Chapitre n°1

Page 4/40

1.2 Et l'informatique dans tout ça ?
1.2.1 Petit point d'histoire
Étymologiquement, le mot algorithme prend ses racines dans le nom du mathématicien arabe du moyen
6

âge : Al-Kawarizmi. Le mot fut inventé par Ada Lovelace , assistante de Charles Babbage.

7

En 1936, le mathématicien anglais Alan Turing publie un document sur la résolution des problèmes
calculables par une machine virtuelle simple :

la machine de Turing. Considérée comme le premier ordinateur

conceptualisé, sa machine est universelle et peut résoudre tout problème se traduisant en algorithme à partir
d'un nombre très réduit d'instructions élémentaires.
C'est avec le mathématicien américano-hongrois John von Neumann qu'il réalisera et fera fonctionner le
21 juin 1948 le premier ordinateur :
informatique,

1.2.2

le Manchester Mark I.

Pour la circonstance il crée le premier langage

le short code, doté d'une cinquantaine d'instructions.

Machine et algorithme

Une machine en général et un ordinateur en particulier sont des objets idiots qui se contentent de faire à la
lettre ce que vous lui dictez de faire. Les mythes d'ordinateurs intelligents (Matrix, 2001 Odyssée de l'espace,
R2D2, etc.) restent pour l'instant du domaine de la science- ction !
Un ordinateur n'est qu'un ensemble de circuits logiques

8

9

traitant des informations binaires . Une façon

de s'adresser à lui pour lui faire remplir une tâche est de lui parler dans son langage primaire :

machine

10

le langage

.

C'est long et fastidieux !
C'est pour cette raison que se sont développés des logiciels appelés

langages de programmation 11 qui sont en

quelque sorte des interprètes traduisant des instructions claires en langage machine.
Lorsqu'il est traduit dans un langage de programmation, l'algorithme s'appelle un
teur le

programmeur

ou

développeur

programme et son concep-

s'il s'agit de projets plus sophistiqués.

Le but de ce cours est d'apprendre à écrire des algorithmes, c'est à dire à décomposer une action compliquée
en instructions simples. Cet exercice est

a priori

totalement indépendant d'un langage de programmation et

reste un travail de papier . Nous écrirons nos algorithmes dans un

pseudo-langage

et, pour les tester sur

une machine, nous les traduirons dans un langage de programmation.
Cette mise en ÷uvre d'un algorithme sur une machine s'appelle l'
Nous choisirons le Python 3

12

implémentation.

. La syntaxe liée à ce langage gure en annexe de ce document et sera vue

au fur et à mesure du déroulement du cours d'algorithmique.

6. Fille de l'écrivain britannique Lord Byron (1788-1824)
7. Mathématicien inventeur britannique (1791-1871) qui fut l'un des précurseurs de l'informatique en concevant sur le papier
une machine analytique mécanique, programmable, à mémoires et dotée d'organes d'entrées-sortie. La technique des tailles de
pignon d'engrenage et autres petites pièces mécaniques n'était pas su samment maitrisée à l'époque et il ne verra jamais sa
machine fonctionner ! A la n du XXe siècle, des chercheurs britanniques réalisèrent la machine selon les plans de l'inventeur et
nous savons aujourd'hui qu'elle fonctionne.
8. portes OU, ET, NON, NONET, NONOU, etc.
9. présence ou absence de courant sur une patte d'entrée d'un composant électronique
10. succession de 1 et 0 traduisant des instructions et données, avec un nombre restreint d'instructions
11. ADA, FORTRAN, BASIC, COBOL, PASCAL, C, JAVA, etc.
12. Ce choix est arbitraire et l'algorithme écrit est universel . . . vous pouvez le traduire dans tout autre langage
U22 - Algorithmique - Chapitre n°1

Page 5/40

U22 - Chapitre n° 2
Variables et opérateurs

2.1 Utilisation des variables
2.1.1 Les conventions d'écriture
Pour fonctionner, un algorithme a besoin de mémoriser des valeurs (données fournies par l'utilisateur, résultats à a cher, quantités intermédiaires pour un traitement . . .) a n de pouvoir les réutiliser ensuite.
Pour cela il utilise ce qu'on appelle une

variable, comparable à une boîte dans laquelle on peut déposer ou y
nom de variable.

lire une valeur. A n de s'y retrouver, cette boîte est étiquetée par un

Les noms de variables ne doivent pas comporter d'espace et ne peuvent pas commencer par
un chi re. D'une façon générale, on se limitera aux caractères alphanumériques non accentués et au tiret
de soulignement.
La bonne lisibilité d'un algorithme étant fondamentale, il est important de choisir des noms de variable
re étant le rôle joué par la variable en question.
Par exemple voici quelques noms de variable valides :

2.1.2

N ; Date ; Resultat_01 ; NbreValeurs ; Nom_Famille

...

Affectation d'une variable

a ectation. Dans l'écriture d'un algorithme, elle est

Le fait d'attribuer un contenu à une variable s'appelle l'
symbolisée par



selon la syntaxe :

N omV ariable ← V aleur
signi ant que la quantité située à droite de la èche est évaluée, puis stockée dans la variable nommée

NomVariable,

remplaçant ainsi son ancien contenu.

Voici quelques exemples d'a ectation :

N←7
Mess ← "Bonjour"
Date ← "7"
A←B
Res ← Nb1+Nb2
P ← P+2

2.1.3

Met la valeur 7 dans la variable

Mess

N

Bonjour
Date
Met dans la variable A le contenu de la variable B
Additionne les contenus des variables Nb1 et Nb2 et met le
Ajoute 2 au contenu de P et met le résultat dans P
Met dans la variable

Met la chaîne de caractère

la chaîne de caractères

7

dans la variable

résultat dans

Res

Évaluation à la main

Lors de la mise au point d'un algorithme ou de la recherche d'erreurs, il est extrêmement important de savoir
le tester à la main . Cela consiste à simuler la machine en suivant l'algorithme pas à pas et en tenant à
jour un tableau de contenu des variables. On parle alors du

tracé pas à pas

de l'algorithme.

Voici dans le tableau de droite un exemple de tracé de la suite d'instructions écrite à gauche :

Début

A←2
B←5
C ← 12
D←A+B
C←A+C
B←B+C
A←C A
D←B×D C

Fin

U22 - Algorithmique - Chapitre n°2

instructions

A

B

C

D

début

n.a.

n.a.

n.a.

n.a.

A

←2
←5
C ← 12
D ← A + B
C ← A + C
B ← B + C
A ← C A
D ← B × D C

2

n.a.

n.a.

n.a.

B

2

5

n.a.

n.a.

2

5

12

n.a.

2

5

12

7

2

5

14

7

2

19

14

7

12

19

14

7

12

19

14

119

12

19

14

119

n

Page 6/40

2.1.4

Typage et transtypage de variables

On distingue pour pour commencer 4 types de variables :

entier ; réel ; chaîne de caractères ; booléen.

Les deux premiers types servent à manipuler les nombres entiers ou "à virgule" (Z ou

R)

Les chaînes de caractères sont conventionnellement écrites entre guillemets dans un algorithme.

Vrai ou Faux. Par exemple, si dans
Test est déclarée booléenne, on pourra trouver des instructions du genre Test ← Vrai
Test ← (Annee > 1582) 1 .

Une variable de type booléen ne peut accueillir que l'une des deux valeurs
un algorithme la variable
ou encore

Les a ectations opérées par l'algorithme doivent évidemment être cohérentes avec les types déclarés ! Par
exemple, si les variables
De même, si
que

B←A

A et B sont déclarées entières, les instructions A ← 3.7 ou A ← B/2 sont des erreurs.

A une variable de type entière et B de type réelle, l'a ectation A ← B engendre une erreur, alors

est une instruction correcte.

Il convient de faire la di érence entre "3.14" (chaîne de caractères) et 3.14 (nombre réel) ou entre 3.0 (nombre
réel) et 3 (nombre entier)
Certaines fonctions, comme la partie entière ou l'arrondi à 0 décimale, ont la faculté de transformer un
nombre réel en nombre entier et pourront s'avérer fort utiles.
D'autres opérations de

transtypage

permettent de transformer une chaîne de caractères en nombre et ré-

ciproquement. Lors du transtypage d'une chaine en nombre, il est nécessaire que le contenu de la chaine
soit cohérent avec ce qu'on veut en faire ! Par exemple le transtypage de la chaine "3.14" en nombre entier
engendre une erreur.

Avant leur utilisation, les variables doivent toujours être initialisées, soit par une saisie (voir plus
loin), soit par l'a ection d'une valeur xée.

2.1.5

Lecture / Écriture

Un algorithme doit évidemment pouvoir communiquer avec son utilisateur !
La

lecture

d'une donnée saisie au clavier par l'utilisateur et son stockage dans une variable s'écrit :

NomVariable ← saisir()

En arrivant sur cette instruction, le programme se met en attente d'une

entrée.

L'utilisateur tape quelque

chose au clavier et le valide, provoquant le stockage de la valeur tapée dans la variable

NomVariable

et la

reprise de l'algorithme à l'instruction suivante.

écriture

L'

d'un résultat ou d'un message se fait grâce à l'instruction

Attention de ne pas confondre les instructions
chaîne de caractères

Bonjour

a cher("Bonjour")

et

a cher(. . .)
a cher(Bonjour)

: la première écrira la

à l'écran alors que la seconde écrira le contenu de la variable

Bonjour.

On peut a cher plusieurs informations à la suite en les séparant par des virgules à l'intérieur de l'instruction

a cher.
Par exemple la séquence d'instructions suivante :

...
A←2
B←5
A cher("A vaut ",A," , B vaut ",B," et leur somme vaut ",A+B)
...
provoquera la sortie à l'écran de :

A vaut 2 , B vaut 5 et leur somme vaut 7

On peut provoquer une saisie avec l'a chage d'un message grâce à l'instruction :

NomVariable ← saisir("message à a cher ")

1. Annee étant ici une variable entière ; la variable Test sera a ectée par Vrai ou Faux suivant que le contenu de Annee est
strictement supérieur à 1582 ou non
U22 - Algorithmique - Chapitre n°2

Page 7/40

Par exemple l'algorithme suivant a che le double de la valeur saisie :

Algorithme : A che_Double
Rôle : calculer le double d'un entier donné
Entrées : Un nombre entier A
Sortie : a chage de 2×A
Variables : entier : A
Début

A ← saisir("Donnez-moi un nombre entier : ")
A cher("le double de votre nombre vaut ",2×A)
Fin

2.1.6

Schéma d'écriture d'un algorithme

L'écriture d'un algorithme obéit à des règles précises et doit comporter :

ˆ
ˆ
ˆ
ˆ
ˆ
ˆ

nom (répondant aux mêmes contraintes que les noms de variables)
son rôle (un commentaire décrivant ce que fait l'algorithme et éventuellement sa façon de procéder)
ses entrées / sorties (voir ci-dessous)
la déclaration des variables utilisées (noms et types)
un début et une n encadrant la suite d'instructions constituant l'algorithme
des commentaires a n d'être facilement lisible et compréhensible. On signalera un commentaire par le
un

symbole #. Tout ce qui suit ce symbole sur la même ligne est ignoré par la machine.

2.2 Opérateurs de base
2.2.1 Sur les variables réelles
Les opérations classiques :

+ ; − ; × ; ÷ ; ax

avec les priorités usuelles : l'élévation en puissance est évaluée

avant les multiplications (et divisions) qui sont elles-même évaluées avant les additions (et soustraction).
Vous avez bien sûr le droit (parfois même le devoir !) d'utiliser des parenthèses.

2.2.2

Sur les variables entières

L'addition, la soustraction et la multiplication restent valides. L'élévation en puissance n'est cohérente que si
la puissance est entière et positive (sinon le résultat n'est plus nécessairement entier). Quant à la division, elle
doit s'adapter au cas entier et nous disposons de deux opérateurs :

div

et

mod

qui donnent respectivement

le quotient et le reste de la division euclidienne.
Par exemple :

2.2.3

(17 div 3)

renvoie 5 et

(17 mod 3)

fournit 2.

Sur les chaînes de caractères

Une seule opération est possible sur les chaînes : la
que nous symboliserons par

concaténation, qui consiste à les mettre bout à bout et

+.

Par exemple après la séquence d'instructions (A et

B

étant des variables de type chaîne) :

...
A ← "Salut"
B ← A+"Tu vas bien ?"
...
la variable

2.2.4

B

contiendra :

"SalutTu vas bien ?".

Sur les booléens

Nous retrouvons ici les opérateurs classiques (qui vont être) vus en logique : ET, OU et NON.

U22 - Algorithmique - Chapitre n°2

Page 8/40

2.3 Quelques fonctions utiles
2.3.1 Sur les nombres
En respectant bien les ensembles de dé nition, on peut évidemment utiliser les fonctions mathématiques
usuelles (logarithme, exponentielle, racine carrée, partie entière, valeur absolue...).
Il sera aussi pratique d'utiliser les deux fonctions suivantes :

aléa()

qui renvoie un nombre réel aléatoire de l'intervalle [0 ; 1[

arrondi(x,n)

qui arrondit un réel

2.3.2

x

à un certain nombre

n

de décimales.

Sur les chaînes de caractères

Notons que le premier caractère d'une chaîne a pour rang 0.
Nous nous limiterons à quelques manipulations correspondant à des fonctions existant dans pratiquement
tous les langages de programmation :

long(ch)

nombre de caractères de la chaine

long("et toi ?")

majus(ch) , minus(ch)

position(ch1 ,ch2 ,n)

vaut

ch

8

ch
"ASDEPIQUE"
"asdepique"

mise en majuscule ou minuscule de

majus("AsDePique")
minus("AsDePique")

renvoie
renvoie

ch1 dans la chaîne ch2
−1 si la chaîne ch1 n'est pas trouvée
position("nj","Bonjour",0) renvoie 2
position("o","Bonjour",2) renvoie 4

renvoie la position de la chaîne

à partir de la position

n

renvoie

extrait(ch,n,p)
carASCII(n)

p

caractères extraite de

renvoie la chaîne

carASCII(97)

renvoie

à partir du caractère de rang

n

n

"a"

renvoie le code ASCII du caractère

codeASCII("a")

ch

"njou".

renvoie le caractère dont le code ASCII est

codeASCII(caract)

2.3.3

renvoie la sous-chaine de

extrait("Bonjour",2,4)

renvoie

caract

97.

Transtypage

L'instruction

123 + 456

renvoie

579

alors que

"123"+"456"

renvoie la chaîne

"123456".

Il nous sera souvent utile de pouvoir convertir une chaîne en un nombre, ou réciproquement :

entier(ch)

réel(ch)

chaine(x)

convertit la chaine

ch

en un nombre entier

entier("123") renvoie le nombre entier 123
entier("-12") renvoie le nombre entier -12
entier("12.3") renvoie une erreur
entier("25 km") renvoie une erreur
convertit la chaine

ch

en un nombre réel

réel("123") renvoie le nombre réel 123.0
réel("-12.3") renvoie le nombre réel -12.3
réel("salut") renvoie une erreur
réel("25,8") renvoie une erreur

x (entier ou réel) en
chaine(123) renvoie la chaine "123"
chaine(-12.3) renvoie la chaine "-12.3"

convertit le nombre

U22 - Algorithmique - Chapitre n°2

chaine

Page 9/40

U22 - Chapitre n° 3
Structures de contrôle

3.1 Traitement conditionnel
3.1.1 Traitement simple
Le traitement simple consiste à tester une condition et à réaliser une action (suite d'instructions) lorsque elle
est vraie. Sa structure est la suivante :

Si (condition) Alors

action si condition vraie . . .

Fin Si

La condition est une phrase logique ou une variable booléenne. Dans le cas où la condition n'est pas réalisée,
l'action est ignorée et on passe directement à l'instruction suivant le

Fin Si.

Par exemple, la séquence suivante a che le plus grand nombre pair inférieur ou égal au nombre entier saisi :

...
A ← saisir("Tapez un entier positif : ")
B←A
Si ((A mod 2) = 1) Alors
a cher("votre nombre est impair")
B←A 1
Fin Si
a cher("Le plus grand entier pair inférieur ou égal à votre nombre est : " , B)
...
Et, pour information, son implémentation en Python 3 est :

syntaxe python 3

...
A = int(input( "Tapez un entier positif : "))
B = A
if ((A % 2) == 1) :
print("votre nombre est impair")
B = A 1
# fin Si
print("Le plus grand entier pair inférieur ou égal à votre nombre est : " , B)
...

3.1.2

Traitement étendu

Le principe reste identique au traitement simple, mais on est dirigé vers une autre suite d'instructions lorsque
la condition n'est pas réalisée. La structure est la suivante :

Si (condition) Alors

action si condition vraie . . .

Sinon

action si condition fausse . . .

Fin Si

Notons que cette fois une des deux actions, et une seule, sera exécutée.

U22 - Algorithmique - Chapitre n°3

Page 10/40

Par exemple, voici une séquence comparant deux nombres saisis :

...
a cher("Donnez-moi deux nombres réels : ")
A ← saisir("A = ")
B ← saisir("B = ")
Si (A=B) Alors
a cher("Les deux nombres saisis sont égaux")
Sinon
a cher("Les deux nombres saisis sont di érents")
Fin Si
...
Et son implémentation en Python 3 :

syntaxe python 3

...
print("Donnez-moi deux nombres réels : ")
A = float(input("A = "))
B = float(input("B = "))
if (A == B) :
print("Les deux nombres saisis sont égaux")
else :
print("Les deux nombres saisis sont différents")
# Fin Si
...

3.1.3

Imbrication

Les structures peuvent évidemment être imbriquées les unes dans les autres a n de créer des sous-cas. Par

Age ) et suivant les cas
Conduire de type chaîne).

exemple la séquence suivante saisit l'âge de l'utilisateur (variable entière positive
détermine s'il est en âge de voter ou de conduire (variables

Voter

booléenne et

...
Age ← saisir("Quel est votre âge ? ")
Si (Age > 18) Alors
# il peut voter et conduire seul s'il a le permis
Voter ← Vrai
Conduire ← "possible seul"
Sinon
# il est mineur donc ne peut pas voter
Voter ← Faux
Si (Age > 16) Alors
# peut éventuellement être en conduite accompagnée
Conduire ← "possible accompagné"
Sinon
# moins de 16 ans, il ne peut pas conduire
Conduire ← "impossible"
Fin Si
Fin Si
...
On notera que l'indentation est fondamentale à la compréhension des imbrications !

U22 - Algorithmique - Chapitre n°3

Page 11/40

3.2 Les boucles
3.2.1 La boucle "Tant

Que"

La structure est la suivante :

Tant que (condition)

action . . .

Fin Tant que
Lorsque l'instruction "Tant Que" est rencontrée, la condition est évaluée. Si elle est réalisée, on exécute
l'action spéci ée et lorsque le "Fin Tant Que" est rencontré on revient au "Tant Que" et on recommence. Si
elle n'est pas réalisée, on ignore l'action et on passe directement à l'instruction suivant le "Fin Tant Que"
(sortie de boucle).
Voici par exemple une séquence qui a che l'alphabet en majuscule :

...
n ← 65
Tant que (n 6 90)
a cher(carASCII(n))
n ← n+1
Fin Tant Que
...
et l'implémentation correspondante en Python 3 :

syntaxe python 3

...
n = 65
while (n <= 90) :
print(chr(n))
n = n+1
# Fin Tant Que
...
On notera l'importance de l'initialisation des variables utilisées dans la condition : si

n était initialisé par 95,

les instructions situées dans la boucle ne seraient jamais exécutées. Par ailleurs, les variables utilisées dans
la condition doivent évoluer dans le contenu de la boucle . . . faute de quoi on ne pourrait plus en sortir une
fois rentré ! (enlevez le

n←n+1

dans l'exemple précédent et vous verrez).

Et une mauvaise a ectation peut avoir le même e et. Le seul moyen de ne pas tomber dans le piège des
boucles in nies (ou jamais parcourues !) est de tester son algorithme à la main sur des cas simples . . . et là
les failles apparaissent. Essayez sur le morceau d'algorithme suivant :

...
n←5
Tant que n 6= 10
a cher(n)
n ← n+2
Fin Tant Que
...
Vous remarquerez dans ce cas que le problème peut disparaitre de di érentes façons :

ˆ
ˆ
ˆ

n ← n + 2 par n ← n + 1
n ← 5 par n ← 4
remplaçant la condition n 6= 10 par n < 10

par exemple en remplaçant
ou bien en remplaçant
ou encore en

U22 - Algorithmique - Chapitre n°3

Page 12/40

3.2.2

La boucle "Pour"

Il s'agit d'une boucle "comptée" dans laquelle le programme s'occupe de tout : initialisation de la variable
de comptage, son évolution et la condition d'arrêt. Sa structure est la suivante :

Pour VariableComptage allant de ValeurDébut à ValeurFin

action . . .
VariableComptage suivant
instruction suivante

Lorsque l'instruction "Pour" est rencontrée la première fois, le protocole suivant s'enclenche :

VariableComptage par ValeurDebut
tester la condition (VariableComptage 6 ValeurFin ) :

1. a ecter
2.

Si elle est vraie aller au point 3
Si elle est fausse aller au point 6
3. exécuter la séquence d'instructions de l'action
4. une fois en "V

ariableComptage suivant", incrémenter V ariableComptage (augmenter de 1)

5. aller au point 2
6. continuer l'algorithme à l'instruction "

instruction suivante "

On remarquera que cette boucle est équivalente à la structure "Tant Que" suivante :

VariableComptage ← ValeurDebut
Tant que (VariableComptage 6 ValeurFin)
action . . .
VariableComptage ← VariableComptage + 1
Fin Tant que

instruction suivante
Quatre points extrêmement importants sont à noter :
1. l'action n'est jamais jamais réalisée si
2. si

V aleurDebut > V aleurF in

V aleurDebut 6 V aleurF in,

l'action sera exécutée exactement (V
3. dans l'action, le contenu de

aleurF in − V aleurDebut + 1)

V ariableComptage

4. à la sortie de la boucle "pour",

fois

ne doit en aucun cas être modi é

V ariableComptage

contient la valeur (V

aleurF in + 1)

L'exemple du paragraphe précédent aurait pu aussi s'écrire comme ceci :

...
Pour n allant de 65 à 90
a cher(carASCII(n))
n suivant
...
ce qui donnerait une fois implémenté :

syntaxe Python 3

...
for n in range(65,91) :
print(ch(n))
# n suivant
...

U22 - Algorithmique - Chapitre n°3

Page 13/40

3.2.3

Imbrication

Là encore, les structures peuvent être imbriquées les unes dans les autres. Par exemple, la séquence suivante
a che les tables de multiplications de 2 à 9 :

...
Pour i allant de 2 à 9
a cher("Table des ",i," :")
Pour j allant de 1 à 10
a cher(i , " fois " , j , ' = ' , i×j)
j suivant
i suivant
...
ce qui, une fois implémenté, donnera :

syntaxe python 3

...
for i in range(2,10) :
print("Table des ",i," : ")
for j in range(1,11) :
print(i , " fois " , j , ' = ' , i*j)
# j suivant
# i suivant
...

U22 - Algorithmique - Chapitre n°3

Page 14/40

U22 - Chapitre n° 4
Les tableaux

4.1 Deux exemples pour se faire une idée
4.1.1 Un exemple à une dimension
Variables :

i : entier
Nom_Jour : tableau de chaînes à 1 dimension [0 . . . 6]
Début

...
Nom_Jour[0] ← "lundi"
Nom_Jour[1] ← "mardi"
...
Nom_Jour[6] ← "dimanche"
...
i ← résultat d'un calcul ou d'une saisie
a cher("ce jour là était un " , Nom_Jour[i])
...
Fin

4.1.2

Un exemple à deux dimensions

Un relevé de notes de 5 devoirs réalisés dans une classe de 31 étudiants est un tableau à deux dimensions :

ˆ
ˆ

l'indice de ligne correspondant à l'étudiant concerné
l'indice de colonne correspondant au devoir réalisé

La déclaration de ce tableau est :

Notes : tableau d'entiers à deux dimensions [0 . . . 30][0 . . . 4]

Par exemple la note du 6e étudiant (par ordre alphabétique) au 3e devoir est stockée dans

4.2 La théorie
4.2.1 Des variables

Notes[5][2].

à tiroirs . . .

Un tableau est comparable à un ensemble de boîtes dans lesquelles on va stocker des informations.
Il est repéré par un
et

Notes

nom

Nom_Jour

qui obéit aux même règles que les noms de variable (

dans l'exemple 1

dans l'exemple 2).

type qui dé nit le type des données qui y vont être stockées (chaine de caractères
l'exemple 1 et entier dans l'exemple 2).
Un tableau est aussi caractérisé par une dimension :
ˆ Un tableau à une dimension est comparable à une suite de cases, chacune repérée par un indice
Il possède aussi un

dans

(voir exemple 1)

ˆ

Un tableau

à deux dimensions

est comparable à un meuble à tiroirs, chacun repéré par un

indice de rangée (ou ligne) et un indice de colonne (voir exemple 2).
Chaque "case" ou "tiroir" s'appelle une

cellule et les indices commencent à 0. Pour repérer une cellule précise

dans un tableau, on place son indice entre crochets derrière le nom du tableau.
Un tableau à 2 dimensions est en fait un tableau à 1 dimension (les lignes) dont les cellules sont des tableaux
à 1 dimension (les colonnes).
Dans l'exemple 2, on peut considérer le relevé de notes comme un tableau à 1 dimension et 31 cellules (les
étudiants), chaque cellule étant un tableau à 1 dimension et 5 cellules (les notes).
deux dimensions et

N otes[3]

Notes

est un tableau à

est un tableau à 1 dimension et 5 cellules : les notes du quatrième étudiant.

U22 - Algorithmique - Chapitre n°4

Page 15/40

4.2.2
La

Taille d'un tableau

taille

d'un tableau est son nombre de cellules quand il s'agit d'un tableau à 1 dimension, et son nombre

de lignes et de colonnes pour un tableau à 2 dimensions.
Lors de la déclaration du tableau, la taille sera précisée si elle est prévisible et gée.
La fonction

ˆ
ˆ

long()

qui a été dé nie sur les chaines de caractères sera aussi utilisable pour les tableaux :

pour un tableau à 1 dimension, cette fonction renvoie le nombre de cellules
pour un tableau à 2 dimensions, cette fonction renvoie le nombre de lignes.

En reprenant les notations les exemples :

ˆ long(Nom_Jour) renvoie
ˆ long(Notes) renvoie 31
ˆ long(Notes[3]) renvoie 5

4.2.3

7

Affectation directe

Un tableau peut être initialisé par a ectation directe et globale.
Dans l'exemple 1, les 7 lignes d'initialisation pouvaient être remplacées par une seule :

Nom_Jour ← ["lundi","mardi","mercredi","jeudi","vendredi","samedi","dimanche"]
De même pour un tableau à 2 dimensions. Si vous voulez par exemple que le tableau
3

1

6

0

5

2

4

2

matrice

contienne :

vous pouvez l'a ecter de la façon suivante :

matrice ← [[3,1,6,0],[5,2,4,2]]

4.2.4

Extension d'un tableau

La taille d'un tableau n'est pas toujours prévisible dès le début d'un algorithme. On peut dans ce cas déclarer
un tableau qui sera initialisé

vide

. . . c'est à dire avec 0 cellule, et au gré des besoins on ajoute une nouvelle

cellule au tableau en y stockant une valeur. La taille du tableau évolue en conséquence.
On conviendra que la procédure
avec

valeur

étendre(N omT ableau,V aleur)

ajoute une cellule au tableau

N omT ableau

comme contenu.

machin est a ecté par [2,5,4], l'instruction ci-dessous augmentera sa taille
[2,5,4,8].

Par exemple, si le tableau d'entiers
de 1 et il contiendra ensuite

...
étendre(machin,8)
...
ce que je vous engage à tester en Python 3 avec les instructions suivantes :

éditeur python 3

>>> machin=[2,5,4]
>>> len(machin)

3
>>> machin.append(8)
>>> len(machin)
4
>>> machin
[2,5,4,8]
U22 - Algorithmique - Chapitre n°4

Page 16/40

4.3 Exemples rédigés
4.3.1 Test de lancer de

dés : un tableau de taille fixée

L'algorithme qui suit a pour but de tester le générateur aléatoire. Il simule 600 lancers de dé et a che, pour
chaque face, le nombre de fois où elle a été obtenue en agrémentant cela d'un diagramme bâton horizontal.

ALGORITHME : Lancers de dé
ROLE : Simuler 600 lancers de dés et a cher sous forme d'histogramme les résultats pour chaque face
ENTREES :
SORTIE : L'e ectif d'obtention de chaque face et une présentation en diagramme bâton horizontal
VARIABLES
i , j , lancer
: entiers
DEBUT

e ectif [0 .. 5]

: tableau d'entiers

e ectif ← [0,0,0,0,0,0]
# ===== simulation des lancers
pour i allant de 0 à 599
lancer ← PartieEntiere(6*alea())
e ectif[lancer] ← e ectif[lancer]+1
i suivant
# ===== a chage des résultats
a cher("Face <tab> E ectif <tab> Diagramme")
pour i allant de 0 à 5
a cher(i+1,<tab>,e ectif[i],<tab>,<rester sur la ligne>)
pour j allant de 0 à e ectif[i] 1
a cher("=",<rester sur la ligne>)
j suivant
a cher()
i suivant

# initialisation du tableau d'e ectifs à 0
# 600 lancers : boucle comptée de 600 tours
# nombre entier aléatoire de 0 à 5
# comptabiliser le résultat du lancer
# titres
# i varie de 0 à 5 ; face n (i+1)
# numéro de face et son e ectif
# a cher autant . . .
# . . . de signes "=" que . . .
# . . . l'e ectif de la face
# va à la ligne

FIN

ce que vous pouvez implémenter et sauvegarder sous le nom indiqué :

nom fichier : Cours_4_3_1.py

# ALGORITHME : Lancers de dé
# ROLE : Simuler 600 lancers de dés et
afficher sous forme d'histogramme les résultats pour chaque face
# ENTREES : # SORTIE : L'effectif d'obtention de chaque face et une présentation en diagramme bâton horizontal
# VARIABLES
i , j , lancer
: entiers
#
effectif [0 .. 5] : tableau d'entiers
# importation des modules utiles
from math import *
from random import *
# DEBUT
effectif = [0,0,0,0,0,0]
# initialisation du tableau d'effectifs à 0
# ===== simulation des lancers
for i in range(0,600) :
# 600 lancers : boucle comptée de 600 tours
lancer = floor(6*random())
# nombre entier aléatoire de 0 à 5
effectif[lancer] = effectif[lancer]+1
# comptabiliser le résultat du lancer
# i suivant
# ===== affichage des résultats
print("Face","Effectif","Diagramme",sep="\t")
# titres
for i in range(0,6) :
# i varie de 0 à 5; face n (i+1)
print(i+1,effectif[i],"",sep="\t",end="")
# numéro de face et son effectif
for j in range(0,effectif[i]) :
# afficher autant ...
print("=",end="")
# ... de signes "=" que ...
# j suivant
# ... l'effectif de la face
print()
# va à la ligne
# i suivant
# FIN
U22 - Algorithmique - Chapitre n°4

Page 17/40

4.3.2

Analyse d'une série de notes : un tableau à taille variable

L'algorithme qui suit saisit un certain nombre de notes et les stocke dans un tableau. La n de la saisie est
détectée par l'entrée d'une valeur supérieure strictement à 20 ou strictement négative.
Une fois la série terminée, l'algorithme détermine (et a che) le nombre de notes, les notes extrêmes et la
moyenne arrondie à 1 décimale.
Je vous laisse le soin d'analyser le contenu de cet algorithme et de l'implémenter en Python 3 en le sauvegardant sous le nom

Cours_4_3_2.py.

ALGORITHME : Série de notes
ROLE : Analyser une série de notes en calculant certaines caractéristiques
ENTREES : Une série de notes de 0 à 20
SORTIES : Le nombre de notes, la série de notes, les valeurs extrêmes et la moyenne (à 1 décimale)
VARIABLES :

DEBUT

i , nombre
note , maxi , mini , som
notes[ ]
ni

: entiers
: réels
: tableau de réels
: booléen

notes ← [ ]
# initialisation du tableau de notes (vide)
# ===== saisie des notes
ni ← Faux
# initialisation du détecteur de n de saisie
a cher("l'entrée d'une valeur négative ou supérieure à 20 arrête la saisie")
tant que (non ni)
note ← saisie("valeur suivante : ")
# saisie sous forme de nombre réel
ni ← ((note < 0) ou (note > 20))
# Vrai si note non valide
si (non ni) alors
# note valide donc à prendre en compte
étendre(notes,note)
# ajouter une cellule au tableau avec cette valeur
n si
n tant que
# ===== analyse de la série
nombre ← long(notes)
# nombre de notes saisies
si (nombre > 0) alors
# l'analyse n'est faite que si il y a des notes !
som ← notes[0]
# initialisation somme
maxi ← notes[0]
# initialisation valeur maximale
mini ← notes[0]
# initialisation valeur minimale
pour i allant de 1 à (nombre 1)
# parcours du reste du tableau
som ← som + notes[i]
# calcul de la somme
si (notes[i] > maxi) alors
maxi ← notes[i]
# nouveau maximum
sinon
si (notes[i] < mini) alors
mini ← notes[i]
# nouveau minimum
n si
n si
i suivant
n si
# ===== a chage des résultats
a cher("nombre de notes : ",nombre)
si (nombre > 0) alors
# l'a chage n'a de sens que si il y a des notes !
a cher("notes : ",notes)
a cher("moyenne : ",arrondi(som/nombre,1))
a cher("note maximale : ",maxi)
a cher("note minimale : ",mini)
sinon
a cher("il faudrait saisir au moins une note !")
n si
FIN

U22 - Algorithmique - Chapitre n°4

Page 18/40

4.3.3

Le triangle de Pascal : un tableau à deux dimensions

Le triangle de Pascal est un tableau de nombres permettant d'écrire le développement de

(a + b)n .

Il sera

approfondi en cours de dénombrement et seule sa construction nous intéresse ici.
En voici les premières lignes (complétées par des 0 pour en faire un tableau rectangulaire) :

1

0

0

0

0

0

0

1

1

0

0

0

0

0

1

2

1

0

0

0

0

1

3

3

1

0

0

0

1

4

6

4

1

0

0

1

5

10

10

5

1

0

1

6

15

20

15

6

1

On remarquera plusieurs choses :

ˆ
ˆ
ˆ
ˆ

si on veut écrire les

n

premières lignes du triangle, il faudra

n

colonnes

la première colonne ne contient que des "1"
seul le triangle inférieur gauche est non nul (d'où le nom de la chose)
chaque ligne s'obtient à partir de la précédente en additionnant deux cellules voisines et en
plaçant le résultat sous celle de droite.

L'algorithme suivant saisit le nombre de lignes désiré et les a chent. Faites-en un tracé pas à pas pour la
valeur

n = 4

a n de bien comprendre son fonctionnement. Il est également conseillé de l'implémenter en

Python 3 et de le sauvegarder sous le nom

Cours_4_3_3.py.

ALGORITHME : triangle de Pascal
ROLE : calculer et a cher un certain nombre de lignes du triangle de Pascal
ENTREES : le nombre de lignes désiré
SORTIES : a cher les lignes demandées
VARIABLES :
DEBUT

i,j,n
pascal[ ][ ]

: entiers
: tableau d'entiers

# ===== initialisations
n ← saisie("Nombre de lignes à a cher : ") # combien de lignes à calculer ?
pascal ← tableau n lignes , n colonnes de 0 # initialisation du tableau avec des 0 (voir note a )
pour i allant de 0 à (n 1)
# mettre la première colonne à 1
pascal[i][0] ← 1
i suivant
# ===== calcul des coe cients
pour i allant de 1 à (n 1)
# on va calculer la ligne i
pour j allant de 1 à i
# seulement les cellules à gauche de la diagonale
# somme des deux cellules de la ligne précédente (même colonne et colonne précédente)
pascal[i][j] ← pascal[i 1][j] + pascal[i 1][j 1]
j suivant
i suivant
# ===== a chage des résultats
pour i allant de 0 à (n 1)
# on va a cher la ligne i
pour j allant de 0 à i
# seulement les cellules à gauche de la diagonale
a cher(pascal[i][j],<rester sur la ligne>)
j suivant
a cher()
# aller à la ligne
i suivant
FIN

a.

en python, cette ligne se code : pascal=[[0 for j in range(0,n)] for i in range(0,n)]

U22 - Algorithmique - Chapitre n°4

Page 19/40

U22 - Chapitre n° 5
Procédures et Fonctions

5.1 La sous-traitance
5.1.1 Pourquoi ?
Le concept de

langage procédural, consistant à dé nir des sous-algorithmes

qui peuvent être appelés de façon

indépendante, présente trois avantages non négligeables :

ˆ
ˆ
ˆ

décomposer une tâche complexe en tâches plus simples traitées indépendamment
éviter la répétition d'une portion d'algorithme qui doit être exécutée plusieurs fois
permet la réutilisation d'une tâche routinière dans d'autres algorithmes (copier/coller d'un sous-algorithme)

5.1.2

La division des tâches

Le premier point est la clé de l'analyse dite

descendante

d'un problème. La tâche globale est subdivisée

en sous-problèmes con és à des équipes di érentes qui peuvent à leur tour, si elles en éprouvent le besoin,
les subdiviser à nouveau. Cette structure emboîtée en poupées russes doit évidemment s'assurer que
l'assemblage nal des briques conçues par les di érentes équipes et sous-équipes conduit de façon cohérente au résultat attendu. Chaque sous-algorithme doit donc obéir à un cahier des charges précis édicté par
l'algorithme qui fait appel à lui.
sous probleme 1-a

%
sous probleme 1

%

&

problème général

sous problème 1-b

&
sous problème 2
Cette structure se concrétisera en algorithme de la façon suivante :

sous-algorithme sous_probleme_1_a()

( . . .)

n sous-algorithme
sous-algorithme sous_probleme_1_b()

( . . .)

n sous-algorithme
sous-algorithme sous_probleme_1()

appeler sous_probleme_1_a()
appeler sous_probleme_1_b()

n sous-algorithme

sous-algorithme sous_probleme_2()

( . . .)

n sous-algorithme
algorithme probleme_general

( . . .)

DEBUT

( . . .)
appeler sous_probleme_1()
appeler sous_probleme_2()
( . . .)
FIN
U22 - Algorithmique - Chapitre n°5

Page 20/40

5.1.3

Éviter la répétition

Le deuxième point est dicté par un souci d'optimisation et permet d'éviter la répétition de séquences d'instructions identiques ou similaires. Il n'est pas rare, dans la résolution d'un problème, d'avoir à faire appel
plusieurs fois à une même tâche. Dans ce cas, un sous-algorithme exécutant cette tâche sera dé ni et appelé
plusieurs fois. D'un point de vue structure algorithmique, cela ressemble à cela :

sous-algorithme tache_a_repeter()

( . . .)

n sous-algorithme
algorithme probleme_general

( . . .)

DEBUT

( . . .)
appeler tache_a_repeter()
( . . .)
appeler tache_a_repeter()
( . . .)
appeler tache_a_repeter()
( . . .)
FIN

5.1.4

Fonctionnement général

Il est clair que les sous-algorithmes doivent être dé nis avant qu'un appel ne leur soit destiné. Par exemple
dans le premier encadré, déclarer

sous_probleme_1

avant de déclarer

sous_probleme_1_a engendrerait une

erreur. Comme dans un roman, il faut que les personnages soient présentés avant de les faire intervenir.
Par ailleurs, lors de l'appel d'un sous-algorithme, tout se passe comme si les instructions du sous-algorithme
étaient insérées à l'endroit de l'appel. Il est clair qu'au retour de l'appel, la machine reprend son histoire à
l'instruction qui suit l'appel.
Par exemple, dans la structure suivante :

1 sous-algorithme truc()
( . . .)
n sous-algorithme 2
3 sous-algorithme machin()
( . . .)
n sous-algorithme 4
5 algorithme probleme_general
( . . .)
DEBUT

( . . .)
appeler machin() 6 7
( . . .)
appeler truc() 8 9
( . . .)
appeler machin() 10 11
( . . .)
FIN 12
le cheminement suivi est :

5 → 6 → 3 → 4 → 7 → 8 → 1 → 2 → 9 → 10 → 3 → 4 → 11 → 12

U22 - Algorithmique - Chapitre n°5

Page 21/40

5.1.5

Syntaxe

Les noms donnés aux sous-algorithmes répondent aux mêmes exigences que les noms de variables : caractères
alphanumériques non accentués et trait de soulignement, le premier caractère étant obligatoirement une lettre.
Le nom doit se terminer par un couple de parenthèses (éventuellement vide) dont nous verrons l'utilité plus
loin.

5.2 Deux espèces de sous-algorithme
5.2.1 La procédure
La

procédure

est un sous-algorithme qui réalise une action. On l'appelle en écrivant tout simplement son

nom.
Voici un exemple de procédure qui envoie à l'écran un message d'erreur séparé par des lignes vides lorsqu'elle
est invoquée :

PROCÉDURE erreur()

passer une ligne
a cher("Erreur fatale rencontrée")
passer une ligne

FIN PROCÉDURE

ALGORITHME principal

( . . .)

DEBUT

( . . .)
Si (condition_1) Alors
erreur()
Sinon
Si (condition_2) Alors
(. . .traitement du problème . . .)
Sinon
erreur()
Fin Si
Fin si
(. . .)
FIN

Cet algorithme appellera la procédure et a chera le message d'erreur lorsque
quand elle ne l'est pas, si

5.2.2
La

condition_2

condition_1

sera remplie et,

ne l'est pas non plus.

La fonction

fonction

est un sous-algorithme qui renvoie une valeur. La dernière instruction d'une fonction sera le

renvoi de la valeur en question.
Contrairement à la procédure, elle n'est pas en elle-même une instruction mais doit intervenir, comme une
variable, dans une instruction de l'algorithme qui l'invoque.
Prenons par exemple un algorithme qui a régulièrement besoin d'une valeur de

π

à 5 décimales. Plutôt que

de taper à chaque fois cette valeur, on peut créer une fonction dont le nom est plus court à écrire :

U22 - Algorithmique - Chapitre n°5

Page 22/40

FONCTION pi_()

renvoyer 3,14159

FIN FONCTION

ALGORITHME principal

( . . .)

DEBUT

a cher("une valeur arrondie de PI est : " , pi_())
R←5
a cher("le périmètre du cercle de rayon " , R , " vaut " , 2×pi_()×R)
a cher("et son aire vaut " , pi_()×R2 )
FIN

Un autre intérêt dans cette façon de procéder est que si par la suite on a besoin de résultats plus précis, il
su t d'augmenter le nombre de décimales à un seul endroit : dans le corps de la fonction.

5.2.3

Des sous-algorithmes adaptables

Il est clair que les deux exemples donnés ci-dessus sont quelque peu gés et il serait bon de leur donner un
peu de souplesse.
Prenons l'exemple de la procédure a chant un message d'erreur. Elle pourrait être modi ée de la façon
suivante :

PROCÉDURE
erreur(message)
ARGUMENT message : chaîne de caractères
RÔLE
a cher un message d'erreur

passer une ligne
a cher("Erreur fatale rencontrée : " , message)
passer une ligne

FIN PROCÉDURE

ALGORITHME principal

( . . .)

DEBUT

( . . .)
Si (condition_1) Alors
erreur("division par zéro")
Sinon
Si (condition_2) Alors
(. . .traitement du problème . . .)
Sinon
erreur("racine d'un nombre négatif")
Fin Si
Fin si
(. . .)
FIN

Au moment de l'appel, la valeur mise entre parenthèses est transférée dans la variable

message

servant

d'argument à la procédure.
Lorsque la

condition_1

est remplie, on va voir s'a cher

et lorsque aucune condition n'est remplie, on verra

Erreur fatale rencontrée : division par zéro,

Erreur fatale rencontrée : racine d'un nombre négatif.

De même, l'exemple de fonction donné précédemment serait également plus souple si le nombre de décimales
de l'arrondi n'était pas prédéterminé :

U22 - Algorithmique - Chapitre n°5

Page 23/40

FONCTION
pi_(n)
ARGUMENT
n : entier
TYPE RETOURNE
réel
RÔLE : retourner une valeur de π arrondie à n décimales (n 6 11)
VARIABLE LOCALE
pi_11 : réel

pi_11 ← 3,14159265359
renvoyer arrondi(pi_11 à n décimales)

FIN FONCTION

ALGORITHME principal
DEBUT

a cher("une valeur arrondie de PI à 5 décimales est : " , pi_(5))
R←5
a cher("le périmètre du cercle de rayon " , R , " vaut " , 2×pi_(3)×R)
a cher("et son aire vaut " , pi_(6)×R2 )
FIN

Dans ce cas, le calcul de périmètre se fera avec une précision de 3 décimales et celui de l'aire avec 6 décimales.

5.2.4

Conventions d'écriture

Un sous-algorithme étant en lui même un algorithme, sa rédaction répond aux même règles et doit comporter
les commentaires et déclarations usuels (rôle, variables locales, . . .). Il faut y ajouter les types des arguments
passés et, dans le cas d'une fonction, le type de la valeur retournée (qui peut aussi être un tableau).

5.3 Fonctions et procédures avec arguments
5.3.1 Le passage d'arguments
Nous avons vu dans les deux derniers exemples l'intérêt d'avoir une procédure ou une fonction pouvant
s'adapter à un contexte particulier. Cela se fait en transmettant des paramètres dont le sous-algorithme va
pouvoir se servir pour opérer son traitement.
Les arguments passés gurent entre parenthèses dans la déclaration du sous-algorithme. Ils peuvent être
de types di érents et sont représentés par des noms de variable qui seront utilisé dans le corps du sousalgorithme. Dans le cas de plusieurs arguments, les variables sont séparées par des virgules et l'ordre dans
lequel ils sont déclarés est extrêmement important.
Prenons par exemple la déclaration commençant de la façon suivante :

PROCEDURE
bidule(n , p , test , message)
ARGUMENTS n , p
: entiers

test
message

: booléen
: chaîne de caractères

Les appels de cette procédure ne seront valables que si 4 valeurs sont transmises : deux entiers, un booléen
et une chaîne de caractères, dans cet ordre. Avant de commencer à travailler, la procédure va a ecter les
variables

n, p, test

et

message

par les 4 valeurs respectives transmises.

bidule(3,5,Vrai,"bonjour")

Par exemple l'appel

est correct, de même que

bidule(5,3,Vrai,"bonjour") . . . qui
n ← 3 et p ← 5 alors que dans

donnera probablement un résultat di érent du précédent (dans le premier cas
le second cas

n←5

et

Par contre les appels
ou

bidule(3,5,Vrai,7)

p ← 3).

bidule(3.2,5,Vrai,"bonjour") , bidule(3,5,"Vrai","bonjour") , bidule("3",5,Vrai,"bonjour")

ne sont pas cohérents et engendrent une erreur.

On peut également transmettre une valeur à un sous-algorithme grâce à une variable dont le type est cohérent
avec l'argument correspondant.
Par exemple dans la procédure précédente, l'appel

Nombre_Cas

est une variable entière et

Fini

commencer par transférer les contenus des variables
U22 - Algorithmique - Chapitre n°5

bidule(Nombre_Cas,5,Fini,"salutation")

est correct si

une variable de type booléen. Dans ce cas, la procédure va

Nombre_Cas

et

Fini

dans les variables

n

et

test.
Page 24/40

5.3.2

Un exemple de procédure avec deux arguments

Je vous laisse analyser et véri er les a chages de la procédure et du programme principal suivant :

PROCEDURE
repetition(n , texte)
ARGUMENTS n
: entier

texte
: chaîne de caractères
a che n fois la chaîne texte en séparant par un espace
i
: entier
Pour i allant de 1 à n
a cher(texte," ") en restant sur la même ligne
i suivant
aller à la ligne
ROLE
VARIABLE

FIN PROCEDURE
ALGORITHME
ROLE
ENTREES
SORTIES
VARIABLES
DEBUT

principal
tester la procédure repetition
aucune
a chage de di érents appels par la procédure
Nbre
: entier
Interjection
: chaine de caractères

repetition(4,"Ha")
Nbre ← 3
repetition(Nbre,"Oui")
Interjection ← "Ho"
repetition(Nbre+2, Interjection)
repetition(Nbre-2, "Interjection")
FIN

# a che à l'écran : Ha Ha Ha Ha
# a che à l'écran : Oui Oui Oui
# a che à l'écran : Ho Ho Ho Ho Ho
# a che à l'écran : Interjection

puis l'implémenter en Python 3 :

nom de fichier : Cours_5_3_2.py

def repetition(n , texte):
# TYPE
procédure
# ARGUMENTS
n
: entier
#
texte
: chaîne de caractères
# ROLE
affiche n fois la chaîne texte en séparant par un espace
# VARIABLE
i
: entier
for i in range(n):
print(texte,end=" ")
# i suivant
print()
# FIN PROCEDURE
# ALGORITHME
principal
# ROLE
tester la procédure repetition
# ENTREES
aucune
# SORTIES
affichage de différents appels par la procédure
# VARIABLES
Nbre
: entier
#
Interjection : chaine de caractères
# DEBUT
repetition(4,"Ha")
# affiche à l'écran : Ha Ha Ha Ha
Nbre = 3
repetition(Nbre,"Oui")
# affiche à l'écran : Oui Oui Oui
Interjection = "Ho"
repetition(Nbre+2, Interjection)
# affiche à l'écran : Ho Ho Ho Ho Ho
repetition(Nbre-2, "Interjection")
# affiche à l'écran : Interjection
# FIN

U22 - Algorithmique - Chapitre n°5

Page 25/40

5.3.3

Un classique : la fonction factorielle

Le factoriel d'un entier
et

6! = 720.

n,

noté

n!,

est le produit de tous les entiers de 1 à

n.

Par exemple

3! = 1 × 2 × 3 = 6

Voici un exemple d'écriture de cette fonction :

FONCTION
ARGUMENT
TYPE RENVOYE
ROLE
VARIABLES

factoriel(n)
n
: entier
entier
renvoie le produit de tous les entiers de 1 à n
i , resultat
: entiers

resultat ← 1
Pour i allant de 1 à n
resultat ← resultat × i
i suivant
renvoyer resultat

FIN FONCTION

Notons que ce n'est pas la variable

resultat

qui est retournée, mais son contenu (une valeur numérique). Je

vous laisse le soin de véri er les a chages de ce programme test utilisant la fonction

ALGORITHME
ROLE
ENTREES
SORTIES
VARIABLES
DEBUT

factoriel

:

principal
tester la fonction factoriel
aucune
a chage de di érents retours de la fonction
Nbre1 , Nbre2
: entiers

a cher(factoriel(4))
Nbre1 ← 5
Nbre2 ← 2× factoriel(Nbre1 2) 1
a cher(factoriel(Nbre1))
a cher(factoriel((3 × Nbre2) mod Nbre1))
a cher(factoriel(Nbre2) div factoriel(Nbre1))

FIN

# a che à l'écran : 24
# Nbre2 est a ecté par la valeur 11
# a che à l'écran : 120
# a che à l'écran : 6
# a che à l'écran : 332640

puis de tester le tout en Python 3 :

nom de fichier : Cours_5_3_3.py

def factoriel(n):
# TYPE
fonction
# ARGUMENTS
n
: entier
# TYPE RENVOYE
entier
# ROLE
renvoie le produit de tous les entiers de 1 à n
# VARIABLES
i , resultat
: entiers
resultat = 1
for i in range(1,n+1):
resultat = resultat * i
# i suivant
return resultat
# FIN FONCTION
# ALGORITHME
principal
# ROLE
tester la fonction factoriel
# ENTREES
aucune
# SORTIES
affichage de différents retours de la fonction
# VARIABLES
Nbre1 , Nbre2
: entiers
# DEBUT
print(factoriel(4))
# affiche à l'écran : 24
Nbre1 = 5
Nbre2 = 2*factoriel(Nbre1 2) 1
# Nbre2 est affecté par la valeur 11
print(factoriel(Nbre1))
# affiche à l'écran : 120
print(factoriel((3*Nbre2) % Nbre1))
# affiche à l'écran : 6
print(factoriel(Nbre2) // factoriel(Nbre1)) # affiche à l'écran : 332640
# FIN
U22 - Algorithmique - Chapitre n°5

Page 26/40

5.4 La portée des variables
5.4.1 Quel est le problème ?
Le concept de sous-algorithme est induit par la notion de travail en équipe. Un gros projet est géré par un
chef d'équipe qui va le décomposer en sous-projets, chacun avec un cahier des charges précis, et le con er
à des groupes distincts. Le chef de projet réalise l'algorithme principal qui fera appel aux sous-algorithmes
fournis par les di érents groupes. Chaque chef de groupe peut réitérer ce processus de division du travail
à l'intérieur de son groupe s'il en éprouve le besoin. Chaque groupe ou sous-groupe va ensuite travailler de
façon indépendante et, une fois les di érents modules réalisés, ils seront insérés dans le projet nal comme
des briques de construction . . . et cela doit fonctionner !
Comme elles ne communiquent pas ensemble durant la mise au point des sous-projets, il est tout à fait
possible que plusieurs équipes di érentes utilisent au sein de leur sous-algorithme des variables portant le
même nom (par exemple un compteur

i).

Il est clair que ces variables homonymes ne doivent pas interférer

une fois les sous-algorithmes aboutés dans le projet nal.
De même, il est tout à fait possible que le chef de projet manipule dans son algorithme principal des variables
contenant des données générales importantes pour le bon fonctionnement de l'ensemble. Il serait mal venu
que les sous-algorithmes modi ent les contenus de ces variables . . . même si, par le plus grand des hasards,
ils manipulent des variables de même nom.
Ce qui suit n'est pas simple, c'est même assez subtil . . . mais cela joue un rôle fondamental en programmation
et demande à être bien compris !

5.4.2

Variables globales et locales

Prenons déjà le cas simple d'un algorithme principal appelant un sous-algorithme :

variables globales.
Les variables déclarées et a ectées dans le sous-algorithme sont des variables locales à ce sous-algorithme.
Les arguments passés au sous-algorithme sont des variables locales et leur a ectation se fait automatiquement
Les variables déclarées et a ectées dans l'algorithme principal sont des

lors de l'appel du sous-algorithme.
Par exemple dans la structure suivante :

PROCEDURE
alphonse(n , texte)
ARGUMENTS n
: entier
ROLE
VARIABLE

(. . .)
i←7
(. . .)

texte
...
i

: chaîne de caractères
: entier

FIN PROCEDURE
ALGORITHME
ROLE
VARIABLES
DEBUT

principal
...
Nb
message

: entier
: chaine de caractères

Nb ← 3
message ← "truc"
alphonse(Nb,message)
FIN
les variables

Nb

et

message

A l'appel de la procédure,

sont des variables globales et les variables

n

et

texte

n , texte

et

i

sont des variables locales.

sont initialisées par a ectation des valeurs respectives 3 et "truc" et

i

est ensuite initialisé par la valeur 7.
U22 - Algorithmique - Chapitre n°5

Page 27/40

Albert appelle
Bernard qui, lui-même, appelle le sous-algorithme Chloé, il faut avoir conscience que les
à Bernard sont locales pour Albert, mais globales pour Chloé. Par contre les variables de

Dans le cas d'un appel en cascade, le schéma se répercute à chaque niveau : si l'algorithme
le sous-algorithme
variables propres

Albert

sont globales pour les deux sous-algorithmes.

5.4.3

Visibilité des variables

A chaque étape du déroulement d'un algorithme, les variables globales sont visibles et leurs contenus
peuvent être utilisés par les sous-algorithmes appelés alors que les variables locales ne sont visibles que
dans le sous-algorithme où elles sont dé nies. Mais bien qu'il puisse voir une variable qui lui est globale,
un sous-algorithme ne peut pas en modi er la valeur.
Des exemples s'imposent !
Véri ez attentivement le bien-fondé des commentaires . . . et l'a chage obtenu dans l'exemple suivant :

Esclave(n)
n
: entier # n est une variable locale a ectée lors de l'appel
i
: entier # i est une variable locale qui doit être a ectée dans la procédure
i←7
# a ectation de la variable locale i
a cher("i=",i ," n=",n) # a che des contenus locaux
n←i+n
# a ectation d'une variable locale par des valeurs locales
i ← Nb + n
# a ectation d'une variable locale en utilisant la variable globale Nb
a cher("i=",i ," n=",n) # a che des contenus locaux
a cher("Nb=",Nb)
# a che un contenu global
FIN PROCEDURE
# n d'existence des variables i et n

PROCEDURE
ARGUMENTS
VARIABLE

ALGORITHME
VARIABLES
DEBUT

Nb ← 3
Esclave(Nb)
a cher("Nb=",Nb)
Nb ← Nb + 5
Esclave(Nb+4)
a cher("Nb=",Nb)
FIN

Maitre
Nb : entier
# la variable globale Nb contient 3
# appel de la procédure avec transfert du contenu de Nb dans n
# la variable Nb n'a pas été a ectée par la procédure
# la variable globale Nb vaut maintenant 8
# appel de procédure avec transfert de 12 dans l'argument n
# la variable Nb n'a pas été a ectée par la procédure

A chage obtenu : i=7 n=3 / i=13 n=10 / Nb=3 / Nb=3 / i=7 n=12 / i=27 n=19 / Nb=8 / Nb=8
Mais attention ! L'encadré suivant comporte moult erreurs à bien comprendre :

PROCEDURE
ARGUMENTS
VARIABLE

i ← n + Nb
Nb ← n + i

FIN PROCEDURE
ALGORITHME
VARIABLES
DEBUT

Nb ← 3
Esclave(Nb)
Nb ← 3 × n
a che(i)
FIN

Esclave(n)
n
: entier # n est une variable locale a ectée lors de l'appel
i
: entier # i est une variable locale qui doit être a ectée dans la procédure
# pas de problème : on peut a ecter une locale en utilisant une globale
# ERREUR : la procédure n'est pas autorisée à modi er une variable globale
# les variables i et n n'existent plus à partir de là
Maitre
Nb : entier
# la variable globale Nb contient 3
# appel de la procédure avec transfert du contenu de Nb dans n
# ERREUR : variable locale n invisible d'ici
# ERREUR : variable locale i invisible d'ici

Cela étant vu, que se passe-t-il lorsque des variables globales et locales portent le même nom ?

U22 - Algorithmique - Chapitre n°5

Page 28/40

5.4.4

Le comportement des homonymies

Lorsqu'un sous-algorithme rencontre une variable locale portant le même nom qu'une variable globale, il met
le contenu de la variable globale de côté a n de pouvoir le restituer en sortant.
L'exemple suivant illustre la chose :

Esclave(x)
x
: entier # x est une variable locale a ectée lors de l'appel
y
: entier # y est une variable locale qui doit être a ectée dans la procédure
y←2
# a ectation de la variable locale y
x ← x+10
# modi cation de la variable locale x
a cher("dans la procédure : x=",x ," y=",y)
FIN PROCEDURE
# restitue les valeurs initiales des variables globales x et y

PROCEDURE
ARGUMENTS
VARIABLE

ALGORITHME
VARIABLES
DEBUT

Maitre
x , y : entiers # ces variables sont globales

x←3
# la variable globale x contient 3
y←5
# la variable globale y contient 5
a cher("dans l'algorithme principal avant l'appel de procédure : x=",x," y=",y)
Esclave(x)
# appel de la procédure avec transfert du contenu de x(global) dans x(local)
a cher("en premier retour de procédure : x=",x," y=",y)
x ← x+y
# ce sont ici les variables globales qui sont en jeu
Esclave(x+1)
# appel de procédure avec transfert de 9 dans l'argument x(local)
a che ("en second retour de procédure : x=",x," y=",y)
FIN

et va provoquer l'a chage suivant (à véri er) :
dans l'algorithme principal avant l'appel de procédure : x=3 y=5
dans la procédure : x=13 y=2
en premier retour de procédure : x=3 y=5
dans la procédure : x=19 y=2
en second retour de procédure : x=8 y=5
Pour le fun je vous laisse le soin de véri er que l'appel en cascade suivant :

FONCTION
VARIABLE

x←2
renvoyer x

FIN FONCTION
PROCEDURE
VARIABLE

x←3
a cher(x)
a cher(Esclave())
a cher(x)

FIN PROCEDURE
ALGORITHME
VARIABLES
DEBUT

x←1
a cher(x)
a cher(Esclave())
a cher(x)
Disciple
a cher(x)
FIN

Esclave()
x
: entier # x est une variable locale qui doit être a ectée dans la procédure
# a ectation de la variable locale x
# retourne le contenu de la variable locale x
# restitue la valeur de x initiale à celui qui a appelé
Disciple()
x
: entier # x est une variable locale qui doit être a ectée dans la procédure
# a ectation de la variable locale x
# a cher le contenu de la variable locale x (globale pour Esclave)
# a che ce que renvoie la fonction Esclave
# a cher le contenu de la variable locale x
# restitue la valeur de x initiale à celui qui a appelé
Maitre
x
: entiers # cette variable est globale
# a ectation de la variable globale x
# a cher le contenu de la variable globale x
# a che ce que renvoie la fonction Esclave
# a cher le contenu de la variable globale x
# appelle la procédure disciple
# a che le contenu de la variable globale x

a che (sur plusieurs lignes) : 1 / 2 / 1 / 3 / 2 / 3 / 1
U22 - Algorithmique - Chapitre n°5

Page 29/40

U22 - Chapitre n° 6
La récursivité

6.1 La magie de l'auto-référence
6.1.1 Un petit exemple ?
Plaçons-nous dans le cadre de l'organigramme hiérarchique d'une entreprise et considérons la dé nition
suivante de "supérieur" d'un individu :

supérieur

: chef du service ou supérieur du chef de service

Au premier abord, cette dé nition semble totalement stupide puisque le mot à dé nir est utilisé dans sa
propre dé nition. Cela nous procure le sentiment de vouloir soulever la chaise sur laquelle nous sommes
assis !
Procédons à une analyse plus approfondie de la chose . . .

6.1.2

Une fonction auto-référentielle

Le but est de dé nir, au regard de l'organigramme, si dans l'entreprise une personne
individu

B.

FONCTION supérieur(A,B)
VARIABLE LOCALE

si B est au sommet de l'organigramme alors
test ← faux
sinon
si A est le chef de service de B alors
test ← vrai
sinon
test ← supérieur(A,chef de service de B)
n si
n si
retourner test

FIN FONCTION

6.1.3

A est un supérieur d'un

La dé nition donnée ci-dessus correspond à la fonction booléenne suivante :

test : booléen
# point 1
# point 2
# point 3
# point 4

Comment ça marche ?

Prenons comme base l'organigramme hiérarchique suivant :

Astride

Boris

David

Igor

Julieta

Traçons deux appels de la fonction

U22 - Algorithmique - Chapitre n°6

Erwan

superieur

Chakira

Farid

Kasumi

Grichka

Liliane

Honoré

Manuelo

en repérant les individus par leur initiale.

Page 30/40

1er cas : Si on appelle la fonction superieur(A, K) (appel 0)
ˆ
ˆ
ˆ

ˆ
ˆ

création d'une première variable locale

K

ˆ
ˆ

du niveau 0

possède un chef de service et que ce n'est pas

pour a ecter

ˆ
ˆ
ˆ

test

A, on va au point 3
superieur(A, G) (appel 1)
création d'une deuxième variable locale test au niveau 1
comme G possède un chef de service et que ce n'est pas A, on va au point 3
pour a ecter test on appelle la fonction superieur(A, C) (appel 2)
ˆ
création d'une troisième variable locale test au niveau 2
ˆ
comme C possède un chef de service et que c'est A, on va au point 2
ˆ
test est donc a ecter par Vrai et on va au point 4
ˆ
l'appel 2 de la fonction retourne donc la valeur Vrai à l'appel 1
l'appel 1 a ecte test du niveau 1 par Vrai en son point 3 et va au point 4

comme

test

on appelle la fonction

l'appel 1 de la fonction retourne donc la valeur Vrai à l'appel 0

l'appel 0 a ecte

test

l'appel de la fonction

de niveau 0 par Vrai en son point 3 et va au point 4

superieur(A, K)

nous renvoie la valeur Vrai

2e cas : Si on appelle la fonction superieur(G, J) (appel 0)
ˆ
ˆ
ˆ

ˆ
ˆ

création d'une première variable locale
pour

ˆ
ˆ
ˆ

ˆ
ˆ

J

test

du niveau 0

G, on va au point 3
a ecter test on appelle la fonction superieur(G, D) (appel 1)
création d'une deuxième variable locale test au niveau 1
comme D possède un chef de service et que ce n'est pas G, on va au point 3
pour a ecter test on appelle la fonction superieur(G, B) (appel 2)
ˆ
création d'une troisième variable locale test au niveau 2
ˆ
comme B possède un chef de service et que ce n'est pas G, on va au point
ˆ
pour a ecter test on appelle la fonction superieur(G, A) (appel 3)
ˆ
création d'une quatrième variable locale test au niveau 3
ˆ
comme A ne possède pas de chef de service on va au point 1
ˆ
test est donc a ectée par Faux et on va au point 4
ˆ
l'appel 3 de la fonction retourne donc la valeur Faux à l'appel 2
ˆ
l'appel 2 a ecte test de niveau 2 par Faux et on va au point 4
ˆ
l'appel 2 de la fonction retourne donc la valeur Faux à l'appel 1
l'appel 1 a ecte test du niveau 1 par Faux en son point 3 et va au point 4

comme

possède un chef de service et que ce n'est pas

3

l'appel 1 de la fonction retourne donc la valeur Faux à l'appel 0

l'appel 0 a ecte

test

l'appel de la fonction

de niveau 0 par Faux en son point 3 et va au point 4

superieur(A, K)

nous renvoie la valeur Faux

Au travers de cette exemple, on comprend la philosophie de la chose : la fonction s'appelle elle-même avec
des paramètres à chaque fois di érents, jusqu'à ce qu'une condition d'arrêt permette de calculer un vrai
résultat et stoppe cette mise en abîme.

6.2 La solution est en vous . . .
6.2.1 Définition de la récursivité
Une fonction ou procédure est dite

récursive

lorsqu'elle possède, dans le corps de sa dé nition, au moins un

appel à elle-même.

6.2.2

Je vous demande de vous arrêter !

Il est évident que si vous expliquez à quelqu'un que pour additionner 7 et 5, il su t d'additionner 7 et 5 . . .
vous n'apportez aucun élément pour aboutir au résultat ! L'appel récursif tourne ici en boucle in nie.
Pour qu'une dé nition récursive se termine en un temps ni, il faut que chaque nouvel appel se fasse en
transmettant des paramètres di érents, diminuant la di culté du problème, pour cheminer vers un cas où le
résultat sera calculé sans avoir recours à un nouvel appel.
U22 - Algorithmique - Chapitre n°6

Page 31/40

6.2.3

Fonctionne avec pile

Nous avons vu dans le premier exemple qu'un même nom de variable va être utilisé moult fois. Il est donc
nécessaire, lors d'un nouvel appel, de laisser au vestiaire les contenus des variables juste avant l'appel a n
de les récupérer lors du retour de l'appel. Ce problème a déjà été évoqué et détaillé à la n du chapitre
précédent.
Pour réaliser ce prodige sans s'emmêler les pinceaux, on utilise une zone mémoire de stockage, appelé pile

LIFO

(Last In First Out), qui fonctionne comme un empilement d'assiettes : la dernière posée sur la pile

sera la première à resservir quand on dépilera.
Le fonctionnement de cette pile est détaillé dans l'exemple qui suit (la dernière valeur entrée est à gauche).

6.2.4

La fonction factorielle, le retour !

Dans le chapitre précédent, nous avons déjà dé ni cette fonction. Nous allons le refaire, cette fois de façon
récursive :

FONCTION Factoriel(n)
Argument n : entier
Type retourné : entier
Rôle : calculer le produit des entiers de 1 à n

si (n=1) alors
retourner 1
sinon
retourner Factoriel(n 1) × n
n si

FIN FONCTION

Étonnant de simplicité, n'est-il pas ? Traçons précisément l'appel

ˆ
ˆ

ˆ

met 4 sans

ˆ
ˆ

(qui renvoie 24) :

n

va dans le "sinon" du 1er appel et doit appeler

ˆ
ˆ

F actoriel(4)

F actoriel(3)

met sur la pile l'ancienne valeur de n (la pile contient [4]) et met 3 dans
va dans le "sinon" du 2e appel et doit appeler F actoriel(2)

ˆ
ˆ

ˆ
ˆ

n

met sur la pile l'ancienne valeur de n (la pile contient [3 ; 4]) et met 2 dans
va dans le "sinon" du 3e appel et doit appeler F actoriel(1)

ˆ
ˆ
ˆ

n

met sur la pile l'ancienne valeur de n (la pile contient [2 ; 3 ; 4]) et met 1 dans
la condition est remplie au 4e appel : renvoie la valeur 1
quitte le 4e appel et dépile la valeur de n : n vaut 2 (la pile contient [3 ; 4])

n

revient dans le calcul du "sinon" du 3e appel et renvoie la valeur 1 × 2, c'est à dire 2
quitte le 3e appel et dépile la valeur de n : n vaut 3 (la pile contient [4])
revient dans le calcul du "sinon" du 2e appel et renvoie la valeur 2 × 3, c'est à dire 6
quitte le 2e appel et dépile la valeur de n : n vaut 4 (la pile est vide)

revient dans le calcul du "sinon" du 1er appel et renvoie la valeur 6

×

4, c'est à dire 24

6.3 Réflexions sur le procédé
6.3.1 Le piège classique
Dans l'utilisation de la récursivité, le plus délicat est de véri er que les appels en cascade vont s'arrêter.
Dans le cas contraire, l'algorithme va s'enfoncer en profondeur à l'in ni dans les appels récursifs. Dans la
pratique, la machine ayant une mémoire limitée, le programme va "planter" lorsque la pile sera saturée.
Il est donc indispensable de tracer l'algorithme précisément "à la main" pour des valeurs raisonnables des
paramètres a n de s'assurer que le processus se termine et "remonte" après un nombre ni d'opérations.

6.3.2

À utiliser avec modération

L'utilisation de la récursivité n'est pas toujours judicieuse !
U22 - Algorithmique - Chapitre n°6

Page 32/40

Reprenons l'exemple du triangle de Pascal vu à la n du chapitre sur les tableaux et créons de façon récursive
la fonction

p

P ascal(n, p)

dont le but est de renvoyer le coe cient de la ligne

n

et colonne

p

du tableau (n et

sont des entiers positifs ou nuls) :

FONCTION Pascal(n , p)
Arguments
Type retourné

n , p : entiers
entier
# on est en première colonne ou sur la diagonale

si ((p=0) OU (n=p)) alors
retourner 1
sinon
# se calcule avec la ligne précédente
retourner Pascal(n-1 , p) + Pascal(n-1 , p-1)
n si

Fin FONCTION

Une première remarque est de constater que chaque appel invoque deux fois la fonction. Analysons sous
forme arborescente l'appel

P ascal(4, 2)

(qui doit retourner 6) :

Pascal(4,2)

Pascal(3,2)

Pascal(2,2)

Pascal(3,1)

Pascal(2,1)

1

Pascal(2,1)

Pascal(2,0)

Pascal(1,1)

Pascal(1,0)

Pascal(1,1)

Pascal(1,0)

1

1

1

1

1

Cet arbre permet de constater que les appels récursifs se terminent bien, que le résultat nal vaut bien 6,
mais aussi que la fonction

P ascal(2, 1)

a été calculée plusieurs fois.

Cela représente donc une redondance et une perte de temps qui devient importante lorsque nous transmettons
des valeurs plus élevées. Ici, l'utilisation de la récursivité ne s'avère pas très judicieuse !

6.3.3

En bouquet final : les tours de Hanoï

L'histoire de ce divertissement se perd dans la nuit des temps et il est répertorié sous di érentes appellations :
tours de Hanoï, de Brahma

1

2

ou de Lucas .

Un plateau de jeu comporte 3 tiges verticales et sur l'une d'entre elles sont empilés des disques de tailles
décroissantes, les deux autres étant vides (tapez "tour de Hanoï" dans un moteur de recherche d'images). Le
but est de transférer la pile de disque sur un autre pic en respectant les deux règles suivantes : on ne bouge
qu'un disque à la fois et on ne peut pas poser un disque sur un autre plus petit que lui.
Par exemple, pour transférer une pile de 3 disques du pic no 1 sur le pic no 2, on procède de la façon suivante :

ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
ˆ

passer le disque 1 (le plus petit) du pic 1 au pic 2
passer le disque 2 (le moyen) du pic 1 au pic 3
passer le disque 1 du pic 2 au pic 3 (en le posant sur le 2)
passer le disque 3 (le grand) du pic 1 au pic 2 (maintenant libre)
passer le disque 1 du pic 3 au pic 1 (qui est vide)
passer le disque 2 du pic 3 au pic 2 (en le posant sur le 3)
passer le disque 1 du pic 1 au pic 2 (en le posant sur le 2. . . TERMINE)

n disques, le nombre
2n − 1. Pour la petite histoire, l'anecdote rapporte que des moines d'un temple

Cela nous a demandé 7 manipulations. On démontre que pour transférer une pile de
minimal de manipulations est

1. Dieu créateur dans la religion Hindouiste
2. du nom du mathématicien Édouard LUCAS du XIXe siècle
U22 - Algorithmique - Chapitre n°6

Page 33/40

Bouddhiste devaient transférer 64 disques d'or et que l'aboutissement du transfert déclencherait la n du
monde. Une estimation optimiste consistant à considérer que les moines transfèrent 1 disque par seconde sans
jamais se tromper . . . nous conduit à une durée d'environ 580 milliards d'années pour réaliser l'opération !
Dormez tranquilles, braves gens !
L'algorithme de transport des disques se règle aisément de façon récursive. Prenons l'exemple du transfert
de 7 disques du pic 1 au pic 2. Le disque 7 étant le plus grand, n'importe quel autre peut être posé dessus. Il
su t donc de transporter les 6 autres disques du pic 1 au pic 3 en ignorant le disque 7, puis le disque 7 du
pic 1 au pic 2, puis ramener les 6 autres disques du pic 3 au pic 2 où la pile va se reconstituer sur le disque
7. Ainsi, nous voyons que si nous sommes capable de transférer une pile de 6 disques, alors nous savons le
faire pour 7. C'est le principe même de la récursivité.
Une dernière remarque avant de passer à l'algorithme : les pics étant numérotés de 1 à 3, leur somme vaut
6. Cela implique que si je veux transférer du pic
numéro

a

vers le pic

b,

le pic intermédiaire (le troisième) a pour

(6 − a − b).

PROCEDURE Hanoi(n,a,b)
Arguments
n , a , b : entiers
Rôle
transférer n disques du pic a vers le pic b
Sortie
a cher la manipulation à opérer
Variable locale
inter : entier

si (n=1) alors
# bouger 1 disque (celui du dessus)
a cher("porter un disque du pic ",a," au pic ",b)
sinon
# bouger une pile de n disques
inter ← 6 a b
# numéro du troisième pic
Hanoi(n 1,a,inter)
# envoyer n − 1 disques vers le pic intermédiaire
Hanoi(1,a,b)
# bouger le plus grand disque
Hanoi(n 1,inter,b)
# ramener n − 1 disques du pic intermédiaire
n si

Fin PROCEDURE

On constate que la procédure s'appelle trois fois, mais en transmettant un nombre de disques plus petit, et
qu'elle se résout lorsque ce nombre de disque vaut 1.
La traduction en python, que je vous engage à implémenter est la suivante :

nom de fichier: Cours_6_3_3.py

def Hanoi(n,a,b):
# Type:
# Arguments:
# Rôle:
# Sortie:
# Variable locale:
if (n==1) :
print("porter un disque
else :
inter = 6 a b
Hanoi(n 1,a,inter)
Hanoi(1,a,b)
Hanoi(n 1,inter,b)
fin si
# Fin PROCEDURE

procédure
n , a , b : entiers
transférer n disques du pic a vers le pic b
afficher la manipulation à opérer
inter : entier
# bouger 1 disque (celui du dessus)
du pic ",a," au pic ",b)
# bouger une pile de n disques
# numéro du troisième pic
# envoyer n − 1 disques vers le pic intermédiaire
# bouger le plus grand disque
# ramener n − 1 disques du pic intermédiaire

Testez-là avec un appel à partir du programme principal . . . mais attention : pour transférer 10 disques, il y
a 1023 manipulations !

U22 - Algorithmique - Chapitre n°6

Page 34/40

Python 3 Annexe A
Les bases du Python 3

A.1 Interface
En lançant l'application IDLE (Python GUI) une fenêtre d'exécution

Python Shell

s'ouvre. Vous pouvez y

tester des lignes de commande et c'est là que les résultats de vos programmes s'a cheront.
En chargeant un programme (menu Fichier) ou en créant un nouveau document, une fenêtre d'édition appa-

Ces derniers doivent être sauvegardés
avec l'extension ".py" pour être reconnus par l'éditeur et pro ter de la coloration syntaxique.
raît. C'est dans celle-ci que vous pourrez taper vos programmes.

A.2 Commentaires
Les commentaires doivent être précédés du symbole

A.3 Structure générale
La structure d'un programme écrit en

Python

#. La n de ligne à partir de ce symbole est alors ignorée.

doit ressembler à ceci :

structure type en Python 3

# ALGORITHME
# ROLE
...
# ENTREES
# SORTIES
# VARIABLES
: types
# DEBUT
...
instructions
# ===== titre
instructions

...
...
...
noms

# commentaire
# commentaire

...
# FIN

A.4 Affectation
L'a ectation de

NomVariable

se fait grâce au symbole

= suivant le schéma : NomVariable = Valeur

A.5 Chaînes de caractères
Doit être placée entre ' (et si une apostrophe gure dans la chaîne on la notera \') ou encore entre ". Un
retour à la ligne peut être provoqué en insérant

\n

dans la chaîne.

A.6 Saisie
input(message ) a che le contenu de message, attend une saisie au clavier validée par entrée
saisie sous forme d'une chaîne de caractères.
Par exemple :

et renvoie la

Nom = input('Quel est votre nom ? ')

Si la valeur de la saisie doit être stockée dans une variable entière (respectivement réelle) on lui appliquera
la fonction

int (respectivement oat).

Par exemple :

Age = int(input('Quel est votre âge ? '))

A.7 Affichage
print(Arg1 , Arg2 , . . .) a che les valeurs des arguments (contenus de variables, chaînes ou nombres) en les
séparant par un espace. En ajoutant en dernier argument sep=chaîne , c'est la chaîne spéci ée qui séparera
l'a chage des arguments.

sep='*' les séparera par une étoile , sep= (chaîne vide) les accolera, sep='\t' insèrera une
tabulation entre chaque et sep='\n' les écrira en passant à la ligne à chaque fois.
De la même façon, en ajoutant en dernier argument end=chaîne vous pouvez décider comment l'a chage
doit se comporter à la n de l'instruction print et, par exemple, l'empêcher d'aller à la ligne pour exécuter

Par exemple

l'a chage suivant (en mettant la chaîne vide ou d'un espace).
U22 - Algorithmique - Annexe A

Page 35/40

Python 3 Annexe B
Opérations et fonctions élémentaires en Python 3

B.1 Opérations et opérateurs de base
Symbole
Signi cation
+


/
∗∗
//
%
==
!=

Exemple

Valeur renvoyée
5

1.5

reste entier (mod)

3+2
3−2
3∗2
3/2
3 ∗ ∗2
17//3
17%3

égalité

(7 == 2)

False

non égalité

(7 != 2)

True

addition
soustraction
multiplication
division
exponentiation
quotient entier (div)

ou de (**)

9
5
2

<; >

comparaison stricte

(5 < 4)

False

comparaison large

(2+2 <= 4)

True

+

concaténation

+

'abcdef '

and

ET logique

(3 > 0) and (1 < 0)

or

OU logique

(3 > 0) or (1 < 0)

True

not

NON logique

not(3>0)

False

Dans les exemples, la variable
(*)

6

>= ; <=

B.2 Fonctions
1

1

2

'abc'

'def '

False

X est de type chaîne et est a ectée par 'BonjouR'. Les fonctions annotées de

nécessite le chargement d'un module spécial en début de programme.

Fonction

réel , entier )
abs(réel )

round(

random()

réel )
réel )
log(réel positif )
sqrt(réel positif ou nul )
int(chaîne )
oat(chaîne )
str(nombre )
chr(code ASCII )
ord(caractère )
len(chaîne )
chaîne.upper()
chaîne.lower()
chaîne [n]
chaîne [n : p]
chaîne [n :]
chaîne [: p]
chaîne [−n :]
chaîne. nd(ch )

Signi cation

Type

Exemple

Renvoie

arrondi

réel

round(3.2572 , 2)

3.26

réel

abs(-3.25)

3.25

−3
0.301. . .
−0.105. . .
1.923. . .

valeur absolue
nombre aléatoire dans

[0; 1[

(**)

réel

oor(

partie entière (*)

entier

oor(−2.3)

exp(

exponentielle (*)

réel

exp(−1.2)

logarithme népérien (*)

réel

log(0.9)

racine carrée (*)

réel

sqrt(3.7)

conversion en nombre entier

entier

int('235')

235

conversion en nombre réel

réel

oat('23.5')

23.5

conversion en chaîne

chaîne. nd(ch,n)
chaîne. nd(ch,n,p)

code ASCII
caractère



chaîne

str(3/2)

'1.5'

caractère

chaîne

chr(97)

'a'

code ASCII



entier

ord('a')

97

nombre de caractères

entier

len(X)

7

mise en majuscule

chaîne

X.upper()

'BONJOUR'

mise en minuscule

chaîne

X.lower()

'bonjour'

caractère de rang
extrait du rang

n

n

chaîne

p−1
rang n

au rang

extrait à partir du

p premiers caractères
les n derniers caractères

les

ch

position d'apparition de

n
p−1

cherche à partir du rang
cherche du rang

n

au rang

X[2]

'onjo'

chaîne
entier

X. nd('o')

1

X. nd('ur')

1

entier

X. nd('o',2)

4

entier

X. nd('o',2,4)

1

chaîne
chaîne

X[1

'n'

: 5]
X[4 :]
X[: 3]
X[−2 :]

chaîne

'ouR'
'Bon'
'uR'

1. mettre en début de programme l'instruction : from math import *
2. mettre en début de programme l'instruction : from random import *
U22 - Algorithmique - Annexe B

Page 36/40

Python 3 Annexe C
Structures de contrôle élémentaires en Python 3

C.1 Traitement conditionnel simple
...

if ( condition ) :
...
instructions à réaliser si la condition est remplie
...

# end if
...

C.2 Traitement conditionnel étendu
...

if ( condition ) :
...
instructions à réaliser si la condition est remplie
...

else :

...
instructions à réaliser si la condition n'est pas remplie
...

# end if
...

C.3 Boucle Tant que
...

while (condition ) :
...
instructions à réaliser dans la boucle
...

# end while
...

C.4 Boucle Pour
...

for variable de comptage in range(valeur départ,valeur d'arrivée

):

+ 1

...
instructions à faire pour chaque valeur
...

# end for variable de comptage
...
Attention :
Si vous voulez que votre variable

U22 - Algorithmique - Annexe C

i

de comptage aille de 5 à 10, il faudra mettre :

for i in range(5,11).

Page 37/40

Python 3 Annexe D
Les tableaux en Python 3

D.1 Tableau à une dimension
D.1.1 Déclaration
Un tableau à une dimension peut être initialisé de di érentes façons :
L'instruction

T = []

L'instruction

T = [2, 7, 0]

crée une variable tableau
crée un tableau

T

T

à 1 dimension de taille 0.

à 1 dimension de taille 3 donc les contenus des cellules

sont initialisés respectivement à 2, 7 et 0.
Pour créer un tableau

T

à 1 dimension de taille

n

dont tous les contenus sont initialisés à

x,

les instructions

suivantes sont équivalentes :

T = [x, x, · · · , x]

D.1.2

T = [x

for

i

in range(0, n)]

Accès aux données

La fonction
Pour
variable

D.1.3

T = [x] ∗ n

len(T ) renvoie la taille du tableau T

0 6 i 6 len(T ) − 1 ,
T [i] (que ce soit pour

(nombre de cellules)

T

se fait en utilisant la

en y mettant la valeur

x. La taille du tableau

l'accès au contenu de la cellule de rang

i

du tableau

utiliser ou changer son contenu).

Affectation dynamique

L'instruction

T.append(x)

ajoute une cellule au tableau

T

est donc augmentée de 1.

D.2 Tableau à deux dimensions
D.2.1 Déclaration
Un tableau

T

à deux dimensions de taille

dimension de taille

n

n × p (n

lignes et

p

colonnes) se déclare comme un tableau à une

dont les composantes sont des tableaux à une dimension de taille

p.

Un tableau à deux dimensions peut être initialisé en y a ectant directement le contenu de ses cellules :

T = [[2, 3], [5, 6], [8, 9]]

Par exemple l'instruction

crée le tableau

T

à deux dimensions, 3 lignes et 2

colonnes, possédant donc 6 cellules. Le contenu de la cellule qui se trouve à la ligne d'indice 2 et à la colonne
d'indice 0 valant 8.
Pour initialiser un tableau

T

écrira l'instruction suivante :

D.2.2

n lignes et p colonnes en mettant la valeur x
T = [[x for j in range(0, p)] for i in range(0, n)]

de

Accès aux données

Pour un tableau

T

à 2 dimensions, l'expression

T [i] représente la ligne d'indice i. C'est
T . L'expression len(T [0]) renvoie donc
La variable

D.2.3

T [i][j]

dans toutes ses cellules, on

len(T ) renvoie le nombre de lignes du tableau T .

un tableau à 1 dimension dont la taille est le nombre de colonnes de
le nombre de colonnes du tableau

représente la cellule de la ligne d'indice

i

T.

et de la colonne d'indice

j.

Affectation dynamique

L'a ectation dynamique (un "append") sur un tableau à 2 dimensions est risquée !
En e et, si vous voulez lui ajouter une ligne, il faudra que l'ajout transmette un tableau à 1 dimension dont
la taille correspond au nombre de colonnes du tableau. Par exemple si le tableau

T

comporte

p

colonnes et

qu'on veut lui ajouter une ligne de "x", on écrira :

T.append([x] ∗ p)
Et si vous voulez lui ajouter une colonne, il faut cette fois ajouter une cellule par ligne et il faudra utiliser
une boucle. Par exemple si

T

contient

n

for

U22 - Algorithmique - Annexe D

i

lignes et qu'on veut lui ajouter une colonne de "x", on écrira :
in range(0, n)

: T [i].append(x)
Page 38/40

Python 3 Annexe E
Définition de procédure et fonction en Python 3

E.1 Procédure
def NomProcédure (liste d'arguments éventuels séparés par des virgules ) :
# type : procédure
# arguments :

noms

et

types

# rôle : (. . .)

noms et types
suite d'instructions

# variables :

# Fin de procédure

E.2 Fonction
def NomFonction (liste d'arguments éventuels séparés par des virgules ) :
# type : fonction
# arguments :

noms

et

types

# rôle : (. . .)

type
noms et types
suite d'instructions
return NomDeVariable ou ValeurCalculée

# valeur renvoyée :
# variables :

#

Fin de fonction

U22 - Algorithmique - Annexe E

Page 39/40

Python 3 Annexe F
Codes Ascii de 32 à 127
Décimal

Hexadécimal

Binaire

Caractère

Décimal

Hexadécimal

Binaire

Caractère

32

20

00100000

espace

80

50

01010000

P

33

21

00100001

!

81

51

01010001

Q

34

22

00100010

"

82

52

01010010

R

35

23

00100011

#

83

53

01010011

S

36

24

00100100

$

84

54

01010100

T

37

25

00100101

%

85

55

01010101

U

38

26

00100110

&

86

56

01010110

V

39

27

00100111

'

87

57

01010111

W

40

28

00101000

(

88

58

01011000

X

41

29

00101001

)

89

59

01011001

Y

42

2A

00101010

*

90

5A

01011010

Z
[

43

2B

00101011

+

91

5B

01011011

44

2C

00101100

,

92

5C

01011100

45

2D

00101101

-

93

5D

01011101

46

2E

00101110

.

94

5E

01011110



47

2F

00101111

/

95

5F

01011111

_

48

30

00110000

0

96

60

01100000

`

49

31

00110001

1

97

61

01100001

a

50

32

00110010

2

98

62

01100010

b

51

33

00110011

3

99

63

01100011

c

52

34

00110100

4

100

64

01100100

d

53

35

00110101

5

101

65

01100101

e

54

36

00110110

6

102

66

01100110

f

55

37

00110111

7

103

67

01100111

g

56

38

00111000

8

104

68

01101000

h

57

39

00111001

9

105

69

01101001

i

58

3A

00111010

:

106

6A

01101010

j

]

59

3B

00111011

;

107

6B

01101011

k

60

3C

00111100

<

108

6C

01101100

l

61

3D

00111101

=

109

6D

01101101

m

62

3E

00111110

>

110

6E

01101110

n

63

3F

00111111

?

111

6F

01101111

o

64

40

01000000

@

112

70

01110000

p

65

41

01000001

A

113

71

01110001

q

66

42

01000010

B

114

72

01110010

r

67

43

01000011

C

115

73

01110011

s

68

44

01000100

D

116

74

01110100

t

69

45

01000101

E

117

75

01110101

u

70

46

01000110

F

118

76

01110110

v

71

47

01000111

G

119

77

01110111

w

72

48

01001000

H

120

78

01111000

x

73

49

01001001

I

121

79

01111001

y

74

4A

01001010

J

122

7A

01111010

z

75

4B

01001011

K

123

7B

01111011

{

76

4C

01001100

L

124

7C

01111100

|

77

4D

01001101

M

125

7D

01111101

}

78

4E

01001110

N

126

7E

01111110



79

4F

01001111

O

127

7F

01111111

delete

U22 - Algorithmique - Annexe F

Page 40/40




Télécharger le fichier (PDF)

Dossier Python Algo.pdf (PDF, 553 Ko)

Télécharger
Formats alternatifs: ZIP







Documents similaires


2cours algorithme 2
serie 4 c
examen de rattrapage
tp info
serie3 enonce
cours pascal

Sur le même sujet..