LP - Activités #

Ce document est mis à disposition selon les termes de la Licence Creative Commons Attribution 3.0 France.

• Titre du document d’origine complet : Livret Pédagogique CodingUP
• Auteurs : Laurent Signac, Emmanuel Laize, Freddy Lege, Caroline Tartary

Ce document est la seconde partie du Livret pédagogique, dans laquelle nous présentons quelques tactiques pour aborder les problèmes typiques des défis de programmation.

La suite du document, intitulée Livret pédagogique : Exercices propose des exercices corrigés.

Activités autour des nombres #

De nombreuses activités sont basées sur les nombres entiers. Les énoncés sont généralement simples et mettent en jeu des suites, les nombres premiers, les changements de base, la décomposition d’un nombre en chiffres. Il n’est pas rare que les nombres mis en jeu soient assez grands (afin que le problème ne soit pas trivial à résoudre manuellement) et l’utilisation d’un langage ne limitant pas trop la taille des entiers simplifie beaucoup les choses.

Test de divisibilité, primalité, liste des diviseurs #

Pour tester si un nombre est divisible par un autre, on peut utiliser l’opérateur modulo (%) qui calcule le résultat de la division entière.

Il en découle un algorithme immédiat pour savoir si un nombre est premier : on tente de le diviser par tous les nombres strictement supérieurs à 1 et plus petits que lui. On peut arrêter les tests à l’entier inférieur ou égal à la racine du nombre à tester. On peut aussi diviser le nombre de tests par 2 en ne testant la division que par les nombres impairs (en en traitant 2 à part)

def est_premier(n):
    if n % 2 == 0:
        return False
    for i in range(3, 1 + int(n ** 0.5), 2) :
        if n % i == 0:
            return False
    return True

Dans le cas où les nombres sont grands ou s’il faut faire beaucoup de tests de primalité, on devra améliorer cet algorithme. Si on dispose d’une liste de nombre premiers, on peut tester la division par ces nombres uniquement, et ainsi répondre rapidement à la question de la primalité d’un nombre inférieur au carré du plus grand nombre premier de notre liste. Disposer de la liste des nombres premiers jusqu’à 1000 permet ainsi de tester très rapidement la primalité des nombres jusqu’à un million. Si ce n’est pas suffisant, une bonne implémentation du crible d’Érathostène (qui permettra d’allonger la liste des premiers connus) permet généralement de se sortir d’affaire (Crible d’Ératosthène et Sieve of Erathosthenes in Python on RosettaCode).

Si on ne s’intéresse pas uniquement à la primalité du nombre mais aussi à la liste de ses diviseurs, on pourra procéder ainsi :

def liste_diviseurs(n):
    liste = [1]
    for i in range(2, n) :
        if n % i == 0:
            liste.append(i)
    liste.append(n)
    return liste

On pourrait d’ailleurs, si l’efficacité n’est pas une priorité, tester la primalité de n en vérifiant si la fonction précédente renvoie [1, n].

La somme des diviseurs stricts d’un nombre est par exemple utilisée pour construire les suites aliquotes. Dans ce cas précis, on est juste intéressé par la somme des diviseurs qui peut être déduite de la décomposition en facteurs premiers du nombre. Calculer cette décomposition est généralement plus rapide que calculer la liste des diviseurs (Somme des diviseurs).

Suites #

Les suites sont une source inépuisable de problèmes. L’exemple le plus utilisé est probablement la suite de Fibonacci, qui modélise (de manière assez peu réaliste) l’accroissement du nombre de couples de lapins. Chaque mois, tous les couples entamant leur deuxième mois donnent naissance à un nouveau couple de lapins. Le nombre de couples au mois \(n+2\) est obtenu par récurrence : \(F_{n+2}=F_{n+1}+F_{n}\) et \(F_0=0, F_1=1\)

La programmation des suites définies par des relations de récurrence est immédiate en écrivant des fonctions récursives, mais le résultat est parfois très peu efficace.

Voici une implémentation récursive de la suite de Fibonacci :

def fibo_rec(n) :
    if n < 2:
        return n
    return fibo_rec(n - 1) + fibo_rec(n - 2)

