Exercices d'entraînement☘

Prenez l'habitude de revenir vous entraîner régulièrement avec ces exercices tout au long de l'année. Ils sont généralement accompagnés de pistes et de leur solution pour vous permettre de progresser.

Avant de vous précipiter sur ces solutions dès la première difficulté, n'oubliez pas les conseils suivants :

Avez-vous bien fait un schéma au brouillon pour visualiser le problème posé ?
Avez-vous essayé de rédiger un algorithme en français, avec vos propres mots, avant de vous lancer dans la programmation sur machine ?
Avez-vous utilisé des affichages intermédiaires, des print(), pour visualiser au fur et à mesure le contenu des variables ?
Avez-vous testé le programme avec les propositions de tests donnés dans l'exercice ?
Avez-vous testé le programme avec de nouveaux tests, différents de ceux proposés ?

Rappels

Chaque programme Python doit être sauvegardé sous forme de fichier texte avec l'extension .py.
Enregistrez ce fichier dans le dossier [E01-Diviser_Regner] avec le nom donné à l'exercice : ProgE01.51.py, ProgE01.52.py, etc...
Pour exécuter ce programme, il suffit de le sauvegarder puis d'appuyer sur la touche [F5].

Le programme principal doit contenir un appel au module doctest :

##----- Programme principal et tests -----##
if __name__ == '__main__':
    import doctest
    doctest.testmod()

ProgE01.51 - Exponentiation rapide☘

$a$ et $n$ étant des entiers, on souhaite calculer l'expression $a^n$ de la manière la plus efficace possible (sans utiliser l'opérateur « ** » de Python).

Copiez/collez et complétez le corps de la fonction expo() avec une boucle for.

def expo(a, n):
    """
    a, n – int, entier strictement positif
    Sortie: int – a^n
    >>> expo(10, 5)
    100000
    >>> expo(2, 8)
    256
    """

Une solution imperative

def expo(a, n):
    """
    a, n – int, entier strictement positif
    Sortie: int – a^n
    >>> expo(10, 5)
    100000
    >>> expo(2, 8)
    256
    """
    result = 1
    for i in range(n):
        result = result*a
    return result

Une solution récursive

def expoRec(a, n):
    """
    a, n – int, entier strictement positif
    Sortie: int – a^n
    >>> expoRec(10, 5)
    100000
    >>> expoRec(2, 8)
    256
    """
    if n<=1:
        return a
    else:
        return a*expoRec(a, n-1)

Déterminez sur le cahier la complexité de cette fonction.

Une solution
Dans la solution impérative, les opérations sont élémentaires.
Seule la boucle for parcourue n fois est à prendre en compte.
Par conséquent, la complexité de cette fonction est en $O(n)$ .

Copiez/collez et complétez le corps de la fonction expoRapide() en utilisant la propriété suivante :

$a^n = (a^2)^{\frac{n}{2}}$ si $n$ est pair ;
$a^n = a \times a^{n-1}$ si $n$ est impair.

def expoRapide(a, n):
    """
    a, n – int, entier strictement positif
    Sortie: int – a^n
    >>> expoRapide(10, 5)
    100000
    >>> expoRapide(2, 8)
    256
    """

Une solution récursive

