Aller au contenu

50 problèmes en Python

Adapté en français et en Python (NSI / prépa ITC) à partir des « Ninety-Nine Prolog Problems » (P-99) de Werner Hett.

Étoiles de difficulté : (*) facile, (**) intermédiaire, (***) difficile.

??? Info +"Conventions"

Text Only
1
2
3
4
5
6
- Les listes sont des `list` Python. Les exemples utilisent des chaînes d'un caractère ou des entiers.
- Dans les énoncés, les **positions comptent à partir de 1** (comme dans l'original). À vous de convertir vers les indices Python (qui commencent à 0).
- Sauf mention contraire, **la liste d'entrée ne doit pas être modifiée** : on renvoie une nouvelle liste.
- Quand l'énoncé interdit une fonction (ex. `len`, `reversed`, le découpage `l[i:j]`…), respectez la consigne : c'est l'objet de l'exercice.
- Vous pouvez écrire chaque fonction en version **itérative** puis en version **récursive**, et comparer.
- Ajoutez des tests (`assert`) pour chaque fonction, y compris pour les cas limites (liste vide, un seul élément…).

Listes⚓︎

??? Info +"P01 (*) Dernier élément d'une liste"

Text Only
1
2
3
4
5
6
Écrire `mon_dernier(l)` qui renvoie le dernier élément de la liste `l`.

```python
>>> mon_dernier(['a', 'b', 'c', 'd'])
'd'
```

P02 (*) Avant-dernier élément d'une liste⚓︎

Écrire avant_dernier(l) qui renvoie l'avant-dernier élément de l.

P03 (*) K-ième élément d'une liste⚓︎

Écrire element_en(l, k) qui renvoie le k-ième élément de l. Le premier élément porte le numéro 1.

Python
>>> element_en(['a', 'b', 'c', 'd', 'e'], 3)
'c'

P04 (*) Nombre d'éléments d'une liste⚓︎

Écrire longueur(l) qui renvoie le nombre d'éléments de l, sans utiliser len.

P05 (*) Inverser une liste⚓︎

Écrire inverse(l) qui renvoie une nouvelle liste contenant les éléments de l dans l'ordre inverse, sans utiliser reversed, reverse() ni l[::-1].

P06 (*) Palindrome⚓︎

Écrire est_palindrome(l) qui indique si la liste l est un palindrome, c'est-à-dire si elle se lit de la même façon dans les deux sens, par exemple ['x', 'a', 'm', 'a', 'x'].

P07 (**) Aplatir une liste imbriquée⚓︎

Une liste peut contenir d'autres listes comme éléments. Écrire aplatir(l) qui renvoie la liste « plate » obtenue en remplaçant (récursivement) chaque sous-liste par ses éléments.

Python
>>> aplatir(['a', ['b', ['c', 'd'], 'e']])
['a', 'b', 'c', 'd', 'e']

Indice : isinstance(x, list) permet de tester si x est une liste.

P08 (**) Supprimer les doublons consécutifs⚓︎

Si une liste contient des éléments répétés consécutivement, les remplacer par un seul exemplaire. L'ordre ne doit pas être modifié. Écrire compresse(l).

Python
>>> compresse(['a','a','a','a','b','c','c','a','a','d','e','e','e','e'])
['a', 'b', 'c', 'a', 'd', 'e']

P09 (**) Regrouper les doublons consécutifs en sous-listes⚓︎

Écrire regroupe(l) qui place les éléments identiques consécutifs dans des sous-listes distinctes.

Python
>>> regroupe(['a','a','a','a','b','c','c','a','a','d','e','e','e','e'])
[['a','a','a','a'], ['b'], ['c','c'], ['a','a'], ['d'], ['e','e','e','e']]

P10 (*) Codage par plages (run-length encoding, RLE)⚓︎

En utilisant le résultat du problème P09, écrire encode(l) qui réalise la compression RLE : les doublons consécutifs sont codés par des couples [n, e] où n est le nombre de répétitions de l'élément e.

Python
>>> encode(['a','a','a','a','b','c','c','a','a','d','e','e','e','e'])
[[4,'a'], [1,'b'], [2,'c'], [2,'a'], [1,'d'], [4,'e']]

P11 (*) Codage par plages modifié⚓︎

Modifier le résultat de P10 : si un élément n'a pas de doublon, on le recopie tel quel dans la liste résultat. Seuls les éléments répétés sont codés par [n, e]. Écrire encode_modifie(l).

Python
>>> encode_modifie(['a','a','a','a','b','c','c','a','a','d','e','e','e','e'])
[[4,'a'], 'b', [2,'c'], [2,'a'], 'd', [4,'e']]

P12 (**) Décoder une liste codée par plages⚓︎

Étant donnée une liste codée comme à la question P11, écrire decode(l) qui reconstruit la liste non compressée.

P13 (**) Codage par plages (solution directe)⚓︎

Implémenter directement la compression RLE : sans créer explicitement les sous-listes de doublons comme en P09, mais en comptant seulement les répétitions. Comme en P11, un élément seul est simplement recopié (et non pas [1, x]). Écrire encode_direct(l).

Python
>>> encode_direct(['a','a','a','a','b','c','c','a','a','d','e','e','e','e'])
[[4,'a'], 'b', [2,'c'], [2,'a'], 'd', [4,'e']]

P14 (*) Dupliquer les éléments d'une liste⚓︎

Écrire dupli(l) qui duplique chaque élément de l.

Python
>>> dupli(['a','b','c','c','d'])
['a','a','b','b','c','c','c','c','d','d']

P15 (**) Dupliquer les éléments un nombre donné de fois⚓︎

Écrire dupli_n(l, n) qui répète chaque élément de l exactement n fois.

Python
>>> dupli_n(['a','b','c'], 3)
['a','a','a','b','b','b','c','c','c']

Question : que se passe-t-il pour n = 0 ? Pour n négatif ? Faites un choix et justifiez-le.

P16 (**) Supprimer un élément sur N⚓︎

Écrire supprime_tous_les(l, n) qui supprime chaque n-ième élément de l.

Python
>>> supprime_tous_les(['a','b','c','d','e','f','g','h','i','k'], 3)
['a','b','d','e','g','h','k']

P17 (*) Couper une liste en deux⚓︎

Écrire coupe(l, n) qui renvoie un couple de listes (l1, l2) où l1 contient les n premiers éléments de l. N'utilisez pas le découpage l[i:j] ni de fonction toute faite : parcourez la liste.

Python
>>> coupe(['a','b','c','d','e','f','g','h','i','k'], 3)
(['a','b','c'], ['d','e','f','g','h','i','k'])

P18 (**) Extraire une tranche d'une liste⚓︎

Étant donnés deux indices i et k, la tranche est la liste des éléments compris entre le i-ième et le k-ième élément de la liste d'origine (bornes incluses). On compte à partir de 1. Écrire tranche(l, i, k).

Python
>>> tranche(['a','b','c','d','e','f','g','h','i','k'], 3, 7)
['c', 'd', 'e', 'f', 'g']

P19 (**) Rotation d'une liste de N places vers la gauche⚓︎

Écrire rotation(l, n).

Python
1
2
3
4
>>> rotation(['a','b','c','d','e','f','g','h'], 3)
['d','e','f','g','h','a','b','c']
>>> rotation(['a','b','c','d','e','f','g','h'], -2)
['g','h','a','b','c','d','e','f']

Indice : utilisez la longueur de la liste, l'opérateur % et le résultat de P17.

P20 (*) Retirer le K-ième élément d'une liste⚓︎

Écrire retire_en(l, k) qui renvoie un couple (x, r) où x est le k-ième élément de l et r la liste restante.

Python
>>> retire_en(['a','b','c','d'], 2)
('b', ['a','c','d'])

P21 (*) Insérer un élément à une position donnée⚓︎

Écrire insere_en(x, l, k) qui insère x à la position k dans l.

Python
>>> insere_en('alfa', ['a','b','c','d'], 2)
['a', 'alfa', 'b', 'c', 'd']

P22 (*) Liste d'entiers dans un intervalle⚓︎

Écrire intervalle(a, b) qui renvoie la liste de tous les entiers de a à b inclus. N'utilisez pas range pour construire directement le résultat final (vous pouvez le faire avec une boucle ou récursivement).

Python
>>> intervalle(4, 9)
[4, 5, 6, 7, 8, 9]

P23 (**) Extraire des éléments tirés au hasard⚓︎

Écrire tirage(l, n) qui renvoie une liste de n éléments de l choisis au hasard, sans remise (on ne tire pas deux fois le même élément).

Python
>>> tirage(['a','b','c','d','e','f','g','h'], 3)
['e', 'd', 'a']    # exemple : le résultat varie

Indice : module random (random.randrange) et le résultat de P20.

P24 (*) Loto : tirer N numéros différents parmi 1..M⚓︎

Écrire loto(n, m) qui renvoie une liste de n entiers distincts tirés au hasard dans {1, ..., m}.

Python
>>> loto(6, 49)
[23, 1, 17, 33, 21, 37]    # exemple

Indice : combinez les solutions de P22 et P23.

P25 (*) Permutation aléatoire⚓︎

Écrire permutation_aleatoire(l) qui renvoie une permutation aléatoire des éléments de l (sans utiliser random.shuffle).

Python
>>> permutation_aleatoire(['a','b','c','d','e','f'])
['b', 'a', 'd', 'c', 'e', 'f']    # exemple

Indice : utilisez la solution de P23.

P26 (**) Combinaisons de K objets parmi N⚓︎

De combien de façons peut-on choisir un comité de 3 personnes dans un groupe de 12 ? On sait qu'il y a C(12, 3) = 220 possibilités (C(n, k) désigne les coefficients binomiaux). Mais ici, on veut réellement générer toutes les possibilités.

Écrire un générateur combinaisons(k, l) (avec yield) qui produit toutes les combinaisons de k éléments pris dans l, sans tenir compte de l'ordre.

Python
>>> list(combinaisons(3, ['a','b','c','d','e','f']))
[['a','b','c'], ['a','b','d'], ['a','b','e'], ...]

Vérifiez que le nombre de combinaisons produites est bien C(n, k). N'utilisez pas itertools.

P27 (**) Partitionner un ensemble en sous-groupes disjoints⚓︎

a) De combien de façons un groupe de 9 personnes peut-il se répartir en 3 sous-groupes disjoints de 2, 3 et 4 personnes ? Écrire un générateur groupes3(l) qui produit toutes les possibilités.