Inutile d’espérer calculer \(F_{100}\) avec ce qui précède.

La version itérative est en revanche rapide, et l’opérateur d’affectation simultanée de Python permet de condenser un peu l’écriture :

def fibonacci(n):
    if n == 0:
        return 0
    a, b = 0, 1
    for i in range(1, n + 1):
        a, b = b, a + b
    return n

Une adaptation efficace de la version récursive d’une fonction est d’utiliser la mémoïsation (enregistrement des résultats intermédiaires dans une table). Le résultat sera presque aussi efficace que la version itérative, mais on gardera l’écriture récursive de la fonction (le principe des décorateurs Python permet de faire ce genre d’opérations de manière très propre, sans toucher une seule ligne du code de la fonction récursive). Cela dépasse toutefois le cadre de ce document.

Les exemples de suites sont très nombreux et les ouvrages de curiosités mathématiques en utilisent un bon nombre. On pourra citer par exemple :

• les suites de Lucas
• la suite de Collatz
• les suites aliquotes
• …

Enfin, l’encyclopédie en lignes des séquences d’entiers (Oeis) contient, outre ces quelques exemples, des milliers (342 474 au moment où ces lignes sont écrites) d’autres suites, pouvant donner lieu à des problèmes.

Extraction des chiffres #

Les changements de base et les calculs sur les chiffres (dans une base donnée) d’un nombre reviennent assez souvent dans les défis de programmation. Selon les outils proposés par le langage choisi, cette opération peut être très facile.

En Python, si on parvient à écrire la représentation d’un nombre dans une base particulière sous forme d’une chaîne de caractère, on peut extraire ses chiffres en utilisant le fait qu’il est immédiat d’itérer sur les caractères d’une chaîne. Voici une fonction qui calcule la somme des chiffres d’un nombre exprimé en base 10 :

def somme_chiffres(n):
    s = 0
    for c in str(n) :
        s = s + int(c)
    return s

Dans le programme qui précède, le nombre est transformé en chaîne de caractères par str(n) et la boucle itère sur cette chaîne. Dans la boucle, chaque chiffre c est retransformé en nombre par int(c) avant d’être ajouté à la somme.

On peut aller encore plus vite (en taille de code) en utilisant la fonction sum qui renvoie la somme des éléments d’une liste, et la construction d’une liste en compréhension :

>>> n = 1234
>>> s = sum([int(c) for c in str(n)])
>>> print(s)
10

Certains changements de base sont déjà implantés dans le langage, comme le passage en binaire ou en hexadécimal :

>>> n = 105
>>> bin(n)
'0b1101001'
>>> hex(n)
'0x69'

Le résultat obtenu étant une chaîne, on peut retirer les premiers caractères avec l’opérateur [] :

>>> n = 105
>>> s = bin(n)
>>> s[2:]
'1101001'

Une autre solution, si on veut un résultat sur 16 bits par exemple :

>>> "{:016b}".format(1245)
'0000010011011101

ou encore, en utilisant les f-strings :

>>> f"{1245:016b}"
'0000010011011101

On peut alors procéder comme pour la base 10 et faire la somme des chiffres (éventuellement en utilisant un dictionnaire pour le cas où plus de 10 chiffres sont utilisés).

Une manière plus universelle de changer de base permet aussi d’accéder aux chiffres. Voici un exemple de fonction qui opère des divisions successives pour passer dans une base b arbitraire. Le résultat est une liste contenant les valeurs des chiffres dans cette base.

def change_base(n, b=10):
    liste = []
    while n > 0:
        liste.insert(0, n % b)
        n = n // b
    return liste or [0]

Voici un exemple d’utilisation :

>>> change_base(145)
[1, 4, 5]
>>> change_base(145,16)
[9, 1]
>>> change_base(145,2)
[1, 0, 0, 1, 0, 0, 0, 1]

On peut directement obtenir la somme des chiffres :

>>> sum(change_base(1234,10))
10

Exploration systématique #

De nombreux problèmes sont basées sur la nécessité de faire une exploration systématique de solutions potentielles jusqu’à trouver la solution. Ces problèmes sont généralement basés sur le fait qu’il n’existe pas de moyen simple de calculer une solution, mais que vérifier si une instance donnée est solution ou non est assez rapide (ceci peut être relié à la notion de problèmes de classe NP)

