Bien sûr ! Voici un jeu en Python inspiré par le domaine des algorithmes, avec un ton sympa :
—
Bienvenue dans le jeu « Algo Adventure » !
Salut, aventurier des algorithmes ! Prépare-toi à explorer le monde fascinant des algorithmes et à résoudre des énigmes amusantes. Ton objectif est de naviguer à travers différents niveaux en résolvant des problèmes d’algorithmique. Prêt à commencer l’aventure ?
# Règles du jeu
1. **Niveaux** : Il y a 5 niveaux, chacun avec une énigme à résoudre.
2. **Indices** : Si tu es bloqué, tu peux demander un indice.
3. **Victoire** : Atteins le niveau final pour gagner le jeu !
# Niveau 1 : La Tour de Hanoï
Bienvenue au niveau 1 ! La Tour de Hanoï est un classique des énigmes d’algorithmique. Tu as trois poteaux et plusieurs disques de tailles différentes. L’objectif est de déplacer tous les disques du poteau de départ vers le poteau d’arrivée en respectant les règles :
– Un disque ne peut être placé que sur un disque plus grand ou sur un poteau vide.
– Seul le disque du dessus peut être déplacé à la fois.
« `python
def tour_de_hanoi(n, source, auxiliaire, destination):
if n == 1:
print(f »Déplacer le disque 1 de {source} vers {destination} »)
return
tour_de_hanoi(n – 1, source, destination, auxiliaire)
print(f »Déplacer le disque {n} de {source} vers {destination} »)
tour_de_hanoi(n – 1, auxiliaire, source, destination)
# Testons avec 3 disques
tour_de_hanoi(3, ‘A’, ‘B’, ‘C’)
« `
Si tu réussis, passe au niveau suivant !
# Niveau 2 : Le Problème du Sac à Dos
Félicitations pour avoir résolu la Tour de Hanoï ! Maintenant, prépare-toi pour le problème du sac à dos. Tu as une liste d’objets avec leurs poids et valeurs, et un sac à dos de capacité limitée. L’objectif est de maximiser la valeur totale des objets dans le sac à dos sans dépasser la capacité.
« `python
def sac_a_dos(poids, valeurs, capacite):
n = len(poids)
dp = [[0 for _ in range(capacite + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(1, capacite + 1):
if poids[i – 1] <= w:
dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - poids[i - 1]] + valeurs[i - 1])
else:
dp[i][w] = dp[i - 1][w]
return dp[n][capacite]
# Testons avec des exemples
poids = [1, 3, 4, 5]
valeurs = [1, 4, 5, 7]
capacite = 7
print(sac_a_dos(poids, valeurs, capacite))
```
Bien joué ! Passe au niveau suivant.
# Niveau 3 : Le Problème du Plus Long Sous-Séquence Commune (LCS)
Super, tu es presque à la fin ! Le problème du LCS consiste à trouver la plus longue séquence commune entre deux chaînes de caractères.
```python
def lcs(str1, str2):
m = len(str1)
n = len(str2)
dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if str1[i - 1] == str2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
# Testons avec des exemples
str1 = "AGGTAB"
str2 = "GXTXAYB"
print(lcs(str1, str2))
```
Excellent travail ! Un seul niveau te sépare de la victoire.
# Niveau 4 : Le Problème du Chemin le Plus Court
C'est le dernier niveau ! Le problème du chemin le plus court consiste à trouver le chemin le plus court entre deux nœuds dans un graphe.
```python
import heapq
def dijkstra(graph, start, end):
queue = []
heapq.heappush(queue, (0, start))
distances = {vertex: float('infinity') for vertex in graph}
distances[start] = 0
previous_vertices = {vertex: None for vertex in graph}
while queue:
current_distance, current_vertex = heapq.heappop(queue)
if current_vertex == end:
break
for neighbor, weight in graph[current_vertex].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
previous_vertices[neighbor] = current_vertex
heapq.heappush(queue, (distance, neighbor))
path = []
step =