Activités pratiques 2

Durée1h15

Présentation & objectifs

Voici une liste d’exercices pour expérimenter la construction d’algorithmes en se concentrant sur la construction de boucles. Le sujet porte sur la manipulation des chaînes de caractères. À l’instar des listes/tableaux, les chaînes peuvent être parcourues, et peuvent être vues comme une collection de caractères.

Une fois vos algorithmes conçus, il est recommandé de les coder en Python afin de pouvoir les tester. Cependant, si vous ne vous sentez pas encore à l’aise avec Python, vous pouvez simplement les écrire sur une feuille et les tester à la main.

Lors du test de vos algorithmes, essayez de penser à des cas couvrant tous les résultats possibles. Par exemple, si votre algorithme doit retourner true ou false, testez-le avec des entrées qui conduisent aux deux cas.

Contrainte – Il existe de nombreuses façons d’écrire un algorithme pour résoudre un problème, et de nombreuses façons de programmer un algorithme. Dans cette activité pratique, vous n’avez pas le droit d’utiliser le mot-clé break. Réfléchissez également soigneusement à savoir si vous avez besoin d’une boucle bornée (for) ou non bornée (while).

Important

Le but de cette séance est de vous aider à maîtriser des notions importantes en informatique. Un assistant de programmation intelligent tel que GitHub Copilot sera capable de vous fournir une solution à ces exercices uniquement à partir d’un nom de fichier judicieusement choisi.

Pour comprendre et apprendre, vous ne devez pas utiliser ces outils pour l’instant.

Prendre le temps de réfléchir, de concevoir des algorithmes et de les coder vous-même est essentiel pour acquérir les compétences nécessaires.

Contenu de l’activité

1 — Dernière occurrence

Commencez avec le programme suivant :

​
# The string to manipulate
s = "IMT Atlantique"
print(s)

# Write your codes here
# ...

Concevez un algorithme qui détermine la position (entre 0 et la longueur de s moins 1) de la dernière occurrence d’un symbole dans la chaîne s. Le symbole recherché est stocké dans une variable nommée v. L’algorithme affiche la position trouvée ou indique si le symbole n’est pas présent dans s.

L’algorithme peut être évalué avec les valeurs suivantes :

  • s = "IMT Atlantique" et v = 'l'
  • s = "IMT Atlantique" et v = 'z'
  • s = "I love Computer Science and Algorithms" et v = 'o'

2 — Première occurrence

Reprenez le même code de base que dans l’exercice 1.

Concevez un algorithme qui détermine la position (entre 0 et la longueur de s moins 1) de la première occurrence d’un symbole dans la chaîne s. Le symbole recherché est stocké dans une variable nommée v. L’algorithme affiche la position trouvée ou indique si le symbole n’est pas présent dans s.

L’algorithme peut être évalué avec les valeurs suivantes :

  • s = "IMT Atlantique" et v = 'l'
  • s = "IMT Atlantique" et v = 'z'
  • s = "I love Computer Science and Algorithms" et v = 'o'

3 — Préfixe

Reprenez le même code de base que dans l’exercice 1.

Considérant un second tableau de caractères, nommé pref par exemple, déterminez si pref est un préfixe de s. Réfléchissez bien aux différents scénarios possibles liés aux longueurs de s et pref. L’algorithme affiche si pref est un préfixe de s.

L’algorithme peut être évalué avec les valeurs suivantes :

  • s = "IMT Atlantique" et pref = "IMT"
  • s = "IMT Atlantique" et pref = "IMT Atlantique is a great school"
  • s = "I love Computer Science and Algorithms" et pref = "I love"

4 — Inverser

Reprenez le même code de base que dans l’exercice 1.

Déterminez un algorithme qui inverse le contenu de la chaîne s.

L’algorithme peut être évalué avec les valeurs suivantes :

  • s = "IMT Atlantique"
  • s = "euqitnaltA TMI"
  • s = "I love Computer Science and Algorithms"

5 — Palindrome

Un palindrome est un mot qui peut se lire dans les deux sens, comme par exemple “radar” ou “laval”. Déterminez une première stratégie naïve pour vérifier si une chaîne est un palindrome basée sur l’algorithme d’inversion conçu précédemment.

L’algorithme peut être évalué avec les valeurs suivantes :

  • s = "laval"
  • s = "rennes"
  • s = "detartrated"

5.1 — Défi supplémentaire (optionnel)

Un palindrome peut aussi être une phrase, telle que "A man, a plan, a canal: Panama". Adaptez votre algorithme pour ignorer les espaces, les signes de ponctuation et convertir en minuscules avant de vérifier si la chaîne est un palindrome.

Python fournit des méthodes intégrées pour ces opérations : isalnum(), lower().

6 — Contient

Reprenez le même code de base que dans l’exercice 1.

Considérant un second tableau de caractères, nommé substr par exemple, déterminez si substr est présent dans s. L’algorithme retourne la position de la première occurrence de substr dans s ou -1 s’il n’est pas présent.

L’algorithme peut être évalué avec les valeurs suivantes :

  • s = "IMT Atlantique" et substr = "Atlan"
  • s = "IMT Atlantique" et substr = "Pyhton"
  • s = "I love Computer Science and Algorithms" et substr = "and"

Pour aller plus loin

7 — Hexadécimal

Considérez une chaîne représentant un nombre en format hexadécimal. Calculez sa valeur décimale.

Pour rappel, un nombre hexadécimal peut contenir les chiffres suivants : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F. ‘A’ vaut 10, et ainsi de suite. Par exemple :

$$\text{8EA4} = 4 * 16^0 + 10 * 16^1 + 14 * 16^2 +8 * 16 ^3$$

Une solution intégrée existe en Python (et dans d’autres langages) pour résoudre ce problème, mais essayez de travailler avec des boucles pour vous familiariser avec leur utilisation. On suppose que chaque symbole dans la chaîne à convertir est un chiffre acceptable en format hexadécimal.