Exercices

Exercice 1

Comprendre

Quelle est la sortie de ce programme ?

# exercice: guess
# default_start
def mystere(values, target):
    start = 0
    end = len(values) - 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([1, 3, 7, 14, 28, 34, 45, 51], 67))
# test_end

# exercice: show
# default_start
def mystere(values, target):        # values=[1,3,7,14,28,34,45,51], target=67
  start = 0                         # start=0                          
  end = len(values) - 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([1, 3, 7, 14, 28, 34, 45, 51], 67))
# 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

# exercice: show
# default_start
def mystere(items):                     
    start = 0                         # 1 affectation
    end = len(values) - 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)\]

Exercice 2

Concevoir

Écrire une fonction \(twoSum(values, target)\) qui prend en paramètre une liste d’entiers \(values\) et un entier \(target\), et retourne une liste de deux indices tels que la somme des éléments situés à ces indices soit égale à \(target\). Si aucune paire d’indices ne satisfait cette condition, la fonction doit retourner une liste vide.

Exemple d’utilisation :

• \(twoSum([2, 7, 11, 15], 9)\) retourne \([0, 1]\) car \(values[0] + values[1] = 2 + 7 = 9\).
• \(twoSum([3, 2, 4], 6)\) retourne \([1, 2]\) car \(values[1] + values[2] = 2 + 4 = 6\).
• \(twoSum([3, 3], 6)\) retourne \([0, 1]\) car \(values[0] + values[1] = 3 + 3 = 6\).
• \(twoSum([1, 2, 3], 7)\) retourne \([]\) car aucune paire d’indices ne satisfait la condition.

# exercice: design 
# default_start
def twoSum(values, target):
    return None
# default_end
# test_start
print(twoSum([2, 7, 11, 15], 9))
print("C683AKRMaR") 
print(twoSum([3, 2, 4], 6))
print("C683AKRMaR")
print(twoSum([3, 3], 6))
print("C683AKRMaR")
print(twoSum([1, 2, 3], 7))
# test_end
# solution_start
def twoSum(values, target):
  i = 0
  while i < len(values):
    j = i + 1
    while j < len(values):
      if values[i] + values[j] == target:
        return [i, j]
      j = j + 1
    i = i + 1
  return []
  
def twoSum(values, target):
  result = []
  found = False
  i = 0
  while not found and i < len(values):
    j = i + 1
    while not found and j < len(values):
      if values[i] + values[j] == target:
        result = [i, j]
        found = True
      j = j + 1
    i = i + 1
  return result
# solution_end

Exercice 3

Concevoir

Écrire une fonction \(areIsomorphics(pairs1, pairs2)\) qui prend en paramètre deux dictionnaires \(pairs1\) et \(pairs2\) avec les mêmes clés et retourne un booléen indiquant si les deux dictionnaires sont isomorphes ou non. Deux dictionnaires sont isomorphes si chaque valeur de \(pairs1\) est associée à exactement une valeur de \(pairs2\) et chaque valeur de \(pairs2\) est associée à exactement une valeur de \(pairs1\). En d’autres termes, il doit exister une bijection entre les valeurs de \(pairs1\) et les valeurs de \(pairs2\) telle que les clés associées à ces valeurs soient les mêmes dans les deux dictionnaires.

Exemple d’utilisation :

