Partage
  • Partager sur Facebook
  • Partager sur Twitter

Calcul de la somme des entiers

Nombre d'itération d'une boucle for (problème de calcul)

25 juin 2023 à 18:57:48

Bonjour tout le monde ! 

Je débute en algorithmie et je suis bloqué sur le calcul du nombre d'itération d'une boucle for.

Pour résumer nous devons à un moment calculer la sommes des entiers allant de 1 à n-1 (qu'on appellera S); en développant, je tombe sur S = (n²)/2 mais toutes les vidéos sur les quels je tombe trouvent un résultat de S = ((n-1)*n)/2 et je ne trouve rien qui justifie cela.

Image à l'appuie :

 Merci à vous pour votre aide !

  • Partager sur Facebook
  • Partager sur Twitter
26 juin 2023 à 14:39:39

Justification :

Si tu additionnes

  • 1 et n-1
  • 2 et n-2
  • 3 et n-3
  • ...

Tu as des sommes qui valent chacune  k + (n-k) = n

Et si tu pars de k=1 pour aller jusqu'à n-1,  ça te fait n-1 sommes soit n x (n-1)

Si maintenant tu regardes la première colonne de la liste, c'est 1,2, 3.... n-1   et pareil dans la deuxième. Donc 2 fois la somme des entiers de 1 à n-1.

A part ça, ce que tu as écrit en bas à droite est horriblement faux.

-
Edité par michelbillaud 27 juin 2023 à 22:34:10

  • Partager sur Facebook
  • Partager sur Twitter
26 juin 2023 à 15:21:27

Pour illustrer ce que dit michelbillaud avec la somme des entiers de 1 à 100


1 100


2  99


3  98


...


98  3

99  2

100 1

À gauche, j'ai les nombres de 1 à 100 en ordre ascendant. À droite, ils sont en ordre descendant.


La somme à gauche sera la somme désirée. Même chose pour la somme à droite.


La somme de chaque ligne est 101, donc la somme totale est 100 * 101


Mais Il y a deux fois la somme désirée. Donc la somme est 100*101 / 2

  • Partager sur Facebook
  • Partager sur Twitter

Le Tout est souvent plus grand que la somme de ses parties.

27 juin 2023 à 17:15:47

Merci pour votre explication, je comprends mieux à présent ; et pour ce qui est écrit en bas à droite c'est car c'est "l'ordre" du résultat qui nous intéresse pas le résultat en lui même. Merci encore à vous.

michelbillaud a écrit:

Justification :

Si tu additionnés

  • 1 et n-1
  • 2 et n-2
  • 3 et n-3
  • ...

Tu as des sommes qui valent chacune  k + (n-k) = n

Et si tu pars de k=1 pour aller jusqu'à n-1,  ça te fait n-1 sommes soit n x (n-1)

Si maintenant tu regardes la première colonne de la liste, c'est 1,2, 3.... n-1   et pareil dans la deuxième. Donc 2 fois la somme des entiers de 1 à n-1.

A part ça, ce que tu as écrit en bas à droite est horriblement faux.

-
Edité par michelbillaud hier à 14:40



  • Partager sur Facebook
  • Partager sur Twitter
27 juin 2023 à 22:26:57

Ordre de grandeur, ou plus exactement comparaison asymptotique : dans ce cas on utilise la notation "grand O" :

\(O(\frac{n(n-1) }{ 2}) = O(n^2)\)

pour dire que ça grandit comme le carré de n, en gros. On colle pas une égalité comme ça.

https://fr.m.wikipedia.org/wiki/Comparaison_asymptotique

Alternative : utiliser un autre symbole que l'égalité pour indiquer que c'est une équivalence 

\(\frac{n(n-1)}{2} \approx n^2\)

-
Edité par michelbillaud 28 juin 2023 à 9:50:27

  • Partager sur Facebook
  • Partager sur Twitter
21 septembre 2023 à 18:34:12

Il est compréhensible que vous ayez des questions sur le calcul du nombre d'itérations d'une boucle for et sur la formule pour la somme des entiers allant de 1 à n-1 (S). Il semble y avoir une confusion ici, et la formule correcte est en effet S = ((n-1) * n) / 2.
La formule S = (n²) / 2 n'est pas correcte pour la somme des entiers de 1 à n-1. La formule correcte est dérivée de la formule de Gauss pour la somme des premiers entiers positifs et s'explique comme suit :
1 + 2 + 3 + ... + (n-1) + n = (n * (n+1)) / 2
Cependant, si vous souhaitez comprendre plus en détail pourquoi cette formule est correcte et comment elle est dérivée, je vous recommande de consulter le cours sur l'arithmétique, les nombres entiers et rationnels disponible à l'adresse suivante : https://mathovore.fr/arithmetique-nombres-entiers-et-rationnels-cours-maths-24 .
Ce cours devrait vous fournir une explication approfondie de la formule, des exemples pratiques et des démonstrations mathématiques pour vous aider à comprendre le calcul du nombre d'itérations d'une boucle for et la formule pour la somme des entiers de 1 à n-1.
N'hésitez pas à explorer ce cours pour obtenir une compréhension plus approfondie de ce sujet spécifique en algorithmie.

-
Edité par miragemirage 22 septembre 2023 à 21:37:44

  • Partager sur Facebook
  • Partager sur Twitter
22 septembre 2023 à 9:50:47

miragemirage a écrit:

La formule S = (n²) / 2 n'est pas correcte pour la somme des entiers de 1 à n-1. La formule correcte est dérivée de la formule de Gauss pour la somme des premiers entiers positifs et s'explique comme suit :
1 + 2 + 3 + ... + (n-1) + n = (n * (n+1)) / 2

1. Heureusement, personne n'a écrit que la somme était la moitié du carré

2. Ton truc, c'est pas une explication mais une formule tirée du chapeau.

Une explication :

La somme  S = 1 + 2 +  .... + (n-2) + (n-1) comporte n-1 termes.

Elle peut aussi s'écrire à l'envers  S = (n-1) + (n-2) + ..... + 2 + 1

En additionnant les deux expressions, on a

     2S = 1+(n-1)  + 2+(n-2) . ... + (n-2)+2  + (n-1)+1

On y voit  n-1 termes   de la forme  k+(n-k), qui valent chacun n.

Donc 2S = (n-1)n.

3. Ton lien ne marche pas.

-
Edité par michelbillaud 22 septembre 2023 à 9:51:26

  • Partager sur Facebook
  • Partager sur Twitter
23 septembre 2023 à 16:05:28

(Oups... J'ai cru qu'il fallait calculer le nombre d'itération de la boucle for nécessaire pour calculer S. Mais en fait je devine qu'il s'agit de calculer un nombre d'itération pour une certaine boucle for, ce qui mène à calculer S. Du coup j'ai répondu de travers, j'enlève.)

-
Edité par robun 23 septembre 2023 à 22:17:03

  • Partager sur Facebook
  • Partager sur Twitter
24 septembre 2023 à 16:06:42

En musique, ça s'appellerait « variations sur un thème ».

Ou toutes les façons différentes de dire la même chose.

  • Partager sur Facebook
  • Partager sur Twitter

Le Tout est souvent plus grand que la somme de ses parties.

20 octobre 2023 à 19:14:17 - Message modéré pour le motif suivant : Réponse à un message modéré


23 novembre 2023 à 21:46:07 - Message modéré pour le motif suivant : Message complètement hors sujet


24 novembre 2023 à 1:38:15

@AbouziaKrazidiDiallo:

Postes ton propre sujet au lieu d'un sujet qui n'a rien à voir.

Ta question n'est pas suffisamment claire.

Postes quelque chose de plus complet.

Tu devrais probablement poster dans la catégorie sur le langage C.

-
Edité par PierrotLeFou 24 novembre 2023 à 1:40:56

  • Partager sur Facebook
  • Partager sur Twitter

Le Tout est souvent plus grand que la somme de ses parties.

24 novembre 2023 à 10:42:20

@AbouziaKrazidiDiallo Bonjour, merci de ne pas squatter le sujet des autres pour une nouvelle question, créer votre propre sujet dans le respect des règles du forum à savoir qu'un message commence par des règles de politesses (Un bonjour ou des salutations à la communauté et se termine par des remerciements par avances pour les futures réponses), la description de votre problème et le code que vous avez écrit inséré sur le forum à l'aide de l'outil d'intégration de code soit le bouton code </>

Déterrage

Citation des règles générales du forum :

Avant de poster un message, vérifiez la date du sujet dans lequel vous comptiez intervenir.

Si le dernier message sur le sujet date de plus de deux mois, mieux vaut ne pas répondre.
En effet, le déterrage d'un sujet nuit au bon fonctionnement du forum, et l'informatique pouvant grandement changer en quelques mois il n'est donc que rarement pertinent de déterrer un vieux sujet.

Au lieu de déterrer un sujet il est préférable :

  • soit de contacter directement le membre voulu par messagerie privée en cliquant sur son pseudonyme pour accéder à sa page profil, puis sur le lien "Ecrire un message"
  • soit de créer un nouveau sujet décrivant votre propre contexte
  • ne pas répondre à un déterrage et le signaler à la modération

Je ferme ici.

  • Partager sur Facebook
  • Partager sur Twitter