Voici un exemple : Étant donnés 5 nombres 2,3,5,1,4, de combien de manières différentes peut on obtenir une somme inférieure à 8 en sélectionnant puis additionnant certains des 5 nombres.

Dans l’exemple qui précède, en tâtonnant un peu, on trouvera :

• 2, 2+3, 2+5, 2+1, 2+4, 2+3+1, 2+5+1, 2+1+4
• 3, 3+5, 3+1, 3+4, 3+1+4
• 5, 5+1,
• 1, 1+4
• 4

Il y a donc 18 solutions.

Si on dispose de plus de beaucoup plus de 5 nombres, le comptage manuel devient pénible. Voyons comment le résoudre dans le cas où tous les nombres sont positifs (éléments de l’ensemble ainsi que somme maximum).

La fonction combinations du module itertools de Python permet de générer les sous-ensembles à k éléments d’un objet itérable (comme une liste de nombres). Son utilisation simplifie assez l’écriture d’un programme. L’idée est toute simple : générer tous les sous ensembles (ceux à 1 élément, puis ceux à 2 éléments, puis ceux à 3 éléments etc…) et vérifier la valeur de leur somme. Les entrées du problème sont donc la liste d’éléments et la somme à ne pas dépasser :

import itertools
def nb_sommes(liste, S):
    nb = 0
    for k in range(1, len(liste) + 1) :
        for c in itertools.combinations(liste, k) :
            if sum(c) <= S:
                nb = nb + 1
    return nb

Ce qui nous donne :

>>> nb_sommes([2, 3, 5, 1, 4], 8)
18
>>> nb_sommes([2, 3, 5, 1, 4, 8, 7, 3, 6, 5, 1, 9], 22)
1285

Si les calculs deviennent trop long (ce qui est souvent le cas dans ce genre de problème), il faut parfois chercher à diminuer l’espace des solutions potentielles.

Reprenons l’exemple où nous devons dénombre le nombre de manières de faire 22 ou moins à partir de la liste [2, 3, 5, 1, 4, 8, 7, 3, 6, 5, 1, 9]. On pourrait remarquer que puisque tous les nombres sont strictement inférieurs à 10, en ajouter 2 donnera toujours un total inférieur à la valeur limite 22. Ce qui nous donne \(C_{12}^{1}+C_{12}^2\) solutions basés sur des sommes de 1 ou 2 chiffres, sans avoir à les générer. Inversement, si on trie la liste de nombres, on obtient [1, 1, 2, 3, 3, 4, 5, 5, 6, 7, 8, 9]. On constate alors qu’en ajoutant 8 des nombres de la liste, le plus petit total qu’on peut obtenir est 24. Ce qui signifie qu’on ne peut pas obtenir un total inférieur à 22 en ajoutant 8 nombres ou plus. Dans le programme qui précède, on peut donc faire varier k de 3 à 8 plutôt que de 1 à 12. Ces petites optimisations sont très faciles à faire. On peut en trouver de bien plus compliquées, dont l’implantation sera ou non justifiée en comparaison du temps de calcul nécessaire à la résolution du problème.

Enfin, si on travaille avec un langage qui ne dispose pas des outils pour générer les sous-ensembles d’un ensemble à \(N\) éléments, on peut procéder ainsi :

• associer à un nombre \(n<2^N\) son écriture binaire (qui aura donc au plus \(N\) chiffres)
• construire le sous ensemble qui contient l’élément i si et seulement si le bit i de l’écriture de n est à 1.

Il suffit de faire ceci pour tous les nombres de 0 à \(2^N-1\) et on générera pour chaque nombre une sous partie de l’ensemble (il y en a bien \(2^N\) au total).

Voici un exemple d’implémentation en Python :

def sous_parties(L) :
    ens = []
    for n in range(0, 2 ** len(L)):
        s = bin(n)[2:]
        combi = []
        for k in range(len(L)) :
            if k < len(s) and s[len(s)-k-1] == '1':
                combi.append(L[k])
        ens.append(combi)
    return ens

Une manière un peu plus pythonique de faire ceci utiliserait les générateurs :

