Ce TD est noté.

• Il est réalisé en durée limité: 2h
• L’utilisation des notes de cours est autorisées, ainsi que vos fichiers de TP disponibles sur votre machine.
• Internet n’est pas autorisé sauf le site de la documentation Python et les notes de cours.
• En cas de blocage, vous pouvez demander de l’aide.

Exercice 2. Documentation et Complexité (10pts)

Proposez un nom et une documentation (incluant des doctests et la complexité) pour les fonctions suivantes:

def f1(N):
  a = 0
  for i in range(N):
    if i % 2 == 0:
      a += 1
  return a

def f2(L):
  K = []
  n = len(L) 
  for i in range(1, n+1):
    K.append(L[n-i])
  return K

def f3(L):
  if len(L) == 0:
    return []
  return [L[-1]] + f3(L[:-1])

def f4(L):
  a = 0
  n = len(L)
  for i in range(n):
    a += L[i]
  return a/n

def f5(L):
  n = len(L)
  if n == 1:
    return L[0]
  else:
    return (f5(L[:-1])*(n-1) + L[-1])/n

def f6(n):
  if n == 0:
    return [""]
  K = []
  for u in f6(n-1):
    K.append(u+'a')
    K.append(u+'b')
  return K

Exercice 3. Matrices ! (7pts)

La fonction transpose qui prend entrée une liste de listes de taille \(m \times n\) où \(m\) est le nombre de sous-listes et \(n\) le nombre d’éléments dans chaque sous-liste et retourne la transposée:

Si M = [[1]], transpose(M) retourne [[1]].

Si M = [[1, 2]], transpose(M), retourne [[1], [2]].

Si M = [[1, 2], [3, 4]], transpose retourne [[1, 3], [2, 4]].

1. Écrire une version impérative de transpose.

2. Écrire une version récursive de transpose.

3. Proposez une analyse de complexité de votre implémentation en fonction de \(m\) et \(n\).

Exercice 3. Plateau (7pts)

La fonction plateau prend en entree un entier \(N\) et retourne un plateau de jeu de taille \(N \times N\) sous la forme d’une liste de listes. Si N = 2 , plateau retourne:

[
  ['x', 'o'],
  ['o', 'x']
]

Si \(N = 3\), plateau retourne:

[
  ['x', 'o', 'x'],
  ['o', 'x', 'o'],
  ['x', 'o', 'x']
]

1. Écrire une version impérative de plateau.

2. Écrire une version récursive de plateau.

3. Proposez une analyse de complexité de votre implémentation.

Compiled the: lun. 18 nov. 2024 15:48:28 CET