Base TP2 AlgoTouch Python

Consignes

  • Durée 2h00
    • Présentation des outils : 0h00
    • Exercices de TP : 2h00
  • Pas d’internet sauf pour pour tester les programmes Python sur http://pythontutor.com/visualize.html#mode=edit
  • Déposer les fichiers sur moodle au fur et à mesure des résultats
  • Les enseignants sont là pour aider sur les aspects techniques de Python ou d’AlgoTouch
  • Pour que l’expérience soit concluante, il est important que chaque étudiant cherche et trouve les solutions par lui-même.
  • Attention : tous ces programmes sont réalisables avec une seule boucle (sans imbrication de boucle).

Exercice 1 : Tasse tableau

Version 1 : Tasse zéros (sans conservation de l’ordre)

Soit le tableau (collection) t de longueur n contenant des valeurs entières quelconques. L’objectif de cet exercice est de tasser le tableau : tous les zéros se retrouvent à la fin, l’ordre des autres nombres ne doit pas être conservé.

Exemple :  Pour un tableau de longueur 8, t=[0, 5, 0, 4, 0, 0, 7, 2], le tableau t tassé vaut [2, 5, 7, 4, 0,  0, 0 ,0].

Version 2 : Tasse zéros ( avec ordre conservé)

Soit le tableau (collection) t de longueur n contenant des valeurs entières quelconques. L’objectif de cet exercice est de tasser le tableau : tous les zéros se retrouvent à la fin, l’ordre des autres nombres ne doit pas être modifié.

Exemple :  Pour un tableau de longueur 8, t=[0, 5, 0, 4, 0, 0, 7, 2], le tableau t tassé vaut [5, 4, 7, 2, 0,  0, 0, 0].

Version 3 : Tasse tableau généralisé (Principe version 2 avec ordre conservé)

Soit le tableau (collection) t de longueur n contenant des valeurs entières quelconques. L’objectif de cet exercice est de tasser le tableau : chaque valeur du tableau ne doit figurer qu’une seule fois. L’ordre des nombres ne doit pas être modifié.

Exemple :  Pour un tableau de longueur 10, t=[0, 5, 1, 4, 1, 0, 4, 4, 5, 2], le tableau t tassé vaut [5, 1, 4, 2, 0, 0, 0, 0, 0, 0].

  • Source Python :
  • Sources AlgoTouch :

Version 4 : Tasse tableau généralisé (Principe version 2 avec ordre conservé, y compris le zéro)

(Test : Difficile à réaliser avec une seule boucle et sans macro. La différence avec la version 3, c’est qu’elle tiendra compte de la valeur Zéro parmi la liste des valeurs).

Soit le tableau (collection) t de longueur n contenant des valeurs entières quelconques. L’objectif de cet exercice est de tasser le tableau : chaque valeur du tableau ne doit figurer qu’une seule fois, y compris le zéro. L’ordre des nombres ne doit pas être modifié.

Exemples :

– Version 3 : Pour un tableau de longueur 8, t=[5, 5, 5, 0, 0, 7, 7, 8], le tableau t tassé vaut [5, 7, 8] (le zéro ne figure pas dans le tableau final)
– Version 4 : Pour un tableau de longueur 8, t=[5, 5, 5, 0, 0, 7, 7, 8], le tableau t tassé vaut [5, 0, 7, 8] (le zéro figure dans le tableau tassé).

  • Source Python :
  • Sources AlgoTouch :

Exercice 2 : Suppression des Zéros (Patrice)

Version 1 : Suppression zéros (sans conservation de l’ordre)

Soit le tableau (collection) t de longueur n contenant des valeurs entières quelconques. L’objectif de cet exercice est de supprimer les zéros. L’idée principale est de parcourir le tableau à partir de l’indice 0 et de remplacer chaque valeur 0 du tableau par une autre valeur différente de 0, en l’occurrence par les valeurs du tableau situées à la fin du tableau.

Exemple :  Pour un tableau de longueur 9, t=[3, 0, 0, 1, 3, 5, 0, 3, 4], le tableau t après suppression  vaut [3, 4, 3, 3, 3,  5, 0, 3, 4].  Les seules indices à retenir dans le tableau pour les valeurs non nulles sont de 0 à 5. Les autres indices 6, 7 et 8 ne sont plus à considérer.

On devra appliquer le principe suivant :

– A la rencontre de la première valeur 0, la dernière valeur du tableau (4) d’indice 8 est copiée à sa place, on obtient le tableau t=[3, 4, 0, 1, 3, 5, 0, 3, 4].  Le nouvel indice de la dernière valeur réelle du tableau est à la position 7 (valeur 3).

