Aller au contenu

Sujet n°19

Sujet original

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

Exercice n°1

Écrire une fonction recherche qui prend en paramètres un tableau tab de nombres entiers triés par ordre croissant et un nombre entier n, et qui effectue une recherche dichotomique du nombre entier n dans le tableau non vide tab.

Cette fonction doit renvoyer un indice correspondant au nombre cherché s’il est dans le tableau, -1 sinon.

Exemple

>>> recherche([2, 3, 4, 5, 6], 5)
3

>>> recherche([2, 3, 4, 6, 7], 5)
-1
Une solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def recherche(tab, n):
    """
    tab - list, tableau de nombres entiers triés par ordre croissant
    n - int, un entier
    Sortie: int, indice correspondant à la position de n dans tab
                 si n est présent, -1 sinon
    """
    i_debut = 0
    i_fin = len(tab)-1
    while i_debut <= i_fin:
        i_milieu = (i_debut + i_fin)//2
        if tab[i_milieu] == n:
            return i_milieu
        elif tab[i_milieu] < n:
            i_debut = i_milieu+1
        else:
            i_fin = i_milieu-1
    return -1


if __name__ == '__main__':
    # Exemples de l'énoncé
    print(recherche([2, 3, 4, 5, 6], 5) == 3)
    print(recherche([2, 3, 4, 6, 7], 5) == -1)

    # Exemples supplémentaires
    print(recherche([2, 3, 4, 4, 6, 7, 9, 10, 11, 14], 4) == 2)
    print(recherche([2, 3, 4, 4, 6, 7, 9, 10, 11, 14, 15, 16, 17, 18, 18], 4) == 3)

Exercice n°2

Le codage de César transforme un message en changeant chaque lettre en la décalant dans l’alphabet.

Par exemple, avec un décalage de 3, le A se transforme en D, le B en E, ..., le X en A, le Y en B et le Z en C. Les autres caractères (espaces ou caractères de ponctuation '!', '?', ...) ne sont pas codés.

La fonction position_alphabet ci-dessous prend en paramètre un caractère lettre et renvoie la position de lettre dans la chaîne de caractères ALPHABET s’il s’y trouve.

La fonction cesar prend en paramètre une chaîne de caractères message et un nombre entier decalage et renvoie le nouveau message codé avec le codage de César utilisant le décalage decalage.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
ALPHABET = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

def position_alphabet(lettre):
    return ord(lettre) - ord('A')

def cesar(message, decalage):
    resultat = ''
    for ... in message :
        if 'A' <= c and c <= 'Z' :
            indice = ( ... )%26
            resultat = resultat + ALPHABET[indice]
        else:
            resultat = ...
    return resultat
Commentaire sur le code original

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

Compléter la fonction cesar().

Exemple

>>> cesar('BONJOUR A TOUS. VIVE LA MATIERE NSI !', 4)
'FSRNSYV E XSYW. ZMZI PE QEXMIVI RWM !'

>>> cesar('GTSOTZW F YTZX. ANAJ QF RFYNJWJ SXN !', -5)
'BONJOUR A TOUS. VIVE LA MATIERE NSI !'
Une solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
ALPHABET = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

def position_alphabet(lettre):
    return ord(lettre) - ord('A')

def cesar(message, decalage):
    resultat = ''
    for c in message :
        if 'A' <= c and c <= 'Z' :
            indice = (decalage + position_alphabet(c))%26
            resultat = resultat + ALPHABET[indice]
        else:
            resultat = resultat + c
    return resultat


if __name__ == '__main__':
    # Exemples de l'énoncé
    message = 'BONJOUR A TOUS. VIVE LA MATIERE NSI !'
    print(cesar(message, 4) == 'FSRNSYV E XSYW. ZMZI PE QEXMIVI RWM !')

    message = 'GTSOTZW F YTZX. ANAJ QF RFYNJWJ SXN !'
    print(cesar(message, -5) == 'BONJOUR A TOUS. VIVE LA MATIERE NSI !')

    # Exemples supplémentaires
    message = 'UN TEST OU RIEN NE BOUGE'
    print(cesar(message, 26) == 'UN TEST OU RIEN NE BOUGE')

    message = 'UN TEST OU RIEN NE BOUGE'
    print(cesar(message, -52) == 'UN TEST OU RIEN NE BOUGE')