Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

TD 7 - Listes et chaˆ ınes de caract` eres. Informatique MPSI/PCSI - Lyc´ ee Th

TD 7 - Listes et chaˆ ınes de caract` eres. Informatique MPSI/PCSI - Lyc´ ee Thiers Exercice 1 : Tri ` a bulle Exercice 2 : Tri par S´ election Exercice 3 : Cryptage de C´ esar Exercice 1 : Tri ` a bulle Enonc´ e Corrig´ e Exercice 2 : Tri par S´ election Enonc´ e Corrig´ e Exercice 3 : Cryptage de C´ esar Enonc´ e Correction Informatique MPSI/PCSI - Lyc´ ee Thiers TD 7 - Listes et chaˆ ınes de caract` eres. Exercice 1 : Tri ` a bulle Exercice 2 : Tri par S´ election Exercice 3 : Cryptage de C´ esar Enonc´ e Corrig´ e Exercice 1 - Enonc´ e I - Algorithmes de tri : Un algorithme de Tri prend en param` etre une liste de nombre et l’ordonne dans le sens croissant (ou d´ ecroissant). Exercice 1. Le Tri ` a bulle. Un exemple d’algorithme de est le Tri ` a bulle. Il s’op` ere de la fa¸ con suivante : – Parcourir les ´ el´ ements du tableau de gauche ` a droite. – D` es que l’on rencontre deux ´ el´ ements cons´ ecutifs qui ne sont pas dans le bon ordre, on ´ echange leur position. C’est ` a dire : SI tableau[i] > tableau[i+1] ALORS : ´ echanger tableau[i] et tableau[i+1] – Recommencer tant que l’on a chang´ e quelque chose. Ecrire une fonction TriBulle en python qui prend en param` etre une liste de nombres et retourne la liste tri´ ee par l’algorithme du tri ` a bulle. Informatique MPSI/PCSI - Lyc´ ee Thiers TD 7 - Listes et chaˆ ınes de caract` eres. Exercice 1 : Tri ` a bulle Exercice 2 : Tri par S´ election Exercice 3 : Cryptage de C´ esar Enonc´ e Corrig´ e Exercice 1 - Correction # Tri a bulle def triBulle(L): n = len(L) chgt = True while chgt: chgt = False for k in range(n-1): if L[k] > L[k+1]: L[k], L[k+1] = L[k+1], L[k] chgt = True n = n-1 return L Apr` es le k-i` eme passage dans la boucle for les k derniers ´ el´ ements sont ` a leur place d´ eﬁnitive. C’est pourquoi apr` es chaque boucle for on d´ ecr´ emente n. Informatique MPSI/PCSI - Lyc´ ee Thiers TD 7 - Listes et chaˆ ınes de caract` eres. Exercice 1 : Tri ` a bulle Exercice 2 : Tri par S´ election Exercice 3 : Cryptage de C´ esar Enonc´ e Corrig´ e Exercice 2 - Enonc´ e Exercice 2. Le Tri par s´ election. Un autre exemple d’algorithme de tri est le tri par s´ election. il s’op` ere de la fa¸ con suivante : – Chercher l’indice de l’´ el´ ement maximal de L, – ´ echanger dans L l’´ el´ ement maximal avec le dernier ´ el´ ement de L, – Recommencer le mˆ eme proc´ ed´ e pour les ´ el´ ements de L allant du premier ` a l’avant-dernier, – et ainsi de suite... 1. Ecrire une fonction echange(L,i,j) prenant en param` etre une liste L et deux entiers positifs i, j, et qui ´ echange dans la liste L ses ´ el´ ements d’indice i et j. 2. Ecrire une fonction IndiceMax(L,k) qui prend en param` etre une liste L de nombres et un entier positif k et qui retourne l’indice de l’´ el´ ement maximal dans la sous-liste de L allant de l’indice 0 ` a l’indice k. 3. En appelant les fonctions pr´ ec´ edentes, ´ ecrire une fonction triSelection(L) prenant en param` etre une liste de nombres et qui les ordonne dans le sens croissant en appliquant un tri par s´ election. Informatique MPSI/PCSI - Lyc´ ee Thiers TD 7 - Listes et chaˆ ınes de caract` eres. Exercice 1 : Tri ` a bulle Exercice 2 : Tri par S´ election Exercice 3 : Cryptage de C´ esar Enonc´ e Corrig´ e Exercice 2 - Corrig´ e 1. def echange(L,i,j): L[i], L[j] = L[j], L[i] 2. def indiceMax(L,k): ind = 0 for i in range(1,k+1): if L[i] > L[ind]: ind = i return ind 3. def triSelection(L): n = len(L) for k in range(n-1,0,-1): i = indiceMax(L,k) echange(L,i,k) return L Informatique MPSI/PCSI - Lyc´ ee Thiers TD 7 - Listes et chaˆ ınes de caract` eres. Exercice 1 : Tri ` a bulle Exercice 2 : Tri par S´ election Exercice 3 : Cryptage de C´ esar Enonc´ e Correction Exercice 3 - Enonc´ e Exercice 3. ´ Epreuve type ; Oral - Banque PT. Soit n un entier v´ eriﬁant n ⩽26. On souhaite ´ ecrire un programme qui code un mot en d´ ecalant chaque lettre de l’alphabet de n lettres. Par exemple pour n = 3, le d´ ecalage sera le suivant : avant d´ ecalage a b c d . . . . . . x y z apr` es d´ ecalage d e f g . . . . . . a b c Le mot oralensam devient ainsi rudohqvdp. 1. D´ eﬁnir une chaˆ ıne de caract` eres contenant toutes les lettres dans l’ordre alphab´ etique (caract` eres en minuscule). 2. ´ Ecrire une fonction decalage, d’argument un entier n, renvoyant une chaˆ ıne de caract` eres contenant toutes les lettres dans l’ordre alphab´ etique, d´ ecal´ ees de n, comme indiqu´ e ci-dessus. 3. ´ Ecrire une fonction indices, d’arguments un caract` ere x et une chaˆ ıne de caract` eres phrase, renvoyant une liste contenant les indices de x dans phrase si x est une lettre de phrase et une liste vide sinon. 4. ´ Ecrire une fonction codage d’arguments un entier n et une chaˆ ıne de caract` eres phrase, renvoyant phrase cod´ e avec un d´ ecalage de n lettres. 5. Comment peut-on d´ ecoder un mot cod´ e ? Informatique MPSI/PCSI - Lyc´ ee Thiers TD 7 - Listes et chaˆ ınes de caract` eres. Exercice 1 : Tri ` a bulle Exercice 2 : Tri par S´ election Exercice 3 : Cryptage de C´ esar Enonc´ e Correction Exercice 3 - Corrig´ e 1. variable alphabet. alphabet = ’abcdefghijklmnopqrstuvwxyz’ 2. Fonction decalage. def decalage(n): return alphabet[n:] + alphabet[:n] 3. Fonction indices. def indices(x,phrase): n = len(phrase) L = [] for i in range(n): if x == phrase[i]: L.append(i) return L Informatique MPSI/PCSI - Lyc´ ee Thiers TD 7 - Listes et chaˆ ınes de caract` eres. Exercice 1 : Tri ` a bulle Exercice 2 : Tri par S´ election Exercice 3 : Cryptage de C´ esar Enonc´ e Correction 4. def codage(n,phrase): alphabetCode = decalage(n) # Obtention de l’alphabet cod´ e # Constitution de la liste des caract` eres de phrase listePhrase = [] for x in phrase: listePhrase.append(x) # Codage de la liste en utilisant la fonction indices(,) for i in range(26): lettre = alphabet[i] lettreCode = alphabetCode[i] ind = indices(lettre,phrase) for i in ind: listePhrase[i] = lettreCode # Obtention de la chaine cod´ ee : phraseCode = ’’ for lettre in listePhrase : phraseCode += lettre return phraseCode Informatique MPSI/PCSI - Lyc´ ee Thiers TD 7 - Listes et chaˆ ınes de caract` eres. Exercice 1 : Tri ` a bulle Exercice 2 : Tri par S´ election Exercice 3 : Cryptage de C´ esar Enonc´ e Correction 5. Pour d´ ecoder un message crypt´ e avec un d´ ecalage de n, il suﬃt de coder avec d´ ecalage -n (la fonction decalage marche aussi avec un argument n´ egatif). def decodage(n, phrasecode): return codage(-n, phrasecode) Informatique MPSI/PCSI - Lyc´ ee Thiers TD 7 - Listes et chaˆ ınes de caract` eres. uploads/Science et Technologie/ td-7-listes-et-chaines-de-caracteres-informatique-mpsi-pcsi-lycee-thiers.pdf