– A la rencontre de la seconde valeur 0, la dernière valeur du tableau (3) est copiée à sa place, on obtient le tableau t=[3, 4, 3, 1, 3, 5, 0, 3, 4]. Le nouvel indice de la dernière valeur réelle du tableau est à la position 6 (valeur 0).

– Pour les trois valeurs suivantes (1, 3, 5), elles sont différentes de zéros.

– La valeur suivante à l’indice 6 vaut 0. La dernière valeur (0) à la position 6 est copiée à sa place. La dernière valeur réelle du tableau est à l’indice 5, qui indique les indices à retenir pour le tableau final à considérer (la taille finale du tableau après suppression).

  • Source Python :
  • Sources AlgoTouch :

Version 2 : Suppression zéros (avec conservation de l’ordre)

Soit le tableau (collection) t de longueur n contenant des valeurs entières quelconques. L’objectif de cet exercice est de supprimer les zéros. L’idée principale est de parcourir le tableau à partir de l’indice 0 et de copier les valeurs non nulles du tableau dans la partie inférieure (gérée par un indice i). A une étape donnée, la partie inférieure du tableau contient des valeurs non nulles déjà rencontrées, copiées au fur et à mesure de leur apparition. En fait, Lorsqu’on rencontre une valeur non nulle à la position j, on l’ajoute dans la partie inférieure du tableau à la position i.

Exemple :  pour un tableau de longueur 8, t=[0, 4, 0, 3, 2, 0, 1, 0], le tableau t après suppression  vaut [4, 3, 2, 1, 2,  0, 1, 0]. Les seules indices à retenir dans le tableau pour les valeurs non nulles sont de 0 à 3. Les autres indices variant de 4 à 7 ne sont plus à considérer.

Donc, on obtient les quatre valeurs non nulles en début du tableau, dans le même ordre que le tableau initial : soit 4 3 2 1.

Déroulons l’algorithme, en parcourant le tableau  :

  • Etape 1 (valeur 0) : avancer (incrémenter la position j de 1).
  • Etape 2 (valeur 4) : recopier la valeur 4 en début du tableau. On obtient le tableau t=[4, 4, 0, 3, 2, 0, 1, 0], la première valeur non nulle est au début du tableau.
  • Etape 3 (valeur 0) :  avancer (incrémenter la position j de 1)
  • Etape 4 (valeur 3) : recopier la valeur 3 en début du tableau. On obtient le tableau t=[4, 3, 0, 3, 2, 0, 1, 0], les deux premières valeurs non nulles sont au début du tableau.
  • Etape 5 (valeur 2) : recopier la valeur 2 en début du tableau.  On obtient le tableau t=[4, 3, 2, 3, 2, 0, 1, 0], les trois premières valeurs non nulles sont en début du tableau.
  • Etape 6 (valeur 0) : avancer (incrémenter la position j de 1).
  • Etape 7 (valeur 1) : recopier la valeur 1 en début du tableau.  On obtient le tableau t=[4, 3, 2, 1, 2, 0, 1, 0], les quatre premières valeurs non nulles sont en début du tableau.
  • Etape 8 (valeur 0) : avancer (incrémenter la position j de 1). Fin parcours, fin de l’algorithme.

Le tableau final contient les quatre valeurs non nulles en début du tableau dans la partie inférieure de valeurs :  4 3 2 1.

  • Source Python :
  • Sources AlgoTouch :

Exercice 3 : Dichotomie

Soit le tableau (collection) t de longueur n contenant des valeurs entières quelconques. On suppose que le tableau est trié dans l’ordre croissant. On cherche à savoir si le tableau t contient une certaine valeur entière x.  Pour la recherche de la valeur x, on propose la méthode de recherche par dichotomie :

  • soient les deux indices gauche (indice minimum) et droite (indice maximum)  du tableau tels que gauche=0 et droite= (n-1)
  • soit m (indice milieu ) compris entre gauche et droite  tel que ( gauche <= m <= droite)
  • si la valeur recherché x est inférieure ou égale à t[m], alors la valeur recherchée, s’il est dans le tableau, est nécessairement dans l’intervalle [gauche..m], sinon elle est dans l’intervalle [m+1..droite].

En répétant la subdivision par 2 de l’intervalle [gauche .. droite] plusieurs fois, on encadre la valeur recherchée x dans un intervalle [gauche ..droite] de plus en plus petit, jusqu’à qu’il ne contienne plus qu’une valeur.  A ce stade, soit t[m] est égale à la valeur recherchée x, et on a trouvé, sinon elle n’est pas dans le tableau.

Exemples :

