Listes - Exercices

1 Exercice 1

Difficulté :

Comprendre

Quelle est la sortie de ce programme ?

# exercice: guess
# default_start
def mystere(items, item1, item2):
    items.insert(0, item1)
    items.insert(items.size(), item2)
    return items
# default_end
# test_start
print(mystere(List([1, 2, 1, 4]), 2, 1))
print("C683AKRMaR")
print(mystere(List([3, 5, 3]), 4, 3))
print("C683AKRMaR")
print(mystere(List([6, 7, 8, 9]), 5, 6))
# test_end

# exercice: show
# default_start
def mystere(items, item1, item2):     # items=List([1, 2, 1, 4]) item1=2 item2=1
    items.insert(0, item1)            # items=List([2, 1, 2, 1, 4])
    items.insert(items.size(), item2) # items=List([2, 1, 2, 1, 4, 1])
    return items                      # List([2, 1, 2, 1, 4, 1])

print(mystere(List([1, 2, 1, 4]), 2, 1))   
# 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, item1, item2):     
    items.insert(0, item1)              # O(items.size()) insertion 
    items.insert(items.size(), item2)   # O(items.size()) insertion 
    return items                        # 1 retour
# n = items.size()
# T(n) = O(n) + O(n) + 1 
#      = n + n + 1
#      = 2n + 1 
#      => O(n)
# default_end

Concevoir

Écrire une fonction \(moveItem(items, index1, index2)\) qui prends en paramètres une liste \(items\) et deux entiers \(index1\) et \(index2\). La fonction doit déplacer l’élément de la liste se trouvant à l’indice \(index1\) vers l’indice \(index2\), tout en maintenant l’ordre des autres éléments. La liste \(items\) modifiée doit ensuite être retournée.

Exemples d’utilisation:

• \(moveItem(List([1,3,2,5,4]), 1, 3)\) retourne \(List([1, 2, 5, 3, 4])\)
• \(moveItem(List([6,9,7,8,1,2]), 3, 0)\) retourne \(List([8, 6, 9, 7, 1, 2])\)
• \(moveItem(List([3,2,6,9,7,8,1]), 4, 6)\) retourne \(List([3, 2, 6, 9, 8, 1, 7])\)

Votre réponse

# exercice: design 
# default_start
def moveItem(items, index1, index2):
    return None
# default_end
# test_start
print(moveItem(List([1, 3, 2, 5, 4]), 1, 3))
print("C683AKRMaR")
print(moveItem(List([6, 9, 7, 8, 1, 2]), 3, 0))
print("C683AKRMaR")
print(moveItem(List([3, 2, 6, 9, 7, 8, 1]), 4, 6))
# test_end
# solution_start
def moveItem(items, index1, index2):
    item = items.remove(index1)
    items.insert(index2, item)
    return items
# T(n) => O(n)
# solution_end

2 Exercice 2

Difficulté :

Comprendre

Quelle est la sortie de ce programme ?

# exercice: guess
# default_start
def mystere(items):
    item = items.dequeue()
    items.enqueue(item)
    return items
# default_end
# test_start
print(mystere(Queue([1, 2, 3, 4])))
print("C683AKRMaR")
print(mystere(Queue([-1, 7, 3, 0])))
print("C683AKRMaR")
print(mystere(Queue([14, 9, 8, 6, 5])))
# test_end

# exercice: show
# default_start
def mystere(items):         # items=Queue([1, 2, 3, 4])
    item = items.dequeue()  # item=1, items=Queue([2, 3, 4])
    items.enqueue(item)     # items=Queue([2, 3, 4, 1])
    return items            # Queue([2, 3, 4, 1])

