Support formation LIESSE

Demande des participants :

● approfondir la programmation en Python
● connaitre la façon dont on enseigne l'informatique
● intéressé par l'algorithmique (compléxité, preuve....) pour l'enseigner aux élèves
● acquisition de compétences dans le cadre des nouveaux programmes d'informatique
des classes prépa
● attend a priori un approfondissement, en particulier sur numpy, matplotlib,les
bibliothèques graphiques…
● des exemples de sujets illustrant de façon attrayante et convaincante les notions au
programme et de la meilleure manière de les traiter
● approfondissement : par exemple en algorithmique et en ce qui concerne la complexité
d'un algorithme.
● me former sur python pour utiliser ce langage lors les TP ... que je traitais initialement
avec Scilab.
● comment peut­on lire et écrire dans des fichiers (.txt ; .csv ; .xls ; ...) depuis un
programme en python ?
● Je connais très superficiellement le langage Python et je souhaite donc me perfectionner
dans la pratique de ce langage
● discuter de pratiques pédagogiques et regarder plus en détail quelle progression de
cours nous utilisons pour enseigner l'informatique
● avoir des pistes d'utilisation de l'enseignement informatique pour mon enseignement de
Mathématiques de première année.

Quelques clés pour enseigner l’informatique (à un public non destiné à devenir

informaticien)

Une des premières difficultés est que le niveau des élèves est très hétérogène.
Selon nous, il faut que les principes fondamentaux soient bien assimilés avant d’explorer les
différentes possibilités offertes par le langage.

1
Introduction
Correspond aux chapitres 1 et 3 (Wack et al.) :

Environnement de programmation
● rappels sur la structure d’un ordinateur et sur les différentes façons d’exécuter un
programme (notions de processeur, compilateur, interpréteur, machine abstraite)
● Python est un langage de programmation. Il est exécutable (c’est un interpréteur
composé d’un compilateur et d’une machine abstraite)
● il existe différents environnements de programmation (éditeur, interpréteur Python,
environnement intégré IDE)
● avant de commencer, se poser la question : quelles peuvent être les richesses ou les
caractéristiques d’un langage de programmation (constructions, expressivité, efficacité,
portabilité, bibliothèques, sûreté, …)
● quelles sont les caractéristiques de Python ?
● se positionner dans l’ensemble des langages existants

Types de données et constructions élémentaires

● types primitifs de Python (int, float, string, list)
● notion d’expression et de valeur (non mutable)
● notion d’instruction

Présentation interactive illustrant les concepts

● illustrer les notions de variable, affectation, print, type, accès indexé, fonction len

>>> a = 3
>>> print(a)
3
>>> print(type(a))
<type 'int'>
>>>
>>> a = 3.14
>>> print(a)
3.14
>>> print(type(a))
<type 'float'>
>>>
>>> b = a
>>> print(b)
3.14
>>> a = 4
>>> print(b)
3.14

2
 >>> s = 'abc'
>>> print(s)
abc
>>> print(type(s))
<type 'str'>
>>>
>>> s = "abc"
>>> print(s)
abc
>>> print(type(s))
<type 'str'>
>>>
>>> print(s[0])
a
>>> print(s[1])
b
>>> print(len(s))
3
>>>
>>> l = ['a', 'b', 'c']
>>> print(l)
['a', 'b', 'c']
>>> print(type(l))
<type 'list'>
>>>
>>> print(l[0])
a
>>> print(l[1])
b
>>> print(len(l))
3

Exemple de TD

Exercices de la séance 1 ([Link]

Séance 1

3
Rappel des notions vues en cours :

expressions
int
float
type(x)
id(x) [n’est pas dans le livre]
+ ­ / % * **
True False not and or
== < <= > >= !=
n­uplet : construction
acces : t[0]
concatenation +
appartenance in
longueur len
chaine : construction, accès, concaténation, longueur, appartenance
sous­chaine : s[0:3]
multiplication 3 * ”he”
instantiation : % [n’est pas dans le livre]

conversion/construction d’un type : str, int, float, bool

liste (sans effet de bord) : construction, concaténation, accès, longueur, appartenance,

conversions
constructeur range()

input()

instructions
print
affectation x = …
déconstruction x, y = …

objectifs de la séance :
● prendre en main l’environnement wing 101
● maîtriser les types de données élémentaires et les opérations associées
● être capable d’écrire et d'exécuter des programmes simples (évaluations d’expressions,
affectations de variables)
● entraînement sur CodingBat

