Corrigé

Algorithme

Le successeur d'un élément est l'élément plus 1. La somme du dernier bit de N avec 1 fait alors soit :

Si la somme vaut 10, cela revient à réitérer le processus sur l'avant dernier bit.

Donc on commence par regarder le bit N[i] en commençant par le dernier. S'il vaut :

La complexité de l'algorithme va dépendre du nombre d'éléments dans la liste en entré. Notons $n = N.\mbox{\small longueur}$.

On remarque (facilement) que cette complexité vaut $C(n) = K \cdot \mathcal{O}(1)$ où $K$ est le nombre de fois où l'on rentre dans la boucle tant que. D'où :

Complexité en moyenne

On suppose que chaque nombre décrit par $N$ peut apparaître de façon équiprobable. En posant $n = N.\mbox{\small longueur}$, séparons les $2^n$ nombres possibles en classes selon le nombre d'itérations dans la boucle :

Le nombre moyen d'itérations dans la boucle vaut alors :

$$ W_\text{moy}(N) = \mathcal{O}(1) \cdot \sum_{i=0}^{N-1} i \cdot \frac{1}{2^{i+1}} $$

On a vu que $\sum_{i=0}^{+\infty} i \cdot \frac{1}{2^{i}} = 2$, donc $\sum_{i=0}^{N-1} i \cdot \frac{1}{2^{i+1}} \leq \frac{1}{2}\sum_{i=0}^{N-1} i \cdot \frac{1}{2^{i}} \leq \frac{1}{2}\sum_{i=0}^{+\infty} i \cdot \frac{1}{2^{i}} \leq 1$. Ceci montre que $W_\text{moy}(N) \leq \mathcal{O}(1)$.

Vérification expérimentale

def successeur(N):
    K = 0

    while i >= 0 and (N[i] == 1):
        K += 1

        N[i] = 0
        i -= 1

    if i >= 0:
        N[i] = 1

    return K


def tous(n):

    N = [0] * n
    total = 0
    for i in range(2**n):
        total += successeur(N)
        print(n)

    return total / 2 ** n


x = tous(5)
print(x)

Récursif

Preuve

Chaque récursion modifie le tableau à une position inférieure, cet élément valant d'abord 0, puis 1 lorsque l'on reviendra à cette fonction après la récursion.

Complexité en mémoire

La complexité en mémoire est de $n$, car chaque aucune récursion ne crée de nouveau tableau ! C'est le même tableau qui est modifié à chaque récursion.

Généralisation

Clairement, l'algorithme suivant fonctionne :

fonction tous_rec(N: [caractère], i: entier)  vide:

    si i == -1:
        affiche à l'écran N
    sinon:
        pour chaque x de ["⚀", "⚁", "⚂", "⚃", "⚄", "⚅"]:
        N[i]  x
        tous_rec(N, i-1)

algorithme tous(n)  vide:
    N  nouveau tableau de caractères de taille n

    tous_rec(N, n-1)