Apprendre Python et s'initier à la programmation

Dans le deuxième problème, on reçoit un nombre naturel comme donnée et il faut produire comme résultat le nombre que l'on obtiendrait en le lisant à l'envers (de droite à gauche). Pour résoudre ce problème, on va se baser sur les deux propriétés suivantes, étant donné un nombre :

• le reste de sa division entière par kitxmlcodeinlinelatexdvp10finkitxmlcodeinlinelatexdvp donne son dernier chiffre ;
• sa division entière par kitxmlcodeinlinelatexdvp10finkitxmlcodeinlinelatexdvp l'ampute de son dernier chiffre.

Grâce à ces deux propriétés, on va pouvoir parcourir le nombre reçu en paramètre chiffre par chiffre, en partant du dernier. On aura parcouru tous les chiffres lorsqu'on arrivera à zéro, ce qui est la condition d'arrêt de la boucle while. L'implémentation de la fonction est assez directe :

def reverse(n):
    result = 0
    while n != 0:
        result *= 10
        result += n % 10
        n //= 10
    return result

Comme on le constate, les chiffres extraits un à un doivent être combinés pour construire le résultat demandé. Pour cela, on initialise une variable result à zéro, et on la multiplie par kitxmlcodeinlinelatexdvp10finkitxmlcodeinlinelatexdvp à chaque tour de boucle, avant de lui ajouter le chiffre extrait du nombre de départ. On obtient ainsi à la fin le nombre de départ dans le sens inverse.

Pour le troisième problème, on reçoit deux nombres naturels non nuls et il faut déterminer le nombre de diviseurs stricts qu'ils ont en commun. Pour rappel, un diviseur strict d'un nombre naturel kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp est un naturel kitxmlcodeinlinelatexdvpdfinkitxmlcodeinlinelatexdvp compris entre kitxmlcodeinlinelatexdvp1finkitxmlcodeinlinelatexdvp et kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp (exclu) tel que le reste de la division entière de kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp par kitxmlcodeinlinelatexdvpdfinkitxmlcodeinlinelatexdvp soit nul. Pour résoudre le problème, il suffit de parcourir tous les naturels de kitxmlcodeinlinelatexdvp1finkitxmlcodeinlinelatexdvp au plus petit des deux nombres reçus (exclu), et de compter ceux qui divisent les deux nombres :

def nbcommondivisors(a, b):
    result = 0
    for i in range(1, min(a, b)):
        if a % i == 0 and b % i == 0:
            result += 1
    return result

Vous pouvez constater l'utilisation de la fonction prédéfinie min qui renvoie le plus petit des deux nombres qu'elle reçoit en paramètres.

Dans ce dernier problème, il s'agit de calculer et renvoyer la liste de tous les diviseurs d'un nombre naturel donné. On a déjà vu précédemment comment faire pour retrouver les diviseurs d'un nombre, et il s'agira ici d'en plus les stocker dans une liste :

def divisors(n):
    result = []
    for i in range(1, n+1):
        if n % i == 0:
            result.append(i)
    return result

La variable result est initialisée à une liste vide et elle est complétée au fur et à mesure dans la boucle, par chaque diviseur, à l'aide de la fonction append appliquée sur la liste.

Commençons avec une fonction récursive qui résout le problème du nombre de chiffres. On part des deux propriétés suivantes :

• si le nombre est strictement inférieur à kitxmlcodeinlinelatexdvp10finkitxmlcodeinlinelatexdvp, il n'a qu'un seul chiffre ;
• sinon, il possède un chiffre de plus que le nombre de chiffres du résultat de sa division entière par kitxmlcodeinlinelatexdvp10finkitxmlcodeinlinelatexdvp.

La première propriété correspond au cas de base qui permettra d'arrêter la récursion et la seconde propriété correspond au cas récursif. En exploitant ces deux propriétés, on obtient l'implémentation suivante :

def nbdigits(n):
    if n < 10:
        return 1
    return 1 + nbdigits(n // 10)

Notez que le choix du cas de base n'est pas unique. Pour cet exemple, on aurait pu se baser sur le fait qu'en faisant les divisions entières par kitxmlcodeinlinelatexdvp10finkitxmlcodeinlinelatexdvp successives, on finirait par obtenir kitxmlcodeinlinelatexdvp0finkitxmlcodeinlinelatexdvp. On peut utiliser cette valeur de n comme cas de base, en renvoyant la valeur kitxmlcodeinlinelatexdvp0finkitxmlcodeinlinelatexdvp :

def nbdigits(n):
    if n == 0:
        return 0
    return 1 + nbdigits(n // 10)

Ce choix est néanmoins moins intuitif, car cela n'a que peu de sens que de considérer que le nombre de chiffres de kitxmlcodeinlinelatexdvp0finkitxmlcodeinlinelatexdvp est nul. De plus, dans la définition du problème, il est clairement mentionné que n doit être un nombre naturel non nul.

La factorielle d'un nombre naturel non nul kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp, notée kitxmlcodeinlinelatexdvpn!finkitxmlcodeinlinelatexdvp, est le produit kitxmlcodeinlinelatexdvpn! = 1 \cdot 2 \cdot ... \cdot nfinkitxmlcodeinlinelatexdvp et avec kitxmlcodeinlinelatexdvp0! = 1finkitxmlcodeinlinelatexdvp, par convention. On peut la calculer en utilisant une simple boucle while ou for, ou alors de manière récursive en exploitant les deux propriétés suivantes :

La première propriété correspond au cas de base et la seconde au cas récursif. On obtient dès lors directement l'implémentation suivante :

def fact(n):
    if n == 0:
        return 1
    return n * fact(n - 1)

On remarque que la structure est similaire à celle de l'exemple précédent. Le corps de la fonction commence avec une instruction if pour le cas de base puis vient le return du cas récursif, qui rappelle la fonction.

Le plus grand commun diviseur (PGCD) de deux naturels non nuls est le plus grand nombre entier qui divise à la fois les deux nombres. Pour le trouver, il suffit de tester tous les diviseurs possibles, compris entre le plus petit des deux nombres et kitxmlcodeinlinelatexdvp1finkitxmlcodeinlinelatexdvp, et de s'arrêter dès qu'on en trouve un qui divise les deux. On peut également se tourner vers une solution récursive en exploitant les propriétés suivantes :

La première propriété est le cas de base et les deux autres sont des cas récursifs. On obtient directement l'implémentation suivante :

def pgcd(a, b):
    if b == 0:
        return a
    if a > b and b != 0:
        return pgcd(b, a % b)
    return pgcd(b, a)

On a donc, cette fois-ci, deux cas récursifs. On commence toujours le code avec une instruction if pour le cas de base, puis vient le premier cas récursif, dans une instruction if également. On termine enfin le corps de la boucle avec le second cas récursif.

Dans la suite des nombres de Fibonacci, chaque nombre s'obtient comme la somme des deux termes précédents de la suite, sachant que les deux premiers sont fixés. Si on note par kitxmlcodeinlinelatexdvpF_nfinkitxmlcodeinlinelatexdvp, le kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp^e nombre de la suite, on peut définir la suite comme :

On a cette fois-ci un exemple où l'on a deux cas de base (les deux premières propriétés) et un cas récursif (la troisième propriété) qui est une double récursion, c'est-à-dire qu'on se rappelle deux fois. L'implémentation d'une fonction permettant de calculer n'importe quel terme de la suite de Fibonacci est immédiat. On peut même la rendre plus courte en se rendant compte que le résultat à produire pour les deux cas de base est le même :

def fibo(n):
    if n == 1 or n == 2:
        return 1
    return fibo(n-1) + fibo(n-2)

Le premier problème consiste simplement à faire la somme des éléments d'une liste ou d'un tuple de nombres. La solution est immédiate en ce sens qu'il suffit de parcourir tous les éléments de la séquence et d'en faire la somme à l'aide d'une variable :

def sumall(data):
    result = 0
    for elem in data:
        result += elem
    return result

On commence par initialiser une variable result à zéro. On fait ensuite une boucle pour parcourir les éléments de la séquence. Comme on n'a pas besoin des indices, une boucle for est suffisante et plus lisible. On ajoute chacun des éléments parcourus à la variable result qu'on renvoie simplement à la fin.

Le deuxième problème consiste à trouver, dans une liste ou un tuple de nombres, la plus petite valeur qu'y s'y trouve. Pour ce faire, il suffit de parcourir tous les éléments de la séquence et de retenir dans une variable la plus petite valeur qu'on a déjà rencontrée.

Si la séquence reçue en paramètre est vide, le problème n'a pas de sens. On ne peut en effet pas trouver la valeur minimale d'une séquence qui ne contient aucun élément. On peut gérer ce cas particulier de deux manières différentes : soit on interdit tout simplement que le paramètre soit une séquence vide, soit on renvoie une valeur particulière dans le cas où la liste est vide, par exemple kitxmlcodeinlinelatexdvp+\inftyfinkitxmlcodeinlinelatexdvp. En faisant l'hypothèse que la séquence n'est pas vide, l'implémentation est assez directe :

def findmin(data):
    result = data[0]
    for elem in data:
        if elem < result:
            result = elem
    return result

On peut initialiser la variable result à la valeur de data[0] puisque la séquence n'est pas vide et contient donc au moins un élément. Ensuite, à chaque nouvel élément parcouru, on vérifie s'il est plus petit que celui stocké dans result et, si c'est le cas, on met à jour result avec cette valeur qui est donc la plus petite rencontrée jusqu'à présent.

Pour gérer le cas d'une séquence vide, il suffit simplement d'initialiser la variable result à la valeur math.inf qui représente l'infini positif, en ayant avant tout importé le module math, évidemment.

Le troisième problème consiste à vérifier si une séquence est une sous-séquence d'une autre. On a vu précédemment qu'on pouvait utiliser directement l'opérateur in pour les chaines de caractères, mais il n'est pas applicable aux autres séquences.

Une solution assez immédiate en Python se base sur le slicing. On va parcourir la séquence principale et en extraire successivement toutes les sous-séquences possibles et les comparer avec la sous-séquence que l'on cherche :

def issubsequence(subseq, seq):
    n = len(subseq)
    for i in range(0,len(seq)-n+1):
        if seq[i:i+n] == subseq:
            return True
    return False

On peut visualiser comment ce code fonctionne à l'aide de la figure 2. On va donc positionner la sous-séquence en face de la séquence principale, ce qui pourra se faire de l'indice kitxmlcodeinlinelatexdvp0finkitxmlcodeinlinelatexdvp à l'indice len(seq) - len(subseq) (on doit faire +1 lorsqu'on utilise la fonction range, car la seconde borne n'est pas incluse). Grâce à un slicing, on découpe une partie de la séquence principale, de la même longueur que la sous-séquence, que l'on compare avec cette dernière avec l'opérateur ==. Si on a correspondance, on arrête tout en renvoyant True et si on n'a jamais trouvé correspondance, la boucle se termine et on renvoie False.

Le quatrième problème consiste à compter le nombre de voyelles que contient une chaine de caractères. Pour cela, il suffit de parcourir tous les caractères de la chaine, de tester s'il s'agit ou non d'une voyelle et de les compter pour avoir le résultat attendu :

def nbvowels(s):
    result = 0
    for c in s:
        if c in 'aeiou':
            result += 1
    return result

Remarquez que la condition c in 'aeiou' est un raccourci pour c == 'a' or c == 'e' or c == 'i' or c == 'o' or c == 'u', que l'on peut se permettre grâce à la présence de l'opérateur in.

Ce cinquième problème consiste à extraire, depuis une chaine de caractères, la liste des caractères uniques qui y sont présents. Il suffit pour cela de parcourir la chaine de caractères, caractère par caractère. Chaque caractère passé en revue a soit déjà été rencontré ou est un nouveau. Il faut ignorer ceux qu'on a déjà rencontrés et stocker les nouveaux. Pour cela, on va à chaque fois vérifier si on a déjà rencontré le caractère grâce à l'opérateur in.

L'implémentation est directe, et utilise une liste seen qui contient, à tout moment, les caractères uniques déjà rencontrés.

def uniquechars(s):
    seen = []
    for c in s:
        if c not in seen:
            seen.append(c)
    return seen

On verra au chapitre suivant, dans la deuxième partie de ce cours, une structure de données plus adaptée pour représenter l'ensemble des caractères déjà rencontrés.

Le sixième problème consiste à filter une séquence de nombres selon un critère donné. Ici, on souhaite ne garder que les nombres qui sont strictement positifs. On parcourt les éléments de la séquence reçue en paramètre, ne gardant que ceux qui sont strictement positifs, en les ajoutant dans une autre liste, initialisée à [] et renvoyée par la fonction :

def filter_positive(data):
    result = []
    for elem in data:
        if elem > 0:
            result.append(elem)
    return result

On pourrait rendre cette fonction plus générique en passant le critère à appliquer en paramètre, comme on l'a fait à la section 4.1. On définit une nouvelle fonction filter avec un paramètre accept, qui est une fonction qui doit renvoyer un booléen qui signale si on doit garder ou non l'élément qu'on lui fournit en paramètre. On peut réécrire l'exemple précédent comme suit :

def positive(n):
    return n > 0

def filter(data, accept):
    result = []
    for elem in data:
        if accept(elem):
            result.append(elem)
    return result

def filter_positive(data):
    return filter(data, positive)