Discussion :

[Beginner.]

Salut,

J’essaie de faire cet exercice :



J'ai fait ce code :

Code phyton :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
def trouverK1(n):
    k = 0
    while 1:
        a = k*(k+1)/2
        b = (k+1)*(k+2)/2
 
        if a <= n and n < b:
            print("La valeur de k recherchée est :", k)
            print("On a bien : %d <= n(%d) < %d" % (a, n, b))
            break
        k += 1
    print("Fin")

Après je me suis dit qu'on pouvait éviter une division par 2 pour les bornes a et b et du coup je fais la comparaison avec 2n (pour diviser ou multiplier par 2 j'utilise un décalage binaire c'est plus rapide normalement et on travaille avec des entiers).

Code phyton :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
def trouverK2(n):
    k = 0    
    n2 = n << 1  # n2 = 2 * n
    while 1:
        a = k*(k+1)
        b = (k+1)*(k+2)
 
        if a <= n2 < b:
            print("La valeur de k recherchée est :", k)
            print("On a bien : %d <= n(%d) < %d" % (a >> 1, n, b >> 1))
            break
        k += 1
    print("Fin")

on peut probablement optimiser encore (en évitant de commencer à k=0 par exemple...) mais bon ...

Mais je n'ai pas compris la dernière question "Encadrer le nombre d’itération en fonction de n"...

Qu'en pensez-vous ?

[danielhagnoul]

En fonction de la valeur de n :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
def test(n):
    # k <= n ; n = 0 k = 0 ; n = 1 k = 1 ; n = 2 k = 1 etc.
    for k in range(0, n+1): 
        b = (k * (k + 1)) / 2
        h = ((k + 1) * (k + 2)) / 2
        if b <= n < h:
            return (k, b, n, h)
 
 
print('k = {} ; {} <= {} < {}'.format(*test(2)))

[Beginner.]

Merci, je vais tester et essayer de comprendre...

[wiztricks]

Salut,

La suite k*(k+1)/2 est monotone croissante.
Ce qui signifie que pour tout k >= 0, k*(k+1)/2 < (k+1)*(k+2)/2.
Donc trouver le "k" tel que k*(k+1)/2 <= n < (k+1)*(k+2)/2, c'est trouver le premier k tel que k*(k+1)/2 > n.

Ce travail préliminaire étant fait, le traduire en Python s'écrit:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
>>> def f(n):
...     k = 0
...     while k*(k+1)/2 <= n:
...          k+=1
...     return k-1, k
...

- W

[Beginner.]

Salut,

@wiztricks Oui c'est bien vu par contre je n'ai pas compris pourquoi retourner k-1 et k (la bonne réponse étant k-1).

Sinon j'ai modifié ta fonction pour ajouter l'astuce dont j'avais parlé : éviter une division par 2 à chaque tour de boucle, k*(k+1) au lieu de k*(k+1)/2 (du coup on doit faire la comparaison avec 2n et pour multiplier par 2 j'utilise un décalage binaire qui est plus rapide normalement et on travaille avec des entiers).

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
def f1(n):
    n2 = n << 1  # n2 = 2 * n
    k = 0
    while k*(k+1) <= n2:
        k += 1
    return k-1

[wiztricks]

Sinon j'ai modifié ta fonction pour ajouter l'astuce dont j'avais parlé : éviter une division par 2 à chaque tour de boucle, k*(k+1) au lieu de k*(k+1)/2 (du coup on doit faire la comparaison avec 2n et pour multiplier par 2 j'utilise un décalage binaire qui est plus rapide normalement et on travaille avec des entiers).

Soit on se contente de traduire en Python ce que nous demande de faire l'exercice soit on optimise.
Et si "on optimise", on va d'abord chercher à trouver un meilleur algorithme avant de toucher au code.

On peut par exemple se souvenir que k*(k+1)/2 est la somme des k premiers entier ou que çà se calcule avec une racine carrée.

- W