Aller au contenu

Exercices concrets avancés⚓︎

Jeux sérieux⚓︎

RoboZZle⚓︎

Version 8 niveaux de l'Université de Lyon 1 : Robozzle

D'autres niveaux plus difficiles en lien avec ce chapitre :

  • 536 : Recursed A simple puzzle for understanding the call stack : RoboZZle
  • 330 : Learning Stack : RoboZZle
  • 59 : Recursion : RoboZZle

CargoBot⚓︎

Reprises⚓︎

Certains exercices ont été résolus avec des copies de tranche, cette méthode étant lente, nous allons les reprendre de manière plus efficace.

Maximum d'une liste non vide⚓︎

Écrire une fonction récursive maxi telle que maxi(nombres, i, j) renvoie le maximum des éléments de la liste nombres dont les indices k sont tels que i <= k < j. On garantit que i < j.

Réponse
🐍 Script Python
def maxi_2(a, b):
    if a > b:
        return a
    else:
        return b

def maxi(nombres, i, j):
    ip1 = i + 1
    if ip1 == j:
        return nombres[i]
    else:
        maxi_fin = maxi(nombres, ip1, j)
        return maxi_2(nombres[i], maxi_fin)

On peut alors utiliser cette fonction

🐍 Script Python
def maximum(nombres):
    return maxi(nombres, 0, len(nombres))

assert maximum([7]) == 7
assert maximum([7, 13]) == 13
assert maximum([13, 7]) == 13
assert maximum([-19, -13, -19]) == -13

Test de palindrome⚓︎

Écrire une fonction récursive telle que est_palindrome(mot, i, j) renvoie un booléen qui détermine si la chaine mot est un palindrome entre les indices i inclus et j exclu. On garantit i <= j.

Réponse
🐍 Script Python
def est_palindrome(mot, i, j):
    "Détermine si mot[i:j] est un palindrome"

    if i + 2 < j:
        return True
    else:
        return (mot[i] == mot[j - 1]) and est_palindrome(mot, i + 1, j - 1)

Compte d'occurrences⚓︎

Écrire une fonction récursive telle que nb_occurrences(lettre, mot, i) renvoie le nombre d'occurrences de la lettre dans le mot à partir de l'indice i.

Réponse
🐍 Script Python
def nb_occurrences(lettre, mot, i):
    "Renvoie le nombre d'occurrences de la lettre dans mot[i:]"
    if i == len(mot):
        return 0
    else:
        nb_occ = nb_occurences(lettre, mot, i + 1)
        if lettre == mot[i]:
            nb_occ += 1
        return nb_occ

# pour l'utiliser, on part de 0
assert nb_occurrences("o", "bonjour", 0) == 2
assert nb_occurrences("i", "salut", 0) == 0
assert nb_occurrences("t", "tttt", 0) == 4

Suite⚓︎

  1. Prologin
    1. Niveau 1
      • 2004 Netiquette
      • 2004 Addition binaire
      • 2011 Décryptage
    2. Niveau 3
      • 2013 Reverse Alchemying
  2. Algo de tri rapide avec pivot choisi au hasard
  3. Recherche dichotomique dans tableau trié
  4. Rendu de monnaie minimal
  5. une fonction récursive pour la conversion décimal vers romain
  6. https://www.spoj.com/problems/tag/recursion 4 ; beaucoup de bonnes idées pour des exos plus durs !!!

Aide pour Prologin⚓︎

🐍 Script Python
"""
author:  Votre nom
problem: https://prologin.org/train/2004/semifinal/netiquette
"""

def netiquette(texte: str, largeur=80):
    """Affiche le texte formaté sur plusieurs lignes,
    avec une largeur maximale définie, 80 par défaut.

    >>> nétiquette("123 12 1", 4)
    123
    12 1

    """
    ...  # à compléter

import doctest
doctest.testmod()

longueur = int(input())
texte = input()  # le parchemin
assert longueur == len(texte), f"{longueur} ≠ {len(texte)}"

netiquette(texte)
🐍 Script Python
"""
author:  Votre nom
problem: https://prologin.org/train/2004/semifinal/addition_binaire
"""

def addition_binaire(nb_bits: int, nombre_1: str, nombre_2: str) -> str:
    """Renvoie la somme de deux nombres écrits en binaire sur nb_bits.
    Le débordement est perdu.

    >>> addition_binaire(3, "111", "101")
    '100'

    """
    ...

def somme_binaire(nb_bits: int, nombres: list) -> str:
    """Renvoie la somme des nombres donnés sur nb_bits,
    le débordement est perdu.

    >>> nombres = ["1010", "1111", "1001"]
    >>> somme_binaire(4, nombres)
    '0010'

    >>> nombres = ["001", "001", "100"]
    >>> somme_binaire(3, nombres)
    '110'

    """
    ...  # à compléter


# Tests
import doctest
doctest.testmod()

# Entrée
nb_bits = int(input())
nb_nombres = int(input())
nombres = []
for i in range(nb_nombres):
    nombre_en_binaire = input()
    assert nb_bits == len(nombre_en_binaire), f"Erreur avec le {i}e nombre"
    nombres.append(nombre_en_binaire)

# Sortie
print(somme_binaire(nb_bits, nombres))
🐍 Script Python
"""
author:  Votre nom
problem: https://prologin.org/train/2011/semifinal/decryptage
"""

def est_extrait(texte:str, partie: str) -> bool:
    """Renvoie True ou False selon que
    `partie` est un extrait de `texte`
    >>> est_extrait("Un morceau complet", "U orc cplt")
    True
    >>> est_extrait("Un morceau complet", "Z")
    False
    >>> est_extrait("Un morceau complet", "nU")
    False
    >>> est_extrait("J'ai dit ho", "diiit")
    False
    """
    ...  # à compléter

import doctest
doctest.testmod()


# Entrée
taille_message_chien = int(input())
message_chien = input()
taille_message_test = int(input())
message_test = input()

# Sortie
print("1" if est_extrait(message_chien, message_test) else "0")