Exercices sur les séquences

Exercice 1: Des carrés partout !

Pour les questions suivantes, vous proposerez, dans la mesure du possible, au moins deux versions de chaque fonction demandée nom_de_la_fonction1(),nom_de_la_fonction2(), … en utilisant les différentes façons de construire une liste (explicitement, par concaténation, par compréhension).

a) Écrire une fonction carres() de paramètre n, un nombre entier positif, et qui retourne la liste des \(n\) premiers carrés.

Jeu de test:

>>> carres(7)
[0, 1, 4, 9, 16, 25, 36]

b) Écrire une fonction carres_inf() de paramètre n, un nombre entier positif, et qui retourne la liste des carrés inférieurs à \(n\).

Jeu de test:

>>> carres_inf(50)
[0, 1, 4, 9, 16, 25, 36, 49]

c) Écrire une fonction carres_digits() de paramètre digits, un nombre entier positif, et qui retourne la liste des carrés qui s’écrivent avec exactement un nombre de chiffres égal à digits.

Jeu de test:

>>> carres_digits(2)
[16, 25, 36, 49, 64, 81]

d) Écrire une fonction carres_digits_finissant() de paramètres digits et dernier, deux nombres entiers positifs, et qui retourne la liste des carrés qui s’écrivent avec exactement un nombre de chiffres égal à digits et qui commencent par le chiffre dernier.

Jeu de test:

>>> carres_digits_finissant(3, 9)
[169, 289, 529, 729]

e) Écrire une fonction carres_palindromes() de paramètre digits, un nombre entier positif, et qui retourne la liste des carrés qui s’écrivent avec exactement un nombre de chiffres égal à digits et dont l’écriture décimale est un palindrome (exemple: “kayak” est un palindrome puisque ce mot écrit à l’envers est lui-même).

Jeu de test:

>>> carres_palindromes(3)
[121, 484, 676]

Exercice 2: File de véhicules sur un circuit

Présentation

File de longueur 20 avec 13 véhicules

Nous allons ici simuler le déplacement de véhicules dans une file sur un circuit où quelques règles sont imposées:

a) Interdiction de sortir de la file (pas de dépassement, …) ou du circuit,
b) Sens de parcours: de droite vers la gauche,
c) Un véhicule peut avancer uniquement si la case devant lui est libre. En particulier, le véhicule le plus a gauche peut avancer si la case la plus à droite est libre.

La file sera une liste de 0 (case vide) et de 1 (véhicule présent).

Partie 1: les déplacements des véhicules sont supposés synchronisés

On considère dans cette partie que les véhicules avancent en même temps pour ceux qui le peuvent.

Autrement dit, à chaque étape, on détermine la nouvelle file une fois tous les déplacements simultanés effectués à partir de la file précédente.

a) Sur papier, déterminer la file suivante si l’on part de file = [1, 0, 1, 1, 1, 0, 0, 1, 0, 0].

Réponse ?

b) Écrire une fonction initialisation_file() de paramètre longueur qui retourne une file aléatoire de longueur souhaitée.

Jeu de test:

>>> file = initialisation_file(5)
>>> len(file) == 5
True

c) Écrire un prédicat est_libre() de paramètres file, index qui renvoie True si la case représentée par file[index] est libre (sans véhicule). Vous prêterez attention aux valeurs possibles prises par index.

Jeu de tests:

>>> file = [1, 0, 1, 1, 0]
>>> est_libre(file, -1)
True
>>> est_libre(file, 2)
False

d) Écrire une fonction evolution_synchro() de paramètre file qui retourne la file à l’étape suivante.

Jeu de test:

>>> file = [1, 0, 1, 1, 1, 0, 0, 1, 0, 0]
>>> evolution_synchro(file)
[0, 1, 0, 1, 1, 0, 1, 0, 0, 1]

e) Écrire une fonction afficher() de paramètres file et etape (on pourra considérer ce dernier en paramètre optionnel de valeur par défaut 0) qui affichera dans la console un message donnant le numéro de l’étape ainsi que l’état de la file. On supposera que la file à l’étape n°0 désigne la file de départ.

Jeu de test:

>>> file = [0, 1, 0, 1, 1, 0, 1, 0, 0, 1]
>>> afficher(file, 1)
Etape n°1 [0, 1, 0, 1, 1, 0, 1, 0, 0, 1]