– Pour un tableau de longueur 9, t=[10, 13, 27, 42, 47, 50, 61, 77, 95], la valeur recherchée x égale à 42 retrouvée en quatre étapes :

Etape 1 :  Intervalle[0..8], m=4, x <= t[m] Etape 2 : Intervalle [0..4], m=2, x > t[m] Etape 3 : Intervalle [3..4], m=3, x <= t[m] Etape 4 : Intervalle [3..3], x=t[m], valeur retrouvée !

– Pour un tableau de longueur 9, t=[10, 13, 27, 42, 47, 50, 61, 77, 95], la valeur recherchée x égale à 100  non retrouvée dans le tableau après quatre étapes :

Etape 1 : Intervalle[0..8], m=4, x > t[m] Etape 2 : Intervalle [5..8], m=6, x > t[m] Etape 3 : Intervalle [7..8], m=7, x > t[m] Etape 4 : Intervalle [8..8], x ≠ t[m], valeur non retrouvée !

  • Source Python :
  • Sources AlgoTouch :

Exercice 4 : Partition

Soit le tableau (collection) t de longueur n contenant des valeurs entières quelconques. On cherche à diviser le tableau en deux parties en se basant sur un élément “pivot” :

  • On fixe le premier élément du tableau comme élément “pivot”
  • Partition : on place le pivot à sa place définitive, en permutant les éléments,  pour séparer les éléments du tableau en deux parties, la partie de gauche contient les éléments inférieurs ou égaux au pivot, la partie de droite contient les éléments supérieurs au pivot.

On considère deux indices: gauche et droite. Au départ, le pivot est la première valeur, à l’indice gauche. A chaque itération on compare les valeurs des indices gauche et droite. Si la valeur de gauche est supérieure à la valeur de droite, on échange les valeurs, le pivot change de place. A chaque itération, on fait évoluer l’un des deux indices en fonction de la place du pivot.

Exemple: soit le tableau t = [19, 12, 29, 11, 43, 6, 26, 14, 61, 62]. L’indice gauche vaut 0, l’indice droite vaut 9. Le pivot vaut 19, il est à gauche.

Déroulement de l’algorithme:

  • comparer 19 avec 62 : 62 est du bon côté, le pivot est à gauche, on décrémente droite
  • comparer 19 avec 61 : 61 est du bon côté, le pivot est a gauche, on décrémente droite
  • comparer 19 avec 14 : 14 est du mauvais côté, on échange 19 et 14, le pivot est à droite, on incrémente gauche
  • comparer 12 avec 19 : 12 est du bon côté, le pivot est a droite, on incrémente gauche
  • comparer 29 avec 19 : 29 est du mauvais côté, on échange 29 et 19, le pivot est à gauche, on décrémente droite
  • comparer 19 avec 26 : 26 est du bon côté, le pivot est a gauche, on décrémente droite
  • comparer 19 avec 6 : 6 est du mauvais côté, on échange 19 et 6, le pivot est à droite, on incrémente gauche
  • comparer 11 avec 19 : 11 est du bon côté, le pivot est à droite, on incrémente gauche
  • comparer 43 avec 19 : 43 est du mauvais côté, on échange 43 et 19, le pivot est à gauche, on décrémente droite

Le tableau final est: t = [14, 12, 6, 11, 19, 43, 26, 29, 61, 62]. On note que le pivot est à sa place  définitive en position 4. Il partage le tableau en deux sous parties.

  • Source Python :
  • Sources AlgoTouch :

Exercice 5 : Codage Jules Cesar

Version  1  généralisée (Moncef)  : Cryptage/ Décryptage avec clé et texte quelconque.  Le cryptage/ décryptage concerne les caractères  majuscules, minuscules et les chiffres.  Les autres caractères restent inchangés (cf énoncé). Enoncé : Jules Cesar transmettait des messages cryptés, en décalant chaque lettre de trois  positions par exemple  (valeur clé = 3) : A devient  D, B devient  E, … , W devient Z, X devient A, Y devient B, Z devient C). Les chiffres sont décalés de la même façon, les autres caractères (espaces, virgules, points…) ne sont pas modifiés. Ecrire un programme réalisant le chiffrement / cryptage d’un message. Exemples de cryptage avec clé de valeur 3, décryptage dans le sens inverse  avec clé de valeur -3 : “LePython.com” donne “OhSbwkrq.frp”
“AlgoTouch.net” donne “DojrWxfk.qhw””UE M1102” donne “XH P4435”

  • Source Python :
  • Source AlgotTouch :

