Discussion :

[Grye300]

Bonjour,

J'ai un exercice dont voici l'énoncé :

Votre programme doit d'abord lire un entier, le nombre maximum de pierres dont pourra être composée la pyramide. Il devra ensuite calculer la hauteur de la plus grande pyramide qui pourra être construite, ainsi que le nombre de pierres qui sera nécessaire.

EXEMPLE 1

entrée :
20
sortie :
3
14
EXEMPLE 2

entrée :
26042
sortie :
42
25585

Exemple d'une pyramide :


On remarque tout de suite qu'il s'agit de la somme d'une suite des n termes au carré : 1, 4, 9, 16, 25 etc..

Ce que j'ai fait :

Code :

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

1
2
3
4
5
6
7
8
9
result = 0
i = 1
maxPierres = int(input())
 
while result < maxPierres:
    result = (i*i) + result
    i = i + 1
print i
print result

Quand je rentre 20, j'obtiens bien le résultat escompté, mais quand je rentre 26042, non. J'ai donc fait un autre programme qui utilise la suite de la somme des n premiers nombres au carré n(n+1)(2*n+1)/6 :

Code :

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

1
2
3
4
5
6
7
8
result = 0
n = 1
maxPierres = int(input())
while result < max:
   result = ((n(n+1)(2*n+1))/(6)) + result
   n = n + 1
print (n)
print (result)

mais j'obtiens l'erreur suivante :

Traceback (most recent call last):
File "<stdin>", line 5, in <module>
TypeError: 'int' object is not callable

Merci de votre aide.

[Viand0x]

Bonjour,

Pour ta deuxième version le bug provient de ceci:

Code :

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

result = ((n(n+1)(2*n+1))/(6)) + result

En effet python ne comprend pas la notation n(n+1), il faut que tu laisse apparaitre les opérations:

Code :

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

result = ((n*(n+1)*(2*n+1))/(6)) + result

Mais j'ai du mal à comprendre l'origine de cette fonction.



Pour moi ton premier code par contre ne fonctionne pas, même avec 20 en entré. La raison est simple, je m'explique: tu essaye de savoir le nombre d'étage de pierre on peut faire avec 20 pierres disposés en pyramide. Tu fais donc:

Code :

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

1
2
3
4
5
6
7
8
9
10
result = 0
i = 1
maxPierres = int(input())
 
while result < maxPierres:
    result = (i*i) + result
    i = i + 1
 
print i
print result

Le truc c'est que ton "while" va fonctionner jusqu'à ce que result soit supérieur à maxPierre. Or result représente le nombre de pierres que tu as placé donc lorsque tu aura result > maxPierre la boucle s'arrêtera mais tu aura dépassé le nombre max de pierre autorisés!

Mais bon...tu as moyen de te débrouiller =), une foi la boucle terminé il te suffit de revenir une étape avant!

[Sve@r]

Mais j'ai du mal à comprendre l'origine de cette fonction.

Bonjour
Cette formule n'est pas évidente à trouver => http://www.les-suites.fr/somme-des-n...ers-carres.htm

Mais bon...tu as moyen de te débrouiller =), une foi la boucle terminé il te suffit de revenir une étape avant!

