Exo : Trouver k

1 pièce(s) jointe(s)

Exo : Trouver k

Salut,

J’essaie de faire cet exercice :

Pièce jointe 514103

J'ai fait ce code :
Code:

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:

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 ?

:salut:

En fonction de la valeur de n :

Code:

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)))

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

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:

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

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:

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

Citation:

Envoyé par Beginner.

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

Oui oui, l'optimisation n'est pas obligatoire, c'est un plus...
Et le fait de ne tester que l’inégalité k*(k+1)/2 <= n est déjà une optimisation...