TP — Cadre des TP et révisions de Python¶

Travaux pratiques · MPSI (tronc commun) · 2021-2022 · Python

Présentation des feuilles Jupyter¶

Dans une telle feuille il y a deux types de cellules :

les cellules de texte comme celle-ci qui servent à vous présenter ce cadre ;
les cellules de code dans lesquelles du code peut être saisi et qui peuvent être évaluées en appuyant sur le bouton Run (ou Exécuter) dans la barre d'outils ou avec la combinaison de touches Ctrl+Entrée ;
certaines de ces cellules de code sont en lecture seule, elles correspondent à des exemples ou des tests qui ont déjà été écrits par vos professeurs. Vous devez tout de même les évaluer pour suivre les explications ou pour valider vos résultats.

# Évaluez cette cellule
print('Bravo')

Bravo

Afin d'évaluer automatiquement votre code, on vous demandera d'écrire votre code à la place d'une ligne qui est prévue pour produire une erreur si vous ne répondez pas à la question.

# Écrivez x = 3 comme réponse

Corrigé

x = 3

Des tests sont alors proposés pour vous permettre d'évaluer votre code en vérifiant qu'il fonctionne. Il est possible que des tests soient cachés pour moins vous guider.

# si vous n'avez pas répondu à la question précédente, ce test produira une erreur

from nose.tools import assert_equal

assert_equal(x, 3)

Révisions de Python¶

Dans cette partie du TP, on va revoir très rapidement la syntaxe de Python qui a déjà été vue au lycée en mathématiques ainsi qu'en physique-chimie.

Valeurs¶

En Python, on manipule des valeurs de différents types.

Entiers relatifs `int`¶

Le type int correspond aux entiers relatifs qu'on peut ajouter, multiplier, … avec les opérateurs usuels et qui permettent de faire des calculs en précision arbitraire (nombres aussi grands qu'on le souhaite, du moment que l'ordinateur a la capacité pour).

>>> 3 + 5
8
>>> """la précision étant arbitraire, on peut manipuler de grands nombres"""
>>> 2 ** 120
1329227995784915872903807060280344576
>>> 12 // 5 # division entière : renvoie le quotient de la division euclidienne
2
>>> 12 % 5 # opérateur modulo : renvoie le reste de la division euclidienne
2

Nombres à virgule flottante `float`¶

