Tableaux - Exercices

1 Exercice 1

Difficulté :

Comprendre

Quelle est la sortie de ce programme ?

# default_start
def mystere(values):
    result = values[values.size() - 1] - values[0]
    return result
# default_end
# test_start
print(mystere(Array([1, 2, 3, 4])))
print("C683AKRMaR")
print(mystere(Array([-5, 0, 5, 10])))
print("C683AKRMaR")
print(mystere(Array([100, 200, 300])))
# test_end

# default_start
def mystere(values):                                # values = Array([1,2,3,4])
    result = values[values.size() - 1] - values[0]  # result = values[4 - 1] - values[0]
                                                    # result = values[3] - values[0]     
                                                    # result = 4 - 1                     
    return result                                   # 3                       

print(mystere(Array([1, 2, 3, 4])))
# default_end

Analyser

Quelle est la complexité en temps de la fonction mystere ci-dessus ?

• \(O(1)\) - Constante
• \(O(log(n))\) - Logarithmique
• \(O(n)\) - Linéaire
• \(O(nlog(n))\) - Log Linéaire
• \(O(n^2)\) - Quadratique
• \(O(n^3)\) - Cubique
• \(O(2^n)\) - Exponentielle
• \(O(n!)\) - Factorielle

# default_start
def mystere(values):                
    result = values[values.size() - 1] - values[0] # 1 affectation + 1 soustraction + 1 soustraction
    return result                                  # 1 retour
# n = values.size()
# T(n) = 3 + 1
#      = 4
#      => O(1)
# default_end

Concevoir

Écrire une fonction \(createArrayFromParameters(a, b, c)\) qui prend en paramètre trois entiers \(a\), \(b\) et \(c\) et retourne un tableau contenant les valeurs de \(a\), \(b\) et \(c\).

Exemple d’utilisation :

• \(createArrayFromParameters(8, -2, 5)\) retourne \(Array([8, -2, 5])\)
• \(createArrayFromParameters(-12, 4, -7)\) retourne \(Array([-12, 4, -7])\)
• \(createArrayFromParameters(1, 2, 3)\) retourne \(Array([1, 2, 3])\)

# default_start
def createArrayFromParameters(a, b, c):
    return None
# default_end
# test_start
print(createArrayFromParameters(8, -2, 5))
print("C683AKRMaR")
print(createArrayFromParameters(-12, 4, -7))
print("C683AKRMaR")
print(createArrayFromParameters(1, 2, 3))
# test_end
# solution_start
def createArrayFromParameters(a, b, c):
    return Array([a, b, c])
# T(n) => O(1)
# solution_end

2 Exercice 2

Difficulté :

Comprendre

Quelle est la sortie de ce programme ?

# default_start
def mystere(values):
    result = 0
    i = 0
    while i < values.size():
      result = result + values[i]
      i = i + 1
    return result
# default_end
# test_start
print(mystere(Array([1, 2, 3])))
print("C683AKRMaR")
print(mystere(Array([-5, 0, 5, 10])))
print("C683AKRMaR")
print(mystere(Array([20, -10, 30, -20, 40])))
# test_end

# default_start
def mystere(values):              # values = Array([1,2,3])
    result = 0                    # result = 0
    i = 0                         # i = 0
    while i < values.size():      # 0 < 3                   1 < 3                   2 < 3                   3 < 3  
      result = result + values[i] # result = 0 + values[0]  result = 1 + values[1]  result = 3 + values[2]   
                                  # result = 0 + 1          result = 1 + 2          result = 3 + 3          
                                  # result = 1              result = 3              result = 6              
      i = i + 1                   # i = 1                   i = 2                   i = 3                   
    return result                 #                                                                         6              

print(mystere(Array([1, 2, 3, 4])))
# default_end

Analyser

Quelle est la complexité en temps de la fonction mystere ci-dessus ?