Exercice (sur papier) : différencier les expressions des instructions

● a=2
● a == 2

4
 ● t = (1, 2, 3)
● t=t+t
● b=a+5
● a ­ b >= 0
● print( a ­ 3 )
● s = ‘s vaut %s’ % 3
● (1,2,3)[0]
● ((1,2) + (3,4))[1:3]

Note : une instruction est un ordre qui est exécuté

Une expression peut toujours s’évaluer en une valeur

Exercice (sur papier) : soient a et b deux variables, écrire les instructions permettant d’inverser
le contenu de deux variables

Exercice (sur papier) : évaluer les expressions suivantes

● True and (3 > 2)
● ‘ab’ == ‘ba’
● ‘ab’ + ‘cd’ == ‘a’ + ‘bcd’

Exercice (sur papier) : écrire les tables de vérité de and, or, not, xor

Exercice (avec un interpréteur Python) : écrire les cinq premiers termes de la suite de
Syracuse en partant de 7.
Partant d’un entier positif, on le divise par 2 s’il est pair et on le multiplie par 3 et on ajoute 1
sinon.

CodingBat
Aller sur la page CodingBat ([Link]
Créer un compte
Une fois connecté, dans l’onglet prefs, ajoutez l’adresse mail de votre chargé de TD dans la
section ‘Share To’
● pierre­[Link]@[Link]

Tous les exercices sont à résoudre en ne tapant qu’une seule ligne de la forme :

def nom_de_fonction(arguments):
return expression_a_trouver

Warmup­1 :
● sleep_in
● monkey_trouble
● parrot_trouble

5
 ● makes10
● near_hundred
● missing_char
Warmup­2 :
● string_times
● front_times
String­1 :
● hello_name
● make_abba
● make_tags
● make_out_word
● extra_end
● first_two
● first_half
● without_end
● non_start
● left2
Logic­1 :
● squirrel_play
● love6
● in1to20

Pour les plus rapides

Dans le cadre de ces exercices nous considérons que les listes se comportent comme des
tuples

List­1 :
● first_last6
● same_first_last
● make_pi
● common_end
● sum3
● rotate_left3
● reverse3
● max_end3
● middle_way
● make_ends
● has23

6
Algorithmique
Correspond au chapitre 4 (Wack et al.) :

Notions abordées : instructions, variables, tests, boucles, tableaux

● instructions conditionnelles et notion de condition (introduit la notion de bloc)
● boucle while
● boucle for (itérateur sur une liste)
● présenter les opérations élémentaires sur les listes (constructeurs, +, len, in, min, max,
range)
● fonctions et paramètres
● présenter les 2 façons d’écrire des commentaires

Ces connaissances permettent de travailler sur des problèmes algorithmiques simples

(manipulations de variables, une ou deux itérations imbriquées sur les listes)

Exemples d’exercices : recherche d’un élément dans une liste, recherche de l’élément
maximum, calcul de la moyenne, de la variance, recherche par dichotomie dans une liste triée,
recherche du zéro d’une fonction, recherche d’une sous­chaîne dans une chaîne, etc.

Pour intégrer ces notions il faut les mettre en pratique. En TD nous suggérons de traiter un à un
ces exercices en écrivant dans un premier temps l’algorithme sur papier en utilisant une syntaxe
approximative (éventuellement en français). Rendre ensuite l’algorithme exécutable en le
programmant dans l’environnement Python.

Fonctions
Correspond au chapitre 5 (Wack et al.) :

notion de fonction (au sens informatique), définition dans le langage utilisé, paramètres (ou
arguments) et résultats, portée des variables.
Ne pas confondre return et print

Rappel des notions vues en cours :

● notion de fonction : suite d’instructions qui dépend de paramètres
● retour de valeur
● ne pas confondre return et print
● variable locale
● variable globale (vu dans le livre mais nous n’insistons pas dessus)
● fonction comme valeur de première classe
● fonctions de bibliothèques (import math, [Link], from math import sqrt)
● valeur par défaut des paramètres, arguments avec étiquettes

Règles :

7
 ● une fonction doit toujours retourner quelque chose : une valeur ou None
● on ne met jamais de print dans une fonction qui retourne autre chose que None (sauf
dans le premier exercice pour faire comprendre la différence entre return et print)

Exercice : recherche dans une liste

Écrire une fonction indice qui prend un élément et une liste en paramètre et qui retourne le
premier indice de l’élément si celui­ci apparaît dans la liste.

Exercice : recherche du maximum dans une liste de nombres

Exercice : calcul de la moyenne et de la variance.

Exercice : recherche par dichotomie dans un tableau trié.

Exercice : recherche par dichotomie du zéro d’une fonction continue et monotone.

Exercice : méthodes des rectangles et des trapèzes pour le calcul approché d’une intégrale sur
un segment.

Exercice : recherche d’un mot dans une chaîne de caractères.

On utilisera pour cela un algorithme naïf. Mais on peut imaginer l’étude des algorithmes de
Knuth­Morris­Pratt, ou Rabin­Karp par exemple.

Exercice : étant donné un tableau d’entiers, retourner un tableau commençant avec les entiers
pairs et se terminant avec les entiers impairs

Exercice : même exercice en utilisant des compréhensions de liste

Exemple de TD

Quelques remarques pour les assistants de TD

● Ce TD est long, il faut faire les 4 premiers exercices assez rapidement en les aidant un
peu. L’idée est de les familiariser avec les notations. Ensuite, ils peuvent travailler plus en
autonomie.
● On n’introduit qu’une seule notion : algorithme, pas de fonction, méthode ou procédure
● Un algorithme prend zéro, un ou plusieurs paramètres (passage par valeur pour le moment) et
retourne un résultat, éventuellement vide, à la fin (pas d’interruption du flot de contrôle)
● Pour le moment on ne parle pas de type
● On ne parle pas de récursivité
● On utilise deux types de boucles : pour i de 1 à n, tantque condition
● Les étudiants doivent être capables de passer de la boucle pour à la boucle tantque
● Les variables sont locales à un algorithme. Comme il n’y a pas de déclaration, on ne peut pas
parler de bloc, mais il est de bon goût d’initialiser une variable au début d’un algorithme.

8
 ● L’indentation est importante. Pour terminer un bloc, on utilise soit le mot clé correspondant
finpour, fintantque, finsi, soit le mot clé générique fin
● Un tuple est une suite ordonnée de valeur. Pour le moment il n’y a pas de structure, pas de
champs, pas de fonction d'accès. La récupération des données se fait par filtrage :
(x,y) ← algorithmeRetournantUnCouple
● L’indice de début d’un tableau est 0. longueur retourne le nombre d’éléments d’un tableau
● On n’aborde que les simples boucles (sauf les deux derniers exercices pour ceux qui s’embêtent)
● Les commentaires s’écrivent # suivi d’un commentaire

TD ­ Séance 2

Exercice 1
Écrire un algorithme calculant le périmètre d’un cercle de rayon donné.

Exercice 2
Écrire un algorithme calculant le maximum de 2 entiers.
Écrire un algorithme qui lit deux entiers au clavier et affiche l’élément maximum

Exercice 3
Écrire un algorithme qui prend comme arguments 2 entiers a et b et retourne la paire (b,a)

Exercice 4
Écrire un algorithme qui prend comme arguments un entier représentant une durée en secondes et retourne
le nombre de secondes, de minutes, d’heures et de jours.

Exercice 5
Écrire un algorithme qui calcule la somme des entiers pairs de 1 à n

Exercice 6
Écrire un algorithme qui retourne le PGCD de deux nombres donnés en entrée. Rappel de la méthode de
calcul :
1. effectuer la division euclidienne du plus grand des deux nombres par le plus petit.
2. effectuer la division euclidienne du diviseur par le reste de la division précédente, jusqu’à ce que le
reste de la division soit égal à zéro.
3. le PGCD est le dernier reste non nul dans la succession des divisions euclidiennes.

9
Exercice 7
Un nombre n est dit triangle si :
k
n = ∑ i avec k ∈ N
i=1
Écrire un algorithme qui pour n et k donnés, permet de savoir si le nombre est triangle ou pas.

Exercice 8
Écrire un algorithme qui prend en entrée un tableau de n valeurs, et qui retourne le produit des éléments de
ce tableau.

Exercice 9
Écrire un algorithme qui prend comme argument un tableau T et un nombre n et qui retourne le nombre
d’éléments dans le tableau plus grands que n.

Exercice 10
Soit un tableau d’entiers. Écrire un algorithme qui range le tableau avec d’un côté les nombres pairs, de
l’autre les nombres impairs. On ne tient pas compte de l’ordre initial des éléments.
Considérons par exemple le tableau [7,2,4,9,3,12,5], une solution possible est [4,12,2,3,9,7,5]

Exercice 11 (optionnel, pour ceux qui vont vite)

Écrire un algorithme qui permet de supprimer les doublons dans un tableau. Par exemple, pour le tableau
[4, 3, 4, 5, 3], on retournera [4, 3, 5].

Exercice 12 (optionnel, pour ceux qui vont vite)

Décrire l’algorithme tri­a­bulle. On parcourt le tableau en échangeant 2 cases consécutives mal ordonnées.
On répète ce procédé tant que le tableau n’est pas trié.

CodingBat (pour s’entraîner)

warmup­1
● sum_double
● diff21
● pos_neg
● not_string
● front_back
● front3

warmup­2

10
 ● string_bits
● array_count9
● array_front9
● array123

string­1
● combo_string

custom
● is_triangular

11
Structures de données avancées
Notions abordées : structures de données mutables (liste, ensemble, dictionnaire, collection),
compréhensions

Aborder les problèmes de partage, de mutation et de copie avec l’exemple des matrices.

Exemple :
l = [None] * 5
m = [l] * 5
print(m)
m[2][3] = (2,3)
print(m)

Solution 1 :
m = [None] * 5
l = [None] * 5
for i in range(5):
m[i] = list(l)

Solution 2 :
l = [None] * 5
m = [list(l) for i in range(5)]

Fonctions et données mutables

l = range(5)

def mut(t):
t[2] = 42

print(l)
mut(l)
print(l)

Exercices mettant en pratique les notions de liste, d’ensemble, de mutabilité et de

compréhension

Exercice 1
Lire un fichier contenant un mot par ligne et construire un ensemble contenant les mots
([Link]
Afficher la cardinalité de cet ensemble.

12
Afficher l’ensemble

Pour les champions (378974 mots) :

[Link]

Exercice 2
Etant données n lettre (n <= 8), proposer un algorithme permettant de trouver le mot le plus long
pouvant être écrit avec ces lettres

Exemples d’éxécution :
tirage = ['b', 'p', 'd', 'w', 's', 'y', 'w', 'i']
solution = bis
['bis', 'bd']

tirage = ['a', 'r', 'b', 'g', 'e', 's', 'c', 'j']

solution = sacre
['sacre', 'sabre', 'baser', 'cabre', 'garce', 'crase', 'brase',
'barge', 'caser', 'jaser', 'crabe', 'scare', 'aber', 'gare',
'sage', 'gars', 'rase', 'arec', 'acre', 'jars', 'case', 'base',
'cage', 'rage', 'jase', 'bras', 'race', 'ars', 'sac', 'arc',
'are', 'jar', 'jas', 'bar', 'bas', 'ace', 'cas', 'car', 'age',
'bac', 'cab', 'as', 'ra', 'sa', 'a']

13
Exercices mettant en pratique la notion de dictionnaire :

L’objectif de ce TD est d’améliorer notre outil de recherche de mots en prenant en compte la

valeur des lettres pour trouver le mot qui maximise le nombre de points

Valeurs des lettres :

● A,E,I,L,N,O,R,S,T,U : 1 point
● D,G,M : 2 points
● B,C,P : 3 points
● F,H,V : 4 points
● J,Q : 8 points
● K,W,X,Y,Z : 10 points

Objectifs à atteindre :
● étant donné un ensemble de sept lettres et un ensemble de lettres disponibles sur le
plateau de jeux, trouver le mot composé d’une lettre du plateau de jeu et d’au plus sept
lettres, qui rapporte le plus de points
● ajouter au jeu le symbole ‘?’ qui est un joker valant zéro point mais pouvant remplacer
n’importe quelle lettre

Pour vous aider vous pouvez décomposer le problème de la manière suivante :

Exercice 1 :
quelle structure de données utiliser pour représenter les points associés aux lettres ?
● A,E,I,L,N,O,R,S,T,U : 1 point
● D,G,M : 2 points
● B,C,P : 3 points
● F,H,V : 4 points
● J,Q : 8 points
● K,W,X,Y,Z : 10 points

Exercice 2 :
écrire une fonction score(mot)qui calcule les points correspondant au mot.

Exemple :
● score(‘a’) = 1
● score(‘lettre’) = 6
● score(‘scrabble’) = 14

Exercice 3 : (cet exercice était déjà présent la semaine dernière)

écrire une fonction liste_mot(lettres)qui retourne la liste des mots qu’il est possible
d’écrire avec les lettres de lettresou un sous­ensemble de celui­ci

14
Exemple :
● liste_mot(‘zxcvrrte’) = set(['rte', 'ver', 'ce', 'etc', 'cet', 'ex', 'cr', 'et', 'ter', 'te', 'ct'])

Exercice 4 :
écrire une fonction max_score qui prend une liste de mots et retourne le mot correspondant au
plus grand nombre de points, ainsi que le nombre de points

Exemple :
● max_score(['rte', 'ver', 'ce', 'etc', 'cet', 'ex', 'cr', 'et', 'ter', 'te', 'ct']) = ('ex', 11)

Exercice 5 :
Un joker, noté ‘?’, est un symbole qui peut remplacer n’importe quelle lettre. Sa valeur est de
zéro point.
Comment faut­il modifier notre programme pour autoriser l’utilisation d’un seul joker ?

Exemple :
● max_score(liste_mot('zxcvrrt?')) = ('czar', 14)

15
Classes et Objets

16
Programmation 2

Classes et objets

TD compte bancaire

Interfaces graphiques

Bases de données

Exercice : compte bancaire

L'objectif de ce TD est de s'exercer à la spécification et à la programmation de classes

élémentaires. En particulier, il s'agit à partir d'un énoncé d'identifier et de définir les
caractéristiques d'une classe modélisant un concept donné. [TD inspiré d’un exercice proposé
par Philippe Genoud, Université de Grenoble]

"Cahier des charges"

Il s'agit de définir une classe Python CompteSimple permettant de modéliser des comptes
bancaires.
La somme d'argent disponible sur un compte, appelée solde, est exprimée en Euros. Le
solde est un nombre décimal positif, nul ou négatif. On dit que le compte est à découvert lorsque
son solde est négatif.
En aucun cas le découvert d'un compte ne peut être supérieur à une valeur fixée, appelée
decouvert_autorise. Par exemple pour un compte dont le découvert maximal autorisé est
2000 €, le solde ne pourra jamais être inférieur à ­2000 €. Le découvert maximal autorisé peut
varier d'un compte à un autre, il est fixé arbitrairement par la banque à la création du compte et
peut être ensuite révisé selon les modifications des revenus du titulaire du compte.
Créditer un compte consiste à ajouter un montant positif au solde du compte.
Débiter un compte consiste à retirer un montant positif au solde du compte. Le solde résultant
ne doit en aucun cas être inférieur au découvert maximal autorisé pour ce compte.
Lors d'une opération de retrait, un compte ne peut être débité d'un montant supérieur à une
valeur désignée sous le terme de debit_maximal autorisé. Comme le découvert maximal
autorisé, le débit maximal autorisé peut varier d'un compte à un autre et est fixé arbitrairement
par la banque à la création du compte. Il peut être ensuite révisé selon les modifications des
revenus du titulaire du compte.
Effectuer un virement consiste à débiter un compte au profit d'un autre compte qui sera
crédité du montant du débit.
Lors de la création d'un compte, en l'absence de dépôt initial le solde est fixé à 0 €. Les valeurs
par défaut pour le découvert maximal autorisé et le débit maximal autorisé sont respectivement
de 0 € et 500 €.

17
 Travail demandé :
A partir du "cahier des charges" précédent élaborer une spécification de la classe Python
modélisant un compte bancaire.
● quelles sont les méthodes proposées par la classe ?
● quelles sont les variables d’instances nécessaires ?
● quelle est la signature du constructeur de classe ?
Réaliser une implantation en prenant soin de documenter le comportement du constructeur et
des différentes méthodes.

Scénario de test :
● créer un compte c1 ayant 1000 € comme dépot initial
● afficher le solde de ce compte. Le résultat doit être de la forme
1000 €
● débiter 50 € de ce compte et afficher le solde courant
● créer un compte c2
● transférer 200 € du compte c1 vers le compte c2. Afficher le solde des deux comptes
● transférer 2000 € du compte c1 vers le compte c2. Afficher le solde des deux comptes

"Cahier des charges" (suite)

Un compte bancaire est associé à un client titulaire du compte, ce client est décrit par son
nom ainsi que par la liste des comptes qu’il possède. Toutes les informations relatives à un
client doivent pouvoir être affichées (nom du client, liste de ses comptes et soldes respectifs)

Travail demandé
● réaliser une implantation en langage Python de la classe Client (constructeur prenant en
paramètre le nom du client ainsi que la liste des comptes associés)
● la classe client devra permettre d’afficher la situation financière d’un client. Par exemple :
Client: A
Compte 1 : 0 €
Compte 2 : 300 €

● créer 2 clients (A et B). Le premier possède 2 comptes (le compte c1 créé

précédemment et un nouveau compte initialisé à 50 €) et le second un seul compte (le
compte c2 créé précédemment).
affichez la situation financière de ces clients. L’affichage doit être de la forme
*** situation initiale
Client: A
Compte 1 : 750 €
Compte 2 : 50 €
Client: B

18
 Compte 1 : 200 €
Modifier la classe Client de sorte que chaque client ait un numéro de client unique.
Modifier la méthode qui affiche la situation financière d’une client de sorte que le numéro
apparaisse.

Exercice : monstres et sorciers

(librement adapté d’un exercice conçu par l’équipe de l’IUT Charlemagne, Nancy)

Nous allons développer un jeu dans lequel des personnages s'affrontent. Dans un premier
temps il n’y a qu’un seule sorte de personnages : les monstres.
Les règles de ce jeu sont les suivantes :

Un monstre a un nom et des points de vie. Si le nombre de points de vie est négatif ou nul, alors
il est mort. On représentera un monstre par la classe monstre.

Plusieurs méthodes permettent de gérer l'état interne d'un monstre :

● Affichage : si p est la référence à un monstre, l'appel à print(p) devra afficher quelque
chose comme “ m'appelle Dracula et j'ai 32 points de vie.” ou “Dracula est mort.”
● La méthode est_mort(self) indique si le personnage est mort ou pas.
● La méthode add_vie(self, num) permet d'ajouter num points de vie (valeur
éventuellement négative).

