fonction mystere (python)

[afaf1995]

bonjour tout le monde, je bloque un peu dans un exercice, bon le voilà:
1/ on m'a donné une fonction:
def mystere(n):
***s=0
***for k in range (1,n+1):
*****s=s+factorielle(k)
***return s
désolé pour les * c'est pour garder la marge
(la fonction factorielle est déjà définit elle calcule le factorielle du nombre k)
2/ on m'a demandé quelle est la valeur que renvoie mystere(4):
après calcul j'ai trouvé 33
3/ puis de déterminer le nbr de multiplication qu'effectue cette fonction:
j'ai trouvé que c'est [n(n+1)/2]-n (je l'ai trouvé en se basant sue le cas de mystere(4) je suis pas sur à 100% mais je crois qu'on peu le démontrer par réccurence sur n)
4/ on me demande d'améliorer le script de la fonction mystere(n) pour obtenir une complexité linéaire, là je bloque je sais bien que je dois réduire le nombre de multiplication qu'effectue cette fonction mais j'arrive pas
-----

[azad]

Salut.
Si ta fonction retourne 33, c'est que tu as choisi n= 3. Ce que tu aurais pu nous dire.
Pour le reste, il est évident que ta fonction retourne Sigma ((n+1) !)

[afaf1995]

merci tout d'abord pour votre réponse,
j'ai bien choisi n=4 et non pas 3
si comme vous dites la fonction retourne sigma((n+1)!)
alors pour n=3 on aura (n+1)!=(3+1)!=4!=24 c déjà très proche de 33 si on ajoute de plus le sigma je crois que ça sera plus grand que 33 n'est ce pas?
bon j'ai testé la fonction sur pyzo j'ai trouvé que mystere(4)=33
voilà ce que j'ai comme solution pour la question 4 où je me bloque mais je sais pas si c'est juste ou non

def mystere(n):
***s=0
***c=1
***for i in range (1,n+1):
*******c=c*i
*******s+=c
***return s
voilà, je crois que le nombre de multiplications effectuées diminuera (chaque fois que la boucle for tourne la fonction n'effectuera qu'une seule multiplication) du coup la complexité sera linéaire.
si vous pouvez me corriger si il y a une faute
merci encore une fois

[azad]

Je crois que tu te trompes.
regardes ton code
s=0
for k in range (1,n+1)
s=s+factorielle(k)
si tu choisis n= 3
la première fois que tu exécutes cette boucle tu as k=1
et s initialement à 0 prend la valeur s= factorielle (1) soit s = 1
au deuxième passage s devient factorielle(1) + factorielle(2) qui donne s = 3
au troisième passage s devient factorielle(1) + factorielle(2) + factorielle (3) alors s = 9
voilà le résultat que tu obtiendrais si k variait de 1 à n. Mais il varie de 1 à n+1. Pas vrai ?
il y a donc un quatrième passage qui donne
s = 1! + 2! + 3! + 4! soit 33
Si tu avais choisi n = 5 il y aurait 5+1 passages dans la boucle et s aurait-été égal à 33 + 5! = 153

Pour rendre ton explication plausible il aurait fallu que la boucle soit écrite
for k in range (1,n)

Les autres questions concernent l'optimisation des calculs. Il fut un temps, où la mémoire coutant une petite fortune on jouait à écrire du code le moins gourmand possible. Ton code n'étant pas astreint à l'économie, il est possible que ta fonction factorielle soit mal écrite. Mais le dernier exemple que tu donnes calcule en fait une factorielle c'est pourquoi tu n'appelles plus la fonction existante "factorielle".
Il y a là une nouvelle erreur puisque l'on n'est plus dans les conditions posées par ta première question.

[A voir en vidéo sur Futura]

[afaf1995]

je n'arrive pas à comprendre le fait que la boucle doit être écrite: for k in range (1,n). ce que je connais, c'est que la boucles sous python n'atteint pas la dérnière borne c-à-d dans votre cas la borne n, donc il faut que la boucle soit écrite: for k in range (1,n+1)

[azad]

OK, il s'agit là d'une spécificité de Python, que je ne connaissait pas. Tu as donc raison.

[afaf1995]

Merci beaucoup

[azad]

Et bien sûr ton dernier exemple est bon, puisque dans la même boucle tu calcules les factorielles, et la somme de ces factorielles, sans avoir besoin d' appeler une fonction.

[michiel]

je peux savoir ou vous avez trouvé cet exercice merci d'avance