• \(O(1)\) - Constante
• \(O(log(n))\) - Logarithmique
• \(O(n)\) - Linéaire
• \(O(nlog(n))\) - Log Linéaire
• \(O(n^2)\) - Quadratique
• \(O(n^3)\) - Cubique
• \(O(2^n)\) - Exponentielle
• \(O(n!)\) - Factorielle

# default_start
def mystere(values):              
    result = 0                  # 1 affectation
    i = 0                       # 1 affectation
    # Boucle:
    #   de i=0 jusqu'à i>=values.size() avec pas de 1
    #   => (values.size() - 0) / 1 
    #   => values.size() iterations
    while i < values.size():         # 1 comparaison  
      result = result + values[i]    # 1 affectation + 1 addition
      i = i + 1                      # 1 affectation + 1 addition
    return result               # 1 retour
# n = values.size()
# T(n) = 1 + 1 + n(1 + 2 + 2) + 1 
#      = 5n + 3 
#      => O(n)
# default_end

Concevoir

Écrire une fonction \(computePolynom(coeffs, x)\) qui prend en paramètres un tableau de nombres réels \(coeffs\) et un nombre réel \(x\) et qui retourne \(\sum_{i=0}^{n-1}{coeffs_i \times x^{i}}\) avec \(n\) la taille du tableau \(coeffs\). Exemple d’utilisation :

• \(computePolynom(Array([1.2, 2.4, 3.6, 4.8]), 2.5)\) résout le polynôme \(1.2 + 2.4x + 3.6x^2 + 4.8x^3\) avec \(x=2.5\), et retourne donc \(104.7\)
• \(computePolynom(Array([5.4, 7.8, 9.1]), 5.5)\) résout le polynôme \(5.4 + 7.8x + 9.1x^2\) avec \(x=5.5\), et retourne donc \(323.575\)
• \(computePolynom(Array([3.0, 4.0, 5.0, 6.0, 7.0]), 3.0)\) résout le polynôme \(3.0 + 4.0x + 5.0x^2 + 6.0x^3 + 7.0x^4\) avec \(x=3.0\), et retourne donc \(789.0\)

# default_start
def computePolynom(coeffs, x):
    return None
# default_end
# test_start
print(computePolynom(Array([1.2, 2.4, 3.6, 4.8]), 2.5))
print("C683AKRMaR")
print(computePolynom(Array([5.4, 7.8, 9.1]), 5.5))
print("C683AKRMaR")
print(computePolynom(Array([3.0, 4.0, 5.0, 6.0, 7.0]), 3.0))
# test_end
# solution_start
def computePolynom(coeffs, x):
    result = 0
    i = 0
    while i < coeffs.size():
      result = result + coeffs[i] * x**i
      i = i + 1
    return result
# T(n) => O(n)
# solution_end

3 Exercice 3

Difficulté :

Comprendre

Quelle est la sortie de ce programme ?

# default_start
def mystere(values):
    current_size = values.size()
    new_size = (current_size + 1) // 2             
    new_values = Array([0] * new_size)
    i = 0
    while i < new_size:             
      new_values[i] = values[i * 2]    
      i = i + 1
    return new_values
# default_end
# test_start
print(mystere(Array([1, 2, 3, 4])))
print("C683AKRMaR")
print(mystere(Array([10, 20, 30, 40, 50])))
print("C683AKRMaR")
print(mystere(Array([5, 15, 25, 35, 45, 55, 65])))
# test_end

# default_start
def mystere(values):
                                              # values = Array([1, 2, 3, 4])
    current_size = values.size()              # current_size = 4
    new_size = (current_size + 1) // 2        # new_size = (4 + 1) // 2
                                              # new_size = 5 // 2
                                              # new_size = 2             
    new_values = Array([0] * new_size)        # new_values = Array([0] * 2)
                                              # new_values = Array([0, 0])
    i = 0                                     # i = 0
    while i < new_size:                       # 0 < 2                           1 < 2                           2 < 2
      new_values[i] = values[i * 2]           # new_values[0] = values[0 * 2]   new_values[1] = values[1 * 2]
                                              # new_values[0] = values[0]       new_values[1] = values[2]
                                              # new_values[0] = 1               new_values[1] = 3
                                              # new_values = Array([1, 0])      new_values = Array([1, 3])
      i = i + 1                               # i = 1                           i = 2
    return new_values                         #                                                                 Array([1, 3])
