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 :
- 1 si le dernier bit vaut 0
- 10 si le dernier bit vaut 1
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 :
- 1 on le place à 0 et on décrémente i
- 0 on le place à 1 et on stoppe.
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é (max) : parcourt toute la liste (pour une liste uniquement constituée): $\mathcal{O}(n)$
- complexité min : parcourt 1 seul élément de la liste (pour une liste se terminant par un 0): $\mathcal{O}(1)$
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 :
- dernier élément vaut 0 : 0 itération. Vrai pour $2^n/2$ nombres. Probabilité de 1/2.
- derniers éléments valent
[0, 1]
: 1 itération. Vrai pour $(2^N/2)/2 = 2^N/4$ nombres. Probabilité de 1/4. - derniers éléments valent
[0, 1, 1]
: 2 itérations. Vrai pour $(2^N/4)/2 = 2^N/8$ nombres. Probabilité de 1/8. - ...
- derniers éléments valent
[0] + i *[1]
: i itérations. Vrai pour $(2^N/4)/2 = 2^N/2^{i+1}$ nombres. Probabilité de 1/2^{i+1}. - le premier élément vaut 0 et tous les autres valent 1 : $N-1$ itérations Vrai pour 1 nombre. Probabilité de 1/2^{N}.
Le nombre moyen d'itérations dans la boucle vaut alors :
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)