Inscription / Connexion Nouveau Sujet
Niveau algorithmique
Partager :

Algorithme calcul de limite

Posté par
ZiYun
15-07-19 à 12:33

Bonjour,

Je bloque sur un algorithme pour calculer une certaine limite. On pose pour n\in \mathbb{N}^{*} l'ensemble A_{n} des k entre 1 et n tels que le reste de la division euclidienne est supérieur à \frac{k}{2}.
Je veux calculer la limite de (\frac{card(A_{n)}}{n})_{n}
Voici mon code Python :

def countA(n): #Pour calculer le cardinal de notre ensemble
    l=[]
    for i in range(1,n+1):
        if n%i>=i/2 :
            l.append(i)
    return len(l)


def lim(n): #Fonction pour la limite
    epsilon=1e-6
    p=n
    while abs((countA(p)/p)-(countA(p+1)/(p+1)))>=epsilon:
        p+=1
    return countA(p)/p


Mais l'algorithme ne marche pas. En fait, je ne reçois aucun message d'erreur mais le calcul ne se fait pas. Pour lim(1) j'ai 0.0. Mais pour lim(2) je n'ai rien. Le calcul ne se termine pas.

J'espère que vous pourrez m'aider afin de comprendre mon erreur et de corriger l'algorithme.

Merci d'avance,

Posté par
lg124
re : Algorithme calcul de limite 15-07-19 à 13:10

Bonjour,

Je ne vois pas d'erreurs, juste ton algo est lent (O(n²)) et que ça converse pas si rapidement que ça.

Essaye en mettant un epsilon plus petit ou en commençant avec un n plus grand

Que cherches-tu à déterminer exactement?

Posté par
lg124
re : Algorithme calcul de limite 15-07-19 à 13:12

lg124 @ 15-07-2019 à 13:10

Bonjour,

Je ne vois pas d'erreurs, juste ton algo est lent (O(n²)) et que ça converge pas si rapidement que ça.

Essaye en mettant un epsilon plus grandou en commençant avec un n plus grand

Que cherches-tu à déterminer exactement?

Posté par
carpediem
re : Algorithme calcul de limite 15-07-19 à 13:36

salut

Citation :
le reste de la division euclidienne
de quoi par quoi ?

parce qu'en lisant ton algo le reste de la division euclidienne de k par n est suéprieur à k/2 si k < n/2 ...

Posté par
ZiYun
re : Algorithme calcul de limite 15-07-19 à 20:32

Bonjour,

Je m'excuse. C'est le reste de la division euclidienne de n par k (supérieur à k/2).
Merci pour votre réponse. Je ne peux pas mettre de n plus grand car ca ne se termine pas dès n=2...
En prenant un epsilon plus petit j'ai toujours le même problème.

Merci d'avance,

Posté par
carpediem
re : Algorithme calcul de limite 16-07-19 à 20:52

ok ...

par contre j'ai dit une grosse con... ensuite ...

Posté par
lafol Moderateur
re : Algorithme calcul de limite 16-07-19 à 21:55

Bonjour
c'est un epsilon plus GRAND qu'il faut que tu mettes au départ

Posté par
ZiYun
re : Algorithme calcul de limite 16-07-19 à 23:20

Bonjour,

Je m'excuse pour ma faute. J'ai mis epsilon=10-3 et j'obtiens : lim(3)=lim(50)=0.38825448613376834.

Pouvez-vous m'expliquer où se cachait le problème s'il vous plaît ? Etait-ce trop difficile pour l'ordinateur de trouver des différences inférieures au epsilon initial ? Cela serait-donc un problème de la représentation des réels par l'ordinateur ?

Merci d'avance,

Posté par
carpediem
re : Algorithme calcul de limite 17-07-19 à 12:27

ouais en fait je ne vois pas l'intérêt de créer une fonction count qui a même rôle que la fonction len

def liste(n)
  for i in range (n)
    if n%i >= i/2
      liste.append(i)
  return liste

e = int(input("précision"))
n = 1
a = len(liste(n))/n
b = len(liste(n + 1))/(n + 1)
while abs(a - b) > e
  n+ = 1
  a, b = b, len(liste(n))/n
print a, b

Posté par
ZiYun
re : Algorithme calcul de limite 17-07-19 à 17:40

Bonjour,

Vous avez raison, il n'y a pas raison de définir la fonction count. Je l'avais fait pour avoir plus de clarté.

Sinon, le problème avec le epsilon très petit c'était quoi en fait ? Problème dans la représentation des réels ?

Merci d'avance,

Posté par
lg124
re : Algorithme calcul de limite 17-07-19 à 18:37

ZiYun @ 17-07-2019 à 17:40



Sinon, le problème avec le epsilon très petit c'était quoi en fait ? Problème dans la représentation des réels ?



Bof , 10^{-6} c'est pas si petit, je pense que simplement la suite converge lentement et le calcul des termes est assez lent aussi  (O(n)) donc au final ça prend longtemps ...

Posté par
ZiYun
re : Algorithme calcul de limite 17-07-19 à 18:39

Je vois. Peut-être que je devais prendre un n très grand avec le 10-6 comme on me l'avait suggéré aussi.

Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !