TD E1 : Les fonctions en python, problème d'introduction¶

I. Introduction¶

Dans un même programme, une opération, ou une séquence d'opérations peut intervenir à plusieurs reprises. Dans ce cas, il est intéressant de définir une fonction qui exécute ce bloc d'instructions. Découper un programme en fonctions élémentaires permet d'améliorer et de faciliter sa lisibilité. De même lorsqu'on résout un problème, il est souvent intéressant de le scinder en plusieurs petits problèmes. Là encore la notion de fonction prend son sens. Nous allons voir dans ce chapitre comment cela s'utilise.

Un exemple minimaliste :

In [1]:
def f(x):
    y = x*x
    return y

print(f(2))

4

Q1. À l'aide d'une boucle et d'une fonction, compléter le script suivant pour qu'il affiche :

l'image de -5 par la fonction cube est -125
l'image de -4 par la fonction cube est -64
l'image de -3 par la fonction cube est -27
l'image de -2 par la fonction cube est -8
l'image de -1 par la fonction cube est -1
l'image de 0 par la fonction cube est 0
l'image de 1 par la fonction cube est 1
l'image de 2 par la fonction cube est 8
l'image de 3 par la fonction cube est 27
l'image de 4 par la fonction cube est 64
l'image de 5 par la fonction cube est 125
In [2]:
# un script qui affiche les cubes des entiers entre -5 et 5 :
def f(x):
    return x**3

for x in range(-5,6):
    print(f"l'image de {x} par la fonction cube est {f(x)}")

l'image de -5 par la fonction cube est -125
l'image de -4 par la fonction cube est -64
l'image de -3 par la fonction cube est -27
l'image de -2 par la fonction cube est -8
l'image de -1 par la fonction cube est -1
l'image de 0 par la fonction cube est 0
l'image de 1 par la fonction cube est 1
l'image de 2 par la fonction cube est 8
l'image de 3 par la fonction cube est 27
l'image de 4 par la fonction cube est 64
l'image de 5 par la fonction cube est 125

II. Un petit problème d'introduction: la persistance multiplicative¶

1. Présentation et analyse du problème¶

Une question non encore résolue concerne la persistance multiplicative des nombres en base 10. Voilà de quoi il s'agit :

!!! note Problème d'introduction : la persistance multiplicative « On part d'un nombre entier positif. On effectue les produits de ses chiffres pour obtenir un autre entier positif, et on recommence le procédé. On s'arrête lorsque l'on obtient un nombre compris entre 0 et 9. La persistance multiplicative est le nombre d'étapes effectuées avant de s'arrêter.»

Par exemple, si l'on part de 377 on obtient la suite multiplicative suivante : $$ 377 \longrightarrow 3\times7\times7=147 \longrightarrow 1\times4\times7=28 \longrightarrow 16 \longrightarrow 6\times 1 = 6 $$ La persistance multiplicative de 377 est le nombre d'étapes effectuées, ici 4.

De nombreuses questions peuvent se poser. Par exemple :

  1. Pour un nombre donné, est-on sûr que le procédé va s'arrêter, c'est à dire est-on sûr que la persistance multiplicative est toujours finie ?
  2. Si on répond oui à la question précédente, peut-on trouver des persistances aussi grandes que l'on veut ou bien un maximum est-il atteint ?

!!!

Autant on peut répondre affirmativement à la première question, autant la deuxième est toujours en suspens !

Pour répondre à la première question, on va démontrer que la suite multiplicative obtenue par le procédé est finie. En effet, on va montrer que cette suite est une suite d'entiers positifs strictement décroissante. On en déduit alors qu'elle atteindra nécessairement un entier positif inférieur à 9, et le procédé s'arrêtera:

Considérons pour cela un entier $N$. Montrons que le produit de ses chiffres est strictement inférieur à $N$.

En effet, ce nombre $N$ s'écrit en base 10: $N=\overline{a_1a_2\cdots a_c}$ (on a considéré $c$ chiffres). Alors puisque chaque $a_i$ est un chiffre (entre 0 et 9), le produit sera au plus de $a_1\times 9^{c-1}$. Or ce nombre est strictement inférieur à $N$ puisque $N\geqslant a_1\times 10^{c-1}$, donc la suite multiplicative est strictement décroissante, et la persistance multiplicative d'un nombre est ainsi toujours finie.

En revanche, jusqu'à présent, ni le raisonnement, ni le calcul par ordinateur n'ont permis de trouver d'entiers ayant une persistance supérieure à 11. Est-ce le maximum ? La question reste ouverte...

2. Solution algorithmique¶

Il y a bien sûr de multiples façons de découper le problème, mais voici un exemple d'algorithme permettant de calculer la persistance multiplicative d'un nombre :

    Prendre un nombre N
    Initialiser la liste suite_mult à [N]
    Tant que N > 9 :
        Récupérer la liste des chiffres de N
        Faire le produit des chiffres
        Stocker ce produit dans N
        Ajouter N à la fin de la liste
    Stocker dans une variable p la longueur de la liste diminuée de 1
    Afficher " La persistance de N est ", P

Remarque : on note ici que la boucle "tant que N > 9" pourrait a priori être infinie, ce qui pose problème. Mais on a démontré dans la partie précédente qu'il n'en était rien.

!!! abstract Tâches à effectuer Ainsi écrit l'algorithme met en évidence des tâches élémentaires que l'on pourra isoler sous forme de fonctions. Par exemple :

  • une fonction qui reçoit un entier et qui renvoie la liste de ses chiffres,
  • une fonction qui reçoit un entier et qui renvoie le produit de ses chiffres,
  • une fonction qui reçoit un entier et qui renvoie sa persistance.

!!!

3 Implémentation en Python¶

!!! tip Rappel On rappelle qu'ne fonction en informatique est assez proche de la notion de fonction mathématique : elle reçoit des arguments (éventuellement aucun), elle les traite et elle renvoie une valeur (éventuellement aucune). Ne pas oublier que l'utilisation des fonctions doit se faire en deux temps :

  1. D'abord on commence par définir la fonction. Pour cela on utilise les mots clés def et  return. À ce stade, le code contenu dans la fonction n'a pas encore été exécuté.
  2. Pour utiliser, ou appeler la fonction on écrit son nom, suivi de parenthèses contenant éventuellement des arguments.

La syntaxe en python pour définir une fonction est la suivante :

def nom_de_la_fonction(liste de paramètres) :
    """ la documentation... (docstring)"""
    Les instructions...
    return (valeur de retour)

!!!

Sans se préoccuper (pour l'instant) de ce qu'elles contiennent, on peut commencer par décrire les fonctions rencontrées dans le paragraphe précédent de la façon suivante :

Par exemple, la fonction qui donne la liste des chiffres d'un nombre pourra être déclarée ainsi :

def liste_chiffres(n : int)-> list:
    """ on reçoit un entier n et la fonction renvoie
    les chiffres qui composent ce nombre sous forme
    d'une liste. Exemple :
    liste_chiffres(377) -> [7,7,3]"""
    # code à compléter
    return #...

Remarque : la déclaration des types et de la documentation sont facultatifs, mais très fortement recommandés pour écrire du code propre ! (et c'est un attendu du programme pour les concours !)

a) Étape 1 : voyons comment écrire une fonction pour obtenir la liste des chiffres d'un nombre¶

Q2. Prendre l'entier $n=1234$. Calculer de tête le quotient $q_1$ et le reste $r_1$ de la division euclidienne de $n$ par 10. Puis recommencer en calculant le quotient $q_2$ et le reste $r_2$ de la division euclidienne de $q_1$ par 10... répéter l'opération autant de fois que possible et noter les resultats $r_1$, $r_2$ etc.

Réponse :

Q3. En déduire un code pour écrire en python la fonction liste_chiffres(n : int) -> list permettant d'obtenir la liste des chiffres d'un entier. On rappelle :

  • a//b donne le quotient de la division de a par b
  • a % b donne le reste de la division de a par b
  • si lst est une liste, la méthode lst.append(nb) ajoute le contenu de la variable nb en fin de liste.
In [3]:
def liste_chiffres(n : int) -> list :
    """ on reçoit un entier n et la fonction renvoie
    les chiffres qui composent ce nombre sous forme
    d'une liste.
    Exemple :
    liste_chiffres(377) -> [7,7,3]"""

    restes = []
    
    while n > 0 :
        q = n // 10
        r = n %10
        restes.append(r)
        n = q

    return restes

print(liste_chiffres(377))

[7, 7, 3]
In [4]:
# Remarque : on peut afficher la docstring d'une fonction avec la fonction help(...)

help(liste_chiffres)

Help on function liste_chiffres in module __main__:

liste_chiffres(n: int) -> list
    on reçoit un entier n et la fonction renvoie
    les chiffres qui composent ce nombre sous forme
    d'une liste.
    Exemple :
    liste_chiffres(377) -> [7,7,3]
In [5]:
# on teste :

n=1234
print(f"la liste des chiffres de n={n} est :",liste_chiffres(n))
n=2
print(f"la liste des chiffres de n={n} est :",liste_chiffres(n))
n=6528
print(f"la liste des chiffres de n={n} est :",liste_chiffres(n))
n=1201
print(f"la liste des chiffres de n={n} est :",liste_chiffres(n))

la liste des chiffres de n=1234 est : [4, 3, 2, 1]
la liste des chiffres de n=2 est : [2]
la liste des chiffres de n=6528 est : [8, 2, 5, 6]
la liste des chiffres de n=1201 est : [1, 0, 2, 1]

b) Étape 2 : une fonction qui calule le produit des chiffres d'un nombre¶

Q4. Utiliser la fonction précédente pour écrire un code python pour la fonction produit_chiffres(n : int) -> int qui donne le produit des chiffres d'un entier.

In [6]:
def produit_chiffres(n : int) -> int :
    """ on reçoit un entier n et la fonction renvoie
    le produit des chiffres qui composent ce nombre
    ecrit en base 10. Exemple :
    produit_chiffres(377) -> 147 """
    
    chiffres = liste_chiffres(n)
    p = 1
    for c in chiffres :
        p = p*c
    return p

# test :
print(produit_chiffres(377))

147

c) Étape 3 : une fonction qui détermine la persistance multiplicative d'un nombre¶

Q5. Écrie un code pour la fonction persistance(n : int) -> int

In [7]:
def persistance(n : int) -> int :
    """ on reçoit un entier n et la fonction renvoie
    la persistance multiplicative de ce nombre.
    Exemple :
    persistance(377) -> 4 """
    
    lst = []
    while n>9 :
        p = produit_chiffres(n)
        lst.append(p)
        n = p
    return len(lst)

# test :
print(persistance(377))

4

Remarque : l'intérêt d'avoir sectionné notre code en fonctions permet en plus d'améliorer la lisibilité du code, de pouvoir le maintenir et l'améliorer ponctuellement. Par exemple voyons une autre façon de coder la fonction produit_chiffres(n : int) -> int qui donne le produit des chiffres d'un entier. On va utiliser cette fois-ci les chaînes de caractères:

In [8]:
def produit_chiffres(n : int)-> int :
    """ on reçoit un entier n et la fonction renvoie
    le produit des chiffres qui composent ce nombre
    ecrit en base 10. Exemple :
    produit_chiffres(377) -> 147 """
    ch = str(n) # transforme l'entier n en chaine de caractères
    prod = 1
    for chiffre in ch : # on énumère sur tous les chiffres
        prod *= int(chiffre) # on transforme les caractères en entiers pour faire des produits
    return prod

Ainsi, le script principal (c'est à dire la fonction persistance) n'a pas besoin d'être modifié, il fonctionnera encore... On peut le voir dans la cellule suivante :

In [9]:
print(persistance(377))

4

Q6. Solution algorithmique du problème sur la persistance: écrire un script python permettant de déterminer parmi les entiers inférieurs à 1000 quelle est la plus grande persistance, et pour quel entier elle est atteinte. Donner la suite multiplicative correspondante.

In [11]:
maxp = 1
for n in range(10,1000) :
    p = persistance(n)
    if p > maxp :
        maxp = p
        maxn = n
print(f"La persistance max est obtenue pour n={maxn}, et elle vaut {maxp}")
        

La persistance max est obtenue pour n=679, et elle vaut 5