Le type float correspond aux nombres à virgule flottante comme 1.3 ou -2e-3, qui permettent de faire des calculs scientifiques mais avec une précision donnée (erreurs d'arrondis ou de calcul).

>>> 2.2 * 1.2
2.64
>>> 2.1 - 1 # si on mélange int et float, on passe en float
1.1
>>> 12 / 5 # division flottante
2.4

Chaînes de caractères `str`¶

Le type str correspond aux chaînes de caractères comme "Bonjour " ou 'tout le monde' qui permettent de représenter une valeur constante textuelle. On peut utiliser + pour calculer la chaîne obtenue en mettant à la suite deux chaînes (on parle de concaténation).

>>> "Bonjour " + 'tout le monde'
'Bonjour tout le monde'

On peut accéder au \(n\)-ième caractère d'une chaîne s avec s[n] mais uniquement en lecture.

>>> 'test'[1] # on compte à partir de 0
'e'

Variables¶

En Python, on appelle variable un lien entre un nom et une valeur. L'instruction var = valeur permet de définir ou de redéfinir ce lien. Par exemple,

a = 3

lie la valeur 3 au nom a. Après exécution de cette instruction, on peut donc utiliser a à la place de cette valeur.

>>> var1 = 5
>>> var2 = 'Chaine'
>>> var2
'Chaine'
>>> var2 = 3 # on définit un nouveau lien, les types des valeurs n'importent pas
>>> var2+var1
8

Échanger deux variables¶

Pour échanger deux variables il faut prendre soin d'utiliser une variable temporaire. En effet, si on effectue juste les instructions

a = 3
b = 4
b = a
a = b

toutes les variables seront liées à la valeur 3.

Question 1

# Échangez les valeurs liées à a et à b
a = 5
b = 2

Corrigé

a = 5
b = 2
t = b
b = a
a = t

Tests :

from nose.tools import assert_equal

assert_equal(b, 5)
assert_equal(a, 2)

Instructions¶

On a déjà vu l'instruction d'affectation var = valeur permettant de lier une valeur à un nom de variable.

Il existe d'autres instructions en Python. Par exemple, print(expression) affiche le résultat de l'expression sur ce qu'on appelle la sortie standard du programme. C'est une instruction qu'on utilisera peu ici car pour afficher une valeur avec Jupyter, il suffit de l'écrire dans une cellule et d'évaluer la cellule comme on a pu le voir précédemment.

Instruction conditionnelle¶

Certaines instructions permettent de manipuler le flot de contrôle du programme, c'est-à-dire la manière dont les instructions sont exécutées. L'instruction conditionnelle est une de ces instructions, sa syntaxe consiste à écrire :

if expression:
   bloc d'instructions
   si vraie
else:
   bloc d'instructions
   si fausse

Cette instruction permet donc de considérer deux blocs d'instructions, séparés par ce qu'on appelle une indentation (des espaces ou, à éviter, des tabulations) ainsi qu'une expression qui permet de déterminer le bloc à exécuter. Cela fonctionne donc comme un système d'aiguillage pour un train, on choisit la direction où le flot va continuer.

Il est également possible de ne pas préciser de bloc au cas où l'expression soit fausse :

if expression:
   bloc d'instructions
   si vraie

ce qui est équivalent au bloc factice pass :

if expression:
   bloc d'instructions
   si vraie
else:
   pass

On peut enchaîner les tests avec elif, ainsi, au lieu d'écrire

if e1:
  b1
else:
  if e2:
    b2
  else:
    b3

on écrira plutôt :

if e1:
  b1
elif e2:
  b2
else:
  b3

Fonctions¶

Un point essentiel en informatique est celui de la réutilisation efficace et sûre des programmes. C'est pour cela qu'on a introduit la notion de fonction afin d'organiser des instructions. Une fonction c'est une suite d'instructions paramétrées par des entrées, les arguments, et qui produit une valeur, appelée valeur de retour quand on l'appelle.

On déclare une fonction ainsi :

def mafonction(arg1, ..., argn):
    bloc d'instructions

Pour la valeur de retour, on utilise l'instruction return valeur. Pour appeler la fonction, il suffit d'utiliser son nom et de donner des valeurs pour les arguments : mafonction(val1, ..., valn) ; le bloc d'instructions va alors s'exécuter en liant des variables arg1, … aux valeurs val1, … La valeur de cette expression sera alors la valeur de retour correspondante (ou None s'il n'y a pas d'instruction return dans le bloc).

Ainsi, la fonction suivante permet de passer deux nombres et renvoie leur somme :

def ajoute(a, b):
    return a+b

Si on écrit ajoute(1,2)*4 cela va alors exécuter la fonction et évaluer l'expression comme s'il y avait 3*4.

À partir de maintenant, les questions consisteront, étant donné le début de définition d'une fonction, à écrire les instructions qui la constituent. Les tests de validation sont alors des appels de vos fonctions.

Question 2

def multiplie(a,b):
    '''Prend en entrée deux nombres a et b et renvoie leur produit.'''

Corrigé

def multiplie(a,b):
    '''Prend en entrée deux nombres a et b et renvoie leur produit.'''
    return a*b

Tests :

from nose.tools import assert_equal

assert_equal(multiplie(2,3), 6)

Une fonction peut très bien avoir pour argument une autre fonction :

Question 3

def applique_deux_fois(f, a):
    '''Prend en entrée une fonction f de deux arguments, l'applique sur a et a et
    renvoie le résultat.'''

Corrigé

def applique_deux_fois(f, a):
    '''Prend en entrée une fonction f de deux arguments, l'applique sur a et a et
    renvoie le résultat.'''
    return f(a,a)

Tests :

from nose.tools import assert_equal

assert_equal(applique_deux_fois(multiplie, 3), 9)

Boucles¶

Les boucles sont un élément essentiel de l'informatique : ce sont les instructions qui permettent de répéter quelque chose. On parle d'itération pour une répétition d'un même bloc d'instructions.

On distingue deux types de boucles :

les boucles conditionnelles dont une condition permet de déterminer si on doit en sortir ou si on doit continuer avec une autre itération. La syntaxe en Python est :
```
while condition:
    bloc d'instruction
    à exécuter
```
les boucles non conditionnelles qui effectuent un bloc d'instruction un nombre de fois donné. En Python ces boucles sont régies par des valeurs dont on peut énumérer les éléments, on parle d'itérable. Ce sont des valeurs pour lesquelles on peut identifier un premier élément et un ordre de parcours après celui-ci. L'itérable le plus simple est range(a,b) qui contient les entiers a, a+1, …, b-1. Ainsi range(0,5) énumère 0, 1, 2, 3, 4. Comme ce cas est fréquent, le premier paramètre peut être ignoré, on peut ainsi juste écrire range(5). La syntaxe d'une boucle non conditionnelle en Python est alors :
```
for element in iterable:
    bloc d'instruction
    à exécuter
```

Quand on va exécuter ce bloc, on va donc modifier la variable element qui va être tour à tour liée à chaque élément présent dans iterable.

# Exemple
for i in range(5):
    print('La valeur de i est :', i)

La valeur de i est : 0
La valeur de i est : 1
La valeur de i est : 2
La valeur de i est : 3
La valeur de i est : 4

Notons qu'on peut tout à fait faire l'exemple précédent avec une boucle while en définissant nous-même la variable i :

i = 0
while i < 5:
    print('La valeur de i est :', i)
    i = i + 1 # à ne pas oublier sinon on reste indéfiniment dans la boucle !

La valeur de i est : 0
La valeur de i est : 1
La valeur de i est : 2
La valeur de i est : 3
La valeur de i est : 4

Calcul de la somme des carrés¶

Question 4

On vous demande ici de calculer \(\sum_{k=0}^n k^2\) à l'aide d'une boucle for.

def somme_carres(n):
    '''Renvoie la somme des k**2 pour k allant de 0 à n'''

Corrigé

def somme_carres(n):
    '''Renvoie la somme des k**2 pour k allant de 0 à n'''
    somme = 0
    for k in range(n+1):
        somme = somme + k**2
    return somme

Tests :

from nose.tools import assert_equal

assert_equal(somme_carres(12), 650)
assert_equal(somme_carres(0), 0)

Puissance décroissante et factorielle¶

Soit \(n\) et \(k\) des entiers, on note \(n^{(k)} = n \times (n-1) \times \dots \times (n-k+1)\) appelée \(n\) à la puissance décroissante \(k\). On note \(n! = n^{(n)}\) appelée la factorielle de \(n\).

Question 5

def puissance_decroissante(n, k):
    '''Renvoie n à la puissance décroissante k'''

Corrigé

def puissance_decroissante(n, k):
    '''Renvoie n à la puissance décroissante k'''
    produit = 1
    for i in range(k):
        produit = produit * (n-i)
    return produit

Tests :

from nose.tools import assert_equal

assert_equal(puissance_decroissante(4, 4), 24)
assert_equal(puissance_decroissante(12, 3), 1320)
assert_equal(puissance_decroissante(5, 1), 5)
assert_equal(puissance_decroissante(5, 0), 1)

Question 6

def factorielle(n):
    '''Renvoie n! en utilisant la fonction précédente'''

Corrigé

def factorielle(n):
    '''Renvoie n! en utilisant la fonction précédente'''
    return puissance_decroissante(n, n)

Tests :

from nose.tools import assert_equal

assert_equal(factorielle(0), 1)
assert_equal(factorielle(1), 1)
assert_equal(factorielle(4), 24)

Plus grande puissance de 2 supérieure¶

Il est très important en informatique de savoir trouver le nombre minimal de bits sur lesquels on peut coder une information. Pour un entier naturel \(n\), il s'agit de trouver le plus petit \(d\) tel que \(2^d > n \ge 0\).

Étant donné \(n\), on ne peut pas savoir (bon en fait on pourrait avec un logarithme, mais on va supposer qu'on ne sait pas) à l'avance

Question 7

def plus_grande_puissance(n):
    '''Renvoie le plus petit entier d tel que n < 2**d'''

Corrigé

def plus_grande_puissance(n):
    '''Renvoie le plus petit entier d tel que n < 2**d'''
    d = 0
    p = 1
    while p <= n:
        p = p * 2
        d = d + 1
    return d

Tests :

from nose.tools import assert_equal

assert_equal(plus_grande_puissance(0), 0)
assert_equal(plus_grande_puissance(1), 1)
assert_equal(plus_grande_puissance(15), 4)

Autour de la suite de Syracuse¶

Étant donné \(a \in \N^*\), on appelle suite de Syracuse de premier terme \(a\), la suite \((u_n)_{n \in \N}\) définie par \(u_0 = a\) et pour \(n \in \N\) :

\[ u_{n+1} = \begin{cases} \dfrac{u_n}{2} & \text{si } u_n \text{ est pair} \\ 3u_n + 1 & \text{sinon.} \end{cases} \]

Rappel : pour déterminer si un nombre a est pair on peut utiliser le modulo et tester a % 2 == 0. La division entière par deux se note a // 2.

Question 8

def suivant(u):
    '''Etant donné un entier u representant un terme u_n de la suite
    renvoie le terme u_(n+1)'''

Corrigé

def suivant(u):
    '''Etant donné un entier u representant un terme u_n de la suite
    renvoie le terme u_(n+1)'''
    if u % 2 == 0:
        return u // 2
    else:
        return 3 * u + 1

Tests :

from nose.tools import assert_equal

assert_equal(suivant(14), 7)
assert_equal(suivant(7), 22)

Question 9

def syracuse(a, n):
    '''Renvoie u_n le nième terme de la suite de Syracuse de premier terme a'''

Corrigé

def syracuse(a, n):
    '''Renvoie u_n le nième terme de la suite de Syracuse de premier terme a'''
    u = a
    for i in range(n):
        u = suivant(u)
    return u

Tests :

from nose.tools import assert_equal

assert_equal(syracuse(3,5), 4)
assert_equal(syracuse(1,0), 1)
assert_equal(syracuse(1,1), 4)
assert_equal(syracuse(1,2), 2)

En évaluant les termes de la suite, on constate qu'elle semble devenir périodique à partir d'un certain rang. Par exemple, en partant de \(a = 14\) :

\[ 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, \dots \]

Quelle que soit la valeur de \(u_0\), on retombe sur ce cycle. (Demandez une preuve à votre professeur de mathématiques à 12h05)

On appelle temps de vol pour \(a\), le plus petit \(n\) tel que \(u_n = 1\) et altitude maximale pour \(a\) la plus grande valeur prise par la suite. Ici, le temps de vol pour 14 est 17 et son altitude maximale est 52.

Question 10

def temps_de_vol(a):
    '''Renvoie le temps de vol pour a'''
    # On pourra réutiliser syracuse mais c'est plus efficace de reprendre le calcul

Corrigé

def temps_de_vol(a):
    '''Renvoie le temps de vol pour a'''
    u = a
    n = 0
    while u != 1:
        u = suivant(u)
        n = n + 1
    return n

Tests :

from nose.tools import assert_equal

assert_equal(temps_de_vol(1), 0)
assert_equal(temps_de_vol(14), 17)

Question 11

def altitude_maximale(a):
    '''Renvoie l'altitude maximale pour a'''

Corrigé

def altitude_maximale(a):
    '''Renvoie l'altitude maximale pour a'''
    if a == 1 or a == 2:
        return 4
    u = a
    alt = a
    while u != 1:
        u = suivant(u)
        if u > alt:
            alt = u
    return alt

Tests :

from nose.tools import assert_equal

assert_equal(altitude_maximale(1), 4)
assert_equal(altitude_maximale(2), 4)
assert_equal(altitude_maximale(14), 52)

Question 12

def plus_long_temps_de_vol(N):
    '''Renvoie le plus petit entier 0 < a <= N tel que le temps de vol pour a soit maximal
    par rapport aux temps de vol des autres entiers <= N'''

Corrigé

def plus_long_temps_de_vol(N):
    '''Renvoie le plus petit entier 0 < a <= N tel que le temps de vol pour a soit maximal
    par rapport aux temps de vol des autres entiers <= N'''
    a_max = 1
    t_max = 0
    for a in range(2,N+1):
        t = temps_de_vol(a)
        if t > t_max:
            t_max = t
            a_max = a
    return a_max

Tests :

from nose.tools import assert_equal

assert_equal(plus_long_temps_de_vol(1), 1)
assert_equal(plus_long_temps_de_vol(12), 9)
assert_equal(plus_long_temps_de_vol(50), 27)

TP — Cadre des TP et révisions de Python¶

Présentation des feuilles Jupyter¶

Révisions de Python¶

Valeurs¶

Entiers relatifs int¶

Nombres à virgule flottante float¶

Chaînes de caractères str¶

Variables¶

Échanger deux variables¶

Instructions¶

Instruction conditionnelle¶

Fonctions¶

Boucles¶

Calcul de la somme des carrés¶

Puissance décroissante et factorielle¶

Plus grande puissance de 2 supérieure¶

Autour de la suite de Syracuse¶

Entiers relatifs `int`¶

Nombres à virgule flottante `float`¶

Chaînes de caractères `str`¶