f) Appliquer les fonctions précédentes afin de déterminer l’état de la file lors des dix premières étapes, puis jusqu’à l’étape n°100.

Vérification ?

Bonus ! Si vous souhaitez avoir un résultat plus joli. Vous pourrez ajouter ce qui suit dans votre script.

Affichage graphique ?

Vous aurez noter que le résultat est surprenant, mais que ce n’est pas très réaliste de ce que l’on peut observer sur un circuit avec les mêmes règles.

Une première possibilité d’amélioration est d’ajouter un paramètre proba_avancer pour tenir compte du fait qu’un véhicule a une certaine probabilité d’avancer dans le cas où il le peut.

g) Proposer une modification de la fonction evolution_synchro() de sorte qu’elle accepte deux paramètres file et proba_avancer pour tenir compte de l’amélioration souhaitée

Jeu de test:

>>> file = [1, 0, 1, 1, 0]
>>> possibilites = [[1, 0, 1, 1, 0],\
                    [0, 0, 1, 1, 1],\
                    [1, 1, 0, 1, 0],\
                    [0, 1, 0, 1, 1]]
>>> evolution_synchro(file, 50) in possibilites
True

Faire bouger tous les véhicules en même temps ? Pas très réaliste ! Une solution: désynchroniser les mouvements des véhicules !

Partie 2: les déplacements des véhicules sont supposés asynchronisés

Les véhicules bougent les uns après les autres pour ceux qui le peuvent.

Autrement dit, à chaque étape, on modifie directement la file après l’éventuel déplacement d’un des véhicules. En détail, on choisit un élément au hasard de cette file, puis on applique la règle de déplacement.

h) Proposer une fonction evolution_asynchro() qui prend comme paramètre file et qui retourne la file ainsi modifiée de la façon présentée ci-dessus. Une fois réalisée, vous pourrez ajouter le paramètre supplémentaire proba_avancer (défini dans la partie précédente).

Jeu de test:

>>> file = [1, 0, 1, 1, 0]
>>> possibilites = [[1, 0, 1, 1, 0],\
                    [0, 0, 1, 1, 1],\
                    [1, 1, 0, 1, 0],\
                    [0, 1, 0, 1, 1]]
>>> evolution_a1(file) in possibilites
True

i) Admirez le résultat avec la fonction afficher() ou mieux avec afficher2().

Là encore, c’est perfectible. Vous aurez noté que certains éléments de file peuvent être choisies plus souvent que d’autres. On peut améliorer la fonction précédente en listant les véhicules susceptibles de bouger, puis de choisir un par un au hasard les véhicules de cette liste, et enfin, seulement une fois que l’on aura épuisé cette liste, répéter le procédé: “lister, choisir jusqu’à épuisement de la liste, …”.

Exercice 3: Feu de forêt

Présentation

Feu de forêt sur une grille de dimensions 100 x 100 avec un taux d'emboisement de 62%

Nous allons simuler cette fois l’évolution d’un feu de forêt.

La forêt sera représentée par une grille aussi appelée tableau où chaque case peut être dans l’un des 4 états: 0 (clairière), 1 (cendres), 2 (feux) et 3 (arbres).

Partons du principe que le feu suit les règles suivantes:

a) une clairière ne brûle pas,
b) les cendres restent cendres,
c) des arbres en feu deviennent cendres,
b) des arbres prennent feu si ils ont un de leurs 4 voisins (Nord, Sud, Est, Ouest) en feu (voir figure ci-dessous).

Voisinage

Les 4 voisins d'une case (voisins de Von Neumann)

Partie 1: des tableaux …

a) Écrire une fonction nommée grille() prenant deux paramètres colonnes et lignes qui désignent respectivement le nombre de colonnes et le nombre de lignes de la grille désirée.

Jeu de test:

>>> grille(3,2)
[[0, 0, 0], [0, 0, 0]]

b) Écrire deux fonctions nommées nb_colonnes() pour la première et nb_lignes() pour l’autre qui prennent toutes deux comme paramètre grille, un tableau, et qui renvoient respectivement le nombre de colonnes et le nombre de lignes de la grille donnée.

Jeux de test:

