Aller au contenu

Algorithmes sur les tableaux

Chaque exercice est fourni avec un fichier Python à compléter et un énoncé « papier » distribué à l'élève et reproduit ci-dessous.

Remarques importantes

  1. Les exercices de cette page ne sont pas classés par ordre de « difficulté », cette notion de difficulté étant subjective et dépendante de chaque élève.

  2. Les solutions proposées ne sont que des propositions !
    Il existe d'autres codes valables pour répondre à chaque problème que ceux proposés ici : il ne faut pas hésiter à les soumettre à votre enseignant pour qu'il vous donne son avis sur les idées mises en oeuvre.

Permuter à gauche☘

Écrire le code d’une fonction permuter_a_gauche() qui prend en paramètre un tableau non vide tab. Cette fonction est à effet de bord, c'est-à-dire qu'elle ne renvoie rien mais modifie le tableau passé en paramètre en remplaçant le premier élément par le deuxième, le deuxième par le troisième, …, l'avant-dernier par le dernier et le dernier par le premier.

Exemples

>>> T = [0, 1, 0, 0, 1]
>>> permuter_a_gauche(T)
>>> T
[1, 0, 0, 1, 0]

>>> permuter_a_gauche(T)
>>> T
[0, 0, 1, 0, 1]

>>> T = []
>>> permuter_a_gauche(T)
AssertionError: Le tableau passé en argument ne doit pas être vide !

  1. Compléter la définition de la fonction permuter_a_gauche(), sans oublier d'ajouter l'assertion signalée dans l'exemple précédent.

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
    def permuter_a_gauche(tab):
    """
    tab - 
    Sortie: 
            (fonction à effet de bord)
    >>> T = [0, 1, 0, 0, 1]
    >>> permuter_a_gauche(T)
    >>> T
    [1, 0, 0, 1, 0]
    >>> permuter_a_gauche(T)
    >>> T
    [0, 0, 1, 0, 1]
    """
    pass


if __name__ == '__main__':
    import doctest
    doctest.testmod()

  2. Compléter le docstring de cette fonction.

  3. Ajouter au moins deux nouveaux tests avec affichage dans la partie principale du programme (le main).
Une solution possible
 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
33
34
35
36
37
38
39
40
41
def permuter_a_gauche(tab):
    """
    tab - list, tableau d'entiers valant uniquement 0 ou 1
    Sortie: None - modifie le tableau passé en paramètre
            en remplaçant le premier élément par le deuxième,
            le deuxième par le troisième, …,
            l'avant-dernier par le dernier et
            le dernier par le premier
            (fonction à effet de bord)
    >>> T = [0, 1, 0, 0, 1]
    >>> permuter_a_gauche(T)
    >>> T
    [1, 0, 0, 1, 0]
    >>> permuter_a_gauche(T)
    >>> T
    [0, 0, 1, 0, 1]
    """
    assert tab != [], "Le tableau passé en argument ne doit pas être vide !"
    prem = tab[0]
    for i in range(1, len(tab)):
        tab[i-1] = tab[i]
    tab[len(tab)-1] = prem


if __name__ == "__main__":
    import doctest
    doctest.testmod()

    T = [3, 2, 1, 3, 2, 1]
    permuter_a_gauche(T)
    print(T == [2, 1, 3, 2, 1, 3])
    permuter_a_gauche(T)
    print(T == [1, 3, 2, 1, 3, 2])

    T = [0, 0, 0, 0]
    permuter_a_gauche(T)
    print(T == [0, 0, 0, 0])

    T = [1]
    permuter_a_gauche(T)
    print(T == [1])

Permuter à droite☘

Écrire le code d’une fonction permuter_a_droite() qui prend en paramètre un tableau non vide tab. Cette fonction est à effet de bord, c'est-à-dire qu'elle ne renvoie rien mais modifie le tableau passé en paramètre en remplaçant le deuxième élément par le premier, le troisième par le deuxième, …, le dernier par l'avant-dernier et le premier par le dernier.

Exemples

>>> T = [0, 1, 0, 0, 1]
>>> permuter_a_droite(T)
>>> T
[1, 0, 1, 0, 0]

>>> permuter_a_droite(T)
>>> T
[0, 1, 0, 1, 0]

