Aller au contenu

Sujet n°44

Sujet original

Pour télécharger l'énoncé original, cliquer ici.

Exercice n°1☘

Programmer une fonction renverse, prenant en paramètre une chaîne de caractères non vide mot et qui renvoie une chaîne de caractères en inversant ceux de la chaîne mot.

Exemples

>>> renverse("informatique")
"euqitamrofni"
Une solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def renverse(mot):
    """
    mot - str
    Sortie: str - chaîne constituée des caractères de mot
            "écrits" dans l'ordre contraire
    """
    result = ''
    for caractere in mot:
        result = caractere + result
    return result


if __name__ == '__main__':
    print(renverse("informatique") == "euqitamrofni")
Une solution récursive
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def renverse_rec(mot):
    """
    mot - str
    Sortie: str - chaîne constituée des caractères de mot
            "écrits" dans l'ordre contraire - version récursive
    """
    if mot == '':
        return ''
    else:
        fin_mot = ''
        for i in range(1, len(mot)):
            fin_mot = fin_mot + mot[i]
        return renverse_rec(fin_mot) + mot[0]


if __name__ == '__main__':
    print(renverse_rec("informatique") == "euqitamrofni")

Exercice n°2☘

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, 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.

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, incomplète et donnée ci-dessous, prenant en paramètre un entier n strictement supérieur à 1 et renvoyant un tableau contenant tous les nombres premiers plus petits que n.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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(...)
            for multiple in range(2*i, n, ...):
                tab[multiple] = ...
    return premiers

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

Compléter le code de cette fonction.

Commentaires sur le code original

  1. Pour télécharger l'original du fichier à compléter, cliquer ici.

  2. L'exemple est proposé avec une assertion, ce qui diffère des énoncés habituels et devrait être évité par soucis d'harmonisation.

  3. Des exemples plus complets pourraient être proposés. Par exemple : 

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

Une solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
def crible(n):
    """renvoie un tableau contenant tous les nombres premiers plus petit que n"""
    premiers = []
    tab = [True] * n
    tab[0], tab[1] = False, False
    for i in range(2, n):
        if tab[i] == True:
            premiers.append(i)
            for multiple in range(2*i, n, i):
                tab[multiple] = False
    return premiers


if __name__ == '__main__':
    print(crible(40) == [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37])
    print(crible(3) == [2])
    print(crible(10) == [2, 3, 5, 7])
    print(crible(2) == [])