Inscription / Connexion Nouveau Sujet
Niveau première
Partager :

Algorithme de tracé de points

Posté par
Etcha66
08-04-15 à 14:36

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 !

Posté par
mathafou Moderateur
re : Algorithme de tracé de points 08-04-15 à 14:58

bonjour,

c'est "combien de billes" dans un empilement "triangulaire" :
Algorithme de tracé de points
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 ..

Posté par
Etcha66
re : Algorithme de tracé de points 08-04-15 à 15:03

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

Posté par
mathafou Moderateur
re : Algorithme de tracé de points 08-04-15 à 15:13

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)

Posté par
Etcha66
re : Algorithme de tracé de points 08-04-15 à 15:46

Pardon, je voulais dire : (n+1)(n+2) / 2

Posté par
mathafou Moderateur
re : Algorithme de tracé de points 08-04-15 à 15:59

là, on est d'accord.

Posté par
Etcha66
re : Algorithme de tracé de points 08-04-15 à 16:38

Existe-t-il une autre méthode, peut-être plus "évidente" pour trouver le nombre de points tracés en fonction de n ?

Posté par
mathafou Moderateur
re : Algorithme de tracé de points 08-04-15 à 16:48

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.

Posté par
Etcha66
re : Algorithme de tracé de points 08-04-15 à 16:59

D'accord donc cela réside finalement dans le nombre de "boucles".

Posté par
mathafou Moderateur
re : Algorithme de tracé de points 08-04-15 à 17:01

oui, le nombre de boucles exécutées

Posté par
Etcha66
re : Algorithme de tracé de points 08-04-15 à 17:48

Donc si j'ai un algorithme de ce type là, avec plusieurs boucles à exécuter, je calcule la somme ?

Posté par
mathafou Moderateur
re : Algorithme de tracé de points 08-04-15 à 18:05

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 :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1742 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !