Activité pratique 2

Consignes globales

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).

Contenu de l’activité

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.

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

# Write your codes here
# ...

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

# The thing to search
v = 't'

# Last occurrence of v in s
index = len(s) - 1
while index >= 0 and s[index] != v:
    index -= 1

# Print result
if index >= 0:
    print("Found at index", index)
else:
    print("Not found")

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

# The thing to search
v = 'l'

# Use string method to find last occurrence
result = s.rfind(v)

# Print result
if result != -1:
    print("Found at index", result)
else:
    print("Not found")

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.

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

# The thing to search
v = 't'

# Initialize variable for the while loop
index = 0

# Iterate from the start to the end
while index < len(s) and s[index] != v:
    index += 1

# Print the result
if index < len(s):
    print("Found at index", index)
else:
    print("Not found")

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

# The thing to search
v = 'l'

# Use string method to find first occurrence
result = s.find(v)

# Print result
if result != -1:
    print("Found at index", result)
else:
    print("Not found")

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.

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

# The thing to search
pref = "IMT"

# Iterate over the string util a different character is found
i = 0
while i < len(s) and i < len(pref) and s[i] == pref[i]:
    i += 1

# Print result
if i == len(pref):
    print(pref, "is a prefix of", s)
else:
    print(pref, "is not a prefix of", s)

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

# The thing to search
pref = "IMT"

# Use string method for that
if s.startswith(pref):
    print(pref, "is a prefix of", s)
else:
    print(pref, "is not a prefix of", s)

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.

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

# Loop to append to a new string
result = ""
for character in s:
    result = character + result

# Print the result
print("Reversed string:", result)

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

# Using operator []
result = s[::-1]

# Print the result
print("Reversed string:", result)

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.

# Initialize variables
s = "LAVAL"
i = 0

# Iterate over the string
while i < len(s) / 2 and s[i] == s[len(s) - 1 - i]:
    i += 1

# Show result
# Show result
if i >= len(s) / 2:
    print(s, "is a palindrome")
else:
    print(s, "is not a palindrome")

# The string to manipulate
s = "laval"
print(s)

# Check if s is a palindrome
if s == s[::-1]:
    print(s, "is a palindrome")
else:
    print(s, "is not a palindrome")

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.

# The string to manipulate
s = "A man, a plan, a canal: Panama"
print(s)

# Remove spaces, punctuation marks and convert to lowercase
simplified_s = ""
for character in s:
    if character.isalnum():
        simplified_s += character.lower()

# Iterate over the string
i = 0
while i < len(simplified_s) / 2 and simplified_s[i] == simplified_s[len(simplified_s) - 1 - i]:
    i += 1

# Show result
if i >= len(simplified_s) / 2:
    print(s, "is a palindrome")
else:
    print(s, "is not a palindrome")

# The string to manipulate
s = "A man, a plan, a canal: Panama"
print(s)

# Remove spaces, punctuation marks and convert to lowercase
simplified_s = ''.join(character for character in s if character.isalnum()).lower()

# Check if s is a palindrome
if simplified_s == simplified_s[::-1]:
    print(s, "is a palindrome")
else:
    print(s, "is not a palindrome")

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.

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

# The thing to search
substr = "Atlan"

def contains(s, substr):
    # Initialize variables
    index_start = 0
    index_sub = 0
    found = False

    # Outer loop: iterate through each position in the string where the substring could start
    while index_start <= len(s) - len(substr) and index_sub < len(substr):

        # Inner loop: check if the substring matches at this position
        index_sub = 0
        while index_sub < len(substr) and s[index_start + index_sub] == substr[index_sub]:
            index_sub += 1
        index_start += 1

    # Print a message if not found
    if index_sub >= len(substr):
        return index_start - 1
    else:
        return -1

idx = contains(s, substr)
if idx != -1:
    print("Substring found at index", idx)
else:
    print("Substring not found")

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

# The thing to search
substr = "Atlan"

# You can directly check with 'in' keyword
if substr in s:
    print("Substring found at index", s.find(substr))
else:
    print("Substring not found")

Pour aller plus loin

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 :

# Initialize variables
to_convert = "8EA4"
result = 0

# Iterate over the string
for index in range(len(to_convert)):

    # Convert to decimal
    value = None
    match to_convert[index]:
        case 'A': value = 10
        case 'B': value = 11
        case 'C': value = 12
        case 'D': value = 13
        case 'E': value = 14
        case 'F': value = 15
        case  _ : value = int(to_convert[index])
    
    # Aggregate to solution
    power = len(to_convert) - index - 1
    result += 16 ** power * value

# Print result
print("Decimal version of", to_convert, "is", result)

# Value to convert
to_convert = "8EA4"

# Convert into decimal
result = int(to_convert, 16)
print("Decimal version of", to_convert, "is", result)