print(mystere(Queue([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

# exercice: show
# default_start
def mystere(items):                 
    item = items.dequeue()  # 1 affectation + 1 défilement
    items.enqueue(item)     # 1 enfilement
    return items            # 1 retour
# T(n) = 2 + 1 + 1
#      = 4 
#      => O(1)
# default_end

Concevoir

Écrire une fonction \(removeAndAddTwo(items, item1, item2)\) qui prends en paramètres une file \(items\) et deux élements \(item1\) et \(item2\). La fonction doit :

• enlever les deux premiers éléments du début de la file \(items\);
• ajouter \(item1\) et \(item2\) à la fin de file \(items\) si \(item1\) et \(item2\) sont tous les deux strictement plus grands que les deux premiers éléments qui viennent d’être enlevés;
• retourner la file \(items\) modifiée.

Exemples d’utilisation:

• \(removeAndAddTwo(Queue([1,2,3,4]), 6, 7)\) retourne \(Queue([3, 4, 6, 7])\)
• \(removeAndAddTwo(Queue([1,2,3,4]), 0, 3)\) retourne \(Queue([3, 4])\)
• \(removeAndAddTwo(Queue([5,6,7,8,9]), 8, 7)\) retourne \(Queue([7, 8, 9, 8, 7])\)
• \(removeAndAddTwo(Queue([5,6,7,8,9]), 7, 4)\) retourne \(Queue([7, 8, 9])\)
• \(removeAndAddTwo(Queue([9,5,7,3,6,2,0,1]), 11, 10)\) retourne \(Queue([7, 3, 6, 2, 0, 1, 11, 10])\)
• \(removeAndAddTwo(Queue([9,5,7,3,6,2,0,1]), 2, 3)\) retourne \(Queue([7, 3, 6, 2, 0, 1])\)

Votre réponse

# exercice: design 
# default_start
def removeAndAddTwo(items, item1, item2):
    return None
# default_end
# test_start
print(removeAndAddTwo(Queue([1, 2, 3, 4]), 6, 7))
print("C683AKRMaR")
print(removeAndAddTwo(Queue([1, 2, 3, 4]), 0, 3))
print("C683AKRMaR")
print(removeAndAddTwo(Queue([5, 6, 7, 8, 9]), 8, 7))
print("C683AKRMaR")
print(removeAndAddTwo(Queue([5, 6, 7, 8, 9]), 7, 4))
print("C683AKRMaR")
print(removeAndAddTwo(Queue([9, 5, 7, 3, 6, 2, 0, 1]), 11, 10))
print("C683AKRMaR")
print(removeAndAddTwo(Queue([9, 5, 7, 3, 6, 2, 0, 1]), 2, 0))
# test_end
# solution_start
def removeAndAddTwo(items, item1, item2):
    firstItem = items.dequeue()
    secondItem = items.dequeue()
    if item1 > firstItem and item1 > secondItem and item2 > firstItem and item2 > secondItem:
        items.enqueue(item1)
        items.enqueue(item2)
    return items
# T(n) => O(1)
# solution_end

3 Exercice 3

Difficulté :

Comprendre

Quelle est la sortie de ce programme ?

# exercice: guess
# default_start
def mystere(items, pos):
    i = 0
    item = None
    while items.size() > 0 and i <= pos:
        item = items.destack()
        i = i + 1
    return item
# default_end
# test_start
print(mystere(Stack([1, 2, 3, 4]), 1))
print("C683AKRMaR")
print(mystere(Stack([-5, 6, -7, 8, -9]), 0))
print("C683AKRMaR")
print(mystere(Stack([10, 20, 30, 40, 50, 60]), 5))
# test_end

# exercice: show
# default_start
def mystere(items, pos):                    # items=Stack([1,2,3,4]) pos=1
    i = 0                                   # i = 0
    item = None                             # item = None
    while items.size() > 0 and i <= pos:    # 4 > 0 and 0 <= 1             3 > 0 and 1 <= 1           2 > 0 and 2 <= 1
        item = items.destack()              # item=4, items=Stack([1,2,3]) item=3, items=Stack([1,2])
        i = i + 1                           # i = 1                        i = 2
    return item                             #                                                         3

print(mystere(Stack([1,2,3,4]), 1))
# 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, pos):                 
    i = 0                                   # 1 affectation
    item = None                             # 1 affectation
    # Boucle:
    #   Dans le pire des cas, il y a items.size() iterations avant que items.size() <= 0 ou que i > pos
    while items.size() > 0 and i <= pos:        # 1 comparaison + 1 comparaison
        item = items.destack()                  # 1 affectation + 1 dépilement
        i = i + 1                               # 1 affectation + 1 addition
    return item                             # 1 retour
# n = items.size()
# T(n) = 1 + 1 + n * (2 + 2 + 2) + 1 = 6n + 3 = O(n)
# default_end

Concevoir

Écrire une fonction \(firstStack(items)\) qui prend en paramètre une pile \(items\) et retourne le dernier élément de la pile.

Exemple d’utilisation :

• \(firstStack(Stack([3,1,2]))\) retourne \(3\)
• \(firstStack(Stack([6,7,4,5]))\) retourne \(6\)
• \(firstStack(Stack([9,7,8,11,10]))\) retourne \(9\)

Votre réponse

# exercice: design 
# default_start
def firstStack(items):
    return None
# default_end
# test_start
print(firstStack(Stack([3, 1, 2])))
print("C683AKRMaR")
print(firstStack(Stack([6, 7, 4, 5])))
print("C683AKRMaR")
print(firstStack(Stack([9, 7, 8, 11, 10])))
# test_end
# solution_start
def firstStack(items):
    first = items.head()
    while items.size() > 0:
        first = items.destack()
    return first
# T(n) => O(n)
# solution_end

4 Exercice 4

Difficulté :

Comprendre

Quelle est la sortie de ce programme ?

# exercice: guess
# default_start
def mystere(items, item):
    new_items = List()
    i = 0
    while i < items.size():
        if items.get(i) != item:
            new_items.insert(new_items.size(), items.get(i))
        i = i + 1
    return new_items
# default_end
# test_start
print(mystere(List([1, 2, 1, 4]), 1))
print("C683AKRMaR")
print(mystere(List([3, 5, 3, 7]), 3))
print("C683AKRMaR")
print(mystere(List([6, 7, 8, 9]), 10))
# test_end

# exercice: show
# default_start
def mystere(items, item):        # items=List([1,2,1,4]), item=1
    new_items = List()           # new_items=List([])
    i = 0                        # i=0
    while i < items.size():      # 0<4              1<4                 2<4              3<4                      4<4
        if items.get(i) != item: # items.get(0)!=1  items.get(1)!=1     items.get(2)!=1  items.get(3)!=1         
                                 # 1!=1             2!=1                1!=1             4!=1
            new_items.insert(    # 
                new_items.size(),#                  0                                    1
                items.get(i)     #                  2                                    4
            )                    #                  new_items=List([2])                  new_items=List([2, 4])
        i = i + 1                # i=1              i=2                 i=3              i=4
    return new_items             #                                                                                List([2, 4])

print(mystere(List([1,2,1,4]), 1))
# 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, item):    
    new_items = List()                                          # 1 affectation
    i = 0                                                       # 1 affectation
    # Boucle:
    #   items.size() itérations (de i=0 à i=items.size()-1 avec pas de 1)
    while i < items.size():                                         # 1 comparaison
        if items.get(i) != item:                                    # 1 comparaison        
            new_items.insert(new_items.size(), items.get(i))        # O(new_items.size()) insertion
            # Problème:
            #   que vaut new_items.size() en fonction des données en entrée (items) ?
            # Réponse:
            #  i = 0                => new_items.size() = 0
            #  i = 1                => new_items.size() = 1
            #  i = 2                => new_items.size() = 2
            #  ...
            #  i = items.size() - 2 => new_items.size() = items.size() - 2
            #  i = items.size() - 1 => new_items.size() = items.size() - 1
            # Observation:
            #  Il s'agit de  la somme des n premiers entiers naturels, on peut donc écrire :
            #       S = 0 + 1 + 2 + ... + (items.size() - 1)
            #  On peut aussi écrire :
            #       S = (items.size() - 1) + (items.size() - 2) + ... + 1 + 0
            # Si on additionne membre à membre les deux égalités, on obtient:
            #   2 * S = (items.size() - 1 + 0) + (items.size() - 2 + 1) + ... + (1 + items.size() - 2) + (0 + items.size() - 1)
            #   2 * S = (items.size() - 1) + (items.size() - 1) + ... + (items.size() - 1) + (items.size() - 1)
            #   2 * S = items.size() * (items.size() - 1)
            #   S = items.size() * (items.size() - 1) / 2
            #   S = 0.5 * items.size()² - 0.5 * items.size()
            #   => O(len(items)²) insertion au total quand toute la boucle while a terminée
        i = i + 1                                                   # 1 affectation + 1 addition
    return new_items                                            # 1 retour
# n = items.size()
# T(n) = 1 + 1 + n * (1 + 1 + 2) + O(n²) + 1
#      = 2 + n * 4 + O(n²) + 1
#      = 3 + 4n + O(n²)
#      = 3 + 4n + n²
#      => O(n²)

# default_end

Concevoir

Écrire une fonction \(sliceList(items, start, end)\) qui prend en paramètre un liste \(items\) et deux entier \(start\) et \(end\) et retourne une nouvelle liste contenant les élements de la liste \(items\) allant de l’indice \(start\) inclus à l’indice \(end\) exclus.

Exemple d’utilisation :

• \(sliceList(List([0,8,-4,7]), 1, 3)\) retourne \(List([8, -4])\)
• \(sliceList(List([8,-3,5,9,-1]), 0, 4)\) retourne \(List([8,-3,5,9])\)
• \(sliceList(List([11,20,53,42,64,75]), 2, 5)\) retourne \(List([53,42,64])\)

Votre réponse

# exercice: design 
# default_start
def sliceList(items, start, end):
    return None
# default_end
# test_start
print(sliceList(List([0, 8, -4, 7]), 1, 3))
print("C683AKRMaR")
print(sliceList(List([8, -3, 5, 9, -1]), 0, 4))
print("C683AKRMaR")
print(sliceList(List([11, 20, 53, 42, 64, 75]), 2, 5))
# test_end
# solution_start
def sliceList(items, start, end):
    new_items = List()
    i = start
    while i < end:
      new_items.insert(new_items.size(), items.get(i))
      i = i + 1
    return new_items
# T(n) => O(n)
# solution_end

5 Bonus

Difficulté :

Comprendre

Quelle est la sortie de ce programme ?

# exercice: guess
# default_start
def mystere(items):
    new_items = List()
    i = 0
    while i < items.size():
        new_items.insert(new_items.size(), items.get(i))
        i = i + 1
    i = 0
    while i < items.size():
        new_items.insert(0, items.get(i))
        i = i + 1
    return new_items
# default_end
# test_start
print(mystere(List([1, 2, 3])))
print("C683AKRMaR")
print(mystere(List([4, 5])))
print("C683AKRMaR")
print(mystere(List([6, 7, 8, 9])))
# test_end

# exercice: show
# default_start
def mystere(items):           # items=List([1,2,3])
    new_items = List()        # new_items=List([])
    i = 0                     # i=0
    while i < items.size():   # 0<3               1<3                    2<3                 3<3             
        new_items.insert(      
            new_items.size(), # 0                 1                      2                   
            items.get(i)      # 1                 2                      3                   
        )                     # new_items=List([  new_items=List([       new_items=List([    
                              # 1                  1, 2                   1, 2, 3             
                              # ])                ])                     ])                  
        i = i + 1             # i=1               i=2                    i=3                 
    i = 0                     # i=0
    while i < items.size():   # 0<3               1<3                    2<3                 3<3             
        new_items.insert(
            0,                # 0                 0                      0                   
            items.get(i)      # 1                 2                      3                   
        )                     # new_items=List([  new_items=List([       new_items=List([    
                              #  1, 1, 2, 3        2, 1, 1, 2, 3          3, 2, 1, 1, 2, 3                
                              # ])                ])                     ])                  
        i = i + 1             # i=1               i=2                    i=3                 
    return new_items          #                                                              List([3, 2, 1, 1, 2, 3])

print(mystere(List([1,2,3]), 1))
# 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, item):
    new_items = List()                                   # 1 affectation
    i = 0                                                # 1 affectation
    # Boucle 1:
    # items.size() iterations de i=0 jusqu'à i>=items.size() avec pas de 1
    # => items.size() itérations
    while i < items.size():                                 # 1 comparaison
        new_items.insert(new_items.size(), items.get(i))    # O(new_items.size()) insertion
        # Problème:
        #   que vaut new_items.size() en fonction des données en entrée (items) ?
        # Réponse:
        #  i = 0                => new_items.size() = 0
        #  i = 1                => new_items.size() = 1
        #  i = 2                => new_items.size() = 2
        #  ...
        #  i = items.size() - 2 => new_items.size() = items.size() - 2
        #  i = items.size() - 1 => new_items.size() = items.size() - 1
        # Observation:
        #  Il s'agit de la suite arithmétique 0, 1, 2, ..., n - 1
        #  La somme de cette suite est égale à (n - 1) * n / 2 
        # Finalement:
        #  Après items.size() itérations, les insertions auront coûté:
        #   = (items.size() - 1) * items.size() / 2
        #   = 0.5 * items.size()² - 0.5 * items.size()
        #   => O(items.size()²) instructions
        i = i + 1                                           # 1 affectation + 1 addition
    i = 0                                                   # 1 affectation
    # Boucle 2:
    #   items.size() iterations de i=0 jusqu'à i>=items.size() avec pas de 1
    #   => items.size() itérations
    while i < items.size():                                 # 1 comparaison
        new_items.insert(0, items.get(i))                   # 1 insertion O(n)
        # Même problème que précédemment. On retrouve la même suite arithmétique.
        # Après items.size() itérations, les insertions auront coûté:
        #   = (items.size() - 1) * items.size() / 2
        #   = 0.5 * items.size()² - 0.5 * items.size()
        #   => O(items.size()²) instructions
        i = i + 1                                           # 1 affectation + 1 addition
    return new_items                                        # 1 retour
# n = items.size()
# T(n) = 1 + 1 + n * (1 + 2) + O(n²) + 1 + n * (1 + 2) + O(n²) + 1
#      = 2 + n * 3 + O(n²) + 1 + n * 3 + O(n²) + 1
#      = 4 + 6n + 2 * O(n²)
#      = 4 + 6n + 2 * n²
#      = 2n² + 6n + 4
#      => O(n²)
# default_end

Concevoir

Écrire une fonction \(emptyIntoList(stack1, queue1)\) qui prend en paramètre une pile \(stack1\) et une file \(queue1\) et retourne une liste contenant les éléments de la pile \(stack1\) suivis des éléments de la file \(queue1\)

Exemple d’utilisation :

• \(emptyIntoList(Stack([1,2,3]), Queue([4,5,6]))\) retourne \(List([1, 2, 3, 4, 5, 6])\)
• \(emptyIntoList(Stack([7,8,9,10,11]), Queue([12,13,14]))\) retourne \(List([7, 8, 9, 10, 11, 12, 13, 14])\)
• \(emptyIntoList(Stack([15,16,17,18]), Queue([19,20,21,22,23,24]))\) retourne \(List([15, 16, 17, 18, 19, 20, 21, 22, 23, 24])\)

Votre réponse

# exercice: design 
# default_start
def emptyIntoList(stack1, queue1):
    return None
# default_end
# test_start
print(emptyIntoList(Stack([1, 2, 3]), Queue([4, 5, 6])))
print("C683AKRMaR")
print(emptyIntoList(Stack([7, 8, 9, 10, 11]), Queue([12, 13, 14])))
print("C683AKRMaR")
print(emptyIntoList(Stack([15, 16, 17, 18]), Queue([19, 20, 21, 22, 23, 24])))
# test_end
# solution_start
def emptyIntoList(stack1, queue1):
    items = List([])
    while stack1.size() > 0:
        items.insert(0, stack1.destack())
    while queue1.size() > 0:
        items.insert(items.size(), queue1.dequeue())
    return items
# T(n) => O(n)
# solution_end

# default_start
print("Hello World!")

# default_end