De plus, un monstre peut attaquer un autre monstre et subir réciproquement une riposte.

Attaque d’un monstre

La méthode attaque(self, autre) décrit ce qu’il se passe quand le monstre attaque un
autre monstre :
○ Si l’autre monstre est mort, il ne se passe rien.
○ Sinon, il frappe l'autre monstre avec une force égale à la moitié de ses propres
points de vie; éventuellement, cela lui fait perdre des points de vie (voir la
définition de subit_frappe).

Quand un monstre est frappé

La méthode subit_frappe(self, coup) décrit ce qu’il se passe quand le monstre est
frappé par un autre monstre :
○ Quand un monstre est frappé avec une force coup, ses points de vie sont
décrémentés de coup. En retour, il blesse le personnage qui le frappe avec une
blessure égale à la moitié de des points de vie qu’il avait avant de recevoir le

19
 coup, valeur de laquelle le personnage qui l'a frappé devra décrémenter ses
points de vie.

Problème 1
Implanter la classe monstre, créer des monstres et vérifier que les règles de combat sont bien
implantées.

Dans la suite, nous considérons un nouveau type de personnage : les sorciers. Les monstres
et les sorciers sont des personnages.

Les règles de ce jeu sont les suivantes :

Un personnage a un nom et des points de vie. Si le nombre de points de vie est négatif ou nul,
alors il est mort. On représentera un personnage par la classe personnage.
Un personnage peut attaquer un autre personnage et subir réciproquement deux sortes de
d’attaques :
● La méthode attaque(self, autre) : ce qu’il se passe quand le personnage attaque un
autre personnage. Son attaque dépend de son identité de monstre ou de sorcier.
● La méthode subit_frappe(self, coup) : ce qu’il se passe lorsque le personnage est
frappé par un monstre
● La méthode subit_charme(self, coup) : ce qu’il se passe lorsque le personnage est
frappé par un sorcier