def expoRapideRec(a, n):
    """
    a, n – int, entier strictement positif
    Sortie: int – a^n
    >>> expoRapideRec(10, 5)
    100000
    >>> expoRapideRec(2, 8)
    256
    """
    if n==0:
        return 1
    elif n==1:
        return a
    elif n%2==0:
        return expoRapideRec(a*a, n//2)
    else:
        return a*expoRapideRec(a, n-1)

Une solution imperative

Plus compliquée à programmer, cette solution nécessite de réaliser quelques exemples « à la main » pour être comprise : $a^{15} = a \times \left(a \times \left( a\times a^2 \right)^2 \right)^2$

def expoRapide(a, n):
    """
    a, n – int, entier strictement positif
    Sortie: int – a^n
    >>> expoRapide(10, 5)
    100000
    >>> expoRapide(2, 8)
    256
    """
    result = 1
    temp = a
    while n > 0:
        if n%2 == 1:
            result = result * temp
            n = n-1
        else:
            temp = temp*temp
            n = n//2
    return result

Déterminez sur le cahier la complexité de cette fonction.

Une solution
Voici une argumentation possible (peu rigoureuse).

Dans la solution récursive, effectuer un appel à expoRapideRec(n) conduit à effectuer un appel à expoRapideRec(n//2) puisque si $n$ est impair, $n-1$ sera pair.
Par conséquent, en moyenne, le nombre d'appels à expoRapideRec() sera blog(n).
Par conséquent, la complexité de cette fonction est en $O(log(n))$ , soit meilleure que celle de la programmation « naïve ».

ProgE01.52 - Trancher un tableau☘

Cet exercice ne nécessite pas de programmer un algorithme de type « diviser pour régner ». La fonction demandée sera par contre très utile dans les autres exercices de ce chapitre...

Copiez/collez et complétez le corps de la fonction tranche() en respectant ses spécifications.

def tranche(tab, i, j):
    """
    tab – list, un tableau
    i, j - int, entiers positifs tels que 0 <= i <= j <= len(tab)
    Sortie: list – tableau contenant les éléments de tab situés entre les
                   indices i (inclus) et j (exclus)
    >>> tranche([1, 2, 4, 8, 16, 32], 2, 5)
    [4, 8, 16]
    >>> tranche([1, 2, 4, 8, 16, 32], 4, 6)
    [16, 32]
    >>> tranche([1, 2, 4, 8, 16, 32], 4, 4)
    []
    >>> tranche([1, 2, 4, 8, 16, 32], 4, 5)
    [16]
    """

Attention, les appels ci-dessous doivent renvoyer une erreur :

>>> tranche([1, 2, 4, 8, 16, 32], 5, 2)
AssertionError: Les indices i et j ne conviennent pas

>>> tranche([1, 2, 4, 8, 16, 32], 4, 12)
AssertionError: Les indices i et j ne conviennent pas

Une solution

def tranche(tab, i, j):
    """
    tab – list, un tableau
    i, j - int, entiers positifs tels que 0 <= i <= j <= len(tab)
    Sortie: list – tableau contenant les éléments de tab situés entre les
                   indices i (inclus) et j (exclus)
    >>> tranche([1, 2, 4, 8, 16, 32], 2, 5)
    [4, 8, 16]
    >>> tranche([1, 2, 4, 8, 16, 32], 4, 6)
    [16, 32]
    >>> tranche([1, 2, 4, 8, 16, 32], 4, 4)
    []
    >>> tranche([1, 2, 4, 8, 16, 32], 4, 5)
    [16]
    """
    assert 0 <= i <= j <= len(tab), "Les indices i et j ne conviennent pas"
    result = []
    for k in range(i, j):
        result.append(tab[k])
    return result

Une autre solution

En utilisant une définition par compréhension :

def tranche(tab, i, j):
    """
    tab – list, un tableau
    i, j - int, entiers positifs tels que 0 <= i <= j <= len(tab)
    Sortie: list – tableau contenant les éléments de tab situés entre les
                   indices i (inclus) et j (exclus)
    >>> tranche([1, 2, 4, 8, 16, 32], 2, 5)
    [4, 8, 16]
    >>> tranche([1, 2, 4, 8, 16, 32], 4, 6)
    [16, 32]
    >>> tranche([1, 2, 4, 8, 16, 32], 4, 4)
    []
    >>> tranche([1, 2, 4, 8, 16, 32], 4, 5)
    [16]
    """
    assert 0 <= i <= j <= len(tab), "Les indices i et j ne conviennent pas"
    return [tab[k] for k in range(i, j)]

ProgE01.53 - Recherche du maximum☘

Copiez/collez et complétez le corps de la fonction maximumDpR() en respectant ses spécifications. L'idée est d'utiliser un algorithme récursif de type « diviser pour régner » afin de rechercher le plus grand élément d'un tableau non trié.
Vous pouvez utiliser la fonction max() telle que l'appel max(a, b) renvoie la plus grande valeur entre celle de a et celle de b.

def maximumDpR(tab):
    """
    tab – list, un tableau NON VIDE d'entiers (ou d'éléments comparables)
    Sortie: int – le plus grand élément de tab, obtenu avec un algorithme
                  de type "diviser pour régner"
    >>> maximumDpR([1, 2, 4, 8, 16, 32])
    32
    >>> maximumDpR([1, 2, 4, 8, 16, 32, 4, 6])
    32
    """

Une piste

N'hésitez pas à utiliser la fonction tranche().

Un algorithme

Partager la liste en deux sous-listes ;
Chercher le maximum de chaque sous liste ;
Renvoyer le plus grand élément entre ces deux maximum.

Une solution

def maximumDpR(tab):
    """
    tab – list, un tableau NON VIDE d'entiers (ou d'éléments comparables)
    Sortie: int – le plus grand élément de tab, obtenu avec un algorithme
                  de type "diviser pour régner"
    >>> maximumDpR([1, 2, 4, 8, 16, 32])
    32
    >>> maximumDpR([1, 2, 4, 8, 16, 32, 4, 6])
    32
    """
    assert len(tab) >= 1, "Le tableau ne doit pas être vide"
    if len(tab) == 1 :
        return tab[0]
    else:
        milieu = len(tab) // 2
        tab_gauche = tranche(tab, 0, milieu)
        tab_droite = tranche(tab, milieu, len(tab))

        max_gauche = maximumDpR(tab_gauche)
        max_droite = maximumDpR(tab_droite)
        return max(max_gauche, max_droite)

Par rapport à la méthode usuelle de recherche du maximum, la complexité a-t-elle été améliorée ?
Répondre sur le cahier avant de consulter la solution.
Une solution
1. La création des sous-tableaux gauche et droite nécessitent $n$ opérations ;
2. Les deux appels récursifs à maximumDpR() s'effectuent sur des tableaux de taille divisée par 2
La relation de récurrence résultante, pour une taille $n$ de tableau, est donc $T(n) = 2 T(n/2) + n$ . Cette relation conduit a une complexité en $O(n log(n))$ , ce qui est plus coûteux que la recherche usuelle en $O(n)$ .

ProgE01.54 - Minimum et maximum☘

Copiez/collez et complétez le corps de la fonction mini_maxiDpR() en respectant ses spécifications. L'idée est d'utiliser un algorithme récursif de type « diviser pour régner » afin de rechercher en même temps le plus grand et le plus petit élément d'un tableau non trié.
Vous pouvez utiliser les fonctions min() et max() qui renvoient respectivement le plus petit et le plus grand élément entre deux valeurs a et b.

def mini_maxiDpR(tab):
    """
    tab – list, un tableau NON VIDE d'entiers (ou d'éléments comparables)
    Sortie: tuple – couple constitué du plus petit élément et du plus grand élément
                    de tab, obtenus avec un algorithme de type "diviser pour régner"
    >>> mini_maxiDpR([1, 2, 4, 8, 16, 32])
    (1, 32)
    >>> mini_maxiDpR([1, 2, 4, 8, 16, 32, 0, 6])
    (0, 32)
    """

Une piste

N'hésitez pas à utiliser la fonction tranche().

Une autre piste

Il y a deux cas de base :

pour des tableaux de taille 1 ;
pour des tableaux de taille 2.

Une solution

def mini_maxiDpR(tab):
    """
    tab – list, un tableau NON VIDE d'entiers (ou d'éléments comparables)
    Sortie: tuple – couple constitué du plus petit élément et du plus grand élément
                    de tab, obtenus avec un algorithme de type "diviser pour régner"
    >>> mini_maxiDpR([1, 2, 4, 8, 16, 32])
    (1, 32)
    >>> mini_maxiDpR([1, 2, 4, 8, 16, 32, 0, 6])
    (0, 32)
    """
    assert len(tab) >= 1, "Le tableau ne doit pas être vide"
    if len(tab) == 1 :
        return (tab[0], tab[0])
    elif len(tab) == 2 :
        if tab[0] < tab[1]:
            return (tab[0], tab[1])
        else:
            return (tab[1], tab[0])
    else:
        milieu = len(tab) // 2
        tab_gauche = tranche(tab, 0, milieu)
        tab_droite = tranche(tab, milieu, len(tab))

        min_gauche, max_gauche = mini_maxiDpR(tab_gauche)
        min_droite, max_droite = mini_maxiDpR(tab_droite)
        return min(min_gauche, min_droite), max(max_gauche, max_droite)

ProgE01.55 - Multiplication de grands nombres☘

Pour multiplier deux nombres entiers de $n$ chiffres, une méthode naïve consiste à multiplier chaque chiffre du premier nombre par chaque chiffre du second puis d'effectuer les bons décalages et les bonnes sommes.
Le temps de calcul est alors en $O(n^2)$ .

L’algorithme de Karatsuba utilise le principe suivant :

Le premier nombre peut s'écrire sous la forme $a × 10^k + b$ et le second peut s'écrire sous la forme $c × 10^k + d$ .
Leur produit peut donc s'écrire $(a × 10^k + b)(c × 10^k + d) = ac × 10^{2k} + (ad + bc) × 10^k + bd$ .
Ce calcul, qui nécessite quatre produits ( $ac$ , $ad$ , $bc$ et $bd$ ), peut être effectué avec seulement trois produits en regroupant les expressions sous la forme suivante :

$(a × 10^k + b)(c × 10^k + d) = ac × 10^{2k} + (ac + bd − (a − b)(c − d)) × 10^k + bd$

Des soustractions ont effectivement été introduites, mais seulement trois produits de grands nombres sont maintenant nécessaires : $ac$ , $bd$ et $(a − b)(c − d)$ .

Comme les additions et les soustractions sont peu coûteuses (négligeables par rapport aux multiplications), nous allons gagner en temps de calcul.

Remarque

La multiplication par une puissance de la base de calcul correspond à un décalage de chiffre et est donc très rapide à exécuter sur une machine.

Copiez/collez et complétez le corps de la fonction karatsuba() permettant de multiplier deux grands nombres entiers de $n$ chiffres selon ce principe.

def karatsuba(x, y):
    """
    x, y – int, deux entiers ayant le même nombre de chiffres
    Sortie: int – le produit x*y calculé en utilisant l'algorithme de Karatsuba
    >>> karatsuba(112, 24)
    2688
    >>> karatsuba(3, 2)
    6
    """

Une piste

Calculez $a$ , $b$ , $c$ et $d$ avant d'appliquer l'algorithme.

Une solution

def karatsuba(x, y):
    """
    x, y – int, deux entiers ayant le même nombre de chiffres
    Sortie: int – le produit x*y calculé en utilisant l'algorithme de Karatsuba
    >>> karatsuba(112, 24)
    2688
    >>> karatsuba(3, 2)
    6
    """
    if len(str(x)) == 1 or len(str(y)) == 1 :
        return x * y               # En supposant qu’on accepte la multiplication
                                   # d’un grand nombre avec un chiffre
    n = max(len(str(x)), len(str(y)))
    nDiv2 = n // 2

    a = x // (10**nDiv2)
    b = x % (10**nDiv2)
    c = y // (10**nDiv2)
    d = y % (10**nDiv2)

    ac = karatsuba(a, c)
    bd = karatsuba(b, d)
    ad_plus_bc = ac + bd - karatsuba(a-b, c-d)

    return ac * 10**(2*nDiv2) + (ad_plus_bc * 10**nDiv2) + bd




##----- Programme principal et tests -----##
if __name__ == '__main__':
    # On augmente la taille de la pile d'appels récursifs
    import sys
    sys.setrecursionlimit(10000)

    import doctest
    doctest.testmod()

Justifier que cette fonction applique le paradigme du diviser pour régner.
L’algorithme vous semble-t-il optimal ?

Une solution
Pour optimiser, on pourrait garder en mémoire les calculs similaires...
Nous verrons comment faire dans le cadre de la programmation dynamique.