UKOnline

Exemples

Cette section présente plusieurs problèmes résolus, pour lesquels on ne donne et discute que de l'implémentation en Python, sans passer par la description préalable d'un algorithme, en langue naturelle, par exemple. C'est l'occasion de mettre ensemble tout ce qui a été vu dans les cinq chapitres précédents en action, pour écrire des fonctions dignes de ce nom et qui résolvent des problèmes précis !

Manipulation de nombres

Commençons avec quelques exemples simples qui manipulent des nombres à l'aide d'opérations arithmétiques et de fonctions du module math .

Nombre de chiffres

Le premier problème consiste à déterminer le nombre de chiffres que possède un nombre naturel non nul. Pour cela, il suffit de procéder à des divisions entières successives par 10, jusqu'à atteindre $0$. En comptant le nombre de divisions que l'on a faites, on obtient le résultat escompté :

def nbdigits(n): result = 0 while n != 0: n //= 10 result += 1 return result

Vous remarquerez qu'on initialise d'abord la variable qui contiendra le résultat recherché, qu'elle est mise à jour dans la boucle et enfin renvoyée en fin de fonction. Il existe également une solution plus immédiate qui se base sur les propriétés du logarithme en base 10. En effet, en se rappelant que $\log_{10} 10 = 1$, $\log_{10} 100 = 2$, $\log_{10} 1000 = 3$... on arrive directement à la solution suivante :

from math import log10 def nbdigits(n): return int(log10(n)) + 1

Inversion de nombre

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 $10$ donne son dernier chiffre ;
• sa division entière par $10$ 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 $10$ à 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.

Nombre de diviseurs stricts communs

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 $n$ est un naturel $d$ compris entre $1$ et $n$ (exclu) tel que le reste de la division entière de $n$ par $d$ soit nul. Pour résoudre le problème, il suffit de parcourir tous les naturels de $1$ 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.

Liste des diviseurs

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.

Algorithme récursif

On va maintenant voir des exemples d'algorithmes récursifs, c'est-à-dire qu'ils seront implémentés par une fonction qui se rappelle elle-même. Rappelez-vous qu'il s'agit d'un choix d'implémentation, et que tous les problèmes ne se prêtent pas forcément à une implémentation récursive.

Nombre de chiffres

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 à $10$, 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 $10$.

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 $10$ successives, on finirait par obtenir $0$. On peut utiliser cette valeur de n comme cas de base, en renvoyant la valeur $0$ :

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 $0$ est nul. De plus, dans la définition du problème, il est clairement mentionné que n doit être un nombre naturel non nul.

Factorielle

La factorielle d'un nombre naturel non nul $n$, notée $n!$, est le produit $n! = 1 \cdot 2 \cdot ... \cdot n$ et avec $0! = 1$, 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 :

$$\left\{\begin{array}{ll} 0! = 1 \\ n! = n \cdot (n - 1)! & (\textrm{si } n > 0) \end{array}\right.$$

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.

Plus grand commun diviseur

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 $1$, 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 :

$$\left\{\begin{array}{ll} pgcd(a, 0) = a \\ pgcd(a, b) = pgcd(b, a) & (\textrm{si } a < b \textrm{ et } b \neq 0) \\ pgcd(a, b) = pgcd(b, a \,\%\, b) & (\textrm{si } a > b \textrm{ et } b \neq 0) \end{array}\right.$$

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.

Nombre de Fibonacci

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 $F_n$, le $n$^e nombre de la suite, on peut définir la suite comme :

$$\left\{\begin{array}{ll} F_1 = 1 \\ F_2 = 1 \\ F_n = F_{n - 1} + F_{n - 2} \end{array}\right.$$

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)

Interroger et manipuler des séquences

Pour terminer ce chapitre, voyons maintenant des algorithmes qui vont prendre comme données des séquences, pour les interroger ou pour effectuer des manipulations et transformations sur ces dernières.

Somme des éléments

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.

Valeur minimale

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 $+\infty$. 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.

Recherche d'une sous-séquence

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 $0$ à 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.

Nombre de voyelles

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.

Caractères uniques

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 livre, une structure de données plus adaptée pour représenter l'ensemble des caractères déjà rencontrés.

Filtrage

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)

• Précédent
• Suivant