Aller au contenu

Tableaux

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

Remarque importante

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.

Codage par différence

Le codage par différence (« delta encoding » en anglais) permet de compresser un tableau de données en indiquant, pour chaque donnée, sa différence avec la précédente (plutôt que la donnée elle-même). On se retrouve alors avec un tableau de données assez petites nécessitant moins de place en mémoire. Cette méthode se révèle efficace lorsque les valeurs consécutives sont proches.

Programmer la fonction delta() qui prend en paramètre un tableau non vide de nombres entiers et qui renvoie un tableau contenant les valeurs entières compressées à l’aide cette technique.

Exemples

>>> delta([1000, 800, 802, 1000, 1003])
[1000, -200, 2, 198, 3]

>>> delta([42])
[42]

>>> delta([])
AssertionError: Tableau vide !
  1. Compléter la définition de la fonction delta(), 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
    def delta(tab):
        """
        tab - 
        Sortie: 
        >>> delta([1000, 800, 802, 1000, 1003])
        [1000, -200, 2, 198, 3]
        >>> delta([42])
        [42]
        """
        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
 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
def delta(tab):
    """
    tab - list, tableau non vide d'entiers
    Sortie: list, tableau des différences entre chaque élément de tab et
            l'élément précédent
    >>> delta([1000, 800, 802, 1000, 1003])
    [1000, -200, 2, 198, 3]
    >>> delta([42])
    [42]
    """
    assert len(tab) > 0, 'Tableau vide !'
    diff = [tab[0]]
    for i in range(1, len(tab)):
        diff.append(tab[i] - tab[i-1])
    return diff



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

    from random import randint
    print(delta([729, 183, 672, 134, 65, 451, 968, 277]) == [729, -546, 489, -538, -69, 386, 517, -691])

    t = [randint(0, 1000) for _ in range(8)]
    print(t)
    print(delta(t))

    delta([])

Éléments consécutifs

Écrire le code d'une fonction couples_consécutifs() qui prend en paramètre un tableau de nombres entiers tab, et qui renvoie le tableau (éventuellement vide) des couples d'entiers consécutifs successifs qu'il peut y avoir dans tab.

Exemples

>>> couples_consécutifs([1, 4, 3, 5])
[]

>>> couples_consécutifs([1, 4, 5, 3])
[(4, 5)]

>>> couples_consécutifs([7, 1, 2, 5, 3, 4])
[(1, 2), (3, 4)]

