Exercices

1 Exercice 1

Difficulté :

Comprendre

Quelle est la sortie de ce programme ?

# exercice: guess
# default_start
def mystere(values, target):
    start = 0
    end = values.size() - 1
    found = False
    while start <= end and not found:
        middle = (start + end) // 2
        middle_value = values[middle]
        if middle_value == target:
            found = True
        elif middle_value < target:
            start = middle + 1
        else:
            end = middle - 1
    return found
# default_end
# test_start
print(mystere(Array([1, 3, 7, 14, 28, 34, 45, 51]), 67))
# test_end

# exercice: show
# default_start
def mystere(values, target):        # values=Array([1,3,7,14,28,34,45,51]), target=67
  start = 0                         # start=0                          
  end = values.size() - 1           # end=7
  found = False                     # found=False                    
  while start <= end and not found: # 0<=7 and True    4<=7 and True    6<=7 and True   7<=7 and True     8<=8
      middle = (start + end) // 2   # middle=3         middle=5         middle=6        middle=7                
      middle_value = values[middle] # middle_value=14  middle_value=34  middle_value=45 middle_value=51
      if middle_value == target:    # 14==67           34==67           45==67          51==67          
          found = True              #                                                  
      elif middle_value < target:   # 14<67            34<67            45<67           51<67                         
          start = middle + 1        # start=4          start=6          start=7         start=8  
      else:                         # 14>67            34>67            45>67                                             
          end = middle - 1          #                     
  return found                      #                                                                     False
print(mystere(Array([1, 3, 7, 14, 28, 34, 45, 51]), 67))
# default_end

Analyser

Quelle est la complexité en temps de la fonction mystere ?