Les monstres. Un monstre est un personnage. On représentera les monstres par la classe
monstre.
Attaque d’un monstre
● Si l’autre personnage est mort, il ne se passe rien.
● Sinon, il frappe l'autre personnage avec une force égale à la moitié de ses propres points
de vie; éventuellement, cela lui fait perdre des points de vie (voir la définition de
subit_frappe).

Quand un monstre est attaqué

● Quand un monstre est frappé avec une force coup, ses points de vie sont décrémentés
de coup. En retour, il blesse le personnage qui le frappe avec une blessure égale à la
moitié de ses points de vie qu’il avait avant de recevoir le coup, valeur de laquelle le
personnage qui l'a frappé devra décrémenter ses points de vie.
● Quand un monstre est charmé avec une force coup, ses points de vie sont
décrémentés de coup. En retour, il fournit au personnage qui le charme un gain égal à la
moitié des points de vie qu’il avait avant de recevoir le coup. Valeur de laquelle le
personnage qui l'a frappé devra incrémenter ses points de vie.

Les sorciers
Attaque d’un sorcier
● Si l’autre personnage est mort, il ne se passe rien.

20
 ● Sinon, il charme l'autre personnage avec une force égale la valeur ses propres points de
vie multipliée par son pouvoir; éventuellement, cela lui fait gagner des points de vie (voir
la définition de subit_charme).

