Exercice d'algorithmie pour allumer des lampes

Bonjour,
Je suis lycéen (Terminale S option ISN) et j'ai un devoir sur python à faire pendant les vacances, ce devoir comporte 2 exercices, j'ai réussi à faire le 1er mais je bloque sur le deuxième.

Intitulé de l'exercice :

276 lampes sont numérotées de 1 à 276. Pour passer le temps, 25 enfants appuient sur les interrupteurs à tour de rôle. Le premier enfant presse chaque interrupteur. Le second presse les boutons 2,4,6, etc, (il presse les boutons ayant un numéro multiple de 2). Le troisième appuie sur les boutons 3, 6, 9, etc, (multiples de 3). Le quatrième presse tous les boutons ayant un numéro multiples de 4, et ainsi de suite jusqu'au 25ème enfant. Avant le passage du premier enfant, toutes les ampoules sont éteintes.

Questions :
1. Combien d'ampoules seront allumées après le passage des 25 enfants ?
2. Proposer une évolution du programme permettant à l'utilisateur de faire varier le nombres d'enfants.
3. Proposer une évolution du programme permettant à l'utilisateur de faire varier le nombre d'ampoules.

Cela ne fait que 2 mois que nous voyons les bases de python, et j'avoue que pour cet exercice je bloque totalement, je ne sais pas par où commencer.
Cependant, voici ce qui je pense est un début d'idée (mais je sais pas l'exprimer en langage python) :
0 serait la valeur d'une ampoule éteinte et 1 une ampoule allumée.
Il faudrait une liste de 276 ampoules éteintes (donc 0)
Chaque enfant donnerait à la valeur 0 ou 1 son inverse, c'est à dire 1 ou 0. (Une histoire de boléen ça non?)
Par contre je sais pas vraiment (même pas du tout) comment programmer les enfants qui interviennent dans la liste :(:(
Enfin à la fin du programme il faudrait un compteur du type :

Code:

---

1 2 3 4 5 6 7

a=0 for i in (liste de 0 et de 1):   if i==1 #donc ampoule allumée a = a+1   print a #qui normalement nous donnerais le nombre d'ampoules allumées

---

Etant donné que je bloque dès la question, je plante carrément en lisant les 2 autres, mais je pense que après avoir réussi la question 1 ce sera plus simple d'identifier la fonction de chaque ligne du code.
Voilà voilà c'est tout, j'espère vraiment que vous m'aiderez (avec indulgence svp je suis débutant :oops:)

Merci!

Salut,

Il faut apprendre à utiliser les "booleans":

Code:

---

1 2 3 4

>>> ampoules = [False,False,False,False] >>> ampoules[0] = not ampoules[0] >>> ampoules [True, False, False, False]

---

Puis écrire des boucles, ce qui a votre niveau passe par des boucles while:

Code:

---

1 2 3 4 5 6

>>> while i < len(ampoules): ... ampoules[i] = not ampoules[i] ... i = i + 1 ... >>> ampoules [False, True, True, True]

---

Là, on a déjà l'élève qui allume ou éteins toutes les ampoules.
Pour sauter de 2 en 2 ou de 3 en 3, il suffit d'ajouter 2 ou 3 à la place de 1

Voilà, pour le reste, ce n'est qu'en essayant de faire l'exercice que vous allez progresser...

- W

Bonjour,

Ça, c'est un chouette exo! Voilà un coup de pouce.

Au départ, on a 276 lampes éteintes. On peut les représenter par une liste de 277 booléens False (éteinte=False, allumée=True) dont on n'utilisera pas la 1ère valeur d'index 0. On peut ainsi numéroter les lampes dans la liste avec les index 1, 2, 3, ... 276.

On va aussi numéroter les élèves et, en fonction de leur numéro, voir quelles lampes vont changer d'état:

l'élève 1 => 1, 2, 3, 4, 5, ...
l'élève 2 => 2, 4, 6, 8, 10, ...
l'élève 3 => 3, 6, 9, ...
...
l'élève 25 => 25, 50, 75, 100, ...

Si on veut appeler l'élève par son index i (i=1 à 25), il changera les lampes d'index: i, 2*i, 3*i, 4*i, 5*i, ...

A chaque fois qu'une lampe doit être changée on peut utiliser "not" pour inverser sa valeur (puisque not True => False et not False=> True).

On aura donc une 1ère boucle 'for' pour les 25 élèves (=> range(1,26)), et à l'intérieur une 2ème boucle 'for' qui changera l'état des bonnes lampes en fonction du numéro i de l'élève (=> range(i, 277, i)).

A la fin, on peut compter le nombre de lampes allumées dans la liste avec la méthode count: si je ne me suis pas trompé, il y en aura... 154.

Avec ça, tu devrais pouvoir faire le boulot!

Merci beaucoup pour vos réponses !

Effectivement wiztricks j'ai réussi à comprendre que cela se jouerai avec les boléens, c'est pourquoi, pour créer la liste de 276 ampoules éteintes j'ai écrit le petit bloc suivant :

Code:

---

1 2 3

Ampoules=[False] while len(Ampoules)<276: Ampoules= Ampoules + [False]

---

Ensuite pendant la soirée j'ai essayé tout plein d'opérations sur cette liste pour essayer d'en comprendre les propriétés. Notamment, j'ai vu dans mon cours qu'on pouvait demandé d'afficher les termes de la suite avec un certain pas, en effet on note nomdelaliste[premierterme :dernierterme :pas]. De ce fait, j'ai fait quelques tests pour l'élève 1 (en me disant qu'en trouvant pour l'élève 1 cela allait m'éclairer pour les autres), avec cette histoires de pas, je me suis dit qu'on pouvait créer une boucle "for ... in ...:" où la variable sauterait de 2 en 2 si l'on choisissait 2 comme pas ou de 100 en 100 si l'on choisissait 100. Bref jusque là rien de sorcier car je l'avais déjà fait en écrivant

Code:

---

for i in range(0, len(variable), lefameuxpas)

---

Je me suis donc dit que c'était possible d'assembler ces deux propriétés et de créer cette boucle

Code:

---

for i in Ampoules[0 :len(Ampoules) :1]

---

par exemple, pour le premier élève.
Ensuite j'ai compléter cette boucle en écrivant :

Code:

---

1 2 3 4 5 6

for i in Ampoules[0 :len(Ampoules) :1]: if Ampoules[i]==[True]: Ampoules[i]=[False]   elif Ampoules[i]==[False]: Ampoules[i]=[True]

---

Et pour l'instant je n'allait pas plus loin, je faisais juste afficher la liste Ampoules pour voir les changements, sauf que là, problème, la liste était toujours composée de 276 False.

J'ai donc cherché d'autre solutions en essayant encore pleins de petits trucs (après tout c'est en pratiquant qu'on apprend non?),
et je savais que si je faisais par exemple Ampoules[2]= "test", le terme ayant pour index 2 dans la liste Ampoules allait devenir "test".
Je me suis dit que je pouvais donc tout simplement écrire :

Code:

---

Ampoules[0 :len(Ampoules) :25]= not(Ampoules[0 :len(Ampoules) :25]) #Par exemple pour l'enfant 25

---

Sauf que non, ça marche pas.:furieux:

Bref tout ça pour vous dire que j'ai essayé plein de choses mais bon au final j'ai pas trouvé...

Merci Tyrtamos pour ta réponse qui m'aide à visualiser l'ensemble (c'est d'ailleurs à peu près la même explication que mon père sauf que toi tu ajoutes les fonctions correspondantes alors ça m'aide vraiment merci)!
Je continue mes essais demain et je posterai un message de mon avancée ;)

Salut,

Comme l'énoncé est plaisant, Mon petit doigt me dit que Tyrtamos a griffonné quelques codes pour rechercher la méthode de résolution la plus simple.

Moi aussi bien sûr, et j'obtiens une résolution en quatre lignes de code plus deux print de contrôle.

Un conseil : rester le plus simple.

Bonjour VinsS,

Citation:

---

Envoyé par VinsS

j'obtiens une résolution en quatre lignes de code plus deux print de contrôle.

---

Pareil! :D

Salut,

Citation:

---

Envoyé par AlexBsd

Je me suis dit que je pouvais donc tout simplement écrire :

Code:

---

Ampoules[0 :len(Ampoules) :25]= not(Ampoules[0 :len(Ampoules) :25]) #Par exemple pour l'enfant 25

---

Sauf que non, ça marche pas.:furieux:

---

Ca fonctionne mais il faut apprendre à le faire marcher :mouarf:

Code:

---

1 2 3 4 5 6 7

>>> L = [ True, ] * 10 >>> ampoules = [ True, ] * 10 >>> ampoules[0:-1:2] = False Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: must assign iterable to extended slice >>>

---

L'erreur dit qu'on doit assigner autant d'éléments. Ce qui peut se faire avec une construction comme:

Code:

---

1 2 3 4

>>> ampoules[0:-1:2] = (not e for e in ampoules[0:-1:2]) >>> ampoules [False, True, False, True, False, True, False, True, False, True] >>>

---

Mais il faut voir ce genre de construction non comme "solution" mais comme façon rapide d'exprimer/coder ses itérations. Et comme vous débutez, il faut vous appliquer à comprendre ce que sont les itérations/boucles (plutôt que de rechercher les différents styles permettant de les exprimer).
Ce qui commence par:

Code:

---

1 2 3 4

i = 0 # initialisation while i < N: # test de fin # on fait des choses i = i + 1 # on incrémente pour passer au suivant

---

Et la difficulté de votre exercice est que vous devez imbriquer 2 itérations/boucles.

En Python, on préférera remplacer ces 3 instructions par un "for i in range(N):", çà fait la même chose. Et outre que ce soit plus concis, çà évite d'oublier l'initialisation, l'incrémentation,... et permet au programmeur de se concentrer sur ce que fait la boucle plutôt que sur les détails de construction de la boucle (la gestion de l'index).

- W

Salut!
Ca y est je m'y suis remis un peu ce matin en lisant attentivement ton message Tyrtamos et je pense avoir réussi, en plus en proposant directement l'évolution du programme qui permet de faire varier le nombre d'ampoules et d'enfants! :mouarf::mouarf:
Cependant, j'ai pas réussi à le faire en 4 lignes 8O
Donc voilà ce que j'ai écrit :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

n1= input("Nombre d'ampoules : ") n2= input("Nombre d'enfants : ")     Ampoules=[False] while len(Ampoules)<(n1+1): Ampoules= Ampoules + [False] #Liste de (n1+1) Ampoules eteintes, pour ne pas utiliser le boleen d'index 0   for a in range(1,(n2+1)): for b in range(a, len(Ampoules), a): Ampoules[b]= not(Ampoules[b]) # Bloc qui eteint/allume les ampoules   a=0 for i in Ampoules[1::]: if i==True: a=a+1 #Bloc compteur d'ampoules allumees   print "Le nombre d'ampoules allumees est", a

---

Je vous laisse l'essayer et me prévenir si vous y trouvez une erreur ;)
Et ensuite, bien que mon prof (je pense) n'attend pas un perfectionnement total, j'aimerais bien voir votre version en 4 lignes s'il vous plaît :roll::roll:
Merci beaucoup!

Voilà mon petit code (Python 2 et 3, mais j'ai omis les accents pour éviter les pb d'encodage):

Code:

---

1 2 3 4 5 6

lampes = [False for i in range(0, 277)] # liste des lampes de 1 a 276 (0: non utilise) for i in range(1, 26): # pour chaque eleve de 1 a 25 for j in range(i, 277, i): # pour chaque lampe de i à 276 par pas de i lampes[j] = not lampes[j] # modif etat lampe d'index j   print("Nombre de lampes allumees", lampes.count(True)) # => 154

---

Pour paramétrer le nb d'élèves et le lampes, il suffit d'ajouter au début ces 2 variables (nbeleves=25 et nblampes=276), et de remplacer les 26 et 277 du code par nbeleves+1 et par nblampes+1.

Salut,

En 4 lignes:

Code:

---

1 2 3 4

ampoules = [ False ] * 276 for e in range(1, 25 + 1): ampoules[e-1::e] = [ not z for z in ampoules[e-1::e] ] print(sum(ampoules))

---

Pour compter les ampoules allumées, pas la peine d'ajouter un élément à la liste.
*edit* mais si on respecte l'énoncé, le premier élément aura l'index e - 1 et non 0.

Votre code est pas trop mal sauf:

Code:

---

1 2 3 4

a=0 for i in Ampoules[1::]: if i==True: a=a+1

---

s'écrit raisonnablement:

Code:

---

1 2 3

a = 0 for e in Ampoules: a = a + e

---

note: l'intérêt des Boolean True et False est qu'ils savent redevenir 1 et 0 suivant le contexte.

- W

Citation:

---

Envoyé par wiztricks

Code:

---

1 2 3

a = 0 for e in Ampoules: a = a + e

---

note: l'intérêt des Boolean True et False est qu'ils savent redevenir 1 et 0 suivant le contexte.

- W

---

Est-ce vous pouvez m'expliquer ça svp, j'ai pas bien compris pourquoi on pouvait remplacer le compteur par ça :|

Citation:

---

Envoyé par AlexBsd

Est-ce vous pouvez m'expliquer ça svp, j'ai pas bien compris pourquoi on pouvait remplacer le compteur par ça :|

---

Les développeurs du langage ont décidé que les booléens (le type bool) étaient des entiers (le type int). Cela permet d'écrire:

Code:

---

1 2	>>> print (3 + True + True) 5

---

et sum(ampoules) dans mon exemple.

- W

D'accord merci pour tous vos conseils :)

Pour ceux que ça amuse:

même question mais avec 12 enfants et 1 milliard d'ampoules ;)

Citation:

---

Envoyé par dividee

même question mais avec 12 enfants et 1 milliard d'ampoules ;)

---

Dans ce cas, il faut être un peu moins bourrin car sinon çà va prendre un temps certain.
A mon sens l'idée est de dire l'état des ampoules va se répéter.
C'est une fonction du nombre d'enfants qu'on connaît bien: le ppcm.

- W

Citation:

---

Envoyé par wiztricks

Dans ce cas, il faut être un peu moins bourrin car sinon çà va prendre un temps certain.
A mon sens l'idée est de dire l'état des ampoules va se répéter.
C'est une fonction du nombre d'enfants qu'on connaît bien: le ppcm.

---

Oui, c'est l'astuce que j'ai utilisée, mais j'ai dû diminuer le nombre d'enfants pour que ça reste calculable... Si quelqu'un à un moyen pour résoudre (efficacement) le problème avec 25 enfants et 1 milliard d'ampoules, je suis preneur...

Bonjour,

Effectivement, la solution brutale avec 1 milliard de lampes conduit chez moi à un crash mémoire... En passant par un calcul binaire (1 lampe=1bit), je n'ai pas de crash, mais les temps de calculs sont trop longs...

J'aimerais bien une solution plus élégante, mais celle avec le PPCM (que je sais calculer) ne m’apparait pas clairement: pourriez-vous m'en dire plus?

Bonjour,
l'ampoule d'indice i est manipulée par un élève d'indice j uniquement si j est un diviseur de i. Donc après le passage de l'élève E, une ampoule A est allumée si et seulement si le nombre de diviseurs de A inférieurs ou égaux à E est impair, dans le cas contraire elle sera éteinte.
Pour un nombre suffisamment grand d'élève par rapport au nombre d'ampoules les seules ampoules allumées seront les carrés. Seuls les carrés ont un nombre impair de diviseurs.
À vue de nez, la liste devrait ressembler à «motif fixe jusqu'à un certain carré où les carrés sont allumés et les autres éteints», suivi d'un motif d'une certaine longueur qui se répète ensuite. C'est à creuser :)

Citation:

---

Envoyé par tyrtamos

J'aimerais bien une solution plus élégante, mais celle avec le PPCM (que je sais calculer) ne m’apparait pas clairement: pourriez-vous m'en dire plus?

---

Si on part de N lampes et de M élèves, le nombre de fois qu'on appuie sur le bouton de la lampe j est donné par le nombre de diviseurs de j pris dans 1..M.
Par définition, le ppcm sera l'indice de la première ampoule sur laquelle appuieront les M élèves.
Après, on peut démontrer que pour tout les indices i dans 1..ppcm, l'ensemble des diviseurs de i est identique à celui de ppcm + i.
Quelque soit l'entier x pris dans 1..M, le reste de la division i / x est égal à celui de (ppcm + i) / x car ppcm % x == 0 (c'est le ppcm!).
remarque: on ne parle pas des diviseurs premiers mais des nombres de 1..M qui divisent i et ppcm + i.

