Accumulateur et while

Exercice

Écrire une fonction python prenant en entrée un entier naturel M et renvoyant en sortie le plus grand entier naturel $n$ tel que $0+1+2+\dots+n \leqslant M$.

>>> fin_auplus(2)
1
>>> fin_auplus(3)
2
>>> fin_auplus(4)
2
>>> fin_auplus(5)
2
>>> fin_auplus(6)
3
>>> fin_auplus(9)
3
>>> fin_auplus(10)
4

Le principe

Dans une variable S (initialisée à 0), on va accumuler les entiers successifs jusqu'à dépasser la valeur M donnée au préalable.

Par exemple, si l'on s'est donné au départ la valeur M=11:

S ← 0
S ← S + 1 # S a pour valeur 1, S <= 11: on continue
S ← S + 2 # S a pour valeur 3, S <= 11: on continue
S ← S + 3 # S a pour valeur 6, S <= 11: on continue
S ← S + 4 # S a pour valeur 10, S <= 11: on continue
S ← S + 5 # S a pour valeur 15, S > 11: on stoppe

La dernière valeur pour laquelle on a encore S <= 11 est la valeur 4: $0+1+2+3+4 \leqslant 11$ mais $0+1+2+3+4+5 >11$.
Notre fonction doit donc renvoyer 4.

On doit essentiellement répéter une action (du type S ← S + un entier) tant qu'une condition reste vraie (ici S <= M).
Cela se traduit bien sûr par une boucle while.

pseudo-code

fonction fin_auplus(M):
    i ← 0 # i va parcourir les valeurs 0, 1, 2, 3, ...
    S ← 0 # S servira d'accumulateur: on y ajoutera une à une les valeurs de i
    Tant que S <= M:
        i ← i+1
        S ← S + i
    renvoyer i-1 

Remarquez qu'on renvoie i-1 car la dernière valeur prise par i est celle qui fait "déborder", c'est la valeur qui fait que la condition du while devient fausse (qui fait que l'on a S > M), or nous voulons la dernière valeur pour laquelle la condition est encore vraie.

code python

def fin_auplus(M):
    """
    M -- entier naturel

    renvoie le plus grand entier n tel que
    0+1+2+...+n <= M
    """
    i = 0
    S = 0
    while S <= M:
        i += 1
        S += i
    return i-1

Exercice

On reprend l'exercice de la page précédente:

Écrire une fonction prenant en entrée un entier naturel A non nul et renvoyant le plus petit entier m tel que $2^m > A$.

Mais il s'agit maintenant d'écrire une version dans laquelle on s'interdira d'utiliser ** pour calculer une puissance.

Indication: accumulateur

L'idée, pour calculer les puissances de 2 successives sans utiliser **, est à nouveau celle de l'accumulateur.

Le nombre $2^n$ est le produit de 2, 2, 2, ..., 2:
2ⁿ = 2×2×2×...×2 peut se calculer en "accumulant" les facteurs 2...

On commence par:

P ← 1

Puis on multiplie par 2 à chaque étape le contenu de P:

P ← 2P # P désigne maintenant la valeur 2
P ← 2P # P désigne maintenant la valeur 2 × 2 = 2²
P ← 2P # P désigne maintenant la valeur 2 × 2² = 2³
P ← 2P # P désigne maintenant la valeur 2 × 2³ = 2⁴
P ← 2P # P désigne maintenant la valeur 2 × 2⁴ = 2⁵
....

Un code python

def depasseA(A):
    """
    A -- entier naturel non nul

    renvoie  le plus petit entier n tel que 2**n > A
    """
    n = 0
    p = 1   # on a p = 1 = 2^0 = 2^n
    while p <= A:
        n += 1
        p = 2*p   # p = 2^n à chaque fin de passage dans la boucle

    return n 

Remarque: cette fois, on renvoie n et non n-1 car on veut le premier entier qui rend la condition fausse (dans l'exercice précédent, on voulait le dernier entier laissant la condition vraie).