>>> couples_consécutifs([5, 1, 2, 3, 8, -5, -4, 7])
[(1, 2), (2, 3), (-5, -4)]
  1. Compléter la définition de la fonction couples_consécutifs().

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    def couples_consécutifs(tab):
        """
        tab - 
        Sortie: 
        >>> couples_consécutifs([1, 4, 3, 5])
        []
        >>> couples_consécutifs([1, 4, 5, 3])
        [(4, 5)]
        >>> couples_consécutifs([7, 1, 2, 5, 3, 4])
        [(1, 2), (3, 4)]
        >>> couples_consécutifs([5, 1, 2, 3, 8, -5, -4, 7])
        [(1, 2), (2, 3), (-5, -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
 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
def couples_consécutifs(tab):
    """
    tab - list, tableau de nombres entiers
    Sortie: list - tableau des couples d'entiers consécutifs successifs
            qu'il peut y avoir dans tab.
    >>> couples_consécutifs([1, 4, 3, 5])
    []
    >>> couples_consécutifs([1, 4, 5, 3])
    [(4, 5)]
    >>> couples_consécutifs([7, 1, 2, 5, 3, 4])
    [(1, 2), (3, 4)]
    >>> couples_consécutifs([5, 1, 2, 3, 8, -5, -4, 7])
    [(1, 2), (2, 3), (-5, -4)]
    """
    result = []
    for i in range(len(tab)-1):
        if tab[i+1] == tab[i]+1:
            result.append( (tab[i], tab[i+1]) )
    return result

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

    print(couples_consécutifs([7, 2, 9, 1, 8, 3, 6, 7, 2]) == [(6, 7)])

    from random import randint


    t = [randint(0, 10) for _ in range(8)]
    print(t)
    print(couples_consécutifs(t))

Syracuse

Soit un nombre entier k supérieur ou égal à 1 :

  • s'il est pair, on le divise par 2 ;
  • s’il est impair, on le multiplie par 3 et on ajoute 1.

Puis on recommence ces étapes avec le nombre entier obtenu, jusqu’à ce que l’on obtienne la valeur 1.

On admet que, quel que soit l’entier k choisi au départ, on arrivera forcément sur la valeur 1.

Écrire une fonction syracuse() prenant en paramètres cet entier k strictement positif et qui renvoie le tableau des valeurs successives obtenues, en partant de k et jusqu’à atteindre 1.

Exemple

>>> syracuse(1)
[1]
>>> syracuse(4)
[4, 2, 1]
>>> syracuse(7)
[7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
  1. Compléter la définition de la fonction syracuse().

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    def syracuse(k):
        """
        k - 
        Sortie: 
        >>> syracuse(1)
        [1]
        >>> syracuse(4)
        [4, 2, 1]
        >>> syracuse(7)
        [7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 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

Rappel : vous pouvez définir des fonctions supplémentaires si vous le souhaitez.

 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 suivant(k):
    """
    k - int, entier strictement positif
    Sortie: int - k/2 si k est pair, 3*k+1 sinon
    """
    if k%2 == 0:
        return k//2
    else:
        return 3*k+1


def syracuse(k):
    '''
    k - int, entier strictement positif
    Sortie: list - tableau des entiers de k à 1 en suivant le principe de Syracuse 
    >>> syracuse(1)
    [1]
    >>> syracuse(4)
    [4, 2, 1]
    >>> syracuse(7)
    [7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
    '''
    tab = [k]
    while k != 1:
        k = suivant(k)
        tab.append(k)
    return tab        


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

    print(syracuse(5) == [5, 16, 8, 4, 2, 1] )
    print(syracuse(15) == [15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1])

Indice de la première occurrence

Écrire le code d’une fonction premiere_occurrence() qui prend en paramètres elt un nombre entier et tab un tableau de nombres entiers, et qui renvoie l’indice de la première occurrence de elt dans tab si elt est dans tab et -1 sinon.

Exemples

>>> premiere_occurrence(1, [2, 3, 4])
-1

>>> premiere_occurrence(1, [10, 12, 1, 56])
2

>>> premiere_occurrence(1, [1, 50, 1])
0

>>> premiere_occurrence(15, [8, 9, 10, 15])
3
  1. Compléter la définition de la fonction premiere_occurrence().

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    def premiere_occurrence(elt, tab):
        """
        elt - 
        tab - 
        Sortie: 
        >>> premiere_occurrence(1, [2, 3, 4])
        -1
        >>> premiere_occurrence(1, [10, 12, 1, 56])
        2
        >>> premiere_occurrence(1, [1, 50, 1])
        0
        >>> premiere_occurrence(15, [8, 9, 10, 15])
        3
        """
        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
 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
def premiere_occurrence(elt, tab):
    """
    elt - int, un entier quelconque
    tab - list, tableau d'entiers
    Sortie: int, indice de la première occurrence de elt dans tab
            Si elt n'est pas dans tab, renvoie -1
    >>> premiere_occurrence(1, [2, 3, 4])
    -1
    >>> premiere_occurrence(1, [10, 12, 1, 56])
    2
    >>> premiere_occurrence(1, [1, 50, 1])
    0
    >>> premiere_occurrence(15, [8, 9, 10, 15])
    3
    """
    for i in range(len(tab)):
        if tab[i] == elt:
            return i
    return -1

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

    print(premiere_occurrence(7, [2, 9, 1, 7, 3, 7, 7, 2]) == 3)

    from random import randint
    t = [randint(0, 10) for _ in range(8)]
    print(t)
    print(premiere_occurrence(7, t))

Nombre d'occurrences d'un élément

Écrire en langage Python une fonction nb_occurrences() prenant comme paramètres une variable val de type entier et un tableau d'entiers tab. Cette fonction renvoie le nombre d'occurrences de elt dans tab.

Exemples d'utilisations de la fonction recherche

>>> nb_occurrences(5, []) 
0

>>> nb_occurrences(5, [-2, 3, 4, 8]) 
0

>>> nb_occurrences(5, [-2, 3, 1, 5, 3, 7, 4]) 
1

>>> nb_occurrences(5, [-2, 5, 3, 5, 4, 5]) 
3
  1. Compléter la définition de la fonction nb_occurrences().

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    def nb_occurrences(val, tab):
        """
        val -
        tab - 
        Sortie: 
        >>> nb_occurrences(5, []) 
        0
        >>> nb_occurrences(5, [-2, 3, 4, 8]) 
        0
        >>> nb_occurrences(5, [-2, 3, 1, 5, 3, 7, 4]) 
        1
        >>> nb_occurrences(5, [-2, 5, 3, 5, 4, 5]) 
        3
        """
        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
 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
def nb_occurrences(val, tab):
    """
    val - int, un entier quelconque
    tab - list, tableau d'entiers
    Sortie: int, nombre d'occurences de val dans tab
    >>> nb_occurrences(5, []) 
    0
    >>> nb_occurrences(5, [-2, 3, 4, 8]) 
    0
    >>> nb_occurrences(5, [-2, 3, 1, 5, 3, 7, 4]) 
    1
    >>> nb_occurrences(5, [-2, 5, 3, 5, 4, 5]) 
    3
    """
    compte = 0
    for elt in tab:
        if elt == val:
            compte += 1
    return compte


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

    print(nb_occurrences(5, [5, 5, 5, 5, 5, 5]) == 5)
    print(nb_occurrences(0, [1, 0, 1, 0]) == 2)

Indice de la dernière occurrence

Écrire le code d’une fonction derniere_occurrence() qui prend en paramètres elt un nombre entier et tab un tableau de nombres entiers, et qui renvoie l’indice de la dernière occurrence de elt dans tab si elt est dans tab et la longueur du tableau sinon.

Exemples

>>> derniere_occurrence(1, [2, 3, 4])
3

>>> derniere_occurrence(1, [10, 12, 1, 56])
2

>>> derniere_occurrence(1, [1, 50, 1])
2

>>> derniere_occurrence(1, [8, 1, 10, 1, 7, 1, 8])
5
  1. Compléter la définition de la fonction derniere_occurrence().

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    def derniere_occurrence(elt, tab):
        """
        elt - 
        tab - 
        Sortie: 
        >>> derniere_occurrence(1, [2, 3, 4])
        3
        >>> derniere_occurrence(1, [10, 12, 1, 56])
        2
        >>> derniere_occurrence(1, [1, 50, 1])
        2
        >>> derniere_occurrence(1, [8, 1, 10, 1, 7, 1, 8])
        5
        """
        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
 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 derniere_occurrence(elt, tab):
    """
    elt - int, un entier quelconque
    tab - list, tableau d'entiers
    Sortie: int, indice de la dernière occurrence de elt dans tab
            Si elt n'est pas dans tab, renvoie -1
    >>> derniere_occurrence(1, [2, 3, 4])
    3
    >>> derniere_occurrence(1, [10, 12, 1, 56])
    2
    >>> derniere_occurrence(1, [1, 50, 1])
    2
    >>> derniere_occurrence(1, [8, 1, 10, 1, 7, 1, 8])
    5
    """
    indice = len(tab)
    for i in range(len(tab)):
        if tab[i] == elt:
            indice = i
    return indice

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

    print(derniere_occurrence(7, [2, 9, 1, 7, 3, 7, 7, 2]) == 6)

    from random import randint
    t = [randint(0, 10) for _ in range(8)]
    print(t)
    print(derniere_occurrence(7, t))

Indices des occurrences

Écrire le code d’une fonction indices_occurrences() qui prend en paramètres elt un nombre entier et tab un tableau de nombres entiers, et qui renvoie le tableau des indices des occurrences de elt dans tab si elt est dans tab et le tableau vide sinon.

Exemples

>>> indices_occurrences(3, [3, 2, 1, 3, 2, 1])
[0, 3]

>>> indices_occurrences(4, [1, 2, 3])
[]
  1. Compléter la définition de la fonction indices_occurrences().

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    def indices_occurrences(elt, tab):
        """
        elt - 
        tab - 
        Sortie: 
        >>> indices_occurrences(3, [3, 2, 1, 3, 2, 1])
        [0, 3]
        >>> indices_occurrences(4, [1, 2, 3])
        []
        """
        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
 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
def indices_occurrences(elt, tab):
    """
    elt - int, un entier quelconque
    tab - list, tableau d'entiers
    Sortie: list, tableau des indices de elt dans tab
    >>> indices_occurrences(3, [3, 2, 1, 3, 2, 1])
    [0, 3]
    >>> indices_occurrences(4, [1, 2, 3])
    []
    """
    result = []
    for i in range(len(tab)):
        if tab[i] == elt:
            result.append(i)
    return result

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

    print(indices_occurrences(1, [1, 1, 1, 1, 1, 1, 1, 1]) == [0, 1, 2, 3, 4, 5, 6, 7])
    print(indices_occurrences(4, [3, 2, 1, 4, 2, 1]) == [3])

    from random import randint
    t = [randint(0, 10) for _ in range(8)]
    print(t)
    print(indices_occurrences(7, t))