>>> T = []
>>> permuter_a_droite(T)
AssertionError: Le tableau passé en argument ne doit pas être vide !

  1. Compléter la définition de la fonction permuter_a_droite(), sans oublier d'ajouter l'assertion signalée dans l'exemple précédent.

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
    def permuter_a_droite(tab):
    """
    tab - 
    Sortie: 
            (fonction à effet de bord)
    >>> T = [0, 1, 0, 0, 1]
    >>> permuter_a_droite(T)
    >>> T
    [1, 0, 1, 0, 0]
    >>> permuter_a_droite(T)
    >>> T
    [0, 1, 0, 1, 0]
    """
    pass


if __name__ == '__main__':
    import doctest
    doctest.testmod()

  2. Compléter le docstring de cette fonction.

  3. Ajouter au moins deux nouveaux tests avec affichage dans la partie principale du programme (le main).
Une solution possible
 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
33
34
35
36
37
38
39
40
41
def permuter_a_droite(tab):
    """
    tab - list, tableau d'entiers valant uniquement 0 ou 1
    Sortie: None - modifie le tableau passé en paramètre
            en remplaçant le premier élément par le deuxième,
            le deuxième par le troisième, …,
            l'avant-dernier par le dernier et
            le dernier par le premier
            (fonction à effet de bord)
    >>> T = [0, 1, 0, 0, 1]
    >>> permuter_a_droite(T)
    >>> T
    [1, 0, 1, 0, 0]
    >>> permuter_a_droite(T)
    >>> T
    [0, 1, 0, 1, 0]
    """
    assert tab != [], "Le tableau passé en argument ne doit pas être vide !"
    dern = tab[len(tab)-1]
    for i in range(len(tab)-1, 0, -1):
        tab[i] = tab[i-1]
    tab[0] = dern


if __name__ == "__main__":
    import doctest
    doctest.testmod()

    T = [3, 2, 1, 3, 2, 1]
    permuter_a_droite(T)
    print(T == [1, 3, 2, 1, 3, 2])
    permuter_a_droite(T)
    print(T == [2, 1, 3, 2, 1, 3])

    T = [0, 0, 0, 0]
    permuter_a_droite(T)
    print(T == [0, 0, 0, 0])

    T = [1]
    permuter_a_droite(T)
    print(T == [1])

Permuter à gauche jusqu'à☘

Écrire le code d’une fonction permuter_a_gauche_jusqu_a() qui prend en paramètres un tableau non vide tab et un entier k qui représente un indice d'un des éléments du tableau. Cette fonction est à effet de bord, c'est-à-dire qu'elle ne renvoie rien mais modifie le tableau passé en paramètre en remplaçant le premier élément par le deuxième, le deuxième par le troisième, …, le (k-1)-ième par le k-ième et le k-ième par le premier.

Exemples

>>> T = [3, 1, 7, 4]
>>> permuter_a_gauche_jusqu_a(T, 2)
>>> T
[1, 7, 3, 4]

>>> permuter_a_gauche_jusqu_a(T, 2)
>>> T
[7, 3, 1, 4]

>>> permuter_a_gauche_jusqu_a(T, 5)
AssertionError: tab index out of range

  1. Compléter la définition de la fonction permuter_a_gauche_jusqu_a(), sans oublier d'ajouter l'assertion signalée dans l'exemple précédent.

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
    def permuter_a_gauche_jusqu_a(tab, k):
    """
    tab – 
    k – 
    Sortie: 
            (fonction à effet de bord)
    >>> tab = [3, 1, 7, 4]
    >>> permuter_a_gauche_jusqu_a(tab, 2)
    >>> tab
    [1, 7, 3, 4]
    """
    pass


if __name__ == '__main__':
    import doctest
    doctest.testmod()

  2. Compléter le docstring de cette fonction.

  3. Ajouter au moins deux nouveaux tests avec affichage dans la partie principale du programme (le main).
Une solution possible
 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
33
34
35
def permuter_a_gauche_jusqu_a(tab, k):
    """
    tab – list, tableau d'éléments
    k – int, entier compris entre 0 et len(tab)-1
    Sortie: None – Permute à gauche tous les éléments de tab[0..k]
            (fonction à effet de bord)
    >>> tab = [3, 1, 7, 4]
    >>> permuter_a_gauche_jusqu_a(tab, 2)
    >>> tab
    [1, 7, 3, 4]
    """
    assert 0 <= k < len(tab), "tab index out of range"
    temp = tab[0]
    for i in range(k):
        tab[i] = tab[i+1]
    tab[k] = temp


