Dernière modification le 8 novembre 2018
Consignes
Table des matières
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].
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é).
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).
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 :
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.
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 :
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 !
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 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:
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.
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”
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”
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”
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: