Quiz — Programmation dynamique — Mémoïsation

Question 1

Le code Python suivant implémente une version naïve du calcul du nombre de Fibonacci, sans mémoïsation, pour une mission de calcul de trajectoire. Quelle est la valeur de `fib(5)` ?

Accepted Answer

8

Answer

3

Answer

5

Answer

13

Question 2

Dans le cadre de la planification des ressources pour une station spatiale internationale, on utilise un algorithme de programmation dynamique pour calculer le nombre de façons de payer une somme donnée avec des pièces de monnaie. Le code suivant utilise la mémoïsation. Quelle est la valeur de `count_ways([1, 2, 5], 5)` ?

Accepted Answer

4

Answer

3

Answer

5

Answer

6

Question 3

Quelle est la valeur de $f(5)$ après l'exécution de ce code utilisant la mémoïsation pour calculer les nombres de Fibonacci ?
```python
def fib(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

f = fib(5)
```

Accepted Answer

8

Answer

5

Answer

13

Answer

21

Question 4

Quelle est la valeur de $x$ après l'exécution du code Python suivant ? $$
\begin{aligned}
def sac_a_dos(valeurs, poids, capacite):
    n = len(valeurs)
    dp = [0] * (capacite + 1)
    for i in range(n):
        for w in range(capacite, poids[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - poids[i]] + valeurs[i])
    return dp[capacite]

valeurs = [60, 100, 120]
poids = [10, 20, 30]
capacite = 50
x = sac_a_dos(valeurs, poids, capacite)
\end{aligned}$$

Accepted Answer

$220$

Answer

$160$

Answer

$180$

Answer

$280$

Question 5

Soit la fonction $f$ définie par $f(0)=1$, $f(1)=1$, et $f(n)=f(n-1)+f(n-2)$ pour $n\geq 2$. Quelle est la complexité temporelle de cette fonction sans mémoïsation ?

Accepted Answer

$$ O(2^n) $$

Answer

$$ O(1) $$

Answer

$$ O(n) $$

Answer

$$ O(n^2) $$

Programmation dynamique — Mémoïsation

Notions à maîtriser

Teste-toi sur ce chapitre

Programmation dynamique : la mémoïsation expliquée

Garder ta progression ?