• \(areIsomorphics(\{\q{x}: 1, \q{y}: 2, \q{z}: 1\}, \{\q{x}: \q{a}, \q{y}: \q{b}, \q{z}: \q{a}\})\) retourne \(True\) car il existe une bijection entre les valeurs de \(pairs1\) et les valeurs de \(pairs2\) telle que \(1\) est lié à \(a\) et \(2\) est lié à \(b\).
• \(areIsomorphics(\{\q{x}: 1, \q{y}: 2, \q{z}: 3\}, \{\q{x}: \q{a}, \q{y}: \q{b}, \q{z}: \q{a}\})\) retourne \(False\) car il n’existe pas de bijection entre les valeurs de \(pairs1\) et les valeurs de \(pairs2\) telle que \(1\) est lié à \(a\), \(2\) est lié à \(b\) et \(3\) est lié à \(a\).
• \(areIsomorphics(\{\q{sensor1}: True, \q{sensor2}: False, \q{sensor3}: True\}, \{\q{sensor1}: \q{on}, \q{sensor2}: \q{off}, \q{sensor3}: \q{on}\})\) retourne \(True\) car il existe une bijection entre les valeurs de \(pairs1\) et les valeurs de \(pairs2\) telle que \(True\) est lié à \(on\) et \(False\) est lié à \(off\).
• \(areIsomorphics(\{\q{sensor1}: True, \q{sensor2}: False, \q{sensor3}: False\}, \{\q{sensor1}: \q{on}, \q{sensor2}: \q{on}, \q{sensor3}: {off}\})\) retourne \(False\) car il n’existe pas de bijection entre les valeurs de \(pairs1\) et les valeurs de \(pairs2\) telle que \(True\) est lié à \(on\) et \(False\) est lié à \(on\) ou à \(off\).

# exercice: design 
# default_start
def areIsomorphics(pairs1, pairs2):
    return None
# default_end
# test_start
print(areIsomorphics({"x": 1, "y": 2, "z": 1}, {"x": "a", "y": "b", "z": "a"}))
print("C683AKRMaR")
print(areIsomorphics({"x": 1, "y": 2, "z": 3}, {"x": "a", "y": "b", "z": "a"}))
print("C683AKRMaR")
print(areIsomorphics({"sensor1": True, "sensor2": False, "sensor3": True}, {"sensor1": "on", "sensor2": "off", "sensor3": "on"}))
print("C683AKRMaR")
print(areIsomorphics({"sensor1": True, "sensor2": False, "sensor3": False}, {"sensor1": "on", "sensor2": "on",  "sensor3": "off"}))
# test_end
# solution_start
def areIsomorphics(pairs1, pairs2):
  isomorphic = True
  mapping = {}
  keys = pairs1.keys()
  i = 0
  while isomorphic and i < len(keys):
    key = keys[i]
    value1 = pairs1[key]
    value2 = pairs2[key]
    # check injectivity
    if value1 in mapping:
      if mapping[value1] != value2:
        isomorphic = False
    else:
      mapping[value1] = value2
    # check surjectivity
    if value2 in mapping:
      if mapping[value2] != value1:
        isomorphic = False
    else:
      mapping[value2] = value1
    i = i + 1
  return isomorphic
# solution_end

Exercice 4

Concevoir

Écrire une fonction \(getMaxSubSum(values)\) qui prend en paramètre une liste \(values\) et retourne la somme maximale parmi tous les sous-listes possibles de \(values\).

La fonction doit prendre en compte que la sous-liste 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é de la liste si cela maximise la somme.

Exemple d’utilisation :

• \(getMaxSubSum([0, 2, 47, 5, -5])\) retourne \(54\) car la sous-liste \([0, 2, 47, 5]\) a la somme maximale de \(54\).
• \(getMaxSubSum([1, 2, 3, -2, 5])\) retourne \(9\) car la sous-liste \([1, 2, 3, -2, 5]\) a la somme maximale de \(9\).
• \(getMaxSubSum([-1, -2, -3, -4])\) retourne \(-1\) car la sous-liste \([-1]\) a la somme maximale de \(-1\).
• \(getMaxSubSum([5, 4, 7])\) retourne \(16\) car la sous-liste \([5, 4, 7]\) a la somme maximale de \(16\).
• \(getMaxSubSum([8, -14, 7])\) retourne \(8\) car la sous-liste \([8]\) a la somme maximale de \(8\).

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

