Exercice d'algorithmie pour allumer des lampes

Bonjour,

J'ai exploité les explications de picodev (merci!), et voilà le code:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

nblampes = 1000000000 nbenfants = 12   c = 0 for i in range(1, nblampes+1): ci = 0 for j in range(1, nbenfants+1): if i%j==0: ci += 1 if ci%2!=0: c += 1 print(c)

---

Ce qui donne: 491883115 lampes allumées en 3/4 heure.

Je regarde maintenant le message de wiztricks (merci!) avec le PPCM.

Citation:

---

Envoyé par tyrtamos

Je regarde maintenant le message de wiztricks (merci!) avec le PPCM.

---

Avec le PPCM on sort de la boucle lorsque ci == nbenfants car alors on a calculé c pour 1..ppcm.

Citation:

---

Envoyé par tyrtamos

Ce qui donne: 491883115 lampes allumées en 3/4 heure.

---

Normalement, avec 12 enfants, le calcul devrait durer 45 / 36 ~ 90 secondes.

Le soucis est qu'avec 25 enfants, ça devrait durer 45 mns * 2 ~1h30.
Compter le nombre de diviseurs jusqu'au ppcm ne le fait plus.

- W

Merci wiztricks.

Dernier résultat avec mon code précédent pour 1 milliard de lampes et 25 élèves: 477471034 lampes allumées et 1heure 1/4.

Citation:

---

Envoyé par tyrtamos

Dernier résultat avec mon code précédent pour 1 milliard de lampes et 25 élèves: 477471034 lampes allumées et 1heure 1/4.

---

Juste pour le fun:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53

def ttm_count(nblampes, nbenfants):   c = 0 for i in range(1, nblampes+1): ci = 0 for j in range(1, nbenfants+1): if i%j==0: ci += 1 if ci%2!=0: c += 1 return c         def ppcm_count(count, eleves):   def diviseurs(z, n): ci = 0 for j in range(1, n+1): if not(z % j): ci += 1 return ci   def get_la(start, stop): la = 0 for i in range(start, stop): dv = diviseurs(i, eleves) if dv % 2: la += 1 if dv == eleves: return i, la return None, la   ppcm, la = get_la(1, count+1) if not ppcm: return la   q, r = divmod(count, ppcm) ppcm, lr = get_la(1 + count - r, count + 1) return lr + q * la       import time   t0 = time.clock() print('count:', ttm_count(1000000000, 12)) print('elapsed:', time.clock() - t0)   t0 = time.clock() print('count:', ppcm_count(1000000000, 12)) print('elapsed:', time.clock() - t0)

---

Le résultat est:

Code:

---

1 2 3 4

count: 491883115 elapsed: 1996.422998690444 count: 491883115 elapsed: 0.05299734098707631

---

- W

Bonjour wiztricks,

Waou! Effectivement, un tel écart de temps (0.05s / 1996s) justifie qu'on réfléchisse bien aux algorithmes avant de dire que Python est lent...

Intéressant le calcul du ppcm en même temps que le comptage des ampoules.

Voici mon code, j'ai calculé le PPCM explicitement:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

from functools import reduce   def ppcm(a,b): return a // pgcd(a,b) * b   def pgcd(a,b): while b != 0: a,b = b,a%b return a   N = 12 A = 1000000000   periode = reduce(ppcm, range(1, N+1))   # avec un tableau   ampoules = [False]*periode for pas in range(1, N+1): ampoules[pas-1::pas] = [not x for x in ampoules[pas-1::pas]]   print(sum(ampoules)*(A//periode) + sum(ampoules[:A%periode]))   # ... ou par le comptage des diviseurs   c = 0 c_rest = 0 a_rest = A % periode for a in range(1, periode+1): ca = 0 for j in range(1,N+1): if a % j == 0: ca += 1 c += ca & 1 if a == a_rest: c_rest = c   print(c*(A//periode) + c_rest)

---

EDIT: je peux aussi confirmer le résultat de tyrtamos: 477471034 pour 25 enfants et 1 milliard d'ampoules. Calculé avec pypy en 198 secondes (je n'ai pas la patience de tyrtamos ;))