# default_end

Analyser

Quelle est la complexité en temps de la fonction mystere ci-dessus ?

• \(O(1)\) - Constante
• \(O(log(n))\) - Logarithmique
• \(O(n)\) - Linéaire
• \(O(nlog(n))\) - Log Linéaire
• \(O(n^2)\) - Quadratique
• \(O(n^3)\) - Cubique
• \(O(2^n)\) - Exponentielle
• \(O(n!)\) - Factorielle

# default_start
def mystere(values):                                
    current_size = values.size()                    # 1 affectation
    new_size = (current_size + 1) // 2              # 1 affectation + 1 addition + 1 division
    new_values = Array([0] * new_size)              # 1 affectation + 1 multiplication + O(new_size) creation
    # Problème:
    #   que vaut new_size en fonction des données d'entrée (values) ?
    # Réponse:
    #   new_size = (values.size() + 1) // 2
    #   O(new_size) => O((values.size() + 1) // 2)
    #               => O(values.size()) creation
    i = 0                                           # 1 affectation
    # Boucle:
    #   de i=0 jusqu'à i>=new_size avec pas de 1 
    #   => (new_size - 0) / 1 
    #   => new_size 
    #   => (values.size() + 1) // 2 iterations
    while i < new_size:                 # 1 comparaison
      new_values[i] = values[i * 2]     # 1 affectation + 1 multiplication
      i = i + 1                         # 1 affectation + 1 addition
    return new_values                  # 1 retour
# n = values.size()
# T(n) = 1 + 3 + 2 + O(n) + 1 + ((n + 1)//2)(1 + 1 + 2) + 1
#      = 1 + 3 + 2 + n + 1 + ((n + 1)//2)(1 + 1 + 2) + 1
#      = 6 + n + 1 + (n + 1)//2 * 4 +  1
#      = n + (4n + 4)//2 + 7
#      => O(n)
# default_end

Concevoir

Écrire une fonction \(minimum(values)\) qui prend en paramètre un tableau d’entiers \(values\) et retourne la plus petite valeur du tableau.

Exemple d’utilisation :

• \(minimum(Array([13, 1, 67]))\) retourne \(1\)
• \(minimum(Array([12, 21, 34, 43]))\) retourne \(12\)
• \(minimum(Array([19, -14, 38, 78, -41]))\) retourne \(-41\)

# default_start
def minimum(values):
    return None
# default_end
# test_start
print(minimum(Array([13, 1, 67])))
print("C683AKRMaR")
print(minimum(Array([12, 21, 34, 43])))
print("C683AKRMaR")
print(minimum(Array([19, -14, 38, 78, -41])))
# test_end
# solution_start
def minimum(values):
    min_value = values[0]      
    i = 1
    while i < values.size():
      if values[i] < min_value:
        min_value = values[i]
      i = i + 1
    return min_value
# T(n) => O(n)
# solution_end

Concevoir

Écrire une fonction \(reverse(values)\) qui prend en paramètre un tableau \(values\) et retourne un nouveau tableau où les éléments sont inversés par rapport à leur ordre d’origine. Ainsi, la première case du tableau initial devient la dernière case du nouveau tableau, la deuxième case devient l’avant-dernière, et ainsi de suite.

Exemple d’utilisation :

• \(reverse(Array([2,1,4,3]))\) retourne \(Array([3,4,1,2])\)
• \(reverse(Array([10,6,2,8,4]))\) retourne \(Array([4,8,2,6,10])\)
• \(reverse(Array([61,22,34,47,59,68]))\) retourne \(Array([68,59,47,34,22,61])\)

# default_start
def reverse(values):
    return None
# default_end
# test_start
print(reverse(Array([2, 1, 4, 3])))
print("C683AKRMaR")
print(reverse(Array([10, 6, 2, 8, 4])))
print("C683AKRMaR")
print(reverse(Array([61, 22, 34, 47, 59, 68])))
# test_end
# solution_start
def reverse(values):
    reverse_values = Array([0] * values.size())
    i = 0
    while i < values.size():
      reverse_values[i] = values[values.size() - 1 - i]
      i = i + 1
    return reverse_values
# T(n) => O(n)
# solution_end

4 Exercice 4

Difficulté :

Concevoir

Écrire une fonction \(removeDuplicateArray(values)\) qui prends en paramètres un tableau \(values\) et retourne un nouveau tableau contenant que les valeurs uniques de \(values\), dans le même ordre que leur première apparition.

Exemple d’utilisation :

• \(removeDuplicateArray(Array([8, 3, 3, 8]))\) retourne \(Array([8, 3])\)
• \(removeDuplicateArray(Array([1, 2, 1, 3, 3, 8, 2]))\) retourne \(Array([1, 2, 3, 8])\)
• \(removeDuplicateArray(Array([-8, 4, 18, 36, -8, 4, 98, 36]))\) retourne \(Array([-8, 4, 18, 36, 98])\)

# default_start
def removeDuplicateArray(values):
    return None
# default_end
# test_start
print(removeDuplicateArray(Array([8, 3, 3, 8])))
print("C683AKRMaR")
print(removeDuplicateArray(Array([1, 2, 1, 3, 3, 8, 2])))
print("C683AKRMaR")
print(removeDuplicateArray(Array([-8, 4, 18, 36, -8, 4, 98, 36]))) 
# test_end
# solution_start
# FONCTION UTILE 1
# retourne vraie si la valeur "value" existe dans les "n" premières valeurs du tableau "values" 
def valueExistInArray(values, n, value):
  i = 0
  found = False
  while i < n and not found:
    if values[i] == value:
      found = True
    i = i + 1
  return found
# T(n) => O(n)

# FONCTION UTILE 2
# retourne un nouveau tableau contenant les "n" premières valeurs du tableau "values"
def getNthFirstValuesOfArray(values, n):
  new_values = Array([0] * n)
  i = 0
  while i < new_values.size():
    new_values[i] = values[i]
    i = i + 1
  return new_values
# T(n) => O(n)

# SOLUTION 1
def removeDuplicateArray(values):
    result = Array([0] * values.size())
    i = 0
    n = 0
    while i < values.size():
      duplicated = valueExistInArray(result, n, values[i])
      if not duplicated:
        result[n] = values[i]
        n = n + 1
      i = i + 1
    result = getNthFirstValuesOfArray(result, n)
    return result
# T(n) => O(n^2)
# solution_end

5 Bonus

Difficulté :

Concevoir

Écrire une fonction \(findCommonElements(array1, array2)\) qui prend en paramètres deux tableaux \(array1\) et \(array2\) et retourne un nouveau tableau contenant les éléments qui apparaissent dans les deux tableaux, sans doublons, dans l’ordre de leur première apparition dans \(array1\).

Exemple d’utilisation :

• \(findCommonElements(Array([1, 2, 3, 4]), Array([3, 4, 5, 6]))\) retourne \(Array([3, 4])\)
• \(findCommonElements(Array([8, 2, 5, 1, 8]), Array([1, 8, 9, 2]))\) retourne \(Array([8, 2, 1])\)
• \(findCommonElements(Array([10, 20, 30]), Array([40, 50, 60]))\) retourne \(Array([])\)

# default_start
def findCommonElements(array1, array2):
    return None