Python
>>> next(groupes3(['aldo','beat','carla','david','evi','flip','gary','hugo','ida']))
(['aldo','beat'], ['carla','david','evi'], ['flip','gary','hugo','ida'])

b) Généraliser : écrire un générateur groupes(l, tailles) où tailles est une liste de tailles de groupes ; chaque résultat est une liste de groupes.

Python
>>> next(groupes(['aldo','beat','carla','david','evi','flip','gary','hugo','ida'], [2, 2, 5]))
[['aldo','beat'], ['carla','david'], ['evi','flip','gary','hugo','ida']]

On ne veut pas de permutations à l'intérieur d'un groupe : [['aldo','beat'], ...] et [['beat','aldo'], ...] sont la même solution. En revanche, [['aldo','beat'], ['carla','david'], ...] et [['carla','david'], ['aldo','beat'], ...] sont deux solutions différentes.

Pour aller plus loin : cherchez le terme « coefficients multinomiaux » pour compter les solutions.

P28 (**) Trier une liste de listes⚓︎

a) On suppose que l est une liste dont les éléments sont eux-mêmes des listes. Écrire tri_longueur(l) qui trie ces éléments selon leur longueur (les plus courtes d'abord).

Python
>>> tri_longueur([['a','b','c'],['d','e'],['f','g','h'],['d','e'],['i','j','k','l'],['m','n'],['o']])
[['o'], ['d','e'], ['d','e'], ['m','n'], ['a','b','c'], ['f','g','h'], ['i','j','k','l']]

b) Même contexte, mais on trie cette fois selon la fréquence de la longueur : les listes dont la longueur est rare passent en premier, celles dont la longueur est fréquente viennent ensuite. Écrire tri_frequence_longueur(l).

Python
>>> tri_frequence_longueur([['a','b','c'],['d','e'],['f','g','h'],['d','e'],['i','j','k','l'],['m','n'],['o']])
[['i','j','k','l'], ['o'], ['a','b','c'], ['f','g','h'], ['d','e'], ['d','e'], ['m','n']]

Dans cet exemple, les deux premières listes ont pour longueurs 4 et 1, et chacune de ces longueurs n'apparaît qu'une fois. Les troisième et quatrième listes ont pour longueur 3, qui apparaît deux fois. Enfin, les trois dernières listes ont pour longueur 2, la longueur la plus fréquente.

Indice : on peut utiliser un dictionnaire pour compter les fréquences, et l'argument key de sorted.


Arithmétique⚓︎

P31 (**) Nombre premier⚓︎

Écrire est_premier(n) qui indique si l'entier n est premier.

Python
>>> est_premier(7)
True

P32 (**) Plus grand commun diviseur⚓︎

Écrire pgcd(a, b) qui renvoie le PGCD de deux entiers strictement positifs, en utilisant l'algorithme d'Euclide.

Python
>>> pgcd(36, 63)
9

P33 (*) Nombres premiers entre eux⚓︎

Deux nombres sont premiers entre eux si leur PGCD vaut 1. Écrire premiers_entre_eux(a, b).

