Exercice 1 du TP2

Il est parfois utile – voire nécessaire – de mettre en place un premier parcours séquentiel, avec une boucle, et, en fixant ce premier élément, de parcourir une deuxième boucle. De manière artificielle on peut faire

for i in range(4):
    for j in range(3):
        print(i, j)

Combien de fois la fonction print est-elle appelée dans cette boucle ?

On peut aussi créer un tableau rectangulaire – une matrice – avec une liste de listes grâce à deux boucles imbriquées.

Par exemple, pour une matrice de Vandermonde, dont l’élément de la ligne $0 \leqslant i \leqslant n-1$ et de la colonne $0 \leqslant j \leqslant p-1$, est $i^j$,

def vandermonde(n, p):
    M = []
    for i in range(n):
        L = []
        for j in range(p):
            L.append(i∗∗j)
        M.append(L)
    return M

Ce qui peut être, après exécution, testé en console :

>>> vandermonde(6,4)

Quel est la complexité de la fonction vandermonde ?

On peut dans certains cas n'avoir besoin que d'un tableau triangulaire, c'est-à-dire qu'une borne de l'itérateur qui permet de décrire la boucle interne (la deuxième) dépend de l’indice qui permet de décrire la première boucle.

for i in range(4):
    for j in range(i): # noter le i
        print(i, j)

ou encore

def tableau_triangulaire(n):
    """
    crée un tableau triangulaire de taille n avec m[i][j]=(i+1)∗(j+1)
    """
    M = []
    for i in range(n):
        L = []
        for j in range(i): # j décrit l'intervalle d'entier [[0 , i−1]]
            item = (i+1)∗∗(j +1)
            L.append(item)
        M.append(L)
    return M

Après exécution en console :

>>> tableau_triangulaire(5)

Quel est la complexité de la fonction tableau_triangulaire ?