Loading [MathJax]/jax/output/HTML-CSS/jax.js
Danh sách khoá học Đăng nhập

Thông tin

Tác giả Vincent Branders, Pierre Dupont
Hạn chót 26/03/2025 14:00:00
Giới hạn nộp bài Không có giới hạn

Đăng nhập

Đăng nhập

[TP06] Somme des k premiers éléments d'une liste - Récursif

Implémentez une version récursive de l'algorithme itératif étudié dans l'exercice précédent. Votre implémentation récursive doit garder la même complexité que l'algorithme itératif.

On vous demande d'implémenter un algorithme avec récursion. Avant d'élaborer votre algorithme, détaillez :

  1. le cas de base,
  2. comment traiter le cas de base,
  3. comment construire la solution actuelle si je connais une solution pour un problème plus petit.

Rappel du problème :

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

t=10|20|30|10|15k=3

le résultat attendu est 60.

Câu hỏi 1: Le cas de base

Identifiez, parmi les propositions suivantes, celle qui correspond au cas de base de l'algorithme récursif.

Câu hỏi 2: Somme des premiers éléments (récursif)

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_rec.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_rec(t, k):
    """
    Calcule la somme des `k` premiers éléments de `t` par récursion
    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`
    """