if __name__ == "__main__":
    import doctest
    doctest.testmod()

    T = [3, 2, 1, 3, 2, 1]
    permuter_a_gauche_jusqu_a(T, 3)
    print(T == [2, 1, 3, 3, 2, 1])
    permuter_a_gauche_jusqu_a(T, 2)
    print(T == [1, 3, 2, 3, 2, 1])

    T = [0, 0, 0, 0]
    permuter_a_gauche_jusqu_a(T, 2)
    print(T == [0, 0, 0, 0])

    T = [1]
    permuter_a_gauche_jusqu_a(T, 0)
    print(T == [1])

Un tableau est-il trié à partir ?☘

Écrire le code d’une fonction est_trie_a_partir() qui prend en paramètres un tableau d'entiers non vide tab et un entier k qui représente un indice d'un des éléments du tableau. Cette fonction renvoie True lorsque tous les éléments du tableau tab, à partir de l'indice k (inclus), sont triés par ordre croissant et renvoie False dans le cas contraire.

Exemples

>>> est_trie_a_partir([2, 5, 6, 3, 4], 2)
False

>>> est_trie_a_partir([2, 5, 6, 3, 4], 3)
True

>>> est_trie_a_partir([2, 3, 4, 5, 6], 4)
True

>>> est_trie_a_partir([3, 1, 7, 4], 5)
AssertionError: tab index out of range

  1. Compléter la définition de la fonction est_trie_a_partir(), sans oublier d'ajouter l'assertion signalée dans l'exemple précédent.

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
    def est_trie_a_partir(tab, k):
    """
    tab – 
    k – 
    Sortie: 
    >>> est_trie_a_partir([2, 5, 6, 3, 4], 2)
    False
    >>> est_trie_a_partir([2, 5, 6, 3, 4], 3)
    True
    >>> est_trie_a_partir([2, 3, 4, 5, 6], 4)
    True
    """
    pass


if __name__ == '__main__':
    import doctest
    doctest.testmod()

  2. Compléter le docstring de cette fonction.

  3. Ajouter au moins deux nouveaux tests avec affichage dans la partie principale du programme (le main).
Une solution possible
 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 est_trie_a_partir(tab, k):
    """
    tab – list, tableau d'éléments comparables
    k – int, entier compris entre 0 et len(tab)-1
    Sortie: bool – True si tab[k..] est trié par ordre croissant,
            False sinon
    >>> est_trie_a_partir([2, 5, 6, 3, 4], 2)
    False
    >>> est_trie_a_partir([2, 5, 6, 3, 4], 3)
    True
    >>> est_trie_a_partir([2, 3, 4, 5, 6], 4)
    True
    """
    assert 0 <= k < len(tab), "tab index out of range"
    for i in range(k, len(tab)-1):
        if tab[i] > tab[i+1]:
            return False
    return True


if __name__ == "__main__":
    import doctest
    doctest.testmod()

    print(est_trie_a_partir([1, 2, 3, 4, 5], 0) == True)
    print(est_trie_a_partir([5, 4, 3, 2, 1], 4) == True)
    print(est_trie_a_partir([5, 4, 3, 2, 1], 3) == False)
    print(est_trie_a_partir([1, 3, 5, 2, 4], 1) == False)

Permuter à droite à partir☘

Écrire le code d’une fonction permuter_a_droite_a_partir() qui prend en paramètres un tableau non vide tab et un entier k qui représente un indice d'un des éléments du tableau. Cette fonction est à effet de bord, c'est-à-dire qu'elle ne renvoie rien mais modifie le tableau passé en paramètre en remplaçant le (k+1)-ième par le k-ième, , le (k+2)-ième par le (k+1)-ième, …, le dernier par l'avant-dernier et le k-ième élément par le dernier.

Exemples

>>> T = [3, 1, 7, 4, 11]
>>> permuter_a_droite_a_partir(T, 2)
>>> T
[3, 1, 11, 7, 4]

>>> permuter_a_droite_a_partir(T, 2)
>>> T
[3, 1, 4, 11, 7]

>>> permuter_a_droite_a_partir(T, 6)
AssertionError: tab index out of range

  1. Compléter la définition de la fonction permuter_a_droite_a_partir(), sans oublier d'ajouter l'assertion signalée dans l'exemple précédent.

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
    def permuter_a_droite_a_partir(tab, k):
    """
    tab – 
    k – 
    Sortie: 
            (fonction à effet de bord)
    >>> tab = [3, 1, 7, 4]
    >>> permuter_a_droite_a_partir(tab, 1)
    >>> tab
    [3, 4, 1, 7]
    """
    pass


if __name__ == '__main__':
    import doctest
    doctest.testmod()

  2. Compléter le docstring de cette fonction.

  3. Ajouter au moins deux nouveaux tests avec affichage dans la partie principale du programme (le main).
