Somme des $n$ nombres d'un tableau

L’objectif de ce document est d’écrire et d’implémenter un algorithme s’appuyant sur le raisonnement « Diviser pour régner » qui permet de déterminer la somme des $n$ nombres (entiers) d’un tableau.

Écrire le code de fonction somme1 dont la spécification est :

1
2
3
4
5
6
7


def somme1(tab: List[float]) -> float:
    """
    Calcul de la somme des nombres éléments
    de tab.

    Algorithme : Récursivité enveloppée
    """

Penser à écrire un jeu de tests.

Réponse

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


def somme1(tab: List[float]) -> float:
    """
    Calcul de la somme des nombres éléments
    de tab.

    Algorithme : Récursivité enveloppée
    """
    if len(tab) == 1:
        return tab[0]

    return tab[0] + somme1(tab[1:])

if __name__ == "__main__":
    tab = [1, 2, 3, 4, 5, 6, 7]
    n = tab[len(tab) - 1]
    assert somme1(tab) == n * (n + 1) // 2

    print("Done!")

Réfléchir à un algorithme utilisant le principe « Diviser pour régner » qui résoud le même problème.
Écrire le code de la fonction somme2 qui implémente cet algorithme.
Tester cette fonction.

Réponse

 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
31


def somme2(tab: List[float]) -> float:
    """
    Calcul de la somme des nombres éléments
    de tab.

    Algorithme : Diviser pour Régner.
    """
    # Cas de base
    if len(tab) == 1:
        return tab[0]

    # Diviser
    m = len(tab) // 2

    somme_g = somme2(tab[:m])
    somme_d = somme2(tab[m:])

    # Régner
    total = somme_g + somme_d

    # Recombiner
    return total


if __name__ == "__main__":
    tab = [1, 2, 3, 4, 5, 6, 7]
    n = tab[len(tab) - 1]
    assert somme1(tab) == n * (n + 1) // 2
    assert somme2(tab) == n * (n + 1) // 2

    print("Done!")

Décrire le fonctionnement de l’algorithme pour la liste [1, 2, 3, 4, 5, 6, 7].

Réponse

 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
31
32


somme([1, 2, 3, 4, 5, 6, 7])
    somme_g = somme([1, 2, 3])
        somme_g = somme([1])
            retourne 1
        somme_d = somme([2, 3])
            somme_g = somme([2])
                retourne 2
            somme_d([3])
                retourne 3
            total = 5
            retourne 5
        total = 6
        retourne 6
    somme_d = somme([4, 5, 6, 7])
        somme_g = somme([4, 5])
            somme_g = somme([4])
                retourne 4
            somme_d = somme([5])
                retourne 5
            total = 9
            retourne 9
        somme_d = somme([6, 7])
            somme_g = somme([6])
                retourne 6
            somme_d = somme([7])
                retourne 7
            total = 13
            retourne 13
        total = 22
        retourne 22
    total = 28
    retourne 28

Diviser pour régner Récursivité

Suggestions de lecture :