Version  2  simplifiée (Michel) : Cryptage/ Décryptage avec clé quelconque d’un texte utilisant l’alphabet en majuscules uniquement et le caractère espace. Enoncé : Jules Cesar transmettait des messages cryptés avec l’alphabet, en décalant chaque lettre de trois  positions (valeur clé égale à 3) : A devient  D, B devient  E, … , W devient Z, X devient A, Y devient B, Z devient C). Le caractère espace reste inchangé.

Ecrire un programme réalisant le chiffrement / cryptage d’un message.

Exemples de cryptage avec clé de valeur 3, décryptage dans le sens inverse  avec clé de valeur -3 : “CM PYTHON” donne “FP SBWKRQ”
“ALGOTOUCH” donne “DOJRWRXFK”

  • Source Python :
  • Source AlgotTouch :

Version  3  clé variable (Alphabet en majuscules et des espaces) : (Cryptage/ Décryptage d’un texte utilisant l’alphabet en majuscules uniquement et le caractère espace, avec l’utilisation d’une clé variable, par exemple 123 :   décalge +1 pour caractère ordre i,  +2 pour caractère ordre i+1, +3 pour caractère ordre i+3, et ainsi de suite  +1, +2, +3, … Le caractère espace reste inchangé.) Enoncé : Jules Cesar transmettait des messages cryptés avec l’alphabet, en décalant chaque lettre avec une clé variable. Par exemple pour une clé composée de trois valeurs  x,  y et z, on décale la lettre d’ordre i de x positions, la lettre d’ordre (i+1) de y positions et la lettre d’ordre (i+2) de z positions et on recommence pour les caractères suivants (décalage +x, +y, +z positions).  Le décryptage se fait selon le même principe dans le sens opposé (décalage -x, -y et -z positions). Chaque caractère aura un cryptage/décryptage selon son ordre d’apparition dans le message. Le caractère espace reste inchangé.Exemples de cryptage avec clé de valeur 1, 2 et 3, décryptage dans le sens inverse  avec clé de valeur -1, -2, -3  : “ABCDEFGH” donne “BDFEGIHJN””CM PYTHON” donne “DO SZVKPP”
“ALGOTOUCH” donne “BNJPVREK”

  • Source Python :
  • Source AlgoTouch :

Version  4  clé variable  (Code avec chiffres uniquement) : (Cryptage/ Décryptage d’un code composé de chiffres uniquement avec l’utilisation d’une clé variable, par exemple 123 :   décalage +1 pour chiffre ordre i,  +2 pour chiffre ordre i+1, +3 pour chiffre d’ordre i+3, et ainsi de suite  +1, +2, +3, …)   Énoncé : Jules César transmettait des messages cryptés avec des chiffres, en décalant chaque chiffre avec une clé variable. Par exemple pour une clé composée de trois valeurs  x,  y et z, on décale le chiffre d’ordre i de x positions, le chiffre  d’ordre (i+1) de y positions et le chiffre d’ordre (i+2) de z positions et on recommence pour les chiffres suivants (décalage +x, +y, +z positions).  Le décryptage se fait selon le même principe dans le sens opposé (décalage -x, -y et -z positions). Chaque chiffre aura un cryptage/décryptage selon son ordre d’apparition dans le message. Exemple : cryptage code avec clé de valeur 1, 2 et 3, décryptage dans le sens inverse  avec clé de valeur -1, -2, -3  : “58092473” donne “60304785”

Version 4 avec lettres codées 1, 2, … 26 et blanc codé 0

Énoncé : On considère un message contenant uniquement des lettres minuscules et des espaces. Pour simplifier, les lettres a, b, c, … z sont codées par les nombres 1, 2, … 26. Le caractère espace est codé 0. Jules César transmettait des messages cryptés en ajoutant à chaque caractère une clé variable. Par exemple pour une clé composée de trois valeurs  x,  y et z, on ajoute au caractère du message d’ordre i, la valeur x, au caractère d’ordre (i+1), la valeur y  et au caractère d’ordre (i+2), la valeur z et on recommence pour les caractères suivants (ajout de x, puis y, puis z). La valeur cryptée doit rester un nombre compris entre 0 et 26. Pour cela on utilise le reste de la division par 27.

Exemple:

Soit le message “jules cesar” codé: 10, 21, 12, 5, 19, 0, 3, 5, 19, 1, 18 et la clé 12, 7, 19.

Le message crypté vaut 22, 1, 4, 17, 26, 19, 15, 12, 11, 13, 25. En effet:

  • à 10, on ajoute 12 soit 22
  • à 21, on ajoute 7 soit 1 (reste de la division par 27)
  • à 12, on ajoute 19 soit 4 (reste de la division par 27)
  • à 5, on ajoute 12 soit 17
  • à 19, on ajoute 7 soit 26
  • etc.

 

  • Source Python :
  • Source AlgoTouch :