Puis on calcule q, r = div(N, ppcm) pour sortir le nombre de lampes allumées (q * sum(...)) et le nombre de lampes allumées côté "reste".

note: le ppcm des entiers dans 1..M est une fonction qui grimpe vite, pour 16 on est déjà > 0.5 milliard mais avec 12 on divise le problème par 36. Donc on simplifie lorsque M est petit et que N est plusieurs fois plus grand que le ppcm (çà ne sert à rien lorsqu'on a 25 élèves et 276 ampoules comme dans le cas du PO)

Citation:

---

Envoyé par picodev

Pour un nombre suffisamment grand d'élève par rapport au nombre d'ampoules les seules ampoules allumées seront les carrés. Seuls les carrés ont un nombre impair de diviseurs

---

ainsi que les nombres qui se décomposent en 2/4/6/... nombres premiers et probablement des tas d'autres...
De plus, le nombre M d'élèves est au plus égal au nombre N d'ampoules car si M = N + x, les x derniers élèves ne changeront pas l'état des ampoules.

- W

Citation:

---

Envoyé par picodev

Pour un nombre suffisamment grand d'élève par rapport au nombre d'ampoules les seules ampoules allumées seront les carrés. Seuls les carrés ont un nombre impair de diviseurs.

---

Citation:

---

Envoyé par wiztricks

ainsi que les nombres qui se décomposent en 2/4/6/... nombres premiers et probablement des tas d'autres...
De plus, le nombre M d'élèves est au plus égal au nombre N d'ampoules car si M = N + x, les x derniers élèves ne changeront pas l'état des ampoules.

---

En fait mon «suffisamment grand» signifie, les seules ampoules d'indices i≤M seront celles dont l'indice est un carré parfait.

Citation:

---

Envoyé par picodev

À vue de nez, la liste devrait ressembler à «motif fixe jusqu'à un certain carré où les carrés sont allumés et les autres éteints», suivi d'un motif d'une certaine longueur qui se répète ensuite. C'est à creuser :)

---

Pour M élèves et N ampoules la liste L est construite ainsi :

• si i≤M alors L[i]=1 si i est un carré parfait, 0 sinon
• sinon, L[i]=1 si le nombre de diviseurs de i inférieurs ou égaux à M est impair, 0 sinon

de plus pour tout i>M, pour tout k>0, avec P=ppcm({2,3,…,M})
L[i]=L[i+kP]

Effectivement comme le ppcm croît très vite on a pour 25 élèves P=26771144400, ce qui donne
[1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1] + ([... une liste de longueur 26771144400 ...] qui se répète)

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