Quand un sorcier est attaqué

● Quand un sorcier est frappé avec une force coup, ses points de vie sont décrémentés
de coup. En retour, il blesse le personnage qui le frappe avec une blessure égale à la
valeur de ses points de vie multipliée par son pouvoir, valeur de laquelle le personnage
qui l'a frappé devra décrémenter ses points de vie.
● Aucun charme n’a d’effet sur un sorcier

Problème 2
Implanter les classes personnage, monstre et sorcier
Créer des monstres et des sorciers et vérifier que les règles de combat sont bien implantées.
Modifier les classes monstre et sorcier de sorte que la fonction d’affichage de la classe
personnage puisse indiquer s’il s’agit d’un monstre ou d’un sorcier.

Par exemple :
monstre A : 10 points de vie
monstre B : ­1 points de vie
sorcier S1 : 10 points de vie pouvoir: 0.112287998123

21
Algorithmique 2

Piles

Exercice: Ecrire une fonction qui permet de savoir si une expression de parenthèse est
correcte. Exemple (()), ()(), ()(()), … Contre­exemple )()(, ((), ())), …

Récursivité

Exercice: Comptez le nombre de mots (sur ‘(‘ et ‘)’ ) de longueur n bien parenthésés.

Exercice: Etant donnée une chaîne de caractères comme “debarbouiller”, calculez la longueur
de la plus longue sous­suite croissante contenue dans ce mot. Par exemple “abill” a une
longueur 5. L’ordre des lettres est a < b < c < ∙ ∙ ∙ .

