Quelle est la preuve de (N-1) + (N-2) + (N-3) + ... + 1 = N * (N-1) / 2

J'ai eu cette formule à partir d'une structure de données livre dans la bulle de l'algorithme de tri.

Je sais que nous sommes (n-1) * (n fois), mais pourquoi la division par 2?

Quelqu'un peut-il m'expliquer ce à moi ou à donner la preuve détaillée.

Merci

source d'informationauteur skystar7

  2. 15

    Commencer avec le triangle...

        *
   **
  ***
 ****

    représentant 1+2+3+4 jusqu'à présent. Couper le triangle de moitié le long d'une dimension...

         *
    **
  * **
 ** **

    Faire pivoter la partie plus petite de 180 degrés, et le coller sur le dessus de la plus grande partie...

        **
    * 

     *
    **
    **
    **

    Combler l'écart pour obtenir un rectangle.

    À première vue, cela ne fonctionne que si la base du rectangle a une longueur égale - mais si elle a une longueur impaire, vous venez de couper la colonne du milieu en demi -, il fonctionne toujours avec une demi-unité de l'échelle deux fois-comme-haut (encore entier de la zone de bande sur un des côtés du rectangle.

    Quelle que soit la base du triangle, la largeur de votre rectangle est (base /2) et la hauteur est (base + 1)donnant ((base + 1) * base) /2.

    Cependant, mon base est votre n-1depuis le tri à bulles compare une paire d'éléments à la fois, et, par conséquent, parcourt seulement (n-1) positions pour la première boucle.

  3. 8

    Essayer de faire des paires de nombres à partir de l'ensemble. Le premier + le dernier; le second + celui de l'avant-dernier. Cela signifie n-1 + 1; n-2 + 2. Le résultat est toujours n. Et puisque vous êtes à l'ajout de deux nombres ensemble, il y a seulement (n-1)/2 paires qui peuvent être fabriqués à partir de (n-1) nombres.

    C'est comme si (N-1)/2 * N.

  4. 8

    (N-1) + (N-2) +...+ 2 + 1 est une somme de N-1 éléments. Maintenant réorganiser les éléments de sorte, que, après la première vient de la dernière, puis la seconde, puis la seconde à la dernière, c'est à dire (N-1) + 1 + (N-2) + 2 +... La façon dont les éléments sont ordonnés maintenant, vous pouvez voir que chacune de ces paires est égal à N (N-1+1 est le N, N-2+2 N). Comme il y a N-1 éléments, il y a (N-1)/2 paires de telles. Donc, vous êtes à l'ajout de N (N-1)/2 fois, de sorte que la valeur totale est N*(N-1)/2.

  5. 4

    Je sais que nous sommes (n-1) * (n fois), mais pourquoi la division par 2?

    C'est seulement (n - 1) * n si vous utilisez un naïf bubblesort. Vous pouvez obtenir des économies importantes si vous remarquez les éléments suivants:

    • Après chaque compare-and-swap, le plus grand élément que vous avez rencontré sera dans le dernier spot vous étiez à la.

    • Après le premier passage, le plus grand élément sera en dernière position, après le kème pass, le kème plus grand élément sera dans la mème dernière position.

    Donc vous n'avez pas à trier le tout à chaque fois: vous avez seulement besoin de trier les n - 2 éléments de la deuxième fois, n - 3 éléments la troisième, et ainsi de suite. Cela signifie que le nombre total de comparer/swaps que vous avez à faire est (n - 1) + (n - 2) + .... C'est un l'arithmétique de la sérieet l'équation par le nombre total de fois (n - 1)*n /2.

    Exemple: si la taille de la liste est N = 5, alors vous ne 4 + 3 + 2 + 1 = 10 swaps -- et remarquez que 10 est la même que 4 * 5 /2.

  6. 2

    C'est un très commun de la preuve. Une façon de le prouver, ce qui est d'utiliser induction mathématique. Voici un lien: http://zimmer.csufresno.edu/~larryc/proofs/proofs.mathinduction.html

  7. 1

    Somme de progression arithmétique

    (A1+UN)/2*N = (1 + (N-1))/2*(N-1) = N*(N-1)/2

  8. 1

    Supposons n=2. Ensuite, nous avons 2-1 = 1 sur le côté gauche et 2*1/2 = 1 sur le côté droit.

    Noterons f(n) = (n-1)+(n-2)+(n-3)+...+1

    Maintenant, supposons que nous avons testé jusqu'à n=k. Ensuite, nous avons tester pour n=k+1.

    sur le côté gauche, nous avons k+(k-1)+(k-2)+...+1, donc f(k)+k

    Sur le côté droit, nous avons alors (k+1)*k/2 = (k^2+k)/2 = (k^2 +2k - k)/2 = k+(k-1)k/2 = kf(k)

    Si cela a à tenir pour chaque k, et ceci conclut la preuve.

  9. 1

    Voici une preuve par induction, compte tenu de N termes, mais c'est la même chose pour N - 1:

    Pour N = 0 la formule est évidemment vrai.

    Supposons que 1 + 2 + 3 + ... + N = N(N + 1) /2 est vrai pour certaines naturel N.

    Nous allons prouver 1 + 2 + 3 + ... + N + (N + 1) = (N + 1)(N + 2) /2 est également vrai en utilisant notre hypothèse précédente:

    1 + 2 + 3 + ... + N + (N + 1) = (N(N + 1) /2) + (N + 1)
    = (N + 1)((N /2) + 1)
    = (N + 1)(N + 2) /2    .

    Ainsi, la formule vaut pour toutes les N.