Suite de Conway

Exercice 1

Proposer un code possible pour le corps de la fonction suivante:

def nbCaracteresIdentiques(chaine, indice):
    """
    chaine -- chaine de caractères, non vide
    indice -- indice d'un élément de la chaîne

    renvoie le nombre de caractères successifs 
    égaux à chaine[indice] en partant de chaine[indice].
    >>> nbCaracteresIdentiques('b322', 0)
    1
    >>> nbCaracteresIdentiques('bb22', 0)
    2
    >>> nbCaracteresIdentiques('bb555', 2)
    3
    >>> nbCaracteresIdentiques('bb555455', 2)
    3
    """

Important

En langage python, il est possible de sortir d'une boucle for ou while à l'aide de l'instruction break.

>>> for i in range(10):
...     if i == 5: break
...     else: print(i)
... 
0
1
2
3
4

Une solution avec for et break

def nbCaracteresIdentiques(chaine, indice):
    """
    chaine -- chaine de caractères, non vide
    indice -- indice d'un élément de la chaîne

    renvoie le nombre de caractères successifs 
    égaux à chaine[indice] en partant de chaine[indice].
    >>> nbCaracteresIdentiques('b322', 0)
    1
    >>> nbCaracteresIdentiques('bb22', 0)
    2
    >>> nbCaracteresIdentiques('bb555', 2)
    3
    >>> nbCaracteresIdentiques('bb555455', 2)
    3
    """
    caractereInitial = chaine[indice]
    compteur = 1
    for i in range(indice+1, len(chaine)):
        if chaine[i] == caractereInitial:  compteur += 1
        else: break 
    return compteur

Rappel: n'oubliez pas de tester au moins le jeu de tests proposé en docstring.

Une solution avec while et sans break

def nbCaracteresIdentiques(chaine, indice):
    """
    chaine -- chaine de caractères, non vide
    indice -- indice d'un élément de la chaîne

    renvoie le nombre de caractères successifs égaux à chaine[indice] en partant de chaine[indice].
    >>> nbCaracteresIdentiques('b322', 0)
    1
    >>> nbCaracteresIdentiques('bb22', 0)
    2
    >>> nbCaracteresIdentiques('bb555', 2)
    3
    >>> nbCaracteresIdentiques('bb555455', 2)
    3
    """
    assert len(chaine) > 0, "Attention, la chaîne doit être non vide."
    assert 0 <= indice < len(chaine), "Attention, indice doit être compris entre 0 et longueur(chaine)-1."
    caractereInitial = chaine[indice]
    compteur = 1
    i = indice + 1
    while i < len(chaine) and chaine[i] == caractereInitial:
        compteur += 1 
        i += 1
    return compteur

Exercice 2

Saurez-vous déterminer la logique de passage d'une ligne à l'autre dans ce qui suit (appelée suite de Conway):

1
11
21
1211
111221
312211
13112221
1113213211

Explication :

• En première ligne, on commence par la chaîne '1'.
• En seconde ligne, on écrit ce qu'on voit en première ligne : un '1', ce qui donne '11'.
• En troisième ligne, on lit ce que l'on voit dans la ligne précédente : deux '1', ce qui donne '21'.
• Sur la ligne suivante, on écrit de même ce que l'on voit : un '2' et un '1', ce qui donne '1211'
• ...et ainsi de suite.

Écrire une fonction python:

def ligneSuivanteConway(chaine):
    """
    chaine -- chaine de caractères-chiffres, non vide

    renvoie la chaîne descriptive de chaine (suivant le principe exposé ci-dessus).
    >>> ligneSuivanteConway('1')
    '11'
    >>> ligneSuivanteConway('11')
    '21'
    >>> ligneSuivanteConway('21')
    '1211'
    >>> ligneSuivanteConway('1211')
    '111221'
    """

Important

On peut convertir certaines valeurs d'un type à un autre. Par exemple, 12 est de type int. On aimerait concaténer le mot 'malabar' et 12 pour obtenir 'malabar12'.
Mais on ne peut pas ajouter un int et un str.

>>> "malabar" + 12
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: can only concatenate str (not "int") to str

Il suffit de transformer au préalable 12 en chaîne à l'aide de str.

>>> "malabar" + str(12)
'malabar12'

Un code possible avec str

On utilise la fonction de l'exercice précédent.

def nbCaracteresIdentiques(chaine, indice):
    """
    chaine -- chaine de caractères, non vide
    indice -- indice d'un élément de la chaîne

    renvoie le nombre de caractères successifs égaux à chaine[indice] en partant de chaine[indice].
    >>> nbCaracteresIdentiques('b322', 0)
    1
    >>> nbCaracteresIdentiques('bb22', 0)
    2
    >>> nbCaracteresIdentiques('bb555', 2)
    3
    >>> nbCaracteresIdentiques('bb555455', 2)
    3
    """
    assert len(chaine) > 0, "Attention, la chaîne doit être non vide."
    assert 0 <= indice < len(chaine), "Attention, indice doit être compris entre 0 et longueur(chaine)-1."
    caractereInitial = chaine[indice]
    compteur = 1
    i = indice + 1
    while i < len(chaine) and chaine[i] == caractereInitial:
        compteur += 1 
        i += 1
    return compteur


def ligneSuivanteConway(chaine):
    """
    chaine -- chaine de caractères-chiffres, non vide

    renvoie la chaîne descriptive de chaine (suivant le principe exposé ci-dessus).
    >>> ligneSuivanteConway('1')
    '11'
    >>> ligneSuivanteConway('11')
    '21'
    >>> ligneSuivanteConway('21')
    '1211'
    >>> ligneSuivanteConway('1211')
    '111221'
    """
    ligneSuivante = ''
    caractere = chaine[0]
    indice = 0
    repetition = nbCaracteresIdentiques(chaine, indice)

    while indice < len(chaine):
        ligneSuivante = ligneSuivante + str(repetition) + caractere 
        indice = indice + repetition
        if indice < len(chaine): 
            caractere = chaine[indice]
            repetition = nbCaracteresIdentiques(chaine, indice)

    return ligneSuivante    

Testez!

Un code possible sans str

On peut éviter la conversion explicite précédente en utilisant les f-strings.

def ligneSuivanteConway(chaine):
    """
    chaine -- chaine de caractères-chiffres, non vide

    renvoie la chaîne descriptive de chaine (suivant le principe exposé ci-dessus).
    >>> ligneSuivanteConway('1')
    '11'
    >>> ligneSuivanteConway('11')
    '21'
    >>> ligneSuivanteConway('21')
    '1211'
    >>> ligneSuivanteConway('1211')
    '111221'
    """
    ligneSuivante = ''
    caractere = chaine[0]
    indice = 0
    repetition = nbCaracteresIdentiques(chaine, indice)

    while indice < len(chaine):
        ligneSuivante = f"{ligneSuivante}{repetition}{caractere}"
        # ou (version python < 3.6):
        # ligneSuivante = "{}{}{}".format(ligneSuivante, repetition, caractere) 
        indice = indice + repetition
        if indice < len(chaine): 
            caractere = chaine[indice]
            repetition = nbCaracteresIdentiques(chaine, indice)

    return ligneSuivante

Exercice 3

Écrire maintenant un code possible pour la fonction suivante:

def conway(n):
    """
    n -- entier naturel > 0

    renvoie la chaîne des n premières lignes de la suite de Conway
    """

Un code possible

Un code possible dans ce fichier ipynb (version html).