Challenge

• Correction des challenges

Challenges

Challenge 1

Flavius Josèphe était un historien juif du premier siècle. Il participa aux révoltes contre les Romains et fut assiégé avec quarante de ses compatriotes dans la forteresse de Jotapata en 67. Les extrémistes du groupe persuadèrent l’ensemble de se tuer pour ne pas tomber aux mains des Romains. Ne partageant pas ce point de vue mais n’osant s’opposer au groupe, Josèphe proposa que l’on se mette en cercle et que chaque troisième personne soit tuée, la dernière devant se suicider.

En utilisant une file trouver la position à choisir parmi les 41 soldats pour être le dernier éliminé.

Challenge 2

Il est possible de créer une file avec deux piles en appliquant l’algorithme suivant:

• Enfiler: Enfiler un élément dans la pile gauche.
• Défiler:
  • Si la pile de droite n’est pas vide:
    • Dépiler un élément de la pile droite
  • Sinon:
    • Dépiler toute la pile gauche dans la pile droite.
    • Dépiler un élément de la pile droite.

Construire une file à partir de deux piles.

Challenge 3

Un EDI se charge de vérifier si le code écrit par le programmeur est correctement parenthésée, c’est à dire si à chaque parenthèse ouvrante correspond une parenthèse fermante.

Écrire la fonction bien_parenthesee(code: str) -> bool qui vérifie si le code est bien parenthésé.

correcte1 = "((e)ee(e))"
correcte2 = "('test')"
correcte3 = "()'test'()"
incorrecte1 = "(((e))"
incorrecte2 = "((e)))"
incorrecte3 = ")'test'()"

assert bien_parenthesee(correcte1)
assert bien_parenthesee(correcte2)
assert bien_parenthesee(correcte3)
assert not bien_parenthesee(incorrecte1)
assert not bien_parenthesee(incorrecte2)
assert not bien_parenthesee(incorrecte3)

Challenge 4

L’écriture polonaise inverse des expressions arithmétiques place l’opérateur après ses opérandes. Cette notation ne nécessite aucune parenthèse ni aucune règle de priorité. Ainsi l’expression polonaise inverse

1 2 3 × + 4 ×

désigne l’expression traditionnelle

(1 + 2 × 3) × 4

En utilisant une pile pour stocker les résultats intermédiaires, il est facile de calculer l’expression.

Écrire la fonction polonaise(chaine: str) -> int qui calcule l’expression chaine. Les éléments de la chaîne seront séparés par un espace. On n’utilisera que l’addition et la multiplication.

assert polonaise("1 2 3 * + 4 *") == 28
assert polonaise("2 5 *") == 10
assert polonaise("3 2 5 + * 3 +") == 24