Discussion :

[tyrtamos]

Bonjour,

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

Code :

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

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.

[wiztricks]

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.

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

[tyrtamos]

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.

[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.

Juste pour le fun:

Code :

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

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 :

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

1
2
3
4
count: 491883115
elapsed: 1996.422998690444
count: 491883115
elapsed: 0.05299734098707631

- W

[tyrtamos]

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

[dividee]

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 :

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

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 )