Python
>>> premiers_entre_eux(35, 64)
True

P34 (**) Indicatrice d'Euler φ(m)⚓︎

L'indicatrice d'Euler φ(m) est le nombre d'entiers r tels que 1 <= r < m qui sont premiers avec m.

Exemple : pour m = 10, les valeurs de r sont 1, 3, 7, 9, donc φ(10) = 4. Cas particulier : φ(1) = 1.

Python
>>> phi(10)
4

Que vaut φ(m) quand m est premier ? L'indicatrice d'Euler joue un rôle important dans l'un des systèmes de cryptographie à clé publique les plus utilisés (RSA). Ici, utilisez la méthode la plus naïve (il existe des méthodes plus efficaces, voir P37).

P35 (**) Décomposition en facteurs premiers⚓︎

Écrire facteurs_premiers(n) qui renvoie la liste (plate) des facteurs premiers de n dans l'ordre croissant.

Python
>>> facteurs_premiers(315)
[3, 3, 5, 7]

P36 (**) Décomposition en facteurs premiers (2)⚓︎

Écrire facteurs_premiers_mult(n) qui renvoie la liste des facteurs premiers avec leur multiplicité.

Python
>>> facteurs_premiers_mult(315)
[[3, 2], [5, 1], [7, 1]]

Indice : le problème est similaire à P13 (et à P10).

P37 (**) Indicatrice d'Euler (version améliorée)⚓︎

Si la liste des facteurs premiers de m est connue sous la forme de P36, φ(m) se calcule efficacement. Soit [[p1, m1], [p2, m2], [p3, m3], ...] cette liste, alors :

φ(m) = (p1 − 1) · p1^(m1 − 1) · (p2 − 1) · p2^(m2 − 1) · (p3 − 1) · p3^(m3 − 1) · …

Écrire phi_ameliore(m).

P38 (*) Comparer les deux méthodes de calcul de φ⚓︎

Comparer les algorithmes de P34 et P37. Prenez comme mesure d'efficacité le temps d'exécution (module time ou timeit) et/ou un compteur d'opérations que vous ajoutez vous-même au code. Essayez avec φ(10090), puis avec des nombres de plus en plus grands.

P39 (*) Liste de nombres premiers⚓︎

Étant donné un intervalle d'entiers par ses bornes inférieure et supérieure, écrire premiers_entre(a, b) qui renvoie la liste de tous les nombres premiers de cet intervalle.

Pour aller plus loin : comparez avec le crible d'Ératosthène.

P40 (**) Conjecture de Goldbach⚓︎

La conjecture de Goldbach affirme que tout entier pair strictement supérieur à 2 est la somme de deux nombres premiers. Exemple : 28 = 5 + 23. C'est l'un des faits les plus célèbres de la théorie des nombres qui n'a pas été démontré dans le cas général ; il a été vérifié numériquement jusqu'à des valeurs très grandes. Écrire goldbach(n) qui renvoie deux nombres premiers dont la somme est l'entier pair n.

Python
>>> goldbach(28)
(5, 23)

P41 (**) Liste de décompositions de Goldbach⚓︎

Étant donné un intervalle d'entiers par ses bornes, écrire goldbach_liste(a, b) qui affiche tous les nombres pairs de l'intervalle avec leur décomposition de Goldbach.

Python
1
2
3
4
5
6
7
>>> goldbach_liste(9, 20)
10 = 3 + 7
12 = 5 + 7
14 = 3 + 11
16 = 3 + 13
18 = 5 + 13
20 = 3 + 17

Dans la plupart des cas, si un nombre pair s'écrit comme somme de deux nombres premiers, l'un d'eux est très petit. Il est très rare que les deux nombres premiers soient tous deux supérieurs à, disons, 50. Cherchez combien il y a de tels cas dans l'intervalle 2..3000.

Exemple (pour une limite d'affichage de 50) :

Python
1
2
3
4
5
>>> goldbach_liste(1, 2000, 50)
992 = 73 + 919
1382 = 61 + 1321
1856 = 67 + 1789
1928 = 61 + 1867

Logique et codes⚓︎

P46 (**) Tables de vérité d'expressions logiques⚓︎

Définir les fonctions et_(a, b), ou_(a, b), non_et(a, b), non_ou(a, b), xor_(a, b), impl(a, b) et equ(a, b) (équivalence logique) qui prennent et renvoient des booléens (True / False).

Une expression logique à deux variables peut alors s'écrire sous forme de fonction, par exemple :

Python
lambda a, b: et_(ou_(a, b), non_et(a, b))

Écrire ensuite une fonction table(f) qui affiche la table de vérité d'une fonction logique f à deux variables.

Python
1
2
3
4
5
>>> table(lambda a, b: et_(a, ou_(a, b)))
True  True  True
True  False True
False True  False
False False False

P47 (*) Tables de vérité d'expressions logiques (2)⚓︎

Continuer P46 en permettant d'écrire les expressions de façon plus naturelle, avec des opérateurs. En Python, on ne peut pas redéfinir and, or et not, mais on peut surcharger &, |, ^ et ~ en créant une classe, par exemple Bool, avec les méthodes spéciales __and__, __or__, __xor__ et __invert__. On peut aussi définir impl et equ avec d'autres opérateurs, par exemple >> (__rshift__) et == (__eq__).

Attention aux priorités des opérateurs en Python : ~ > & > ^ > |. Vérifiez qu'elles correspondent à ce que vous voulez, et ajoutez des parenthèses si besoin.

Python
1
2
3
4
5
>>> table(lambda a, b: a & (a | ~b))
True  True  True
True  False True
False True  False
False False False

P48 (**) Tables de vérité d'expressions logiques (3)⚓︎

Généraliser P47 pour que l'expression puisse contenir un nombre quelconque de variables. Écrire table(n, f) qui affiche la table de vérité d'une fonction f à n variables booléennes (toutes les combinaisons, dans l'ordre True avant False).

Python
1
2
3
4
5
6
7
8
9
>>> table(3, lambda a, b, c: equ(a & (b | c), (a & b) | (a & c)))
True  True  True  True
True  True  False True
True  False True  True
True  False False True
False True  True  True
False True  False True
False False True  True
False False False True

Indice : pensez à la récursivité, ou à itertools.product si vous l'autorisez, ou encore à compter en binaire de 0 à 2ⁿ − 1.

P49 (**) Code de Gray⚓︎

Un code de Gray à n bits est une suite de chaînes de n bits construite selon certaines règles. Par exemple :

  • n = 1 : C(1) = ['0', '1']
  • n = 2 : C(2) = ['00', '01', '11', '10']
  • n = 3 : C(3) = ['000', '001', '011', '010', '110', '111', '101', '100']

Trouver les règles de construction et écrire une fonction gray(n) qui renvoie la liste du code de Gray à n bits.

Pouvez-vous appliquer la méthode de mémoïsation (cache des résultats) pour rendre la fonction plus efficace quand elle est utilisée de façon répétée ? (Voir dict ou functools.lru_cache.)

P50 (***) Code de Huffman⚓︎

Commencez par vous documenter sur le codage de Huffman dans un bon cours d'algorithmique ou de mathématiques discrètes.

On suppose donné un ensemble de symboles avec leurs fréquences, sous la forme d'une liste de couples (symbole, frequence), par exemple :

Python
[('a', 45), ('b', 13), ('c', 12), ('d', 16), ('e', 9), ('f', 5)]

L'objectif est de construire un dictionnaire (ou une liste de couples) associant à chaque symbole son mot de code de Huffman. Pour cet exemple, un résultat possible est :

Python
{'a': '0', 'b': '101', 'c': '100', 'd': '111', 'e': '1101', 'f': '1100'}

(d'autres codes équivalents sont possibles, par exemple 'a': '01', etc., selon les choix faits quand deux fréquences sont égales).

La fonction huffman(frequences) doit renvoyer la table de codage correspondant à la table des fréquences donnée.

Indices : file de priorité (heapq), arbres binaires (tuples ou classe Noeud), parcours récursif de l'arbre pour construire les codes.