Une solution possible

Il faut penser à parcourir les éléments du tableau « à l'envers ». 

 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
33
34
35
def permuter_a_droite_a_partir(tab, k):
    """
    tab – list, tableau d'éléments
    k – int, entier compris entre 0 et len(tab)-1
    Sortie: None – Permute à droite tous les éléments de tab[k..]
            (fonction à effet de bord)
    >>> tab = [3, 1, 7, 4]
    >>> permuter_a_droite_a_partir(tab, 1)
    >>> tab
    [3, 4, 1, 7]
    """
    assert 0 <= k < len(tab), "tab index out of range"
    dernier = tab[len(tab)-1]
    for i in range(len(tab)-1, k, -1):
        tab[i] = tab[i-1]
    tab[k] = dernier


if __name__ == "__main__":
    import doctest
    doctest.testmod()

    T = [3, 2, 1, 3, 2, 1]
    permuter_a_droite_a_partir(T, 3)
    print(T == [3, 2, 1, 1, 3, 2])
    permuter_a_droite_a_partir(T, 2)
    print(T == [3, 2, 2, 1, 1, 3])

    T = [0, 0, 0, 0]
    permuter_a_droite_a_partir(T, 2)
    print(T == [0, 0, 0, 0])

    T = [1]
    permuter_a_droite_a_partir(T, 0)
    print(T == [1])

Renverser jusqu'à☘

Dans cet exercice, il faut programmer un algorithme de renversement des éléments d'un tableau, jusqu'à une certaine position i connue à l'avance.

Exemple

On considère le tableau ci-dessous :

5 7 1 4 9 8 3 4 0 6

Lorsqu'on décide de renverser les éléments jusqu'à l'indice 7 (inclus), le tableau devient :

4 3 8 9 4 1 7 5 0 6

Écrire le code d’une fonction renverser_jusqu_a() qui prend en paramètres un tableau non vide tab et un indice i d'un élément de ce tableau.
Cette fonction est à effet de bord, c'est-à-dire qu'elle ne renvoie rien mais modifie le tableau
passé en paramètre en renversant les éléments de la « plage d'indices » [0..i].

Exemples

>>> T = [3, 1, 7, 4, 11]
>>> renverser_jusqu_a(T, 2)
>>> T
[7, 1, 3, 4, 11]

>>> renverser_jusqu_a(T, 3)
>>> T
[4, 3, 1, 7, 11]

>>> renverser_jusqu_a(T, 5)
AssertionError: tab index out of range

  1. Compléter la définition de la fonction renverser_jusqu_a(), sans oublier d'ajouter l'assertion signalée dans l'exemple précédent.

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
    def renverser_jusqu_a(tab, i):
    """
    tab – 
    i – 
    Sortie: 
            (fonction à effet de bord)
    >>> T = [3, 1, 7, 4, 11]
    >>> renverser_jusqu_a(T, 2)
    >>> T
    [7, 1, 3, 4, 11]        
    >>> renverser_jusqu_a(T, 3)
    >>> T
    [4, 3, 1, 7, 11]
    """
    pass


if __name__ == '__main__':
    import doctest
    doctest.testmod()

  2. Compléter le docstring de cette fonction.

  3. Ajouter au moins deux nouveaux tests avec affichage dans la partie principale du programme (le main).
Une solution possible
 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 renverser_jusqu_a(tab, i):
    """
    tab – list, tableau de n éléments
    i – int, entier compris entre 0 et n-1
    Sortie: None – l'ordre des éléments de tab[0] jusqu'à tab[i] a été renversé
            (fonction à effet de bord)
    >>> T = [3, 1, 7, 4, 11]
    >>> renverser_jusqu_a(T, 2)
    >>> T
    [7, 1, 3, 4, 11]
    >>> renverser_jusqu_a(T, 3)
    >>> T
    [4, 3, 1, 7, 11]
    """
    assert 0 <= i < len(tab), "tab index out of range"
    for k in range(i//2+1):
        temp = tab[k]
        tab[k] = tab[i-k]
        tab[i-k] = temp


if __name__ == "__main__":
    import doctest
    doctest.testmod()

    A = [215, 681, 818, 609, 398, 635, 765, 882, 756, 418]
    renverser_jusqu_a(A, 3)
    print(A == [609, 818, 681, 215, 398, 635, 765, 882, 756, 418])

    renverser_jusqu_a(A, 6)
    print(A == [765, 635, 398, 215, 681, 818, 609, 882, 756, 418])