Wat is het bewijs van (N–1) + (N–2) + (N–3) + … + 1= N*(N–1)/2

Ik heb deze formule uit een datastructuurboek in het bellensorteeralgoritme.

Ik weet dat we (n-1) * (n keer) zijn, maar waarom deling door 2?

Kan iemand mij dit uitleggen of het gedetailleerde bewijs hiervoor geven.

Bedankt


Antwoord 1, autoriteit 100%

Zie driehoeksgetallen.


Antwoord 2, autoriteit 91%

(N-1) + (N-2) +...+ 2 + 1is een som van N-1 items. Herschik nu de items zo, dat na de eerste de laatste komt, dan de tweede, dan de op één na laatste, dwz (N-1) + 1 + (N-2) + 2 +... Aan de manier waarop de items nu zijn geordend, kunt u zien dat elk van die paren gelijk is aan N (N-1+1 is N, N-2+2 is N). Aangezien er N-1 items zijn, zijn er (N-1)/2 dergelijke paren. Dus je voegt N (N-1)/2 keer toe, dus de totale waarde is N*(N-1)/2.


Antwoord 3, autoriteit 96%

Begin met de driehoek…

   *
   **
  ***
 ****

tot nu toe 1+2+3+4. Snijd de driehoek doormidden langs één dimensie…

    *
    **
  * **
 ** **

Draai het kleinere deel 180 graden en plak het op het grotere deel…

   **
    * 
     *
    **
    **
    **

Sluit de opening om een rechthoek te krijgen.

Op het eerste gezicht werkt dit alleen als de basis van de rechthoek een even lengte heeft – maar als deze een oneven lengte heeft, knip je gewoon de middelste kolom doormidden – het werkt nog steeds met een half-eenheid-brede twee keer zo grote -tall (nog steeds integer gebied) strook aan één kant van je rechthoek.

Wat de basis van de driehoek ook is, de breedte van uw rechthoek is (base / 2)en de hoogte is (base + 1), geef ((base + 1) * base) / 2.

Mijn baseis uw n-1, aangezien de bubble-sorteer een paar items tegelijk vergelijkt en daarom alleen (N-1) herhaalt posities voor de eerste lus.


Antwoord 4, Autoriteit 114%

Probeer paren van cijfers uit de set te maken. De eerste + de laatste; de tweede + die voor het laatst. Het betekent N-1 + 1; N-2 + 2. Het resultaat is altijd n. En aangezien u twee cijfers bij elkaar toevoegt, zijn er alleen (N-1) / 2 paren die kunnen worden gemaakt van (N-1) nummers.

Zo is het als (n-1) / 2 * n.


Antwoord 5, Autoriteit 71%

Ik weet dat we (n-1) * (n keer) zijn, maar waarom de divisie met 2?

Het is alleen (n - 1) * nAls u een naïef bubblesort gebruikt. U kunt een belangrijke besparingen krijgen als u het volgende opmerkt:

  • Na elke vergelijking-en-swap is het grootste element dat u bent tegengekomen op de laatste plek waar u was.

  • Na de eerste pas zal het grootste element in de laatste positie zijn; Na de K TH PASS, staat het grootste element K TH in de laatste positie K TH .

U hoeft dus niet elke keer het hele ding te sorteren: u hoeft alleen N – 2 elementen de tweede keer door, N – 3 elementen de derde keer te sorteren, enzovoort. Dat betekent dat het totale aantal vergelijking / swaps u moet doen is (n - 1) + (n - 2) + .... Dit is een rekenkundige series en de vergelijking voor het totale aantal tijden is (n – 1) * n / 2.

Voorbeeld: Als de grootte van de lijst n = 5 is, dan doe je 4 + 3 + 2 + 1 = 10 swaps – en merk op dat 10 hetzelfde is als 4 * 5 / 2.


Antwoord 6, Autoriteit 29%

Som van de rekenkundige progressie

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


Antwoord 7, Autoriteit 29%

Dit is een vrij algemeen bewijs. Een manier om dit te bewijzen is om wiskundige inductie te gebruiken. Hier is een link: http://zimmer.csufresno.edu/ ~Larryc / Proofs/proofs.mathindectie.html


Antwoord 8, Autoriteit 14%

Neem aan N = 2 aan. Dan hebben we 2-1 = 1 aan de linkerkant en 2 * 1/2 = 1 aan de rechterkant.

duiden op f (n) = (n-1) + (n-2) + (N-3) + … + 1

Neem nu aan dat we tot n = k zijn getest. Dan moeten we testen voor n = k + 1.

Aan de linkerkant hebben we K + (K-1) + (K-2) + … + 1, dus het is f (k) + k

Aan de rechterkant hebben we vervolgens (k + 1) * k / 2 = (k ^ 2 + k) / 2 = (k ^ 2 + 2k – k) / 2 = k + (k-1) K / 2 = k f (k)

Dus dit moet voor elke k vasthouden, en dit concludeert het bewijs.


Antwoord 9

Hier is een bewijs door inductie, overweegt u Ntermen, maar het is hetzelfde voor N - 1:

Voor N = 0De formule is natuurlijk waar.

Stel dat 1 + 2 + 3 + ... + N = N(N + 1) / 2true is voor een natuurlijk N.

We bewijzen 1 + 2 + 3 + ... + N + (N + 1) = (N + 1)(N + 2) / 2is ook waar door onze eerdere veronderstelling:

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

Dus de formule bevat voor alle N.

Other episodes