Exercice:

Le joueur commence à une position a. Il veut atteindre la position b > a. Son premier pas fait une
unité, ce que l’on note P (1) = 1. Le pas P (n + 1) vérifie |P(n+1)−P(n)| ≤ 1. Les longueurs de pas
sont des entiers. Un exemple :
­1 0 1 2 3 4 5 6
fait passer de la position 2 à la position 6 en trois étapes. Peut­on toujours atteindre une position
b à partir d’une position a ? Calculez le nombre de pas le plus court pour passer de a à b.

Exercice : résoudre des cryptarithmes (SEND+MORE=MONEY)

Tris

Exercice: Tri à bulles. On part des deux premiers éléments, s’ils sont inversé, on les permute.
On passe au deux éléments suivant. S’il sont inversés, on les permute, etc jusqu’à la fin de la
liste. On recommence le processus n­1 fois où n est la longueur de la liste

Exercice: Tri par insertion. On trouve le plus petit élément de la liste, et on le permute avec le
premier élément de la liste, on continue avec le deuxième plus petit mis à la place du deuxième,
etc jusqu’à la fin de la liste.

Exercice: Trouver l’élément médian d’une liste L donnée en argument. On rappelle qu’il s’agit de
l’élément x tel que la moitié des éléments de T est plus petit que x, l’autre étant plus grande.

22