def getMaxSubSum(values):
    i = 0
    maxSubSum = getSubSum(values, 0, 1)
    while i < len(values):
      j = i
      while j < len(values):
        subSum  = getSubSum(values, i, j + 1)
        if subSum > maxSubSum:
          maxSubSum = subSum
        j = j + 1
      i = i + 1
    return maxSubSum

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

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

Exercice 5

Concevoir

Écrire une fonction \(getEquilibriumIndex(values)\) qui prend en paramètre une liste d’entiers \(values\) 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’une liste 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([-7, 1, 5, 2, -4, 3, 0])\) retourne \(3\) car la somme des éléments à gauche de l’indice \(3\) est égale à la somme des éléments à droite de l’indice \(3\) : \((-7) + 1 + 5 = (-4) + 3 + 0\).
• \(getEquilibriumIndex([1, 3, 3, 2, 2])\) retourne \(2\) car la somme des éléments à gauche de l’indice \(2\) est égale à la somme des éléments à droite de l’indice \(2\) : \(1 + 3 = 2 + 2\).
• \(getEquilibriumIndex([8, 4, 3, 1, 4])\) retourne \(-1\) car il n’existe pas d’indice d’équilibre dans ce tableau.
• \(getEquilibriumIndex([1, 1, 1, 1])\) retourne \(0\) car la somme des éléments à gauche de l’indice \(0\) est égale à la somme des éléments à droite de l’indice \(0\) : \(0 = 1 + 1 + 1\).
• \(getEquilibriumIndex([1, 2, 3])\) retourne \(-1\) car il n’existe pas d’indice d’équilibre dans ce tableau.

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

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

Exercice 6

Concevoir

Écrire une fonction \(getLongestKeysChain(pairs)\) qui prend en paramètre un dictionnaire \(pairs\) et retourne la longueur de la plus longue chaîne de clés du dictionnaire. Une chaîne de clés est une séquence de clés telles que chaque clé est une sous-chaîne de la clé suivante.

Exemple d’utilisation :

• \(getLongestKeysChain(\{\q{a}: [\q{at}, \q{ab}], \q{at}: [\q{ate}], \q{ab}: [\q{abc}], \q{ate}: [], \q{abc}: []\})\) retourne \(3\) car la chaîne de clés la plus longue est \([\q{a}, \q{at}, \q{ate}]\) ou \([\q{a}, \q{ab}, \q{abc}]\).
• \(getLongestKeysChain(\{\q{x}: [\q{xy}], \q{y}: [\q{yz}], \q{z}: []\})\) retourne \(1\) car la chaîne de clés la plus longue est \([\q{x}]\) ou \([\q{y}]\) ou \([\q{z}]\).
• \(getLongestKeysChain(\{\q{a}: [\q{b}], \q{b}: [\q{c}], \q{c}: [\q{d}], \q{d}: []\})\) retourne \(4\) car la chaîne de clés la plus longue est \([\q{a}, \q{b}, \q{c}, \q{d}]\).

# exercice: design 
# default_start
def getLongestKeysChain(pairs):
    return None
# default_end
# test_start
print(getLongestKeysChain({"a": ["at", "ab"], "at": ["ate"], "ab": ["abc"], "ate": [], "abc": []}))
print("C683AKRMaR")
print(getLongestKeysChain({"x": ["xy"], "y": ["yz"], "z": []}))
print("C683AKRMaR")
print(getLongestKeysChain({"a": ["b"], "b": ["c"], "c": ["d"], "d": []}))
# test_end
# solution_start
def getChainLength(pairs, key):
  if key not in pairs:
    return 0
  max_length = 0
  i = 0
  while i < len(pairs[key]):
    length = getChainLength(pairs, pairs[key][i])
    if length > max_length:
      max_length = length
    i = i + 1
  return max_length + 1

def getLongestKeysChain(pairs):
  longest_chain_length = 0
  for key in pairs:
    chain_length = getChainLength(pairs, key)
    if chain_length > longest_chain_length:
      longest_chain_length = chain_length
  return longest_chain_length
# solution_end

# default_start
print("Hello World!")

# default_end