[TP06] Somme des k premiers éléments d'une liste - Itératif - [LINFO1103] Introduction à l'algorithmique

[TP06] Somme des k premiers éléments d'une liste - Itératif

Supposons que l'on dispose d'un tableau t d'entiers et que l'on veuille connaître la somme de ses k premiers éléments. Par exemple, si les entrées sont

$\begin{align*} t & = \boxed{10 \,\vert\, 20 \,\vert\, 30 \,\vert\, 10 \,\vert\, 15 \,\,}\\ k & = 3 \end{align*}$

le résultat attendu est 60.

Paste this command into your terminal:

The password to connect is

Question 1: Somme des premiers éléments (itératif)

Vous êtes chargés d'implémenter la fonction suivante en Python. Pour préparer votre code, vous pouvez télécharger le fichier sum_first_iter.py qui contient la signature de la fonction et quelques exemples de tests.

Note: Lorsqu'il vous est demandé d'implémenter une fonction, vous êtes invités à ne remplir que le corps de la fonction à implémenter.

def sum_first(t, k):
    """
    Calcule la somme des `n` premiers éléments de `t` avec une boucle (= version itérative)
    pre: `t` un tableau (list) non vide
    pre: `k` un entier tel que 1<=`k`<=len(`t`)
    post: retourne la somme des `k` premiers éléments de `t`
    """

return -1

 
return -1

Question 2: Complexité temporelle

Quelle est la complexité temporelle de l’algorithme ? Choisissez la borne la plus simple et la plus stricte possible.

On suppose que vous n'effectuez pas d'opérations inutiles.

Comme d'habitude, le taille du problème (= le nombre de valeurs à mémoriser) est désignée par n (ici, il s'agit de la longueur de la liste t).
Par ailleurs, k désigne le second paramètre passé à la fonction sum_first.

$\Theta(n^2)$

$O(n)$

$\Theta(k)$

$O(n^2)$

$O(k)$

$\Theta(n)$

Author(s)	Vincent Branders, Pierre Dupont
Deadline	26/03/2025 14:00:00
Abgabenlimit	No limitation

Information

Einloggen