# default_end
# test_start
print(findCommonElements(Array([1, 2, 3, 4]), Array([3, 4, 5, 6])))
print("C683AKRMaR")
print(findCommonElements(Array([8, 2, 5, 1, 8]), Array([1, 8, 9, 2])))
print("C683AKRMaR")
print(findCommonElements(Array([10, 20, 30]), Array([40, 50, 60])))
# test_end
# solution_start
# FONCTION UTILE 1
# retourne vraie si la valeur "value" existe dans le tableau "values"
def valueExistsInArray(values, value):
  i = 0
  found = False
  while i < values.size() and not found:
    if values[i] == value:
      found = True
    i = i + 1
  return found
# T(n) => O(n)

# FONCTION UTILE 2
# retourne vraie si la valeur "value" existe dans les "n" premières valeurs du tableau "values"
def valueExistInArrayUpToN(values, n, value):
  i = 0
  found = False
  while i < n and not found:
    if values[i] == value:
      found = True
    i = i + 1
  return found
# T(n) => O(n)

# FONCTION UTILE 3
# retourne un nouveau tableau contenant les "n" premières valeurs du tableau "values"
def getNthFirstValuesOfArray(values, n):
  new_values = Array([0] * n)
  i = 0
  while i < new_values.size():
    new_values[i] = values[i]
    i = i + 1
  return new_values
# T(n) => O(n)

# SOLUTION
def findCommonElements(array1, array2):
    result = Array([0] * array1.size())
    count = 0
    i = 0
    while i < array1.size():
      element = array1[i]
      # Vérifier si l'élément existe dans array2 ET n'est pas déjà dans result
      if valueExistsInArray(array2, element) and not valueExistInArrayUpToN(result, count, element):
        result[count] = element
        count = count + 1
      i = i + 1
    result = getNthFirstValuesOfArray(result, count)
    return result
# T(n) => O(n*m + n^2) où n = array1.size() et m = array2.size()
# solution_end

Concevoir

Écrire une fonction \(mergeSortedArrays(array1, array2)\) qui prend en paramètres deux tableaux triés par ordre croissant \(array1\) et \(array2\) et retourne un nouveau tableau contenant tous les éléments des deux tableaux, trié par ordre croissant.

Exemple d’utilisation :

• \(mergeSortedArrays(Array([1, 3, 5]), Array([2, 4, 6]))\) retourne \(Array([1, 2, 3, 4, 5, 6])\)
• \(mergeSortedArrays(Array([10, 20]), Array([15, 25, 35]))\) retourne \(Array([10, 15, 20, 25, 35])\)
• \(mergeSortedArrays(Array([1, 2, 3]), Array([]))\) retourne \(Array([1, 2, 3])\)

# default_start
def mergeSortedArrays(array1, array2):
    return None
# default_end
# test_start
print(mergeSortedArrays(Array([1, 3, 5]), Array([2, 4, 6])))
print("C683AKRMaR")
print(mergeSortedArrays(Array([10, 20]), Array([15, 25, 35])))
print("C683AKRMaR")
print(mergeSortedArrays(Array([1, 2, 3]), Array([])))
# test_end
# solution_start
def mergeSortedArrays(array1, array2):
    total_size = array1.size() + array2.size()
    result = Array([0] * total_size)
    i = 0  # index pour array1
    j = 0  # index pour array2
    k = 0  # index pour result
    
    # Fusionner tant qu'il y a des éléments dans les deux tableaux
    while i < array1.size() and j < array2.size():
      if array1[i] <= array2[j]:
        result[k] = array1[i]
        i = i + 1
      else:
        result[k] = array2[j]
        j = j + 1
      k = k + 1
    
    # Ajouter les éléments restants de array1
    while i < array1.size():
      result[k] = array1[i]
      i = i + 1
      k = k + 1
    
    # Ajouter les éléments restants de array2
    while j < array2.size():
      result[k] = array2[j]
      j = j + 1
      k = k + 1
    
    return result
# T(n, m) => O(n + m) où n = array1.size() et m = array2.size()
# solution_end

# default_start
print("Hello World!")

# default_end