• \(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

# exercice: show
# default_start
def mystere(items):                     
    start = 0                         # 1 affectation
    end = values.size() - 1           # 1 affectation + 1 soustraction
    found = False                     # 1 affectation 
    # log2(items.size()) iterations jusqu'à ce que start > end (voir démonstration ci-dessous)
    while start <= end:                 # 1 comparaison
        middle = (start + end) // 2     # 1 affectation + 1 addition + 1 division
        middle_value = values[middle]   # 1 affectation
        if middle_value == target:      # 1 comparaison
            found = True                # 1 affectation
        elif middle_value < target:     # 1 comparaison
            start = middle + 1          # 1 affectation + 1 soustraction
        else:                           # 1 comparaison
            end = middle - 1            # 1 affectation + 1 soustraction
    return found                        # 1 affectation
# n = items.size()
# T(n) = 1 + 2 + 1 + log2(n) * (1 + 3 + 1 + max(2, 4, 4)) + 1
# T(n) = 4 + log2(n) * (5 + 4) + 1
# T(n) = 9log2(n) + 5 
# T(n) => O(logn)
# default_end

L’algorithme ci-dessus divise la taille du tableau par deux à chaque iteration. En effet, La longueur de la partie du tableau comprise entre \(start\) et \(end\) est d’abord \(n\), puis \(n/2\), puis \(n/4\), puis \(n/8\), …, jusqu’à ce que \(n/2^t = 1\).

• Le nombre d’itérations est donc un entier \(t\) tel que \(n/2^t = 1\).
• A ce stade il est nécessaire d’introduire une nouvelle notion mathématique : le “logarithme base 2” noté \(log2\). Par définition, \(log2(2^x)=x\).
• On a donc:

\[n/2^t = 1\] \[2^t = n\] \[log_2(2^t) = log_2(n)\] \[t = log_2(n)\]

2 Exercice 2

Difficulté :

Concevoir

Écrire une fonction \(sort(array)\) qui prend en paramètre un tableau \(array\) et retourne un nouveau tableau contenant les valeurs du tableau \(array\) ordonnées par ordre croissant.

Exemple d’utilisation :

• \(sort(Array([8, 14, 7]))\) retourne \(Array([7, 8, 14])\)
• \(sort(Array([ 0, 2, 47, 5, -5]))\) retourne \(Array([-5, 0, 2, 5, 47])\)

Votre réponse

# exercice: design 
# default_start
def sort(array):
    return None
# default_end
# test_start
print(sort(Array([8, 14, 7])))
print("C683AKRMaR")
print(sort(Array([0, 2, 47, 5, -5])))
# test_end
# solution_start
# SELECTION SORT -> worst: O(n²), best: O(n²) [Algorithme lent]
def selectionSort(array):
  n = array.size()
  i = 0
  while i < n - 1:
    min_i = i
    j = i
    while j < n:
      if array[j] < array[min_i]:
        min_i = j
      j = j + 1
    if min_i != i:
      tmp = array[min_i]
      array[min_i] = array[i]
      array[i] = tmp
    i = i + 1
  return array

# BUBBLE SORT -> worst: O(n²), best: O(n) [Algorithme moyennement rapide]
def bubbleSort(array):
  i = 0
  while i < array.size():
    j = 0
    while j < array.size() - i - 1:
      if array[j] > array[j + 1]:
        tmp = array[j]
        array[j] = array[j + 1]
        array[j + 1] = tmp
      j = j + 1
    i = i + 1
  return array

# INSERTION SORT -> worst: O(n²), best: O(n) [Algorithme moyennement rapide]
def insertionSort(array):
  i = 1
  while i < array.size():
    key = array[i]
    j = i - 1
    while j >= 0 and key < array[j]:
      array[j + 1] = array[j]
      j = j - 1
    array[j + 1] = key
    i = i + 1
  return array

# MERGE SORT -> worst: O(nlogn), best: O(nlogn) [Algorithme rapide]
def slicing(array1, start, end):
    new_size = end - start
    new_arr = Array([0] * new_size)
    i = 0
    while i < new_size:
        new_arr[i] = array1[start + i]
        i = i + 1
    return new_arr
    
def concatenate(array1, array2):
    new_size = array1.size() + array2.size()
    new_arr = Array([0] * new_size)
    i = 0
    while i < array1.size():
        new_arr[i] = array1[i]
        i = i + 1
    i = 0
    while i < array2.size():
        new_arr[array1.size() + i] = array2[i]
        i = i + 1
    return new_arr

def merge(array1, array2):
    new_size = array1.size() + array2.size()
    new_arr = Array([0] * new_size)
    i = 0
    j = 0
    k = 0
    while i < array1.size() and j < array2.size():
        if array1[i] <= array2[j]:
            new_arr[k] = array1[i]
            i = i + 1
            k = k + 1
        else:
            new_arr[k] = array2[j]
            j = j + 1
            k = k + 1
    new_arr = slicing(new_arr, 0, k)
    new_arr = concatenate(new_arr, slicing(array1, i, array1.size()))
    new_arr = concatenate(new_arr, slicing(array2, j, array2.size()))
    return new_arr
    
def mergeSort(array):
    ans = array
    if array.size() > 1:
        mid_size = array.size()//2
        left_arr = slicing(array, 0, mid_size)
        right_arr = slicing(array, mid_size, array.size())
        ans = merge(mergeSort(left_arr), mergeSort(right_arr))
    return ans
    
def sort(array):
  return mergeSort(array)
# solution_end

3 Exercice 3

Difficulté :

Concevoir

Écrire une fonction \(getMaximumSubarraySum(array)\) qui prend en paramètre un tableau \(array\) et retourne la somme maximale parmi tous les sous-tableaux possibles de \(array\).

La fonction doit prendre en compte que le sous-tableau peut être constitué d’un seul élément dans le cas où tous les éléments sont négatifs, ou bien il peut s’agir de la totalité du tableau si cela maximise la somme.

Exemple d’utilisation :

• \(getMaximumSubarraySum(Array([0, 2, 47, 5, -5]))\) retourne \(54\) car \(Array([0, 2, 47, 5])\) est le sous-tableau avec la somme maximale.
• \(getMaximumSubarraySum(Array([1, 2, 3, -2, 5]))\) retourne \(9\) car \(Array([1, 2, 3, -2, 5])\) est le sous-tableau avec la somme maximale.
• \(getMaximumSubarraySum(Array([-1, -2, -3, -4]))\) retourne \(-1\) car \(Array([-1])\) est le sous-tableau avec la somme maximale.
• \(getMaximumSubarraySum(Array([5, 4, 7]))\) retourne \(16\) car \(Array([5, 4, 7])\) est le sous-tableau avec la somme maximale.
• \(getMaximumSubarraySum(Array([8, -14, 7]))\) retourne \(8\) car \(Array([8])\) est le sous-tableau avec la somme maximale.

Votre réponse

# exercice: design 
# default_start
def getMaximumSubarraySum(array):
    return None
# default_end
# test_start
print(getMaximumSubarraySum(Array([0, 2, 47, 5, -5])))
print("C683AKRMaR")
print(getMaximumSubarraySum(Array([1, 2, 3, -2, 5])))
print("C683AKRMaR")
print(getMaximumSubarraySum(Array([-1, -2, -3, -4])))
print("C683AKRMaR")
print(getMaximumSubarraySum(Array([5, 4, 7])))
print("C683AKRMaR")
print(getMaximumSubarraySum(Array([8, -14, 7])))
# test_end
# solution_start
# SOLUTION 1 : Force brute => O(n**3) 
def getSubarraySum(array, start, end):
    res = 0
    i = start
    while i < end:
      res = res + array[i]
      i = i + 1
    return res

def getMaximumSubarraySum(array):
    i = 0
    maxSubarraySum = getSubarraySum(array, 0, 1)
    while i < array.size():
      j = i
      while j < array.size():
        subarraySum  = getSubarraySum(array, i, j + 1)
        if subarraySum > maxSubarraySum:
          maxSubarraySum = subarraySum
        j = j + 1
      i = i + 1
    return maxSubarraySum

# SOLUTION 2 : Algorithme de Kadane => OPTIMAL => O(n)
def maximum(a, b):
  res = a
  if b > a:
    res = b
  return res

def getMaximumSubarraySum(array):
  best_sum = array[0]
  current_sum = 0
  i = 0
  while i < array.size():
    current_sum = maximum(array[i], current_sum + array[i])
    best_sum = maximum(best_sum, current_sum)
    i = i + 1
  return best_sum
# solution_end

4 Exercice 4

Difficulté :

Concevoir

Écrire une fonction \(getEquilibriumIndex(array)\) qui prend en paramètre un tableau d’entiers \(array\) et retourne un indice d’équilibre (s’il existe) ou \(-1\) s’il n’existe pas d’indice d’équilibre.

L’indice d’équilibre d’un tableau est un indice tel que la somme des éléments situés à des indices inférieurs est égale à la somme des éléments situés à des indices supérieurs.

Exemple d’utilisation :

• \(getEquilibriumIndex(Array([-7, 1, 5, 2, -4, 3, 0]))\) retourne \(3\).
• \(getEquilibriumIndex(Array([1, 3, 3, 2, 2]))\) retourne \(2\).
• \(getEquilibriumIndex(Array([8, 4, 3, 1, 4]))\) retourne \(1\).
• \(getEquilibriumIndex(Array([1, 1, 1, 1]))\) retourne \(-1\).
• \(getEquilibriumIndex(Array([1, 2, 3]))\) retourne \(-1\).

Votre réponse

# exercice: design 
# default_start
def getEquilibriumIndex(array):
    return None
# default_end
# test_start
print(getEquilibriumIndex(Array([-7, 1, 5, 2, -4, 3, 0])))
print("C683AKRMaR")
print(getEquilibriumIndex(Array([1, 3, 3, 2, 2])))
print("C683AKRMaR")
print(getEquilibriumIndex(Array([8, 4, 3, 1, 4])))
print("C683AKRMaR")
print(getEquilibriumIndex(Array([1, 1, 1, 1])))
print("C683AKRMaR")
print(getEquilibriumIndex(Array([1, 2, 3])))
# test_end
# solution_start
# SOLUTION 1: force brute => O(n²)
def getEquilibriumIndex(array):
  i = 1
  equilibrium_index = -1
  while i < array.size() and equilibrium_index == -1:
    left_sum = 0
    j = 0
    while j < i:
      left_sum = left_sum + array[j]
      j = j + 1
    right_sum = 0
    k = i + 1
    while k < array.size():
      right_sum = right_sum + array[k]
      k = k + 1
    if left_sum == right_sum:
      equilibrium_index = i
    i = i + 1
  return equilibrium_index


# SOLUTION 2: Optimale => O(n)
def getSum(array):
    res = 0
    i = 0
    while i < array.size():
      res = res + array[i]
      i = i + 1
    return res

def getEquilibriumIndex(array):
  total_sum = getSum(array)
  left_sum = 0
  i = 0
  equilibrium_index = -1
  while i < array.size() and equilibrium_index == -1:
    right_sum = total_sum - array[i] - left_sum
    if left_sum == right_sum:
      equilibrium_index = i
    left_sum = left_sum + array[i]
    i = i + 1
  return equilibrium_index
# solution_end

# default_start
print("Hello World!")

# default_end