Bonjour.
J'ai besoin d'aide pour une notion que je n'ai pas comprise par rapport à un type d'algorithmes : le tracé de points.
Voici l'algorithme en question (on se place dans un repère orthonormé (O;I;J)) :
Entrée:
Saisir n (entier naturel)
Traitement:
Pour i allant de 0 à n Faire
Pour j allant de 0 à i Faire
Placer le point de coordonnées (i;j)
FinPour
FinPour
Exprimer en fonction de n le nombre de points obtenus en sortie.
Comment fait-on ? Quel est le raisonnement à suivre pour trouver une formule explicite ?
Merci pour vos réponses !
bonjour,
c'est "combien de billes" dans un empilement "triangulaire" :
tu peux obtenir ça comme ça te chante "mathématiquement" :
somme des termes d'une suite arithmétique
"géométriquement" (complèter en un rectangle)
"formule connue", ou la démontrer par récurrence
etc ..
Est-ce que ce sont toujours les mêmes méthodes avec ce type d'exercice ?
Par exemple, j'ai trouvé plus simple d'utiliser la somme des terme d'une suite arithmétique : j'obtiens ainsi (n+2)(n+3) / 2
tout dépend de ce que tu appelle "ce type" d'exercice !!
quant à ta formule, essayons pour voir :
entrée n = 1 (par exemple)
pour i de 0 à 1
i = 0 :
pour j de 0 à 0
j = 0 : un point (0; 0)
fin
i = 1
pour j de 0 à 1
j = 0 : un point (1; 0)
j = 1 : un point (1; 1)
fini
fini
total = 3 points
ta formule prétend (1+2)(1+3)/2 = 6 !!
donc elle est fausse (erreurs sur les bornes de la somme des termes : ou sur le premier terme ou sur le nombre de termes etc)
Existe-t-il une autre méthode, peut-être plus "évidente" pour trouver le nombre de points tracés en fonction de n ?
non
cela revient de toute façon a calculer le nombre de boucles le plus internes
c'est à dire que la boucle la plus interne est exécutée :
1 fois quand i vaut 0 (pour j de 0 à 0)
2 fois quand i vaut 1 (pour j de 0 à 1)
3 fois quand i vaut 2 ...
...
et n+1 fois quand i vaut n (pour j de 0 à n)
le nombre cherché est donc la somme 1 + 2 + 3 + ... + (n+1)
que tu calcules comme ça te chante.
oui, ou la somme de sommes de sommes ... selon les imbrications des boucles
cela si la question est "combien de boucles sont exécutées" (ici c'était combien de points sont tracés, parce que à chaque boucle la plus interne exécutée, un point était tracé, donc les deux questions sont équivalentes)
mais une question "du même genre" peut tout aussi bien être "combien de temps risque de durer mon programme si une boucle élémentaire dure 1 millième de seconde"
cela amène à la question importante de la "complexité" d'un programme, de son "efficacité" en quelque sorte.
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :