Aller au contenu

Sujet n°9

Sujet original

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

Exercice n°1☘

Programmer la fonction multiplication, prenant en paramètres deux nombres entiers relatifs n1 et n2, et qui renvoie le produit de ces deux nombres.

Les seules opérations autorisées sont l’addition et la soustraction.

Exemples

>>> multiplication(3, 5)
15

>>> multiplication(-4, -8)
32

>>> multiplication(-2, 6)
-12

>>> multiplication(-2, 0)
0
Une solution

Rien n'interdit de définir des fonctions supplémentaires donc on peut définir une fonction renvoyant la valeur absolue d'un nombre.
Puis, une petite boucle devrait suffire... 

 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 multiplication(n1, n2):
    """
    n1, n2 - int, deux entiers
    Sortie: int, produit des nombres n1 et n2
    """
    signe = 1
    if n1 < 0:
        n1 = -n1
        signe = -1
    somme = 0
    for i in range(n1):
        somme += n2
    if signe == 1:
        return somme
    else:
        return -somme


if __name__ == '__main__':
    # Exemples de l'énoncé
    print(multiplication(3, 5) == 15)
    print(multiplication(-4, -8) == 32)
    print(multiplication(-2, 6) == -12)
    print(multiplication(-2, 0) == 0)

    # Exemples supplémentaires
    print(multiplication(0, 2) == 0)
    print(multiplication(0, 0) == 0)

Exercice n°2☘

Soit tab un tableau non vide d'entiers triés dans l'ordre croissant et n un entier.

La fonction chercher, donnée ci-dessous, doit renvoyer un indice où la valeur n apparaît dans tab si cette valeur y figure et None sinon.

Les paramètres de la fonction sont :

  • tab, le tableau dans lequel s'effectue la recherche ;
  • n, l'entier à chercher dans le tableau ;
  • i, l'indice de début de la partie du tableau où s'effectue la recherche ;
  • j, l'indice de fin de la partie du tableau où s'effectue la recherche.

L’algorithme demandé est une recherche dichotomique récursive.

Recopier et compléter le code de la fonction chercher suivante :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def chercher(tab, n, i, j):
    if i < 0 or j > len(tab):
        return None
    elif i > j:
        return None
    m = (i + j) // ...
    if ... < n:
        return chercher(tab, n, ..., ...)
    elif ... > n:
        return chercher(tab, n, ..., ...)
    else:
        return ...
Commentaire sur le code original

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

Exemple

L’exécution du code doit donner : 

>>> chercher([1, 5, 6, 6, 9, 12], 7, 0, 10)

>>> chercher([1, 5, 6, 6, 9, 12], 7, 0, 5)

>>> chercher([1, 5, 6, 6, 9, 12], 9, 0, 5)
4

>>> chercher([1, 5, 6, 6, 9, 12], 6, 0, 5)
2

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
def chercher(tab, n, i, j):
    if i < 0 or j > len(tab):
        return None
    elif i > j:
        return None
    m = (i + j) // 2
    if tab[m] < n:
        return chercher(tab, n, m+1, j)
    elif tab[m] > n:
        return chercher(tab, n, i, m-1)
    else:
        return m

if __name__ == '__main__':
    # Exemples de l'énoncé
    print(chercher([1, 5, 6, 6, 9, 12], 7, 0, 10) is None)
    print(chercher([1, 5, 6, 6, 9, 12], 7, 0, 5) is None)
    print(chercher([1, 5, 6, 6, 9, 12], 9, 0, 5) == 4)
    print(chercher([1, 5, 6, 6, 9, 12], 6, 0, 5) == 2)

    # Exemples supplémentaires
    print(chercher([1, 5, 6, 6, 9, 12], 1, 0, 5) == 0)
    print(chercher([1, 5, 6, 6, 9, 12, 14], 14, 0, 6) == 6)