>>> grille = [[3, 0, 3],[1, 2, 3]]
>>> nb_colonnes(grille)
3

et

>>> grille = [[3, 0, 3],[1, 2, 3]]
>>> nb_lignes(grille)
2

c) Écrire une fonction effectif() de paramètres grille et etat qui renvoie le nombre de cases de cette grille dans cet état.

Jeu de test:

>>> grille = [[3, 0, 3],[1, 2, 3]]
>>> effectif(grille, 3)
3

d) Écrire une fonction surface() de paramètre grille qui renvoie le nombre de cases qui composent cette grille.

Jeu de test:

>>> grille = [[3, 0, 3],[1, 2, 3]]
>>> surface(grille)
6

e) Écrire une fonction proportion() de paramètres grille et etat qui renvoie la proportion de cases de cette grille dans cet état.

Jeu de test:

>>> grille = [[3, 0, 3],[1, 2, 3]]
>>> proportion(grille, 3)
50.0

f) Écrire une fonction voisins() de paramètres grille, etat, c et l qui renvoie la liste des coordonnées des cases voisines à la case de coordonnées (c, l) dans cet état.

Jeu de test:

>>> grille = [[3, 3, 3],\
              [3, 0, 3],\
              [0, 3, 3],\
              [3, 2, 3]]
>>> len(voisins(grille, 2, 2, 3))
1
>>> voisins(grille, 2, 2, 3)
[(1, 3)]
>>> len(voisins(grille, 3, 1, 0))
2
>>> (0,0) in voisins(grille, 3, 1, 0) and \
(2,0) in voisins(grille, 3, 1, 0)
True
>>> len(voisins(grille, 3, 1, 1))
4
>>> (1,0) in voisins(grille, 3, 1, 1) and \
(1,2) in voisins(grille, 3, 1, 1) and \
(0,1) in voisins(grille, 3, 1, 1) and \
(2,1) in voisins(grille, 3, 1, 1)
True

g) Proposer une fonction afficher() de paramètre grille qui affiche dans la console la grille.

Jeu de test:

>>> grille = [[3, 0, 3],\
              [1, 2, 3]]
>>> afficher(grille)
+---+---+---+
| 3 | 0 | 3 |
+---+---+---+
| 1 | 2 | 3 |
+---+---+---+

Partie 2: mise en place et évolution d’une forêt en feu

h) Écrire une fonction initialisation() de paramètres colonnes, lignes et p. Cette fonction renvoie la forêt sous forme d’un tableau avec uniquement des clairières et des arbres dans la proportion souhaitée désignée par la variable p.

Aide:

Jeu de test:

>>> foret = initialisation_foret(3, 2)
>>> all(foret[l][c] in {0, 1, 2, 3} for l in range(2) for c in range(3))
True

i) Écrire une fonction depart_feu() de paramètre foret qui renvoie cette forêt dans laquelle un départ de feu s’est déclaré de manière aléatoire dans l’une des cases contenant des arbres.

Jeu de test:

>>> foret = [[0, 0, 3],\
             [0, 0, 0]]
>>> depart_feu(foret)
[[0, 0, 2], [0, 0, 0]]

j) Écrire une fonction evolution() de paramètre foret et qui renvoie une nouvelle grille représentant cette forêt après propagation des flammes suivant la règle donnée en début d’énoncé (méthode synchrone).

Jeu de test:

>>> foret = [[3, 3, 3],\
             [3, 0, 3],\
             [0, 3, 3],\
             [3, 2, 3]]
>>> foret = evolution(foret)
>>> foret
[[3, 3, 3], [3, 0, 3], [0, 2, 3], [2, 1, 2]]

k) Pour finir, réaliser une procédure generer() qui prend en paramètre foret et qui va afficher l’évolution de cette forêt au fur et à mesure du temps jusqu’à ce que le feu s’éteigne. Afin de mieux visualiser l’évolution nous ferons une pause d’une seconde entre chaque génération. La fonction sleep du module time vous permettra de faire une telle pause (allez voir la documentation de cette fonction pour savoir comment l’utiliser).

Bonus ! Si vous souhaitez avoir un résultat plus joli et garder en mémoire l’évolution des flammes dans cet forêt. Vous pourrez ajouter ce qui suit dans votre script.

Affichage graphique ?