def gen_sous_parties(L) :
    for n in range(0, 2 ** len(L)):
        s = bin(n)[2:]
        l = [e for e,k in zip(L,reversed(s)) if k == '1']
        yield l

L’exemple qui précède utilise les listes en compréhension, la fonction zip qui combine plusieurs objets itérables, et le mot clé yield qui fabrique un générateur.

La fonction qui précède permet de réécrire la résolution de notre problème ainsi, de manière très concise et compréhensible au premier coup d’œil (le -1 est là pour retirer la sous partie vide, qui satisfait évidemment à la condition si S est positif, mais que nous ne voulons pas compter) :

def nb_sommes2(liste, S) :
    return len([k for k in gen_sous_parties(liste) if sum(k) <= S]) - 1

Activités autour des codes #

Le déchiffrement de codes secrets se prête particulièrement bien aux défis de programmation. Cette activité fait appel à de l’astuce (il faut avoir une idée de la manière dont fonctionne la méthode de chiffrement), à de l’exploration systématique (la machine est utile pour pouvoir tester les possibilités plus rapidement qu’à la main) et elle aiguise généralement facilement la curiosité : on veut arriver à déchiffrer le code.

Les outils nécessaires, pour peu qu’on se limite aux méthode de chiffrement alphanumériques, sont :

• la manipulation de chaînes caractère par caractère
• l’arithmétique sur les caractères (pouvoir ajouter 2 à un caractère par exemple)
• le remplacement de certains caractères par d’autres, la suppression des espaces, le passage en capitales…

Ces outils sont généralement disponibles dans tous les langages. La manipulation caractère par caractère se fait généralement en indiçant la chaîne, l’arithmétique se fait sur les codes Ascii (nous verrons qu’avec Python, ce n’est pas exactement ça, mais ça ne nous gênera pas). On dispose aussi parfois d’outils qui permettent de remplacer une liste de caractères par une autre, de passer en capitales ou en minuscules, d’utiliser des expressions rationnelles pour rechercher ou remplacer.

Manipulation des chaînes #

Une particularité de Python est que les chaînes de caractères sont des objets non modifiables. Cela signifie qu’on ne peut pas modifier un caractère de la chaîne : il faut systématiquement reconstruire une nouvelle chaîne complète, ou bien transformer la chaîne en liste et manipuler la liste (chaque élément de la liste sera alors un caractère). De plus, les chaîne Python sont des chaînes Unicode, ce qui est plutôt une bonne nouvelle, Unicode étant le standard à suivre pour les années à venir. L’encodage par défaut en Python 3 est utf-8, qui est l’encodage le plus courant pour les chaînes Unicode. De plus Unicode coïncide avec la tableau Ascii pour les caractères latins usuels, ce qui implique que dans notre cas, nous ne verrons pas la différence avec un programme plus classique écrit en C par exemple, qui manipule les codes Ascii des caractères. Les chaînes sont de plus itérables : itérer sur une chaîne permet de la parcourir caractère par caractère. Enfin, les chaînes sont délimités indifféremment par " ou '. Les délimiteurs """ ou ''' permettent d’écrire des chaînes multilignes.

Voici un exemple d’opérations courantes sur les chaînes :

>>> str1 = "Une chaîne de caractères"
>>> str1[2]
e
>>> str2 = str1[:3] + " belle" + str1[3:]
>>> str2 
Une belle chaîne de caractères
>>> ord('U')
85
>>> ord(str2) 
85 # utilise le premier caractère de str2
>>> chr(85)
'U'
>>> for c in str1: 
        print(c)
U
n
e

b
e
...
>>> for c in str1:
        print(chr(ord(c) + 5))
Z
s
j
%
h
m
f
...
>>> l = [chr(ord(c) + 5) for c in str1]
>>> l
['Z', 's', 'j', '%', 'h', 'm', 'f', 'ó', 's', 'j', '%', 'i', 'j', '%', 'h', 'f', 'w', 'f', 'h', 'y', 'í', 'w', 'j', 'x'
>>> str3 = "".join(l)
>>> str3
'Zsj%hmfósj%ij%hfwfhyíwjx'

On peut déjà faire pas mal de choses avec tout ceci.

Arithmétique #

Nous avons vu précédemment qu’on passait d’un caractère à un nombre avec ord et d’un nombre à un caractère avec chr. Le nombre en question étant la valeur Unicode du caractère, elle est comprise pour les capitales entre 65 et 90. Une possibilité standard pour manipuler les caractères en décalant l’alphabet est d’appliquer une fonction de type : \(c\mapsto (c+3)%26\) qui décale chaque caractère de 3 à condition que la numérotation commence à 0 (le modulo sert à cycler l’alphabet). Voici un exemple de fonction qui décale une lettre de n positions dans l’alphabet, telle qu’on pourrait l’écrire dans la plupart des langages de programmation :

def decale(c, n):
   " décale le caractère c de n position "
   return (c-ord('A')+n) % 26 + ord('A')

Cette façon de procéder est utile, car elle est assez standard. Néanmoins, dans le cas présent, il serait plus efficace d’utiliser des constructions plus spécifiques à Python, comme nous allons le voir.

Remplacement des caractères #

Python dispose d’une méthode translate probablement inspirée de l’outil Unix tr, qui permet de remplacer chaque caractère d’une chaîne selon une table de correspondance. La table est fabriquée par la méthode statique str.maketrans, qui prend en argument deux chaînes : départ et arrivée. Par exemple, la table : "QSDF","AUIE" remplace Q par A, S par U… Les deux chaînes doivent avoir la même longueur, et chaque caractère doit être unique dans la première.

On peut facilement construire les chaînes de départ et d’arrivée pour un décalage particulier :

>>> dep = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
>>> arr = dep[4:] + dep[:4]
>>> arr
'EFGHIJKLMNOPQRSTUVWXYZABCD'

Il ne reste plus ensuite qu’à appliquer cette table à la chaîne à chiffrer à l’aide des fonctions maketrans et tr :

>>> str = "CACHEZ VOS ROUGES TABLIERS"
>> str.translate(str.maketrans(dep, arr))
'GEGLID ZSW VSYKIW XEFPMIVW'

On peut même s’affranchir de la saisie de l’alphabet en utilisant la variable ascii_uppercase du module string :

>>> import string
>>> string.ascii_uppercase
'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

Voici la méthode complète :

def chiffre(s, cle) :
    import string
    dep = string.ascii_uppercase
    arr = dep[cle:] + dep[:cle]
    return s.translate(str.maketrans(dep, arr))

Notons au passage que cette méthode fonctionne aussi avec des décalages négatifs. Un texte chiffré avec la clé 5 pourra être déchiffré en utilisant la même fonction, pour une valeur de clé de -5 ou 21. Enfin, cette façon de procéder ne modifie que les lettres capitales. Les minuscules, les caractères accentués, la ponctuation et les espaces restent inchangés.

Autres méthodes sur les chaines #

De nombreuses méthodes s’appliquent aux chaînes de caractères dont :

• upper() qui met en capitales
• lower() qui met en minuscules
• split(c) qui découpe la chaîne sur le caractère c

Expressions rationnelles #

Python dispose du module re, permettant d’utiliser toute la puissance des expressions rationnelles. Nous ne couvrirons pas ce module ici, mais on pourra trouver des informations dans la documentation : module re

Exemple : Analyse fréquentielle et César automatique #

Le chiffre de César est un décalage de l’alphabet. C’est donc une méthode de chiffrement monoalphabétique, c’est à dire que chaque lettre est toujours remplacée par la même durant le cryptage du message. En conséquence, le lettre qui revient le plus souvent dans le message chiffré aura de bonnes chances d’être le chiffrement d’un E, puisque E est la lettre la plus courante en français. Entrer dans ce genre de considérations, c’est faire l’analyse fréquentielle du message chiffré. Pour peu que le message soit assez long, cette méthode est très fiable. On peut même faire rechercher automatiquement le décalage utilisé pour chiffrer en les essayant tous (il n’y en a que 26, en comptant les messages non chiffrés), puis en comparant la fréquence des caractères avec les fréquences standard en Français.

Voici une première fonction qui renvoie un tableau contenant les fréquences d’apparition de chaque caractère (en pourcentage) d’une chaîne donnée :

def analyse_freq(s):
    freq = [0] * 26
    for c in s :
        co = ord(c) - ord('A')
        if co >= 0 and co < 26:
            freq[co] += 1
    n = sum(freq)
    return [f / n * 100 for f in freq]

Exemple :

>>> s = "IL PRESIDE AUX CHOSES DU TEMPS. IL PORTE UN JOLI NOM SATURNE, MAIS C'EST UN DIEU FORT INQUIETANT."
>>> f = analyse_freq(s)
>>> f
[5.263157894736842, 0.0, 2.631578947368421, 3.9473684210526314, 11.842105263157894, \
1.3157894736842104, 0.0, 1.3157894736842104, 10.526315789473683, 1.3157894736842104, \
0.0, 3.9473684210526314, 3.9473684210526314, 7.894736842105263, 6.578947368421052, \
3.9473684210526314, 1.3157894736842104, 5.263157894736842, 9.210526315789473, \
9.210526315789473, 9.210526315789473, 0.0, 0.0, 1.3157894736842104, 0.0, 0.0]
>>> max(f)
11.842105263157894

La valeur maximum (11.8%) est obtenue pour la 5ème valeur de f, c’est à dire pour la lettre E.

À présent, chiffrons la chaîne s :

>>> s2 = chiffre(s, 4)
>>> f2 = analyse_freq(s2)
>>> f2
[0.0, 1.3157894736842104, 0.0, 0.0, 5.263157894736842, 0.0, 2.631578947368421, \
 3.9473684210526314, 11.842105263157894, 1.3157894736842104, 0.0, \
 1.3157894736842104, 10.526315789473683, 1.3157894736842104, 0.0, \
 3.9473684210526314, 3.9473684210526314, 7.894736842105263, 6.578947368421052, \
 3.9473684210526314, 1.3157894736842104, 5.263157894736842, 9.210526315789473, \
 9.210526315789473, 9.210526315789473, 0.0]
>>> max(f2)
11.842105263157894

On obtient bien les mêmes valeurs, décalées de 4 cases, ce qui est très visible si on trace un graphe :

Les fréquences moyennes d’apparition des lettres en français sont disponibles par exemple sur Wikipedia (selon les sources, ces moyennes varient un petit peu).

Si nous comparons les fréquences moyennes en français et celles du texte chiffré, nous obtenons :

Ce simple graphe nous permet de calculer le décalage à opérer pour faire coïncider au mieux les deux graphes :

Cette opération peut être réalisée automatiquement avec les séries de fonctions suivantes. La fonction convolve(s1, s2) détermine, pour chaque décalage de la chaîne s2, la somme des produits des s2[i] * s1[i]. Cette valeur est d’autant plus petite que les l’écart entre s1 et s2 est faible (voir corrélation croisée ou produit de convolution discret)

def convolve(s1,s2):
    res=[]
    for dec in range(len(s2)):
        res.append(sum(c1 * c2 for c1, c2 in zip(s1, s2)))
        s2 = s2[1:] + s2[:1]
    return res

def auto_dechiffre(s):
    f1=[9.2, 1.02, 2.64, 3.39, 15.87, 0.95, 1.04, 0.77, 8.41,\
        0.89, 0.0, 5.34, 3.24, 7.15, 5.14, 2.86, 1.06, 6.46,\
        7.9, 7.26, 6.24, 2.15, 0.0, 0.3, 0.24, 0.32] # Fréq Wikipédia
    f2 = analyse_freq(s)
    c = convolve(f1, f2)
    decalage = c.index(max(c))
    return chiffre(s, -decalage)

La fonction auto_dechiffre prend en paramètre une chaîne chiffrée et calcule le décalage qui permet de la faire coïncider au mieux avec les fréquences moyennes en Français, puis, elle applique ce décalage et renvoie le résultat :

>>> s = "CLULG CVBZ KVUJ S'VLPS LAPUJLSSL, WVBY LUALUKYL BUL OPZAVPYL LUJVYL"
>>> auto_dechiffre(s)
"VENEZ VOUS DONC L'OEIL ETINCELLE, POUR ENTENDRE UNE HISTOIRE ENCORE"