Bonjour,

J'ai un programme à faire, mais je ne vois pas comment l'écrire :

Écrire un script qui permet de trouver le plus petit entier naturel n tel que n² + n >= 50000

Pourriez vous m'aider svp ?

Ben...

def fonction_inutile():                   
    for i in range(1000):
        if i**2 + i >= 50000:
            return i

Voici une piste sur comment je ferai (pas très mathématique):

Tu remarque que n² + n est égale à n(n+1). Donc c'est approximativement n*n = n². Je partirai donc de là, et j'incrémenterai au fur et à mesure:

#Texte explicatif:

#On prend la racine carré du nombre qu'on enregistre dans une variable: var
#On convertit ce nombre en entier
#On test var*(var+1)
#On fait une boucle pour voir si le test est supérieur au nombre
#Si le test est positif, on renvoie le nombre
#Sinon on incrémente de 1 la valeur de var, et on retest

La solution de Derzal est correct, mais elle limite le test à la valeur 1000.

Je pense qu'ici, la meilleure solution est la boucle while...

LIMIT = 50000

current = -1
while current**2 + current < LIMIT:
    current += 1

print(current)

-
Edité par Anonyme 17 septembre 2014 à 19:26:36

J'ai mis 1000 parce que j'avais quand même une idée de l'ordre de grandeur de la solution (même si j'ai été un poil large...)

Mais tu as entièrement raison, le while est plus adapté ici.

Salut, pourquoi coder une boucle lorsqu'un algo à temps constant existe ? Il suffit de résoudre \(x(x+1) = C\) , prendre la racine positive si elle existe et arrondir au supérieur...

Ok, merci !

C’est évidement @dr1 qui a raison, mais pour le plaisir voici une méthode en évaluation paresseuse. C’est pas ce qu’il y a de plus propre mais c’est fichtrement rigolo.

>>> import itertools as it
>>> list(it.takewhile(lambda n: n**2+n<50000, it.count(1)))[-1] + 1
224

-
Edité par talpa 18 septembre 2014 à 16:39:32

Je suis absolument d'accord avec @dri1, certes tester successivement toutes les valeurs de n jusqu'à trouver la bonne fonctionne, mais niveau complexité, on pourrait faire bien mieux. Dans ce cas précis, le problème revient à trouver la racine positive du polynôme \(x^2 + x - C\), et vu sa tête, utiliser la méthode de Newton semble bien adapté.

Alors bien sûr, si le programme ne consiste qu'à effectuer ce petit test, pas la peine de s'embêter avec des soucis de cet ordre. Mais lorsqu'il s'agira de réaliser la même opération un très grand nombre de fois, même sur d'autres problèmes du même type, les quelques minutes de plus passées à optimiser l'algorithme seront vite rentabilisées.

-
Edité par Mustiwa 18 septembre 2014 à 16:45:48

Mustiwa a écrit:

Je suis absolument d'accord avec @dri1, certes tester successivement toutes les valeurs de n jusqu'à trouver la bonne fonctionne, mais niveau complexité, on pourrait faire bien mieux. Dans ce cas précis, le problème revient à trouver la racine positive du polynôme \(x\^2 + x - C\), et vu sa tête, utiliser la méthode de Newton semble bien adapté.

Les polynômes de degré 2 sont soluble par radicaux, c’est encore au programme de lycée il me semble. Pourquoi vouloir passer par une méthode numérique ? Cet exercice est faisable à la main et le programme pourrais simplement être print 224

-
Edité par talpa 18 septembre 2014 à 16:51:04

(Oui c'est bien au programme de lycée, mais je préfère taire mon niveau réel d'études, je me ferais fouetter pour ne même pas y avoir pensé, on va dire que c'est la fatigue )

Lorsque j'ai vu ces fonctions, je me suis immédiatement focalisé sur les problème évidents de complexité de ces méthodes, sans même réfléchir à comment expliciter la réponse... C'est assez ridicule je dois l'admettre, mais dans un cas plus général, utiliser une méthode numérique sera presque tout le temps bien plus efficace.

(N'empêche que j'ai super honte )