Ou simplement afficher (i-1) (et faut aussi remplacer l'inégalité stricte < par une inégalité large <=...)

J'ai donc fait un autre programme qui utilise la suite de la somme des n premiers nombres au carré n(n+1)(2*n+1)/6 :

Code :

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

1
2
3
4
5
6
7
8
result = 0
n = 1
maxPierres = int(input())
while result < max:
   result = ((n(n+1)(2*n+1))/(6)) + result
   n = n + 1
print (n)
print (result)

Hum, la formule f(n)=n(n+1)(2n+1)/6 ne doit être appliquée qu'une fois. Elle sert justement à ne pas avoir à sommer chaque élément de 1 à n mais de donner la somme d'un coup.
Par exemple la somme des 5 premiers carrés est f(5)=5*6*11/6=55. Ce n'est certainement pas f(1)+f(2)+f(3)+f(4)+f(5) (qui donnerait 1+5+14+30+55 soit 105...)

[Viand0x]

Bonjour
Cette formule n'est pas évidente à trouver => http://www.les-suites.fr/somme-des-n...ers-carres.htm

Oula oui maintenant que tu le dis je m'en souvient mais la boucle ne m'y aurait jamais fait pensé... ^^'

Ou simplement afficher (i-1) (et faut aussi remplacer l'inégalité stricte < par une inégalité large <=...)

Je crois même qu'il s'agit de i-2. Sinon je disais qu'il fallait revenir une étape en avant car l'exercice demande combien de pierre sont finalement utilisées, il faut donc print resultat (mais avant qu'il dépasse maxPierre).

[Sve@r]

Je crois même qu'il s'agit de i-2.

Non, c'est i-1 si on utilise une inégalité large. Car lorsqu'on sort de la boucle, i vient juste de dépasser le niveau max.

Sinon je disais qu'il fallait revenir une étape en avant car l'exercice demande combien de pierre sont finalement utilisées, il faut donc print resultat (mais avant qu'il dépasse maxPierre).

Ou alors afficher i (i-1) (2i-1)/6 (c'est la même formule mais appliquée à i-1)...

[Grye300]

Salut,

Pour moi ton premier code par contre ne fonctionne pas, même avec 20 en entré. La raison est simple, je m'explique: tu essaye de savoir le nombre d'étage de pierre on peut faire avec 20 pierres disposés en pyramide.

Je me suis trompé quand j'ai copié mon code... Voici celui qui fonctionne quand on entre 20, mais quand on entre 26042, non (22, 3795) :

Code :

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

1
2
3
4
5
6
7
8
9
i = 1
result = 0
maxCubes = int(input())
while maxCubes > result:
    result = (i*i) + result
    maxCubes = maxCubes - result
    i = i + 1
print (i - 1)
print (result)

Le truc c'est que ton "while" va fonctionner jusqu'à ce que result soit supérieur à maxPierre. Or result représente le nombre de pierres que tu as placé donc lorsque tu aura result > maxPierre la boucle s'arrêtera mais tu aura dépassé le nombre max de pierre autorisés!

Effectivement, je me suis pris pas mal la tête avec ça..

J'ai donc fait un autre code :

Code :

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

1
2
3
4
5
6
7
8
9
i = 1
result = 0
maxCubes = int(input())
while maxCubes >= result:
    result = (i*i) + result
    maxCubes = maxCubes - result
    i = i + 1
print (i - 1)
print (result + maxCubes)

Même chose afficher bien ce qu'on lui demande quand on entre 20 mais pas 26042 (22, 6561)

Hum, la formule f(n)=n(n+1)(2n+1)/6 ne doit être appliquée qu'une fois. Elle sert justement à ne pas avoir à sommer chaque élément de 1 à n mais de donner la somme d'un coup.
Par exemple la somme des 5 premiers carrés est f(5)=5*6*11/6=55. Ce n'est certainement pas f(1)+f(2)+f(3)+f(4)+f(5) (qui donnerait 1+5+14+30+55 soit 105...)

Exact, je vais essayer de corriger mon code.

[Viand0x]

Non, c'est i-1 si on utilise une inégalité large. Car lorsqu'on sort de la boucle, i vient juste de dépasser le niveau max.

Hum, comment expliquer ça... Il suffit de tester avec 5 pierres, i-1 retourne 3 et non 2.

C'est logique vu que i est toujours en avance d'un sur le nombre de niveau actuel (i est initialisé à 1 pendant que resultat est à 0). Donc en plus de devoir retrancher 1 de i du fait de l'incrémentation de i dans la boucle, il faut retirer à nouveau 1 à i pour obtenir le véritable niveau actuel...

[Sve@r]

C'est logique vu que i est toujours en avance d'un sur le nombre de niveau actuel (i est initialisé à 1 pendant que resultat est à 0). Donc en plus de devoir retrancher 1 de i du fait de l'incrémentation de i dans la boucle, il faut retirer à nouveau 1 à i pour obtenir le véritable niveau actuel...

Exact. J'ai lu le code sans trop réfléchir.
Toutefois, comme j'ai horreur des trucs en trop à retirer (et visiblement ici c'est deux-fois en trop dont à retirer deux fois), et que j'étais certain que ma solution (remplacer > par >= pour être certain que même avec une valeur parfaite on ferait quand-même une itération supplémentaire ; et donc récupérer simplement en final i-1) devait fonctionner (c'était obligatoire vu qu'il n'y avait qu'une seule itération de trop), je me suis penché avec attention sur le dernier coder proposé (qui diffère très peu du code initial)...

Code python :

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

1
2
3
4
5
6
7
8
9
i = 1
result = 0
maxCubes = int(input())
while maxCubes > result:
    result = (i*i) + result
    maxCubes = maxCubes - result
    i = i + 1
print (i - 1)
print (result)

Il y a dans ce code deux erreurs fondamentales

1. i est incrémenté après que sa valeur ait servi au calcul de result (ce qui fait effectivement que l'itération monte une fois de plus que ce qu'il faut (sauf pour les valeurs parfaites comme 1, 5, 14, etc... à cause de l'inégalité stricte) et que i monte une fois de plus que l'itération ce qui fait bien deux incréments comme tu le dis)
2. maxCube est décrémenté de result pendant que result s'incrémente en parallèle => c'est pour ça que de toute façon ça foire de façon exponentielle

Donc en corrigeant ces deux erreurs, et ainsi avec le simple code suivant

Code python :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
i = 0
result = 0
maxCubes = int(input())
while maxCubes >= result:
    i = i + 1
    result = (i*i) + result
print "hauteur max:", i - 1
 
# Just for fun
print "nb pierres: %d (%s = %d)" % (
	i * (i-1) * (2*i-1) / 6,
	" + ".join("%d" % (x*x) for x in xrange(1, i)),
	sum((x*x) for x in xrange(1, i)),
)

Ca fonctionne bien avec 5 ou 6 ou tout le reste comme je l'avais prédit

PS (pour Grye300): je bosse sous Python 2.7. Avec Python 3.x, faut juste remplacer xrange() par range() et mettre des parenthèses aux print et ça fonctionnera pareil.

[Viand0x]

Ah désolé ma dernière réponse à croisée le dernier post de Grye300 je n'avais pas vu ta proposition.

Je pense que les explications de Sve@r te suffiront à comprendre ton erreur.

Maintenant je ne pensait pas fournir de solution mais maintenant que c'est fait... Le code de Sve@r marche parfaitement, il calcul le nombre de niveau de pierre puis grâce à ce niveau recalcul le nombre de pierres grâce à ton savant calcul n*(n+1)*(2*n+1).

C'est très bien pour t'apprendre à utiliser ces deux aspects, mais après au niveau de ton code tu refais deux fois le même calcul puisque ton nombre de pierre était déjà dans "result". Il suffisait d'arrêter la boucle avant que "result" ne dépasse "maxPierre":

Code :

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

1
2
3
4
5
6
7
8
9
10
result = 0
i = 1
maxPierres = int(input())
 
while i*i + result <= maxPierres:
    result = i*i + result
    i = i + 1
 
print i-1
print result

Bonne continuation...

[Sve@r]

Code :

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

1
2
3
4
5
6
7
8
9
10
result = 0
i = 1
maxPierres = int(input())
 
while i*i + result <= maxPierres:
    result = i*i + result
    i = i + 1
 
print i-1
print result

Mouais. Mais là tu calcules deux fois i*i+result et en plus tu fais ce double calcul à chaque itération. Au-moins dans mon cas, le second calcul n'est fait qu'une fois...

Si vraiment tu veux éviter un double calcul, tu peux passer par la formule directe

Code python :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#!/usr/bin/env python
# -*- coding: utf-8 -*-
 
i = 0
maxCubes = int(input())
while i * (i+1) * (2*i+1) / 6 <= maxCubes: i+=1
print "hauteur:", i - 1
 
# Just for fun
print "nb pierres: %d (%s = %d)" % (
	i * (i-1) * (2*i-1) / 6,
	" + ".join("%d" % (x**2) for x in xrange(1, i)),
	sum((x**2) for x in xrange(1, i)),
)

Ou bien utiliser une variable en plus pour mémoriser le bon total avant de passer au suivant

Code python :

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
#!/usr/bin/env python
# -*- coding: utf-8 -*-
 
i = 0
calcul = 0
total=0
maxCubes = int(input())
while maxCubes >= calcul:
    i = i + 1
    total=calcul
    calcul = i*i + calcul     # En effet, pourquoi des parenthèses inutiles ???
print "hauteur:", i - 1
 
# Just for fun
print "nb pierres: %d (%s = %d)" % (
	total,                # Qui vaut aussi i * (i-1) * (2*i-1) / 6 mais aussi calcul-i**2
	" + ".join("%d" % (x**2) for x in xrange(1, i)),
	sum((x**2) for x in xrange(1, i)),
)

Ceci dit, le calcul en question était assez insignfiant (surtout qu'on peut encore le simplifier en utilisant la dernière valeur de calcul) et (again), n'était fait qu'une seule fois. Perso je préfère ma première solution ou à la rigueur celle qui calcule le total directement plutôt que cette dernière qui rajoute cette variable presque inutile...

[Grye300]

Merci à vous deux, j'ai compris mon erreur en testant étape par étape les résultats de l'algorithme sur papier.