Exercice 1

EXERCICE 1 (10 points)

Programmer une fonction renverse, prenant en paramètre une chaîne de caractères non vide mot et renvoie cette chaîne de caractères en ordre inverse.

Exemple :

>>> renverse("")
""
>>> renverse("abc")
"cba"
>>> renverse("informatique")
"euqitamrofni"

Exercice 2

EXERCICE 2 (10 points)

Un nombre premier est un nombre entier naturel qui admet exactement deux diviseurs distincts entiers et positifs : 1 et lui-même.

Le crible d’Ératosthène permet de déterminer les nombres premiers plus petit qu’un certain nombre n fixé strictement supérieur à 1.

On considère pour cela un tableau tab de n booléens (type list), initialement tous égaux à True, sauf tab[0] et tab[1] qui valent False, 0 et 1 n’étant pas des nombres premiers.

On parcourt alors ce tableau de gauche à droite et pour chaque indice i :

• si tab[i] vaut True : le nombre i est premier et on donne la valeur False à toutes les cases du tableau dont l’indice est un multiple de i, à partir de 2*i (c’est-à-dire 2*i, 3*i …).
• si tab[i] vaut False : le nombre i n’est pas premier et on n’effectue aucun changement sur le tableau.

On dispose de la fonction crible, donnée ci-dessous et à compléter, prenant en paramètre un entier n strictement supérieur à 1 et renvoyant un tableau contenant tous les nombres premiers plus petits que n.

def crible(n):
    """Renvoie un tableau contenant tous les nombres premiers
    plus petits que n."""
    premiers = []
    tab = [True] * n
    tab[0], tab[1] = False, False
    for i in range(n):
        if tab[i]:
            premiers....
            multiple = ...
            while multiple < n:
                tab[multiple] = ...
                multiple = ...
    return premiers

Exemples :

>>> crible(40)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
>>> crible(5)
[2, 3]

Les contraintes ci-dessous sont ajoutées par la plateforme et ne font pas partie du sujet.

Exercice 1

Contraintes :

• mot est une chaîne de caractères (str)
• 0 <= len(mot) <= 10^4
• la chaîne vide est acceptée : renverse("") renvoie ""
• les caractères de mot sont des caractères ASCII imprimables
• la valeur renvoyée est une chaîne de caractères (str)

Exercice 2

Contraintes :

• n est un entier (int)
• 2 <= n <= 10^5
• la valeur renvoyée est une liste d’entiers (list) contenant les nombres premiers strictement inférieurs à n, rangés dans l’ordre croissant
• pour n = 2, la liste renvoyée est vide

Solution

Exercice 1 - renverser une chaîne

L’idée. On ne peut pas modifier une chaîne de caractères en Python : on en construit donc une nouvelle, petit à petit. On part d’une chaîne vide et on parcourt mot lettre par lettre, de gauche à droite. À chaque tour, on colle la lettre lue devant ce qu’on a déjà construit. Comme chaque nouvelle lettre passe devant les précédentes, la dernière lettre du mot finit en tête : la chaîne est renversée.

Un petit exemple. Pour "abc" : on part de "", puis "a", puis "ba" (le b passe devant le a), puis "cba".

def renverse(mot):
    resultat = ""
    # Chaque nouvelle lettre est placée devant celles déjà accumulées
    for lettre in mot:
        resultat = lettre + resultat
    return resultat

resultat contient à tout moment le renversé de la partie du mot déjà lue. Quand la boucle a lu toute la chaîne, resultat est le renversé du mot entier. Si mot est la chaîne vide, la boucle ne fait aucun tour et on renvoie "" : le cas vide se règle tout seul, sans if particulier.

Remarque. Python sait aussi renverser une chaîne d’un coup avec mot[::-1], mais l’exercice demande justement de construire le résultat soi-même : c’est la boucle qui est notée.

Exercice 2 - le crible d’Ératosthène

L’idée. Plutôt que de tester si chaque nombre est premier, on barre les nombres qui ne le sont pas. Le tableau tab sert de tableau de cases à cocher : tab[i] vaut True tant que i n’a pas été barré. On parcourt les indices de gauche à droite. Quand on arrive sur un i encore à True, c’est qu’aucun nombre plus petit ne le divise : i est donc premier, on l’ajoute à premiers. Et aussitôt on barre tous ses multiples 2*i, 3*i, 4*i … : eux ont i comme diviseur, ils ne sont pas premiers.

Un petit exemple. Pour n = 10 : tab[0] et tab[1] sont déjà False. On arrive sur 2, qui est True : on garde 2 et on barre 4, 6, 8. Puis 3 est encore True : on garde 3 et on barre 6, 9. 4 est barré, on passe. 5 est True : on le garde. Etc. Il reste [2, 3, 5, 7].

def crible(n):
    """Renvoie un tableau contenant tous les nombres premiers
    plus petits que n."""
    premiers = []
    tab = [True] * n
    tab[0], tab[1] = False, False
    for i in range(n):
        if tab[i]:
            premiers.append(i)
            multiple = 2 * i
            # On barre les multiples de i : ils admettent i comme diviseur
            while multiple < n:
                tab[multiple] = False
                multiple = multiple + i
    return premiers

Les quatre trous du squelette se remplissent donc ainsi : premiers.append(i), multiple = 2 * i, tab[multiple] = False, multiple = multiple + i.

La variable multiple avance de i en i : elle vaut successivement 2*i, 3*i, 4*i … La condition multiple < n arrête la boucle avant de sortir du tableau, puisque les indices valides vont de 0 à n - 1. On part de 2*i et non de i : sinon on barrerait i lui-même, alors qu’il est premier. Comme on parcourt les indices dans l’ordre croissant et qu’on ajoute i dans premiers au moment où on le rencontre, la liste renvoyée est déjà triée.

Cas limite : pour n = 2, le tableau est [False, False], aucun indice n’est True, et on renvoie la liste vide.